So-net無料ブログ作成

Prolog で型チェック [Prolog]

Prolog の力といえば単一化ですが、[1] の記事でやったような型チェックの場合も、同じ型であるかどうかの判断というのは単一化でうまく書けそうです。

型チェックのところだけ書きたいので構文木は適当に与えられているものとします。 整数と真偽値と条件分岐と変数束縛とラムダから成る簡単な言語を想定して Prolog で型チェックを行ってみます。

type_of(Num, _, number) :- number(Num).
type_of(true, _, bool).
type_of(false, _, bool).

type_of(if(Cond, True, False), Env, T) :-
  type_of(Cond, Env, bool),
  type_of(True, Env, T),
  type_of(False, Env, T).

type_of(let(Sym, Val, Body), Env, T) :-
  type_of(Val, Env, T2),
  extend_env(Env, Sym, T2, Env2),
  type_of(Body, Env2, T).

type_of(Var, Env, T) :- atom(Var), apply_env(Env, Var, T).

type_of(lambda(Arg, Body), Env, (T1 -> T2)) :-
  extend_env(Env, Arg, T1, Env2),
  type_of(Body, Env2, T2).

extend_env(Env, Sym, Val, [Sym:Val | Env]).

apply_env([Sym:Val | _], Sym, Val) :- !.
apply_env([_:_ | Rest], Sym, Val) :- apply_env(Rest, Sym, Val).

ここで a -> b とか a:b は単なる中置演算子で書いた構造で特別なものではありません(それぞれ ->(a,b), :(a,b) と同じ)。

単一化のおかげで Scheme のときのより簡潔に書けているというだけでも大分ありがたいのですが、さらにボーナスがついています。

ちょっとプログラムをテストしてみましょう。

?- type_of(123, [], X).

X = number

Yes
?- type_of(true, [], X).

X = bool

Yes
?- type_of(if(1,2,3), [], X).

No
?- type_of(if(true,2,3), [], X).

X = number

Yes
?- type_of(let(x,1,x), [], X).

X = number

Yes
?- type_of(let(x,false,x), [], X).

X = bool

Yes
?- type_of(lambda(x,if(x,1,2)), [], X).

X = bool->number

Yes
?- type_of(lambda(x,if(true,x,2)), [], X).

X = number->number

Yes
?- type_of(lambda(x,x), [], X).

X = _G215->_G215

Yes

特筆すべきは最後のラムダのところです。

まず [1] の記事の実装では関数の引数の型は明示的に書かなければならなかったのですが、ここでは特別な追加実装なしに引数の型推論もしてくれています。type_of(lambda... のところで Arg の型 T1 はインスタンス化されないまま型環境に追加されて後で単一化により型が決まっているわけです。

また最後の例のように何でもいい型は最後まで型がインスタンス化されないということによって表現されます。

Prolog の機能におんぶにだっこになることによってこうしたことが「ただで」手に入ったということですね。

追記:関数適用の文法を含めるのを忘れてた。まあいいか。

[1] http://rainyday.blog.so-net.ne.jp/2008-03-30


Prolog の Definite Clause Grammar を試す (2) [Prolog]

以前 [1] の記事で DCG で Indexed Grammar を書くことを思いついていろいろ失敗していた。

その後、2冊目の Prolog の本として Gazdar & Mellish の "Natural Language Processing in Prolog" を買ったのだが、それを読むと DCG を取り上げた部分で Indexed Grammar についての話も出てきて、しかもちゃんと無限ループに陥らない書き方の例がいくつか書いてあった。

{ a^n b^n c^n : n >= 0 } はこう書くといい。(Gazdar & Mellish の例とは index の表現方法を変えている)

s              --> s([]).
s(Indices)     --> b(Indices), c(Indices).
s(Indices)     --> [a], s([i|Indices]).
b([i|Indices]) --> [b], b(Indices).
b([])          --> [].
c([i|Indices]) --> [c], c(Indices).
c([])          --> [].

これだと以下の最後の例のように非文の判定もできる。

?- s([], []).

Yes
?- s([a,b,c], []).

Yes
?- s([a,a,b,b,c,c], []).

Yes
?- s(X, []).

X = [] ;

X = [a, b, c] ;

X = [a, a, b, b, c, c] ;

X = [a, a, a, b, b, b, c, c, c]

Yes
?- s([a,a,b,c,c], []).

No

[1] の記事の文法では t のルールで index を生産して a,b,c のルールで消費する形だったのが、a が生産側で b,c が消費側という非対称な形になっている。

{ xx : x ∈ {a,b}* } はこう書ける。(前掲の本だと { xx : x ∈ {a,b,c}* } だったけど。これも index の表現を変えている)

s              --> x([]).
x(Indices)     --> y(Indices).
x(Indices)     --> [a], x([a|Indices]).
x(Indices)     --> [b], x([b|Indices]).
y([a|Indices]) --> y(Indices), [a].
y([b|Indices]) --> y(Indices), [b].
y([])          --> [].

上記2つはいずれも Indexed Grammar の形をしてるんだけど [1] の記事とは違って非文を与えたときにちゃんと停止する。t のルールが問題の元凶だったようだ。

{ a^n b^n^2 : n >= 1 } については載っていなかったので自分で考えてみる。

s              --> [a], s([i]).
s(Indices)     --> b(Indices).
s(Indices)     --> [a], s([i|Indices]).
b([])          --> [].
b([i|Indices]) --> [b], b(Indices), z(Indices), z(Indices).
z([])          --> [].
z([i|Indices]) --> [b], z(Indices).
?- s(X,[]).

X = [a, b] ;

X = [a, a, b, b, b, b] ;

X = [a, a, a, b, b, b, b, b, b|...] [write]

X = [a, a, a, b, b, b, b, b, b, b, b, b] ;

X = [a, a, a, a, b, b, b, b, b, b, b, b, b, b, b, b, b, b, b, b]

Yes
?- s([a,b],[]).

Yes
?- s([a,a,b,b,b,b],[]).

Yes
?- s([a,a,b,b,b],[]).

No

コツがつかめてきた。ついでに本の練習問題だった a^m b^n c^m d^n を書く。

s              --> x([]).
x(Indices)     --> y(Indices).
x(Indices)     --> [b], x([b|Indices]).
x(Indices)     --> [a], x([a|Indices]).
y([a|Indices]) --> y(Indices), [c].
y([b|Indices]) --> y(Indices), [d].
y([])          --> [].
?- s([a,b,c,d],[]).

Yes
?- s([a,a,b,c,c,d],[]).

Yes
?- s([a,b,b,c,d,d],[]).

Yes
?- s([a,a,b,b,c,d,d],[]).

No
?- s([a,b,b,c,d],[]).

No

追記: 最後のはまた間違えてた... これだと s([a,b,a,c,d,c],[]). も Yes になってしまう。書き直したのが以下。

s              --> x([]).
x(Indices)     --> y(Indices).
x(Indices)     --> [a], x([a|Indices]).
y(Indices)     --> z(Indices).
y(Indices)     --> [b], y([b|Indices]).
z([a|Indices]) --> z(Indices), [c].
z([b|Indices]) --> z(Indices), [d].
z([])          --> [].

[1] http://rainyday.blog.so-net.ne.jp/2008-05-12


Prolog による LFG [Prolog]

LFG (Lexical Functional Grammar) とは何なのかというのは以前手短に書いた [1] のでそちらを参照されたい。その記事を書いたときは LFG の素性構造を Ruby のハッシュとして表現していて、その素性構造を単一化するのに結構苦心して、バグを出したりしていた。あと破壊的な操作を導入したのでいまいちコードの正しさに確信が持てていない。

Prolog を使ったらそれが解決されるかというと別にそうでもなくて、やっぱり素性構造のような順序を問わない構造の単一化は難しい。

リストであれば例えば [X,y,Z] と [x,Y,z] を単一化したときに [x,y,z] という実体が「両方向から見える」ようになるのだけど {:a => "a", :b => "b"、:d => "d"} と {:d => "d", :c => "c", :b => "b"} を単一化したときに両方から {:a =>"a", :b => "b", :c => "c", :d => "d"} と見えるようにしないといけないというのはやっぱり破壊的に書かずにいられないのではなかろうか。(ちなみに、ひょっとしたら LiLFeS [2] っていう言語がそういうことができるものなのかもしれないのだが、これは以前試そうとしたら手元の環境でコンパイル不能だったので深追いしなかった)

それでこの問題の一番簡単な回避方法は、順序を問わない構造というのを直接表現するのをやめて普通のリストを使い、素性は名前でなくて位置から決まるようにすればいい。ここでは5要素のリストが [Subj, Pred, Num, Tense, Pers] という素性の値に対応するとみなすことにする。

この決め事に基づいて極めて簡略化された英文法を Prolog の DCG で表現すると以下のようになる。

/* f-structure: [Subj, Pred, Num, Tense, Pers] */

s([Subj|X]) --> np(Subj), vp([Subj|X]).

np(F) --> n(F).
vp(F) --> v(F).

n([_,lion,pl,_,_]) --> [lions].

v([[_,_,pl,_,3],sleep,_,pres,_]) --> [sleep].
v([[_,_,sg,_,3],sleep,_,pres,_]) --> [sleeps].

単一化を言語がサポートしているというのは本当に強力だと思う。これを以下のように使うと、文の f-structure を求めることができる。

?- s(F,[lions,sleep],[]).

F = [[_G224, lion, pl, _G233, 3], sleep, _G245, pres, _G251] ;

No

インスタンス化されない変数が残ってしまうのはこの実装における素性構造の扱いを先のように決めたからでしょうがない。以下のように非文を与えるときちんと失敗する。これは sg と pl が単一化に失敗するからだ。

?- s(F,[lions,sleeps],[]).

No

さらに f-structure から文を求めることもできる。これは前回 Ruby で実装したものではできなかったようなことだ。

?- s([[_,lion,pl,_,3],sleep,_,pres,_],S,[]).

S = [lion, sleeps] ;

No

ところでついでに文のツリー構造(LFG でいう c-structure)も見れるようにした。

s(s(NP,VP),[Subj|X]) --> np(NP,Subj), vp(VP,[Subj|X]).

np(np(N),F) --> n(N,F).
vp(vp(V),F) --> v(V,F).

n(n(lions),[_,lion,pl,_,_]) --> [lions].

v(v(sleep),[[_,_,pl,_,3],sleep,_,pres,_]) --> [sleep].
v(v(sleeps),[[_,_,sg,_,3],sleep,_,pres,_]) --> [sleeps].
?- s(C,F,S,[]).

C = s(np(n(lions)), vp(v(sleep)))
F = [[_G251, lion, pl, _G260, 3], sleep, _G279, pres, _G285]
S = [lions, sleep] ;

No

[1] http://rainyday.blog.so-net.ne.jp/2007-04-09
[2] http://www-tsujii.is.s.u-tokyo.ac.jp/lilfes/index-j.html


Prolog の Definite Clause Grammar を試す [Prolog]

DCG (Definite Clause Grammar) はProlog に組み込みのパーサ記法のようなもので、以下のような感じで文法を表現すると構文解析ができるようになる。

sentence --> noun_phrase, verb_phrase.
noun_phrase --> determiner, noun.
verb_phrase --> verb.
verb_phrase --> verb, noun_phrase.
determiner --> [the].
noun --> [man].
noun --> [apple].
verb --> [eats].
verb --> [sings].

基本的には上記の通り文脈自由文法なんだけど非終端記号がパラメタを持つことができて、その単一化を利用して例えば自然言語の性や数の一致を文法への制約として付け加えたりもできる。

ところで非終端記号に付加情報がついたものといわれて Indexed Grammar を連想した。たまたま本で数ページ紹介されているのを読んだ程度の知識しか無いのだが、Indexed Grammar というのは基本的には文脈自由文法なのだけど、非終端記号に index と呼ばれるシンボルの列をくっつけることができて、文法規則はこのシンボル列を左辺から右辺の非終端記号に引き継いだり、追加したり削除したりできる。ただし追加と削除はスタック的な操作しか許されない。こういう仕組みによって Indexed Grammar は文脈自由文法と文脈依存文法の中間の生成力を持つ。らしい。

文脈自由文法で表現できないが Indexed Grammar で表現できる言語としては以下のものがある。

{ a^n b^n c^n : n >= 0 } (同じ数の a,b,c のこの順に並べた文を生成する)
{ xx : x ∈ {a,b}* } (a と b からなる文字列を2回繰り返した文を生成)
{ a^n b^n^2 : n >= 1 } (a を n 回、b を n^2 回繰り返した文を生成)

最初の言語を Indexed Grammar 風の DCG で表現すると以下のようになる。

s              --> t([]).
t(Indices)     --> a(Indices), b(Indices), c(Indices).
t(Indices)     --> t([i|Indices]).
a([])          --> [].
b([])          --> [].
c([])          --> [].
a([i|Indices]) --> [a], a(Indices).
b([i|Indices]) --> [b], b(Indices).
c([i|Indices]) --> [c], c(Indices).

つまり t(Indices) --> t([i|Indices]). のプロダクションが i という index を任意の数まで増やす役目をしていて、t(Indices) --> a(Indices), b(Indices), c(Indices). でその数を a,b,c に引き継ぐ。a,b,c の規則はそのインデクスを1つずつ消費していく。これを試してみると、

?- s([], []).

Yes
?- s([a,b,c], []).

Yes
?- s([a,a,b,b,c,c], []).

Yes
?- s(X, []).

X = [] ;

X = [a, b, c] ;

X = [a, a, b, b, c, c] ;

X = [a, a, a, b, b, b, c, c, c]

Yes

という感じでここまでは嬉しいくらいうまくいく。でも言語に属さない文を与えると止まらなくなってしまった。

?- s([a,a,b,c,c], []).
ERROR: Out of global stack
?- s([a,a,c,c], []).
ERROR: Out of global stack

先の2つ目の言語は Indexed Grammar だと以下のように定義できる。

s                  --> t([]).
t(Indices)         --> front(Indices), rear(Indices).
t(Indices)         --> t([a|Indices]).
t(Indices)         --> t([b|Indices]).
front([])          --> [].
front([a|Indices]) --> [a], front(Indices).
front([b|Indices]) --> [b], front(Indices).
rear([])           --> [].
rear([a|Indices])  --> [a], rear(Indices).
rear([b|Indices])  --> [b], rear(Indices).

ここでは t の下2つの規則がインデクスとして任意の a,b の列を作りだす。ひとしきり作り終わったところで front と rear の規則に引き継いでそれぞれ作り出されたとおりの文字列を生成する。これは DCG としてうまくいくだろうか。

?- s(X,[]).

X = [] ;

X = [a, a] ;

X = [a, a, a, a] ;

X = [a, a, a, a, a, a] ;

X = [a, a, a, a, a, a, a, a]

Yes
?- s([],[]).

Yes
?- s([a,a], []).

Yes
?- s([a,a,a,a], []).

Yes
?- s([a,b], []).
ERROR: Out of local stack
   Exception: (27,925) t([a, a, a, a, a, a, a, a|...], [a, b], []) ? abort
% Execution Aborted
?- s([a,a,b,b], []).
ERROR: Out of local stack
   Exception: (27,868) t([a, a, a, a, a, a, a, a|...], [a, a, b, b], []) ? abort
% Execution Aborted

インスタンス化されていない変数を与えた場合は front と rear が同じつまらない文しか生成してくれなくなった。さらに言語に含まれるかどうかの判定では言語に含まれているものでも front と rear が違う文だと止まらなくなってしまった。(2008-06-03追記: 訂正!front と rear が違う文は言語に含まれません。ひどい勘違い。[a,b,a,b] みたいなのをつまらなくない文法的な文の例として出すべきところでした。「言語に含まれているものでも~」という部分は正しくないです。)

3つめの言語は以下のように書ける。

s              --> t([]).
t(Indices)     --> a(Indices), b(Indices).
t(Indices)     --> t([i|Indices]).
a([])          --> [a].
a([i|Indices]) --> [a], a(Indices).
b([])          --> [b].
b([i|Indices]) --> [b], b(Indices), z(Indices), z(Indices).
z([])          --> [b].
z([i|Indices]) --> [b], z(Indices).

実験結果。これは1つ目と同じような感じだ。

?- s(X,[]).

X = [a, b] ;

X = [a, a, b, b, b, b] ;

X = [a, a, a, b, b, b, b, b, b|...] [write]

X = [a, a, a, b, b, b, b, b, b, b, b, b] ;

X = [a, a, a, a, b, b, b, b, b, b, b, b, b, b, b, b, b, b, b, b]

Yes
?- s([a,b],[]).

Yes
?- s([a,a,b,b,b,b],[]).

Yes
?- s([a,a,b,b,b],[]).
ERROR: Out of global stack

それで以上のような結果をどう整理したらいいのかというと、実はよく理解できていない。多分再帰下降型のパーサが文脈自由文法のある制限された形しか扱えないのと同様に、DCG でも文法が表現できるということと、それがそのまま Prolog のトップダウン/バックトラック付きのパーシングで解析できるかどうかというのは別の話だということだろうか。

2008-05-15追記:なんか Indexed Grammar の例を考え出したせいで複雑になったけど、単純に Prolog 一般と同様に DCG でも左再帰がだめってことの気がしてきた。


Prolog でスタック言語を作る [Prolog]

Prolog で簡単なスタック言語を作ってみた。組み込み関数は以下の通り。

- dup: スタックの先頭を複製してスタックに積む
- swap: スタックの最初の2つを入れ替える
- pop: スタックの最初の要素を取り除く
- add: スタックの最初の2つを取り除いてそれらを合計したものを積む
- if: スタックの先頭の真偽値に応じて2つ目ないし3つ目の関数を実行
- cons: スタックの最初の要素を2つ目の要素(リスト)にconsする
- emptyp: スタックの最初の要素を取り除き、それが空リストだったらtrue、それ以外だったらfalseをスタックに置く
- car: スタックの先頭要素(リスト)を取り除き、そのcarを積む
- cdr: スタックの先頭要素(リスト)を取り除き、そのcdrを積む
- app: スタックの先頭要素(関数)を適用する
- papp: スタックの先頭要素(関数)を2つ目の要素にだけ部分適用する

これが実行例。
?- exec([], [12,dup], X).

X = [12, 12] ;

No
?- exec([], [12,34,swap], X).

X = [12, 34] ;

No
?- exec([], [12,34,pop], X).

X = [12] ;

No
?- exec([], [12,34,add], X).

X = [46] ;

No
?- exec([], [12,true,[dup,add],[34,swap],if], X).

X = [24] ;

No
?- exec([], [12,false,[dup,add],[34,swap],if], X).

X = [12, 34] ;

No
?- exec([], [nil,12,cons,34,cons], X).

X = [[34, 12]] ;

No
?- exec([], [nil,emptyp], X).

X = [true] ;

No
?- exec([], [nil,12,cons,emptyp], X).

X = [false] ;

No
?- exec([], [nil,12,cons,34,cons,car], X).

X = [34] ;

No
?- exec([], [nil,12,cons,34,cons,cdr], X).

X = [[12]] ;

No
?- exec([], [12,34,[add],app], X).

X = [46] ;

No
?- exec([], [12,34,[add],papp], X).

X = [[34, add], 12] ;

No
?- exec([], [12,34,[add],papp,app], X).

X = [46] ;

No
?- exec([], [12,34,[add],papp,papp], X).

X = [[12, 34, add]] ;

No
?- exec([], [12,34,[add],papp,papp,app], X).

X = [46] ;

No

実装コード。非常にシンプルで、殆ど仕様そのまま。Prolog すごい。

exec(S, [], S).
exec(S1, [H|T], S2) :- value(H,I), !, exec([I|S1], T, S2).
exec(S1, [H|T], S2) :-
  P =.. [H, S1, S3],
  call(P),
  exec(S3, T, S2).

value(X,X) :- number(X).
value(X,X) :- is_list(X).
value(true,true).
value(false,false).
value(nil,[]).

dup([H|T],[H,H|T]).
swap([X,Y|Z],[Y,X|Z]).
pop([H|T],T).
add([X,Y|Z], [S|Z]) :- S is X+Y.
if([_,X,true|Y], Z) :- exec(Y,X,Z).
if([X,_,false|Y], Z) :- exec(Y,X,Z).
cons([X,Y|Z],[[X|Y]|Z]).
emptyp([[]|T],[true|T]) :- !.
emptyp([_|T],[false|T]).
car([[X|Y]|Z],[X|Z]).
cdr([[X|Y]|Z],[Y|Z]).
app([X|Y],Z) :- exec(Y, X, Z).
papp([X,Y|Z], [[Y|X]|Z]).

Prolog で油売り算(幅優先探索) [Prolog]

Prolog で幅優先探索をする方法を覚えたので [1] の油売り算を幅優先探索で解いてみた。(1年遅れですが)

Prolog で素直に組むと深さ優先探索を行うことになるけど、アジェンダをリストとして明示的に持って findall で次の状態のリストを得て後ろに追加してやれば幅優先探索を行うことができる。アジェンダを作る分だけコードはめんどくさい。

abura(Ac,Bc,Cc,Path) :-
  move(Ac,Bc,Cc,[[[Ac,0,0]]],Trail),
  reverse(Trail,Path).

amount(Src,Dest,Cap,Amt) :- Src > 0, Dest < Cap, Src < Cap - Dest, !, Amt = Src.
amount(Src,Dest,Cap,Amt) :- Src > 0, Dest < Cap, Amt is Cap - Dest.

successor(Ac,Bc,Cc,[A,B,C],[A1,B1,C]) :- amount(A,B,Bc,Amt), A1 is A-Amt, B1 is B+Amt.
successor(Ac,Bc,Cc,[A,B,C],[A1,B,C1]) :- amount(A,C,Cc,Amt), A1 is A-Amt, C1 is C+Amt.
successor(Ac,Bc,Cc,[A,B,C],[A1,B1,C]) :- amount(B,A,Ac,Amt), B1 is B-Amt, A1 is A+Amt.
successor(Ac,Bc,Cc,[A,B,C],[A,B1,C1]) :- amount(B,C,Cc,Amt), B1 is B-Amt, C1 is C+Amt.
successor(Ac,Bc,Cc,[A,B,C],[A1,B,C1]) :- amount(C,A,Ac,Amt), C1 is C-Amt, A1 is A+Amt.
successor(Ac,Bc,Cc,[A,B,C],[A,B1,C1]) :- amount(C,B,Bc,Amt), C1 is C-Amt, B1 is B+Amt.

is_goal([Half,Half,0]).
is_goal([Half,0,Half]).
is_goal([0,Half,Half]).

move(_,_,_,Agenda,Trail) :-
  Agenda = [FirstPath|RestPaths],
  FirstPath = [State|_],
  is_goal(State),
  Trail = FirstPath.
move(Ac,Bc,Cc,Agenda,Trail) :-
  Agenda = [FirstPath|RestPaths],
  FirstPath = [State|Past],
  findall([Succ,State|Past],
    (successor(Ac,Bc,Cc,State,Succ),\+member(Succ,Past)),
    SuccPaths),
  /*append(SuccPaths,RestPaths,NewAgenda),*/ /* depth-first */
  append(RestPaths,SuccPaths,NewAgenda), /* breadth-first */
  move(Ac,Bc,Cc,NewAgenda,Trail).

move の中の単一化は述語の引数のところでパターンマッチさせればもっと簡潔になるはずだけど、頭がついていかないので冗長な書き方にした。あと Prolog には @ とか as にあたるものは無いんだろうか。

実行結果。幅優先なので短い順に答えが出る。SWI-Prolog では解の表示が省略されたときは w を押すと全部表示してくれる。

?- abura(10,7,3,Answer).

Answer = [[10, 0, 0], [3, 7, 0], [3, 4, 3], [6, 4, 0], [6, 1, 3], [9, 1, 0], [9, 0|...], [2|...], [...|...]|...] [write]

Answer = [[10, 0, 0], [3, 7, 0], [3, 4, 3], [6, 4, 0], [6, 1, 3], [9, 1, 0], [9, 0, 1], [2, 7, 1], [2, 5, 3], [5, 5, 0]] ;

Answer = [[10, 0, 0], [7, 0, 3], [7, 3, 0], [4, 3, 3], [4, 6, 0], [1, 6, 3], [1, 7, 2], [8, 0, 2], [8, 2, 0], [5, 2, 3], [5, 5, 0]] ;

Answer = [[10, 0, 0], [7, 0, 3], [0, 7, 3], [3, 7, 0], [3, 4, 3], [6, 4, 0], [6, 1, 3], [9, 1, 0], [9, 0, 1], [2, 7, 1], [2, 5, 3], [5, 5, 0]] ;

Answer = [[10, 0, 0], [7, 0, 3], [7, 3, 0], [3, 7, 0], [3, 4, 3], [6, 4, 0], [6, 1, 3], [9, 1, 0], [9, 0, 1], [2, 7, 1], [2, 5, 3], [5, 5, 0]] ;

Answer = [[10, 0, 0], [3, 7, 0], [0, 7, 3], [7, 0, 3], [7, 3, 0], [4, 3, 3], [4, 6, 0], [1, 6, 3], [1, 7, 2], [8, 0, 2], [8, 2, 0], [5, 2, 3], [5, 5, 0]] ;

Answer = [[10, 0, 0], [3, 7, 0], [3, 4, 3], [7, 0, 3], [7, 3, 0], [4, 3, 3], [4, 6, 0], [1, 6, 3], [1, 7, 2], [8, 0, 2], [8, 2, 0], [5, 2, 3], [5, 5, 0]] ;

Answer = [[10, 0, 0], [3, 7, 0], [3, 4, 3], [0, 7, 3], [7, 0, 3], [7, 3, 0], [4, 3, 3], [4, 6, 0], [1, 6, 3], [1, 7, 2], [8, 0, 2], [8, 2, 0], [5, 2, 3], [5, 5, 0]] ;

Answer = [[10, 0, 0], [7, 0, 3], [7, 3, 0], [4, 3, 3], [0, 7, 3], [3, 7, 0], [3, 4, 3], [6, 4, 0], [6, 1, 3], [9, 1, 0], [9, 0, 1], [2, 7, 1], [2, 5, 3], [5, 5, 0]] ;

Answer = [[10, 0, 0], [7, 0, 3], [7, 3, 0], [4, 3, 3], [4, 6, 0], [3, 7, 0], [3, 4, 3], [6, 4, 0], [6, 1, 3], [9, 1, 0], [9, 0, 1], [2, 7, 1], [2, 5, 3], [5, 5, 0]] ;

Answer = [[10, 0, 0], [3, 7, 0], [3, 4, 3], [6, 4, 0], [6, 1, 3], [7, 0, 3], [7, 3, 0], [4, 3, 3], [4, 6, 0], [1, 6, 3], [1, 7, 2], [8, 0, 2], [8, 2, 0], [5, 2, 3], [5, 5, 0]] ;

Answer = [[10, 0, 0], [3, 7, 0], [3, 4, 3], [6, 4, 0], [6, 1, 3], [0, 7, 3], [7, 0, 3], [7, 3, 0], [4, 3, 3], [4, 6, 0], [1, 6, 3], [1, 7, 2], [8, 0, 2], [8, 2, 0], [5, 2, 3], [5, 5, 0]] ;

Answer = [[10, 0, 0], [7, 0, 3], [7, 3, 0], [4, 3, 3], [4, 6, 0], [1, 6, 3], [0, 7, 3], [3, 7, 0], [3, 4, 3], [6, 4, 0], [6, 1, 3], [9, 1, 0], [9, 0, 1], [2, 7, 1], [2, 5, 3], [5, 5, 0]] ;

Answer = [[10, 0, 0], [7, 0, 3], [7, 3, 0], [4, 3, 3], [4, 6, 0], [1, 6, 3], [1, 7, 2], [3, 7, 0], [3, 4, 3], [6, 4, 0], [6, 1, 3], [9, 1, 0], [9, 0, 1], [2, 7, 1], [2, 5, 3], [5, 5, 0]] ;

Answer = [[10, 0, 0], [3, 7, 0], [3, 4, 3], [6, 4, 0], [6, 1, 3], [9, 1, 0], [9, 0, 1], [7, 0, 3], [7, 3, 0], [4, 3, 3], [4, 6, 0], [1, 6, 3], [1, 7, 2], [8, 0, 2], [8, 2, 0], [5, 2, 3], [5, 5, 0]] ;

Answer = [[10, 0, 0], [7, 0, 3], [7, 3, 0], [4, 3, 3], [4, 6, 0], [1, 6, 3], [1, 7, 2], [0, 7, 3], [3, 7, 0], [3, 4, 3], [6, 4, 0], [6, 1, 3], [9, 1, 0], [9, 0, 1], [2, 7, 1], [2, 5, 3], [5, 5, 0]] ;

Answer = [[10, 0, 0], [7, 0, 3], [7, 3, 0], [4, 3, 3], [4, 6, 0], [1, 6, 3], [1, 7, 2], [8, 0, 2], [8, 2, 0], [3, 7, 0], [3, 4, 3], [6, 4, 0], [6, 1, 3], [9, 1, 0], [9, 0, 1], [2, 7, 1], [2, 5, 3], [5, 5, 0]] ;

Answer = [[10, 0, 0], [3, 7, 0], [3, 4, 3], [6, 4, 0], [6, 1, 3], [9, 1, 0], [9, 0, 1], [2, 7, 1], [0, 7, 3], [7, 0, 3], [7, 3, 0], [4, 3, 3], [4, 6, 0], [1, 6, 3], [1, 7, 2], [8, 0, 2], [8, 2, 0], [5, 2, 3], [5, 5, 0]] ;

Answer = [[10, 0, 0], [3, 7, 0], [3, 4, 3], [6, 4, 0], [6, 1, 3], [9, 1, 0], [9, 0, 1], [2, 7, 1], [2, 5, 3], [7, 0, 3], [7, 3, 0], [4, 3, 3], [4, 6, 0], [1, 6, 3], [1, 7, 2], [8, 0, 2], [8, 2, 0], [5, 2, 3], [5, 5, 0]] ;

Answer = [[10, 0, 0], [3, 7, 0], [3, 4, 3], [6, 4, 0], [6, 1, 3], [9, 1, 0], [9, 0, 1], [2, 7, 1], [2, 5, 3], [0, 7, 3], [7, 0, 3], [7, 3, 0], [4, 3, 3], [4, 6, 0], [1, 6, 3], [1, 7, 2], [8, 0, 2], [8, 2, 0], [5, 2, 3], [5, 5, 0]] ;

Answer = [[10, 0, 0], [7, 0, 3], [7, 3, 0], [4, 3, 3], [4, 6, 0], [1, 6, 3], [1, 7, 2], [8, 0, 2], [8, 2, 0], [5, 2, 3], [0, 7, 3], [3, 7, 0], [3, 4, 3], [6, 4, 0], [6, 1, 3], [9, 1, 0], [9, 0, 1], [2, 7, 1], [2, 5, 3], [5, 5, 0]] ;

No

[1] http://karetta.jp/article/blog/ll-spirit/033840


Prolog 手習い (2) [Prolog]

Prolog が少し分かってきたところで以前途中まで読んでいた The Reasoned Schemer を読み返したらだいぶ見通しがよくなっていた。理解を確かめるために The Reasoned Schemer (以下 TRS)の第1章のコードの一部を Prolog に置き換えてみた。

まず対話の10番。

run_10(Q) :- fail.

run_10 はフェイルしかしないので以下のように問うても解は無い。

?- run_10(Q).

No

11番。?- の Q と run_11 の中の Q は別物だけど共有されるので結果的に run_11 の中の Q の値である t が ?- の Q の値になる。

run_11(Q) :- t = Q.
?- run_11(Q).

Q = t ;

No

12番。conjunction の中にフェイルするものがあると全体がフェイルする。

run_12(Q) :- fail, t = Q.
?- run_12(Q).

No

23番。これは TRS でいうと (run* (q) (fresh (x) (== #t x) (== #t q))) という風に fresh というマクロを使って新しいローカルな変数を導入するところなんだけど Prolog では :- の右側に新たに出てくる変数は常にローカルである。これについては個人的には TRS みたいに明示的に導入するほうが Prolog 風よりも分かりやすいと思う。

run_23(Q) :- t = X, t = Q.
?- run_23(Q).

Q = t ;

No

26番と27番。= による単一化は左右入れ替えても同じ意味。

run_26(Q) :- X = t, t = Q.
run_27(Q) :- X = t, Q = t.
?- run_26(Q).

Q = t ;

No
?- run_27(Q).

Q = t ;

No

28番。instantiate されていない変数。SWI-Prolog では _Gnnn という形で表示される。

run_28(X).
?- run_28(X).

X = _G157 ;

No

30番。リスト構造。

run_30(R) :- [X, Y] = R.
?- run_30(R).

R = [_G205, _G208] ;

No

34番。単一化で矛盾が起こるとフェイルするので解が無い。

run_34(Q) :- f = Q, t = Q.
?- run_34(Q).

No

35番。矛盾しないなら何回でも = を使ってよい。

run_35(Q) :- f = Q, f = Q.
?- run_35(Q).

Q = f ;

No

37番。フレッシュな変数同士の単一化。次に見るように両者は共有される。

run_37(R) :- X = R.
?- run_37(R).

R = _G157 ;

No

38番と39番。X と Q を単一化するので X と単一化された値である t が Q の値にもなる。

run_38(Q) :- t = X, X = Q.
run_39(Q) :- X = Q, t = X.
?- run_38(Q).

Q = t ;

No
?- run_39(Q).

Q = t ;

No

47番。バックトラック。複数の解が見つかる。最後の fail の行は TRS にあわせたけど書かなくてもよい。これ以降は書かない。

run_47(X) :- olive = X.
run_47(X) :- oil = X.
run_47(X) :- fail.
?- run_47(X).

X = olive ;

X = oil ;

No

50番。フェイルするルールは飛ばされる。

run_50(X) :- virgin = X, fail.
run_50(X) :- olive = X.
run_50(X).
run_50(X) :- oil = X.
?- run_50(X).

X = olive ;

X = _G157 ;

X = oil ;

No

53番。再びリスト構造。

run_53(R) :- split = X, pea = Y, [X, Y] = R.
?- run_53(R).

R = [split, pea] ;

No

54番。さっきの X と Y の組み合わせに複数の解がある。

run_54(R) :- run_54_helper(X, Y), [X, Y] = R.
run_54_helper(X, Y) :- split = X, pea = Y.
run_54_helper(X, Y) :- navy = X, bean = Y.
?- run_54(R).

R = [split, pea] ;

R = [navy, bean] ;

No

そして54番の別解。一つの節の中に or があるのはあまり Prolog っぽくない?

run_54_2(R) :- (split = X, pea = Y; navy = X, bean = Y), [X, Y] = R.

58番。これはまず TRS の元のコードを先に挙げる。

(run* (r)
  (fresh (x y z)
    (cond-e
      ((== y x) (fresh (x) (== z x)))
      ((fresh (x) (== y x)) (== z x))
      (else fail))
    (== (cons y (cons z '())) r)))

TRS の fresh マクロはこういう風に任意の場所で新しくローカルな変数を導入できて、例えば4行目の fresh のなかの x は2行目で導入された x とは別であるということがポイント。これは Prolog にどう訳せばいいか?

こうやって新たな述語(run_58_helper_1 と run_58_helper_2)を導入するしかないか。まだ知らないだけで TRS の fresh 相当があったりいないかな。

run_58(R) :- run_58_helper(X, Y, Z), [Y, Z] = R.
run_58_helper(X, Y, Z) :- Y = X, run_58_helper_1(Z).
run_58_helper(X, Y, Z) :- run_58_helper_2(Y), Z = X.
run_58_helper_1(Z) :- Z = X.
run_58_helper_2(Z) :- Y = X.
?- run_58(R).

R = [_G205, _G208] ;

R = [_G205, _G208] ;

No

TRS 版だと内側の fresh のなかの z や y が自動的に外側の fresh で導入された z や y を指してくれるけど Prolog 版だとむしろそっちを渡して結び付けてやる必要がある。

上記のような例で外の X と中の X が別だというのは以下のようにするとはっきりする。59番。

run_59(R) :- run_59_helper(X, Y, Z), f = X, [Y, Z] = R.
run_59_helper(X, Y, Z) :- Y = X, run_59_helper_1(Z).
run_59_helper(X, Y, Z) :- run_59_helper_2(Y), Z = X.
run_59_helper_1(Z) :- Z = X.
run_59_helper_2(Y) :- Y = X.
?- run_59(R).

R = [f, _G208] ;

R = [_G205, f] ;

No

もし外と内の X が共有されていたら X=Y=Z でどちらも [f, f] になったところ。


Prolog 手習い (1) [Prolog]

何の脈絡もなく Prolog の勉強を始めた。Amazon のウィッシュリストにいつまでも Clocksin と Mellish の "Programming in Prolog"(第5版)があったのをカートに入れたのだ。

いまのところ第4章のカットのところまで読んだのだけど Prolog の動作の仕組みを念入りに解説してくれていて、大変わかりやすい。これまで Prolog に感じていたもやっとがかなり晴れた(やっぱり論理プログラミングとはいっても内部の動きを意識しないと腹に落ちないのか、と思うとちょっと微妙な気分だけど)。

ここまでの内容では is と数値計算用の関数がよくわからない。まず数値計算用の + だとかは中置演算子の形をしているだけで 1+1 は +(1,1) とみなせると言っている。

だからこう書いておけば

+(john, mary).

こうなる。

?- john + mary.

Yes
?- X + Y.

X = john
Y = mary

ここまではいい。こうした演算子は is と組み合わせると突然数値計算を行う。

?- X is 1 + 1.

X = 2

さっきの + は ML 風に書くと (term * term) -> bool だったんだけど is の右側にくるときは (term * term) -> term になっている。 普通の述語を is の右側に書くとエラーになる。なんか気持ち悪いのは、この is の機能はとってつけたようにこうなっているだけなんだろうか。 つまり + やら - やらは is の方で特別扱いされていて、ユーザ定義で (term * term) -> term になるようなものを書くことはできないってことでいいのかな。

ところで Programming in Prolog は分かりやすいんだけど Prolog の計算の流れを図示する方法は結構苦慮しているように思える。 述語の入れ子関係と、バックトラックの選択肢からなるツリーと、計算過程での変数の状況をいっぺんに静的な図で表現できる書き方はないかなあ。 バックトラックという「動き」はどうにも頭への収まりが悪い。

あと間違いを見つけた。p.56 の左再帰の例で

person(adam).
person(X) :- person(Y), mother(X, Y).

person(X) :- person(Y), mother(X, Y).
person(adam).

前者が左再帰で止まらなくて、後者が解決法だって書いてるんだけど逆ですよね。すごい悩んでしまった。(あと mother でいいのかとも)