Prolog 手習い (2)

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] になったところ。