C++のためのろじっくぱらだいむ

2010年の5月にBoostConがあるというのは良く知られた話らしいです。

2009年のBoostConでは、Andrei Alexandrescuさんによる"Iterators Must Go"をはじめとする発表が行われたようです。
(私はAlexandrescuさんの発表でBoostConの存在を知りましたが...。
それと本エントリとは余り関係ないですが、"The D Programming Language"が出たのち、近い日に休日を潰して泊まり込みで読み合うみたいな会合が在れば誘ってください！)

今年のBoostCon 2010ではこのようなプログラム(http://www.boostcon.com/program)で発表が行われるそうです。
で、気になるプログラムが在ったので、それについて少し調べてみたので適当に纏めてみます。

気になったプログラムというのは「Logic Paradigm for C++」というものです。

先に参考となる動画を張っておきます。取りあえずそれを見てもらえれば雰囲気が分かる気がします。

http://fora.tv/2009/01/21/Logic_Paradigm_for_C
この動画で発表している方その人が、恐らく"Roshan Naik"さんかと思われます。

また、「Castor」それ自体の現在(2010年2月25日)のプロジェクトページはココ(http://www.mpprogramming.com/Cpp/Default.aspx)です。

本エントリは「CastorDesign(http://www.mpprogramming.com/resources/CastorDesign.pdf)」に依っているので、これを読まなくてもCastorDesign.pdfを読めば事足りるのではないでしょうか的な・・・。

Logic Paradigmとはナニモノ？

論理型プログラミング言語は、「How」を記述するのではなく「What」(これは例えば仕様とかルール)を記述するだけでガンガン計算が行われるよ、と良く書かれます。
しかし、Howを記述すると言われている言語でも、十分に抽象化されたライブラリを使ってあげれば、何も世の中はHowばかりではないというのは明らかな話のように思われます。

ただまぁ、私はこういうHowとかWhatとかいう言葉を使った説明でそんなに上手く雰囲気を伝えられる気はしませんが、そういう説明が良く為されるというぐらいに抑えてもらえば。

逆に言えば、解を「探索する術」がデフォルトで与えられているのでそこを実装する余地が無いのでLOCがもしかしたら下がるかもしれないし、そこんとこが固定されると自分に都合の良いやり方じゃなくて、デフォルトで定まってる何かにとって都合の良いやり方をしないといけませんよね！！という事なのでは無いでしょうか・・・。

まぁ例

CastorのTutorialVideoの中に入っている例でやってみます。コメントアウトされてる部分は、Prologで等価で書いた場合のものです。

#include <iostream>
#include <string>
#include <castor.h>
using namespace std;
using namespace castor;

/*
           Gary
            |
  Mary -- Frank
       |
     -----
    |     |
   Sam   Denise
 */

/*
  gender(frank,male).
  gender(sam,male).
  gender(gary,male).
  gander(mary,female).
  gender(denise,female).
 */
relation gender(lref<string> p,lref<string> g)
{
    return eq(p,"Frank")  && eq(g,"male")
	|| eq(p,"Sam")    && eq(g,"male")
	|| eq(p,"Gary")   && eq(g,"male")
	|| eq(p,"Mary")   && eq(g,"female")
	|| eq(p,"Denise") && eq(g,"female");
}

/*
  child(sam,mary).
  child(denise,mary).
  child(sam,frank).
  child(denise,frank).
  child(frank,gary).
 */
relation child(lref<string> c,lref<string> p)
{
    return eq(c,"Sam")    && eq(p,"Mary")
	|| eq(c,"Denise") && eq(p,"Mary")
	|| eq(c,"Sam")    && eq(p,"Frank")
	|| eq(c,"Denise") && eq(p,"Frank")
	|| eq(c,"Frank")  && eq(p,"Gary");
}

/*
  father(F,C) :- gender(F,male) , child(C,F).
 */
relation father(lref<string> f,lref<string> c)
{
    return gender(f,"male") && child(c,f);
}

/*
  mother(M,C) :- gender(M,female) , child(C,M).
 */
relation mother(lref<string> m,lref<string> c)
{
    return gender(m,"female") && child(c,m);
}

/*
  parent(P,C) :- father(P,C).
  parent(P,C) :- mother(P,C).
 */
//parent(a,b)が満たされるのは
//a が bの親で有る時
relation parent(lref<string> p,lref<string> c)
{
    return father(p,c) || mother(p,c);
}

/*
  ancestor(A,D) :- parent(A,D).
  ancestor(A,D) :- parent(A,X) , ancestor(X,D).
 */
//ancestor(a,d)が満たされるのは
//a が dの祖先で有る時
//dから見た祖先の定義は、
//dの親、dの親の親、dの親の親の親、dの親の親の親の親...である
relation ancestor(lref<string> a,lref<string> d)
{
    lref<string> x;
    return parent(a,d) || (parent(a,x) && recurse(ancestor,x,d));
}

int main()
{
    lref<string> a,b;
    relation as = ancestor(a,"Sam");
    while(as())
	cout << *a << " " << flush;//どうなるでしょうか?
    cout << endl;
    as = ancestor("Gary",a);
    while(as())
	cout << *a << " " << flush;//どうなるでしょうか?
    cout << endl;
    as = ancestor(a,b);
    while(as())
	cout << *a << " , " << *b << endl;//どうなるでしょうか?
    return 0;
}

ね、簡単でしょ？？

まず明らかに気になりそうな部分だけ説明してみると

lref は 変数です。参照っぽいけど、参照じゃないよ！！初期化は"しなくても良い"ですし。
operator *やoperator ->がこいつの為に定義されてるので、中身に触るときはポインタっぽい感じになってると思ってもらえば。
relationはファンクタになっていて、コイツを起動してあげる事で「次の解」を見つけて来ます。
解が見つかった → trueが返ります
見つからなかったよ = 解は全て見つけ切った → falseが返ります

mainの中を弄って遊んでみると何か分かるっぽいかも知れません。
取りあえずどういう風に「探索が進むか」という雰囲気を嗅ぎ取って貰えれば良いと思います。

超簡単にCastorDesign.pdfを解説

relation型について

relationはTypeErasureテクニックを使って実装されています。
TypeErasureにする事によって
1.型が長く成らなくて済む
上に書いたgenderでさえ、Or,Or,Or,Or,And>>>>のような型を持つ事に成りかねません。
2.パフォーマンスに関しては、Boost.Functionと同じ様な問題が発生する。
http://www.boost.org/doc/libs/1_42_0/doc/html/function/misc.html

実装はこんな感じ

class relation
{
private:
    struct impl
    {
	virtual ~impl(){}
	virtual impl* clone() const = 0;
	virtual bool operator()() = 0;
    };
    
    template<typename F>
    struct wrapper : public impl
    {
    private:
	F f;
    public:
	explicit wrapper(const F& f_) : f(f_){}
	virtual impl* clone() const{
	    return new wrapper<F>(this->f);
	}
	virtual bool operator()(){
	    return this->f();//require F has `bool operator()()`
	}
    };
    
    std::auto_ptr<impl> pimpl;
public:
    typedef bool result_type;
    
    template<typename F>
    relation(F f) : pimpl(new wrapper<F>(f)){
    }

    relation(const relation& rhs) : pimpl(rhs.pimpl->clone()){
    }
    
    relation& operator=(const relation& rhs){
	this->pimpl.reset(rhs.pimpl->clone());
	return *this;
    }

    bool operator()() const {
	return (*pimpl)();
    }
};

その他の実装案として、relation2というものも挙げられていますが、本エントリでは取りあえず言及しません。

Template lref

"lref"は"Logic REFerence"の略になっていて、C++の参照と似ているけれども初期化はしなくても良いという点が異なります。
lrefには
1.他のlrefの「参照の実体」をコピー(copy)する。(これは代入演算子で引き起こされる)
2.他のlrefと「参照の実体」を共有する(join)する。(これはコピーコンストラクタで引き起こされる)
という2つの挙動が在ります。
joinするには、同じ型でなければ成りません。

まぁ例を挙げるとすると

#include <iostream>
#include <string>
#include <castor.h>
using namespace std;
using namespace castor;

struct Base{};
struct Derived : Base{};

int main()
{
    Derived d;
    lref<Base> lb = d;//参照のように振る舞える。これは割当
    
    lref<string> ls = "castor";//変換可能な型に関する割当
    
    lref<int> li1=1,li2=2;//割当
    li2 = li1;//これはcopy!!
    *li2 = 3;
    cout << "*li1 = " << *li1 << endl;//→ 1
    cout << "*li2 = " << *li2 << endl;//→ 3
    

    lref<double> ld1;
    ld1 = li1;//コピーなので変換可能な型なら大丈夫
    
    lref<int> li3 = li1;//join!!
    //lref<double> ld2 = li3;//型が異なるのでjoin出来ない!!
    
    *li3 = 4;
    cout << "*li1 = " << *li1 << endl;//→ 4
    cout << "*li2 = " << *li2 << endl;//→ 3
    cout << "*li3 = " << *li3 << endl;//→ 4
    
    return 0;
}

とこんな感じになります。

lrefの実装はCastorDesignには書かれていないのですが、この手のものはboost::shared_ptrを使って実装すれば良いのではないかとあたりは付けられます。(lrefは意味的には値を共有して所有している筈なので)

実際に、現在のCastorの実装は

template <typename T>
class lref {
    ::castor::detail::RefCountedPtr<T>* const refPtr;
private:
...
}

として手前で実装したRefCountedPtr(その実体は名前の通りです)によってなされています。

Relation eq

これはPrologのうにふぃけーしょんと違う所があるので注意！！
というのは、未束縛の変数同士のうにふぃけーしょんは出来ません。(というより推奨してません)

面倒臭いのでpdfからそのままyieldを使ったぷせうどコードを引っ張ってくる

bool eq(lref<T> lhs,lref<T> rhs)
{
  if(lhs.defined() && rhs.defined())//どっちも束縛されとったら
    yield (*lhs == *rhs);//値を比較する
  else if(lhs.defined()){//どちらかが束縛されてない!! で 左項が束縛されてたら右項にコピー
    rhs = lhs;
    yield true;
    rhs.reset();
  }
  else {//左項に右項をコピーする
    lhs = rhs;
    yield true;
    lhs.reset();
  }
  return false;
}

これをbool operator()()に合う様に実装してあげれば終わりです。
Boost余ルーチンを使おうと思ったのですがそんなんはまだ入ってないとかで、そういえばそういう話もBoost.勉強会の時にも為されていた気がして、
となるとまぁ普通にステートの遷移を自分で書いてあげれば良いですね。(CastorDesignには実際にstateを表す変数 + switchで実装してます)
Hamigakiライブラリとかも使えるのかしら。

Disjunction と Conjunction

まぁOrとAndの話です。これはもう纏めて行ってしまいます。
あと、OrとAndの実装は「どの様に探索が行われるか　すなわち　どの述語から使っていくか」を決定するので、実際にプログラムを書く上で大変重要です。

これまた、eqの時と同じ様にyieldを使って書くと

Disjunction(Or)

while(lhs())
  yield true;
while(rhs())
  yield true;
return false;

となっており、P1 || P2 || P3と述語が在った場合は、(結合方向を考えると (P1 || P2) || P3)
P1 = print(1)
P2 = print(2) || print(3)
P3 = print(4) || print(5) || print(6)
とした時
1,2,3,4,5,6と表示されます。

Conjunction(And)

relation tmp = rhs;
while(lhs()){
  while(rhs())
    yield true;
  rhs = tmp;
}

となっており、P1 && P2 && P3と述語が在った場合は、(結合方向を考えると (P1 && P2) && P3)
P1 = print(1)
P2 = print(2) || print(3)
P3 = print(4) || print(5) || print(6)
とした時
1,2,4,5,6,3,4,5,6と表示されます。

さらにもう一例

#include <iostream>
#include <string>
#include <utility>
#include <mine.hpp>
using namespace std;

//XからYへ向かう辺がある
relation edge(lref<string> X,lref<string> Y)
{
    return 
	(eq(X,"a") && eq(Y,"b"))
	|=
	(eq(X,"a") && eq(Y,"c"))
	|=
	(eq(X,"b") && eq(Y,"d"))
	|=
	(eq(X,"c") && eq(Y,"d"))
	|=
	(eq(X,"d") && eq(Y,"e"));
}

//Node1からNode2へ向かう辺があるという事に関する定義
relation connected(lref<string> Node1,lref<string> Node2)
{
    lref<string> Link;
    return
	(edge(Node1,Node2))
	|=
	(edge(Node1,Link) && recurse(connected,Link,Node2));//recurseを使ってあげないとインスタンス作り続けてメモリ食い尽くして死ぬので使います！！
}

relation unique_connected(lref<string> Node1,lref<string> Node2)
{
    return connected(Node1,Node2) && Unique<string>(Node1,Node2);
}

int main()
{
    lref<string> n1,n2;
    relation r = connected(n1,n2);
    for(;r(),r.isSuccess();)
    {
	cout << *n1 << " -> " << *n2 << endl;
    }
    return 0;
}
=とかisSuccessとか変なものが現れてしまっているのは、これは私が練習として全部手前で書いてみたやつだからだったりします・・・。

まぁ "|=" を "||"に読み替えて眺めると、edgeが有向な辺を表していて、connectedが2つのノード間に有向なpathがあるかどうかを表しています。

さて、connectedを使うと次のような出力を得ます。

a -> b
a -> c
b -> d
c -> d
d -> e
a -> d//!
a -> e//!!
a -> d//!
a -> e//!!
b -> e
c -> e

図で書くと
ピクチャ 27

だぶりーな結果を得てしまうと大変な事が起こる惑星に住んでいるとするとこれは大変良く無い事なので、C++らしくUniqueという「内部に状態を持つ」relationを定義するのです！！

template<typename T>
struct Unique {
private:
    lref<T> item1_,item2_;
    lref<set<pair<T,T> > > items;
public:
    Unique(const lref<T> &item1,const lref<T> &item2) : item1_(item1) , item2_(item2) , items(set<pair<T,T> >()) {}
    
    ReturnState operator()() {
	pair<T,T> tmp = make_pair(*item1_,*item2_);
	    
	if(items->find( tmp ) != items->end())//既に入ってる！！
	    return False();//ユニークで無いといけない述語として使ってるのでFalseを返すべき
	else{
	    items->insert(tmp);
	    return True();//ユニークなのでTrueを返すべき
	}
    }
};

これを使ったunique_connectedをconnectedの代わりに使ってあげると...

a -> b
a -> c
b -> d
c -> d
d -> e
a -> d
a -> e
b -> e
c -> e

やりました！！

まとめ

この記事では、Castorで実装されているrecurse,cutexprやpredicateのカラクリなどは省略しましたが、Castor自体もそれほど大きいワケでもないので興味ある部分を充分拾い読み出来ると思います。

自分でCastorDesignを参考にして勝手に書いたmine.hppは、500行弱でrelation,eq,And,Or,recurse,cutの実装まで出来ました。(Boostを使ってます)

Logic Paradigm for C++は、"for C++"であってPrologでないという所が重要です。
C++の為のものであって、C++さんに優しく無ければなりませんし、C++さんにとって嬉しいものでなければ成りません。
それは、最後に使ったUniqueのような内部に状態を持つユーザ定義relationなどを定義し、ちゃんと使える所が良いのでは無いかと思います。

LC++(http://www.cc.gatech.edu/~yannis/lc++/tutorial.html)は一方、C++の中にPrologを埋め込んだ感じが余りにも強くて"for C++"ではむしろ無くなってしまっている気がします。(そもそもLC++はin C++であって、for C++とか書いて無いのでそんな事言うのはお門違いだとも思いますがw)

あとは実際のケースでどう使って行くかですね。C++さんはマルチパラダイムなので、きっと素晴らしいでしぐんぱたーんも発見されるのでしょう！！
(Roshan NaikさんはTutorialVideoにおいて、チェスの実装の中で使っています。)

それから

今日 2/25 は千早さんの誕生日です！！！

THE IDOLM@STER MASTER ARTIST 05 如月千早

THE IDOLM@STER MASTER ARTIST 05 如月千早