「The Art of Elegant Programming」を掲げたプログラム言語、 というのを昨日知ったので早速遊んでみようと思います。 その名は CLAIRE。 フランス語でクレールと読んで"綺麗"とか"ゆとり"とかいう意味らしい。 手続き型オブジェクト指向をベースに、関数型や "rule" によるイベント処理型、 あるいはバックトラッキングなどの論理型言語的特徴も取り入れた、 いわゆる「マルチパラダイム」なものだそうな。
いつものように、間違いの指摘等は大歓迎。
以下では現時点の最新である claire3.3 系統を触ってみます。
まず、Yahoo! Groups の claireprogramminglanguage に入らないとダウンロードできないみたいです。 "Files"からソースをダウンロード。VC++かg++のある環境でビルドします。 VC++の場合、
cd (ソースを解凍して出来たディレクトリ)set CLAIRE3_HOME=今いるディレクトリ名nmake -f Makefile.ntでOK。bin\public\ntv 内の claire.exe が処理系になります。
g++の場合は、「public\unix、debug\unix」ディレクトリを作って 「nmakeの代わりにgmake -f Makefile.unix」とやればOKです。
// hello.cl
main() ->
printf( "Hello, World!\n" )
claire> load("hello")
eval[0]> ---- [load CLAIRE file: hello]
true
claire> main()
eval[1]> Hello, World!
unknown
関数定義の文法はこの前やった Erlang と似た感じ。
claire> 1 + 2
eval[0]> 3
claire> 1+2
---- Syntax Error[line: 2]:
**** An error has occurred.
[152] Separation missing between 1
and +2 [none?]
+2 とくっついていると識別子と見なされてしまうようで、
基本的には演算子と引数は離して書いた方がよさそう。
claire> let x := 100 in (x * x)
eval[1]> 10000
claire> let y := 123 in (y := 456, y)
eval[2]> 456
let 変数名 := 値 in 式 で、その名前の変数を式の中で使える。
変数に入れた値はも一度:=することなどで書き換えOK。
claire> let +3 := 4 in +3
eval[3]> 4
claire> let command? := "戦う" in command?
eval[4]> "戦う"
claire> let a\b\c := 2.5 in a\b\c
eval[5]> 2.5000000000000000000
claire> let x := 10 in let x' := 100 in (x + x')
eval[6]> 110
識別子として使えるのはアルファベットと下線だけ…なんてことはなく、 なんだか色々バラエティに富んだ変数名が付けられるようです。 日本語も使えてしまったけれど、これはたまたまのような気も。
ファイルからは load() でインタプリタに読み込めますが、
カレントの init.cl が起動時に読み込まれるので、
init.cl にとりあえずテストコードを書いとくと楽です。
正しい使い方ではないような気もしますが。
手続き型なので、制御構造などなどは馴染みの物ばっかりです。 ので、サクサクと進みましょう。ただ、 上で書いたように何でもかんでも識別子と見なされる可能性がある言語なので、 スペースを入れるべき所には入れなくてはならない点にだけ注意。
sum(n:integer) : integer ->
(let s := 0 in
(for i in (1 .. n) s := s + i,
s))
1 から n までの和を計算する関数を書いてみました。
引数の型の指定（多分必須）には、変数名:型名 とします。
戻り値の型は関数名の後ろに : 型名。省略すると void 扱い
…と書いてあるけど実際はそうなっていない気もします。
ローカル変数は let in で宣言します。
変数の型は、初期値（上の例なら0だからintegerとわかる）
から自動で推論されるので、特に人間が書かなくても大丈夫。
単純な繰り返しは「for 変数名 in Collection ○○○」
です。○○○に複数の文を書くときは()でくくってカンマ区切りで。
ここではCollectionとして、(整数A .. 整数B) で "A以上B以下の整数の集合"
を使ってループしています。
で、最後のs、つまり関数の一番最後の式の値が、関数の返値となります。
平方根を越えないような最大の自然数...。
square(n:integer) : integer ->
let x := 0 in
(
while ( x * x < n ) x :+ 1,
(if ( x * x = n ) x else x - 1)
)
まぁ、みたまんまです。whileの反対のuntilもあります。 なお、whileと(、ifと(の間のスペースは必須。
x :+ y は x := x + y の省略形です。
全ての演算子について、x :op y は x := x op y
だそうで。本当に省略形に過ぎないので、x の部分に副作用のある式を書くと
２回実行されるから気を付けるように、と書いてありました。
sum(x:list) : integer =>
let s := 0 in
(for e in x s :+ e, s)
sum( list(1,3,5) ) とかやると 9 が返ってきます。
list、という複数の値を保持できる型です。list は Collectionの一種なので、
forで使うことができます。上の例だと全部integerを入れましたが、
listの要素としてはどんな型の値でも入ります。
例えば要素をintegerに限ったlistを使うなら、
sum(x:list<integer>) : integer =>
...
という記述ができたりします。何となくC++のtemplateに見た目は似た感じ。
中身はそれなりに違いますが。また、listは順番を保持したり同じ値の要素を
複数もてますが、順番関係なしに単に要素の集合を保持したいときは、
set や set<integer> というのもあります。
claire> set(1,2,3)
eval[1]> {1, 2, 3}
claire> set(1,2,1)
eval[2]> {1, 2}
claire> list(1,2,3)
eval[3]> (1, 2, 3)
claire> list(1,2)
eval[4]> (1, 2)
list() の代わりに tuple() と書くことも可能です。（同じ意味になります。） また、中身が定数の場合 set(1,2,3) ではなく {1,2,3} と略記するのもOK。
少し上の例にさりげなく混ぜてみましたが、関数定義に -> でなく => を使うとinline展開指令になるそうな。
claire> list{x in (1 .. 10) | x mod 2 = 0}
eval[12]> (2, 4, 6, 8, 10)
claire> {(x * x) | x in (1 .. 10)}
eval[13]> {1, 4, 9, 16, 25, 36, 49, 64, 81, 100}
{変数名 in Collection | 条件式} や
{式 | 変数名 in Collection} で、
条件を満たす値のリストが作れます。
hoge() : tuple(integer,integer,integer,integer) ->
let x := 6, y := 3 in
tuple(x + y, x - y, x * y, x / y)
claire> let (ad,sb,ml,dv) := hoge()
in (ad * 1000000 + sb * 10000 + ml * 100 + dv)
eval[14]> 9031802
let 変 := 値, 変 : = 値, ... in と複数個一気に宣言したり、
let (変,変,..,変) := tuple in とtuple(list)
の中身要素で初期値を定めたりするという構文もありです。
結局昨日は全然サクサクと進みませんでしたが、 今日こそ基本は終わらせて早く面白いとこへ入りたいところです。
「CLAIRE3からは list と tuple は別物」とドキュメントに書いてありました。 というわけで別物らしいです。
collectionのメンバ判定。
claire> 1 % {1,2,3}
eval[0]> true
claire> 5 % list(1,2,3)
eval[1]> false
リストのn番目にアクセス。
claire> let x := list<float>(1.0, 2.0, 3.0) in x[2]
eval[3]> 2.0000000000000000000
case 値 (集合 式, 集合 式, ..., 集合 式) でCのswitchみたいな分岐。
claire> case 3 ({1} "aaa", {2,3} "iii", any "uuu")
eval[4]> "iii"
なお、any はCLAIRE上の全ての要素を含む集合を表します。
claire> any % any
eval[5]> true
公理的集合論好きーな人は深く突っ込まずやり過ごしてください。
forall( 変数名 in 集合 | 条件式 ) で、
集合の全要素が条件を満たすならtrue、でなければfalseになります。
exists(同) で、一個でも満たせばtrue。
例として、集合の全要素が平方数かどうか？を判定する関数。
claire> is_all_square?( s:set<integer> ) : boolean ->
forall( n in s | exists(t in (0 .. n) | t * t = n) )
eval[12]> is_all_square? @ set
claire> is_all_square?( set<integer>(49, 16, 100) )
eval[13]> true
claire> is_all_square?( set<integer>(1, 2) )
eval[14]> false
some() は exists と似ていますが、
一個でも条件を満たす物が見つかったら、trueではなくその要素自体を返します。
見つからなかったら unknown を返します。条件を満たす物が複数ある場合、
どれが戻ってくるかは実装依存だそうな。
claire> some( x in {1,2,3} | x > 1 )
eval[15]> 2
let に似てますが、こちらは値が unknown では無かったときにのみ in の中を実行します。 例えば上記の some と組み合わせることが多いです。
claire> empty?( s:set ) ->
(when e := some(e in s | true) in
printf("not empty:~S\n", e)
else printf("empty\n"))
eval[20]> empty? @ (set)
claire> empty?( {} )
eval[21]> empty
unknown
claire> empty?( {"aaa","iii"} )
eval[21]> not empty: "aaa"
unknown
上のように、when ～ else と else をつけるのもあり。
break(値) でループのbreak。breakの引数が、 ループ式全体の値となります。例は省略。
(try 式 catch クラス名 式) で例外のキャッチ。例は省略。
もう一度関数の書き方をおさらい。integerとintegerを取って、 その和を返す簡単な関数です。
claire> add(x:integer, y:integer) : integer -> (x + y)
eval[0]> add @ integer
claire> add(1,2)
eval[1]> 3
このintegerは「型」であると上で説明しました。
では、次にこのコード。
claire> addd(x:{1,2,3}, y:(4 .. 6)) : integer -> (x + y)
eval[2]> addd @ integer
claire> addd(3,4)
eval[3]> 7
claire> addd(5,7)
eval[4]> ---- file: init, line: 10
****[141] list<any>(5, 6) is a wrong arg list for addd.
型として {1,2,3} や (4 .. 6) のような集合を指定できます。 ということは逆に…
claire> 100 % integer
eval[5]> true
claire> 3.14 % integer
eval[6]> false
と、integerに含まれているか？の判定も普通の %
演算子で実行できるわけです。ただし、for x in integer ..
は駄目らしい。基本的に、後で説明するユーザー定義のクラスなども全て、
このような性質を持ちます。
これと関数のオーバーロード（名前は同じでも引数の型の違う関数を使える機構） を組み合わせると、次のような関数型っぽい関数定義がかけちゃいます。
claire> sum(x:{0}) : integer -> 0
eval[0]> sum @ integer
claire> sum(x:integer) : integer -> (x + sum(x - 1))
eval[1]> sum @ integer
claire> sum(100)
eval[2]> 5050
0は{0}の要素でもintegerの要素でもあるのですが、 こういう場合はより範囲の狭まった集合である{0}の方が選択されます。
「型全体の集合」とか、classについては未説明ですが 「class全体の集合」みたいな一段階上の集合も定義されています。 こんな感じ。
claire> integer % type
eval[0]> true
claire> integer % class
eval[1]> true
claire> {1,2,3} % type
eval[2]> true
claire> {1,2,3} % class
eval[3]> false
クラスの定義の仕方は、クラス名 <: 親クラス(プロパティ:型, ...)
で。メソッドも普通の関数として書かれます。多重継承はできなそう。
具体例として、次のような感じ。図形(Shape)達のクラス階層です。
shape <: thing()
rect <: shape(height:float, width:float)
area(x:rect) : float ->
(x.height * x.width)
circle <: shape(radius:float)
area(x:circle) : float ->
(x.radius * x.radius * 3.141592)
tri <: shape(edge1:float, edge2:float, edge3:float)
area(x:tri) : float ->
let s := (x.edge1 + x.edge2 + x.edge3) / 2.0 in
sqrt(s * (s - x.edge1) * (s - x.edge2) * (s - x.edge3))
これをロードすると次のように使えます。
claire> let x := rect(width = 10.0, height = 20.3) in area(x)
eval[0]> 203.00000000000000000
claire> let x := circle(radius = 2.0) in area(x)
eval[1]> 12.566368000000001000
クラス名(プロパティ名 = 値, ...) で実体の生成、と。
今の場合xの型がrectやcircleであると明らかにわかるので、問題なく正しい
areaメソッドが呼ばれています。が、もちろんpolymorphicな動作も可能。
claire> area_sum( lst:list[shape] ) ->
let sum := 0.0 in (for s in lst sum :+ area(s), sum)
eval[2]> area_sum @ list
claire> area_sum( list(
tri(edge1 = 3.0, edge2 = 4.0, edge3 = 5.0),
circle(radius = 1.0),
rect(width = 10.0, height = 10.0) ) )
eval[3]> 109.14159200000000000
area_sum 関数の側ではリストの要素は shape の派生型であることしかわかりませんが、 それぞれのオブジェクトに応じたarea関数で計算されていることが見て取れます。 上は一変数のばあいですが、マルチメソッドもＯＫ。
前回紹介したように、この言語では"型"とは、その型に属する要素全ての集合、
のことでした。だから、今回定義した shape というクラス(⊆型)も、
それに属するオブジェクト全部を含む集合です。
claire> let tmp := list<float>() in
(for s in shape tmp :add area(s), tmp)
eval[4]> list<float>(203.00000000000000000, 100.00000000000000000,
12.566368000000001000, 3.1415920000000002000, 6.0000000000000000000)
ここまでに作った５つのshapeが順不同で格納されています。しかしこれ、 ものすごく面白い機能ではあるのですが、一般的には使いどころがありません。 そこで、クラス定義の後に例えば
ephemeral(rect)
などと書いておくことで、rectクラスはこの動作をしないようにできます。
ephemeral というのは"はかない、短命な"という意味らしい。
クラスの側では参照を保持せずに、他からの参照が全て消えたら
インスタンスがガベコレで消滅する、という意味で「短命な」と。
eval[4]> list<float>(12.566368000000001000, 3.1415920000000002000,
6.0000000000000000000)
abstract(shape)と書いておくと、shapeを抽象クラスにできます。つまり、 shapeから直接インスタンスを生成することはできなくなります。 （つまり、rectやcircleなどの派生クラスから作る。）
final(circle)で、これ以上の派生禁止、とかも。
ephemeral も abstract も final も、そういう構文なのではなく、 クラスを引数に取る関数呼び出し、なのが面白いところ。
classname <: ephemeral_object()
と派生することで ephemeral 性を付加することも可能だそうです。
次はいきなり新しい内容を詰め込みまくったサンプルですが、まずはご覧下さい。
mymodule :: module(part_of = claire, uses = list(claire))
begin(mymodule)
countup_int <: ephemeral_object(
private/cnt:integer = 0
)
read(x:countup_int) : integer =>
let t := x.cnt in (x.cnt :+ 1, t)
write(x:countup_int, c:integer) =>
(x.cnt := c)
end(mymodule)
hoge <: thing(c:mymodule/countup_int = mymodule/countup_int())
reify(c)
claire> load("sample")
eval[0]> ---- [load CLAIRE file: sample]
true
claire> x :: hoge()
eval[1]> x
claire> x.c
eval[2]> 0
claire> x.c
eval[3]> 1
claire> x.c
eval[4]> 2
...
まず最初に目を引くのが module。
C++のnamespace、Javaのpackageに近い概念です。
クラス名や関数名などの名前を階層化したり、
private を指定することで外から隠蔽したりできます。
まず part_of で親階層モジュール名を指定、
uses で使う他のモジュールのリストを指定して、
新しいモジュールを定義します。これを begin() すると、
以下 end() されるまでの間で定義された識別子は、
この新しいモジュールに属すことになります。
外からモジュール内の名前にアクセスするには、頭にモジュール名/
をつけます。下から２行目参照のこと…。また、モジュール内で
private/ を頭につけて識別子を宣言すると、
モジュール内からのみアクセスできるようになります。上の例では、
cnt メンバの宣言に使っています。
module(part_of = ... , uses = ...) という部分が、
クラスのインスタンス生成と全く同じ形であるのが面白いところです。
例えば rect(width = 10.0, height = 20.0)、
などと比べるとそっくりですね。実際これは見た目だけでなく、
意味的には本当に「moduleクラスのインスタンス生成」
として処理されています。
次に目に付くのが、mymodule :: やインタプリタへの入力の方の
x :: のコロンコロン。
これは「新しい名前付きオブジェクトの定義」だそうです。
let による変数定義とよく似ています。
違いとしては、こっちには in が無いこと。
inというスコープの中に限られない「名前」を定義します。
あと細かいですが、let v := exp() in
というのは無名のオブジェクトを作って、それを変数で指す、
みたいなイメージになる、という違いがあります。
（v はオブジェクトの名前ではなく、変数の名前）
claire> let x := thing() in x
eval[0]> unamed
claire> (x :: thing(), x)
eval[1]> x
countup_int クラスの定義で、private/cnt:integer = 0
と書きました。private/は上で説明したとおりですが、うしろの = 0 は、
インスタンス生成時に countup_int() と cnt =
を省略したときのデフォルト値指定になります。
reify(x) しておくと、属性xを c.x という形で参照したときには、
c.xの値ではなく read(c.x) の結果が返るようになり、
c.x := exp の時は write(c.x, exp) が呼び出されます。
C# の「プロパティ」機能みたいな感じ。
辞書で "reify" を調べると「抽象概念の具体化」と書いてあるんだけど、 つながりがイマイチよくわからない。。。
close という名前のメソッドを書いておくと、
そのクラスのインスタンスを生成したときに自動で呼び出されます。
コンストラクタみたいなものと言えると思います。
こっちも名前の由来が謎。初期化ルーチンの最後を飾る締めの関数なので
closeってことでしょうか。
MyClass <: thing()
close(x:MyClass) : MyClass -> (printf("MyClass created"), x)
closeは新しいインスタンスを受け取ってそれを返す関数にすること、とな。
複素数クラスを書いてみました。
complex[re,im] <: thing(re:float = 0.0, im:float = 0.0)
これ、ちょっと普通のクラス定義と違うところはありますが、
complex <: thing(re:float = 0.0, im:float = 0.0)
と書いてあると思ってcomplex()を使っても全く問題ありません。
ただし、reやimが型の一部になっていることで、こんな書き方ができるようになります。
is_real( x:complex[im:{0.0}] ) : boolean => true
is_real( x:complex ) : boolean => false
claire> is_real( complex(1.0, 2.0) )
eval[0]> false
claire> is_real( complex(1.0, 0.0) )
eval[1]> true
関数引数の型として、「complex...の中でも特にimが0.0なもの」 という限定的な型を使うことができるようになりました。 上では complex[im:{0.0}] を受け取るのと complex を受け取る二つの is_real 関数がオーバーロードされています。 このようにクラスのpropertyの一部を型のパラメータとすることができます。
このようなパラメータ化したクラスの使い方として、 型情報をパラメータにとるという手が考えられます。
queue[of] <: object(of:type, data:list = list())
push( q:queue, e:any ) ->
(if (e % q.of) q.data :add e)
ofというプロパティに型情報を保持しています。つまり、型の情報を保持する変数、
なんてものも普通に書けているわけです。
q := queue(of = integer) とかやって使います。
pop( q:queue<integer> ) : integer ->
let a := car(q.data) in (q.data := cdr(q.data), a)
型パラメータofは頻出イディオムなので、
この場合だけ特別な形で関数引数を書けるようになっているそうです。
それが上の、queue<integer>。queue[of:{integer}]
と同じ意味になります。
claire> s :: queue(of = integer)
eval[1]> s
claire> push(s, 1)
eval[2]> unknown
claire> push(s, 2)
eval[3]> unknown
claire> pop(s)
eval[4]> 1
claire> pop(s)
eval[5]> 2
とまあ、こんなです。
上の例、pushの時の型チェックは実行時( e % s.of )だし、 popに至ってはintegerのキューにしか対応してない、とさんざんな状況です。 そこで、関数定義時に"型変数"を使うことで、こんな風に改善します。
push( q:queue<X>, e:X ) ->
(q.data :add e)
pop( q:queue<X> ) : type[X] ->
let a := car(q.data) in (q.data := cdr(q.data), a)
C++の tempalte<typename X> void push(queue<X>& q, X e)
みたいな感じ。ですが、こちらは可変変数部分を明示するのではなく、
of = なパラメータの部分に既存の識別子以外の識別子を書くことで、
変数として使うことになります。
さて、ここからはぐっとClaireに特徴的な話。この言語は "rule based programming" というプログラミング手法をサポートしています。 「このプロパティの値が書き変わったら」 とか 「この配列の値が書き変ったら」 というタイミングに自動的に決められた動作を実行することができます。
myarray[i:(0 .. 100)] : float := 0.0
myrule() :: rule(
myarray[i] := val =>
printf("~S was assigned to [~S]\n", val, i)
)
一行目は、これまで紹介してこなかった table というデータ構造の宣言です。 indexの範囲が (0 .. 100) で、値が float で、初期値が 0.0 の配列みたいなもの。 今回はindexの範囲を整数にしていますが、ここを任意の集合にして、 連想配列として使うこともできます。
instanciated[c:class] : boolean := false
close(x:myclass) : myclass => (instanciated[myclass] := true, x)
あと、indexに変数名を使えることから推測されるように、 初期値の計算にindexを利用するのもOk。
square[x:(0 .. 50)] : integer := (x * x)
とか。えーと話がそれました。ruleを使ったプログラムの実行例を…
claire> myarray[32] := 10.0
eval[0]> 10.000000000000000000 was assigned to [32]
unknown
claire> myarray[4] := -3.5
eval[1]> -3.5000000000000000000 was assigned to [4]
unknown
ご想像通りの結果かと思います。rule( イベント => 式 )
と書いておくことで、イベントパターンにマッチするコードが実行されると、
対応するruleが実行されるようになります。イベントとしては、
配列への代入・更新(arr[x] := y, arr[x] :+ z)、
プロパティへの代入・更新（x.attr := "hoge", x.attr :* k）
リストの拡張(lst :add obj) があるそうです。
フィボナッチ数列を自動で埋める。
fib[i:(0 .. 10)] : integer := 0
fib_fill() :: rule( fib[i] := y & i % (1 .. 9)
=> fib[i + 1] := y + fib[i - 1] )
(fib[0] := 1, fib[1] := 1)
fib[1] := 1 が実行された時点で、fib_fill
ルールのイベントが発火して、本体（fib[2] := 1 + fib[0]）
が実行されます。するとこれはfib[2]への代入なので、
またイベントが発火して…の繰り返して、fib[10]
までが計算されるわけです。
解の候補の中から特定の条件を満たすものを見つけだす 「探索問題」と総称されるジャンルの問題があります。 この手の問題を解く基本的なアルゴリズムは、 "一個試してみて、駄目だったら元に戻して次の候補をまた試す" の繰り返しという非常に単純なもの。Prolog などの論理型言語は、 この"元に戻って他を試す"という処理を言語的にサポートする、 自動backtracking なる機構を備えています。
Claireの場合、完全に自動ではありませんが、 この backtrack を簡単に行えるようになっています。 基本パターンは次のような感じ。
x:integer := 0
store(x)
hoge() ->
(choice(), x := 1, backtrack())
claire> hoge()
eval[0]> unknown
claire> x
eval[1]> 0
storeと指定しておいた変数は、choice() の時に保存され、
backtrack() の時に復元されます。上の例では、choice 後の
x := 1 は破棄されて 0 に戻っていますね。
choice() で元の「世界」のコピーである新しい
「世界」を作って、色々作業した後にbacktrack()
で前の「世界」に戻ることができる、とマニュアルでは表現されています。
で、実際に探索問題を解いてみます。8-Queen。チェスのクイーンを、 お互いの効き筋にぶつからないように８個盤面に置く置き方を探す、 という有名な問題です。
// x行目に置いたクイーンの位置を記録
queen[x:(1 .. 8)] : integer := 0
// (x,y)に置くことができるか？を記録
is_safe[x:(1 .. 8), y:(1 .. 8)] : boolean := true
store(queen, is_safe)
// (x,y)に置いた場合に8-Queenを完成できるか調べる。
can_put_at(x:integer, y:integer) ->
(choice(),
queen[x] := y, // 置く
for xx in (1 .. (8 - x)) ( // is_safe 更新
is_safe[x + xx, y] := false,
(if (y + xx <= 8) is_safe[x + xx, y + xx] := false),
(if (y - xx >= 1) is_safe[x + xx, y - xx] := false)
),
let r := test_line(x + 1) in // 次の行にも置いてみる
(backtrack(), r)
)
// x行目以降にうまくクイーンを置く
test_line(x:integer) ->
(if (x = 9)
(for i in (1 .. 8) // Ok.結果表示
printf("(~S,~S) ",i,queen[i]), printf("\n"), true)
else
exists(y in (1 .. 8) | is_safe[x, y] & can_put_at(x, y)))
eight_queen() ->
test_line(1)
ようは左から順に置ける場所を片っ端から試していってます。 queen, is_safe 変数に「とりあえず置いてみる」 という形でチェックを進めているので、 ダメだった場合に置いたクイーンを戻す手段として choice, backtrack が活躍しています。
別にbacktrackがなくても、「ステップ毎に queen や is_safe の配列を新しく作って、 関数の引数として渡す」とか、「加えた変更を戻すように自分で backtrack 相当の処理を書く」ことでもこのアルゴリズムは実現できますが、 いずれも処理が遅くなったりソースの見た目が汚くなったりで、 エレガントでない感じがします。
まずお気づきかと思いますが、たいていの場合「choice → 作業 → backtrack」
と組になって使われるので、まずchoiceして終わりでbacktrack、
をする branch 構文がclaire側に用意されています。
あと、上の例だと答えが見つかっても見つからなくてもbacktrackして戻っているので、
答えの表示は探索ルーチンの中で行う、という美しくないことになってます。
そこで、branch では、結果がfalseの時だけbacktrackしてくれます。
もう一つ、queenを置いたときにis_safeを更新するのは、前回の rule を使うのが便利。
queen[x:(1 .. 8)] : integer := 0
is_safe[x:(1 .. 8), y:(1 .. 8)] : boolean := true
store(queen, is_safe)
put_queen() :: rule( queen[x] := y =>
for xx in (1 .. (8 - x)) (
is_safe[x + xx, y] := false,
(if (y + xx <= 8) is_safe[x + xx, y + xx] := false),
(if (y - xx >= 1) is_safe[x + xx, y - xx] := false)
))
can_put_at(x:integer, y:integer) ->
branch( (queen[x] := y, test_line(x + 1)) )
test_line(x:integer) ->
((x = 9) | exists(y in (1 .. 8) | is_safe[x, y] & can_put_at(x, y)))
eight_queen() ->
(if (test_line(1))
for x in (1 .. 8) printf("(~S,~S) ",x,queen[x]),
printf("\n")
)
書き残した内容があったので、ちょっと一瞬脇道にそれます。^^;
gcd :: operation(precedence = precedence(*))
gcd(a:{0}, b:integer) : integer => b
gcd(a:integer, b:integer) : integer => gcd(b mod a, a)
claire> 4 + 6 gcd 8
eval[0]> 6
自分で演算子を定義。* と同じ優先度の、gcd という最大公約数を求める演算子を作っております。 これもmodule同様、意味的には「operationクラスの名前付きインスタンスgcdを定義…」 となっていて、文法上の "演算子" という静的なモノがこうやって扱えるのは面白いところですね。
claire> let f := lambda[(x:integer,y:integer), x + y] in f(1,2)
eval[1]> 3
lambda[(引数リスト), 本体] で無名関数を。
たぶんClaireで書かれたプログラムでもっとも有名なもので、 しかもこの言語の特徴をふんだんに活かしている、 「CHOCO」 というライブラリを使ってみます。constraint-solver、 あるいは制約解消系と呼ばれる種類のライブラリ。
本家の解説ページが丁寧なのでそちらをご覧下さい。 とりあえず試すだけであれば、chocv1.xxx.zip を解凍して出来たディレクトリをカレントディレクトリにして claire -s 4 4 -m choco とやってインタプリタを起動すれば使えます。
choco> let
pb := choco/makeProblem("MyProblem", 2), // ２変数の問題
x := choco/makeBoundIntVar(pb, "x", 1, 3), // 変数宣言: x in (1..3)
y := choco/makeBoundIntVar(pb, "y", 1, 3) // 変数宣言: y in (1..3)
in (
choco/post(pb, x + y == 3), // 制約条件: x+y = 3
choco/post(pb, x > y), // 制約条件: x > y
choco/propagate(pb), // これを満たすx,yは？
printf("~S ~S\n", x, y)
)
eval[0]> :2 :1
unknown
このように、満たして欲しい条件をどしどしとpostして
choco/propagate すると、
頑張って条件を満たす値の組を探してきてくれます。
言ってみれば、問題を記述しさえすれば、
プログラマが解き方を教えなくても勝手に解いてくれるモノ、と。
choco/post などの普通の関数に x > y
という式を渡しているのにちょっと驚きますが、これはx,yという IntVar
クラスのオブジェクト用に+演算子がオーバーロードされていて、
結果として別の制約変数オブジェクトを返しています。
C++使いの方は boost::lambda
などをご想像下さい。
choco> let
pb := choco/makeProblem("pb",10),
x := choco/makeBoundIntVar(pb, "X", 0, 5),
y := choco/makeBoundIntVar(pb, "Y", 0, 2),
z := choco/makeBoundIntVar(pb, "Z", 0, 5)
in
(
choco/post(pb,
((2 * x + 2 * y - z <= 3) and (3 * z - 2 * y >= 10)) ifOnlyIf
((x + 4 * y >= 2) or (y <= 3))),
choco/propagate(pb),
printf("~S ~S\n", choco/getSup(x), choco/getInf(z))
)
eval[0]> 4 4
unknown
chocoのテストコードとして付いてきた例ですが、and とか ifOnlyIf といった論理演算や、getSup, getInf のように結果が範囲になる場合もOk。 他にも自前の制約関数を付け加えたり色々できるようです。
とりあえず感想としては、 記号と識別子の間のスペースの必要なところと不要なところが覚えにくい言語、 だなぁ、と。(^^; 他は全て素敵なんですが、そこだけ混乱しました。
…というわけで、Claireに関する記事はここまで。
普通の「手続き型」言語の機能は一通り備えてくれている横で、
rule や CHOCOライブラリのように、
問題を記述しておくとあとはプログラムが勝手に解いてくれる「宣言的」
なスタイルもサポートするという、多方向的な言語でした。
解決したい問題によって最適なプログラミングパラダイムは異なるわけで、
一つの言語で自由自在に複数のパラダイムを使い分けられる、
というのはかなりの利点だと思われます。
.NET
のような、複数の言語でコラボレートする環境と比較するとどうでしょうかね。
ではでは～。