高等魔術の教理と祭儀 - おがさわらなるひこのオープンソースとかプログラミングとか印刷技術とか

とてもタイトルから見るとプログラミング言語の勉強会とは思えませんが、内容は非常に深い Prolog の勉強会でございました。

このエントリは私がついったのハッシュタグ CoP でメモった内容を、上記アジェンダに合わせてコピペしたものを元にしておりますが、なにせ2009.12.26の勉強会でございます故記憶が抜け落ちたり間違ってたりする可能性は何卒御容赦。

そもそもこの会って？

今年のGWにPPIMっていうPrologの勉強会（というかPrologを実装してみようって会）があって、そこで m0h1can さんが「The Craft of Prolog いいよ！」と言ってたら、「じゃあそれを元に勉強会しましょうよ！」みたいなことで始まった……らしいです。

意外や意外、精鋭7人も集まりかなり盛り上がりました。
オイラが一番レベル低かったんじゃないかな？

The Craft of Prolog は良書とはいえ何せ古いので、最新のトピックを m0h1can さんが補うという形で話が進みました。
基本は m0h1can さん作のスライドで進んだのですが、途中でかなりディープな議論などありまして非常に面白かったと思います。
スライドはこちら。

復習しておきたいこと

ありがちなmemberの実装。?-member([a,b,c],X).するとユニフィケーションでX=aが得られる。失敗させるとバックトラックしてb、cが順に得られる。まあ常識。

member([X|_], X).
member([_|Y], Z) :- member(Y, Z).

?-member([a,b,c], X).

  member([a|b,c], a)
  X = a ;

  member([a|b,c], X) :- member([b,c], X).
    member([b|c], b).
  X = b ;

  member([a|b,c], X) :- member([b,c], X).
    member([b|c], X) :- member([c], X).
      member[c|[]], c).
  X = c ;
  fail.

Prologは対話的に実行されているように見えるだけで、実際はトップレベルが反復しているだけ。
- 対話的にfailさせる';'はcurrent_op(1100,xfy,";")である。
Prologにおけるリストはオペレータ'.'で書き下すことができる。やっていることは Lisp の Cons セル。さっきの member を書き直すとこんな感じ。

member('.'(X,_), X).
member('.'(_,Y), Z) :- member(Y, Z).

?-member('.'(a,'.'(b,'.'(c,[]))), X).

  member('.'(a,'.'(b,'.'(c,[]))), a)
  X = a ;

... 以下略（資料参照）

一階述語論理の完全性とバックトラックは不可分。
Prologのユニフィケーションは例えば Erlang などのパターンマッチと同じ？　違う？　Prologのユニフィケーションはバックトラックと不可分？　という議論があった。
- 結論としてはユニフィケーションそのものは他の言語のパターンマッチングと同じ（＝バックトラックとは不可分でない）ととらえていいということになったんだっけ？

Prolog プログラムはホーン節の集合。ホーン節とは正リテラルが高々一つの形式

$\neg P_1 \vee \neg P_2 \vee \cdots \neg P_n \vee P \\ \,\,\,\,\,\, \Rightarrow P \, \leftarrow P_1, P_2, \cdots, P_n$

- これを Prolog では以下の用に書く。

P :- P1, P2, P3, ... Pn

Prologは一階述語論理、を含む
- だから決定不能 *1
- 命題論理だとSAT。
Prolog＝一階述語論理、ではない
- 一階述語論理は変項として述語は扱えない
  - Prolog は扱えてしまう
  - 与えられたホーン節の集合も書き換えてしまう

はじめにインデントありき…コーディングスタイル

Prologはプログラミング言語である。
したがってインデントで構文を明確にしよう。
-

% BAD
hoge(X) :-
  (C -> A1, A2 ; B1, B2),
  P.

% GOOD
% 真となるリテラルを揃える
hoge(X) :-
  (  C ->
     A1,
     A2,
  ;  B1,
     B2),
  P.

accumulator を使う例はこのような感じ*2。

sum(List, Sum) :- sum1(List, 0, Sum).
  sum1([], Sum, Sum).
  sum1([H|T], S1, Sum) :- S2 is H + S1, sum1(T, S2, Sum).

- accumulator を使うような一時関数はインデントして一時関数と明言しよう。
- Q. それって内部関数みたいなことふつーなのに言語仕様に取り込まれないの？
- A. それが Prolog
  Prolog自体はいじらず機械語っぽく使うのが普通。while{} というマクロでそれっぽいことをする。

sum(List, Sum) :- sum1(List, 0, Sum).
while {
  sum1(....)
}

ちょっと脱線

swi-Prolog には PceEmacs という Emacs クローンがある
- この上でソースコードレベルデバッグとかできてご機嫌*3
- とはいっても変数名がぎちょぎちょになったのを元にもどしてくれる機能とかはない。寂しい。

神は二日目に変数や定数や構造体を作ろうとして述語を作った…Prologは一階述語論理です

Prologは一階述語論理言語。一階述語論理で書きましょう。
論理は文字に意味を持たせない。メタキャラクタで記述する。
- 例えばx=a+b→'='('+'(A,B), X)と書くのが本当。
- '+'/2は加算するという演算を行うわけ「ではない」
- これはあくまで'+'(A,B)とXが'='/2で結びついているという意識を持つことがポイント。
  - '='/2はユニフィケーションを明示的に行う述語
- 数値演算はis/2で書く。
  - Q:'='/2 と is/2 はコンテキストで区別つくから一緒にするという言語拡張はありえないの？
  - A:意味が違うものを同じにしてもあまり嬉しくないよーな。
C++ でいうと Prolog のコードは ExpressionTemplate

俺がお前でお前が俺で…Prologの特徴はユニフィケーションです

ユニフィケーションになれましょう。
- ?-[1,2,3]=[X|Y].->X=1, Y=[2,3]. まあここら辺は他言語のパターンマッチ（特に Erlang) と同じ。
差分リスト。L=[1,2|Hole]は後ろに(未束縛の引数という穴が開いた)リスト。後ろに束縛しちゃえば一瞬でappend/3できるのでO(1)でできる。

ap(X-Y,Y-Ys,X-Ys).
?- ap([1,2|Xs]-Xs,[3,4|Ys]-Ys,Z).
=> Z=[1,2,3,4|Ys].

では Z=[1,2,3,4]を返すためにはどうする？
- 正解はこんな感じ。

ap(X-Y,Y-Ys,X-Ys).
?- ap([1,2|Xs]-Xs,[3,4|Ys]-Ys,Z-[]).
=> Z=[1,2,3,4].

- Q: この「穴が開いた構造 (= 変数が未束縛のままで先に進めてしまう性質)」を使ったおもしろい応用って他にないですか？
- A: ちょっと思いつかない。みなさん考えて見てください。

高階関数な話。
- ?-foo(a,b) =.. L. -> L = [foo,a,b]. =.. をuniv演算子と呼ぶ。
- もちろんユニフィケーションも可。
- これで高階関数を実現。
- なおuniv演算子を使う場合にはコードが項の並びに依存しちゃうのでマクロとか使うときには要注意

行ったり来たりは切り捨て御免…グリーンカットとレッドカット

ご存知 repeat - fail ループ（失敗駆動ループともいうかな）。

% 何回バックトラックをしても成功する述語。
% 組み込み述語なので再定義は必要ないよ（下はあくまでも例）。
repeat.
repeat :- repeat.

?-repeat,write('かわいい？(y/n)'),read(X),(X=y->!;fail),write(ok).

!/0カット操作は現在のバックトラック候補を、今のクエリの呼び元のバックトラックに変える。
カットの種類
- ブルーカット：事実の終わりを明言するカット。動作上の意味はない。
- グリーンカット：探索の枝刈りをするカット。
  - The Craft of Prolog ではこれら二つ (あってもなくても意味が変わらないカット) を総称して「グルーカット」と呼ぶがあまり聞かない表現
- レッドカット：取ってしまうと意味が変わるカット。Nagation as Failure のような。*4 *5

% Nagation as Failure の例
\+P :- call(P), !, fail.

% max の例
max(X, Y, X) :- X >= Y, !.
max(X, Y, Y).

ホリ・ススムがクイックスをやるとどうなるか…PrologはDFSです

Prologの実行セマンティックスであるSLD導出はDFS(Depth First Search；深さ優先探索)なのでそのまま書けば深さ優先で証明木を書ける。
BFS(Breath First Search；幅優先探索）の場合は自前でキューを書いてあげなきゃいけないのでちょっと頑張らないとダメ。

answer(X) :-
    start(S), queue(S, Q), breadth_star(Q, X), solution(X).
breadth_star(Q, Y) :-
    queue_head(X, Q1, Q),
    (    Y = X
    ;    children(X, Children),
         queue_last_list(Children, Q1, Q2),
         breadth_star(Q2, Y)).

しかも使いたいデータ構造によっていちいちキューを書かないといけない（テンプレート以前のC++みたいだ）。

念心合体、ゴー!アクエリオン!…Prologはやっぱりユニフィケーションです

copy_term/2 という述語 (ある述語を渡すと、未束縛の変数で引数を置換した述語をコピーして渡してくれる）を使うことでお手軽クロージャが書けるよ！　という話。
- 言語の中に手を突っ込んでるのでチートくさいがISO標準なので大抵使えますよ
例！*6

app(Lambda, Args) :-
    copy_term(Lambda, Skelton),
    Skelton =.. [lambda, Args, Body],
    call(Body).

?- C = lambda([X], (write(X), write('は一つ歳をとりました'), nl)),
    app(C, ['雪歩さん']), app(C, ['春香さん']).

    雪歩さんは一つ歳をとりました
    春香さんは一つ歳をとりました
    true.

- ミソはここで二つの app/2 の呼び出しで同じXを束縛していること
- copy_term/2 がなかったら一個目の束縛で二個目が成立せず fail してしまう
さらにループを書く例とかあるので資料読め！

後で後悔しないために…先にしておく高階述語

Prologでmap/3,filter/3,foldl/4,foldr/4を書いてみよう。
- 基本的には再帰でunivで述語作ってcall/1。
- でもHaskellと違いcall/1はその場で評価されちゃうので注意。
- 正解はコピペめんどくさいから資料見てね。

バベルの図書館入館申請書…知識ベースの取り扱い

トップレベルでdynamic宣言したのは追加削除される*7。
- ISO標準だから大抵入ってる。
- dynamic宣言を入れると述語の検索インデックスの構造が変わる。
まあ具体的な述語は省略。
- asserta/1,assertz/1の存在ってPrologの言語上の妥協だよね。
- たまに「途中に」assert したくなるときってあるよねー。

ATフィールド中和…Prologは知識をマージします

モジュールはISO外だが今は大体のProlog処理系に入っている。
- 元々は Quintas Prolog から。The Craft of Prolog の記述はまだモジュールが入りたてのころなので少し古いが、入り口としてはOK。
  - Q: モジュールについては各処理系のドキュメントを参考ということ？
  - A: YES。あとつぎのISOの改訂（あるんだ！）に入るんじゃないかと。
実は実用ではなくcurcumscription理論の実装として用意されている。
要はそれぞれ極小化したKB。
モジュールの名前空間をくっつけて呼ぶ。
ただし継承関係はない。
モジュール外の（トップレベルの）名前空間は「user:」。
- トップレベルでは省略できる。
- 逆に言えばモジュール内でトップレベル述語を呼びたいときには明示的に user: をつけないとだめ。
モジュールで探索範囲を限定することにより多様性を解決。
- フレーム問題の解決。
- インタプリタでもモジュール解決はさほど遅くない（だろう）し、コンパイルすれば一意に決まるから速度は変わらない。
あるモジュールを他のモジュールから参照するときにモジュール束縛の変数が並ぶのがキモい*8 けど……論理的な意味、Prologらしさからいうと分かるが、もうちょっとなんとかならない？

味付けにマクロを少々……Prologは二度死ぬ

つまりマクロ展開と実際の実行で Prolog の処理系は二回走るという意味。
入力ストリームからトークンを一文字分取得 → トークン列はマクロ展開（expand_term,expand_goal) → コンパイル → クエリがあれば実行。
- expand_goalはチューリング完全なので完全な Prolog の実行が走る。
DCG の実態はマクロ。例は省略（検索してね）。
詳しくは資料参照のこと〜。

追記

m0h1can さんのブログに当該のイベントについてのエントリ上がってました。

あと前述 ranha さんのブログも参考になります。

*1:証明失敗すると無限ループにハマる、という理解でよいのかな。

*2:あ、Prolog 初心者 (がここ読んでるかは疑問) に言っておくと Prolog は変数の再代入ができない言語なので再帰でループするときには計算用の引数を一個追加するというのが定石なのです。これを accumulator と言います。

*3:でも Ubuntu Karmic だとフォントが全部全角フォント幅になって非常に悲しい。どっかで対策見た気がするんだけど。

*4:なお Prolog の否定マーク \+ は論理記号の T を左90度回した文字を negate のストロークを入れた形を模してるそうな。知らんかった。

*5:Nagation as Failure の意味論については資料参照。

*6:この例について物言いがあって d:id:ranha:20091227:1261922172 「雪歩さんは年を取りません！」だそうですが、そうなの？

*7:学生時代使っていた Prolog にはなかった記憶が……＞dynamic宣言。

*8:ここ文章だとなにいってるか分からないと思うけど、資料公開されたらソースはります。ご勘弁。