Rubyist のための他言語探訪 【第 13 回】 Prolog
著者：まつもとゆきひろ
Prolog
今回は「普通の言語」とは異なる計算モデルを採用した言語の代表格である、Prolog を紹介します。
Prolog は 1972 年頃、Alain Colmerauer と Philippe Rousselによって開発されました。 Prolog という名前は「PROgrammation en LOGique (Programming in Logic)」の短縮形で、この言語が論理型計算モデルを採用していることを示しています。
Prolog が採用しているのは「一階述語論理」と呼ばれます。 「一階」とは「高階ではない」、つまり、論理自身は扱わないという意味です。 述語とは真偽を判定できる命題であり、Prolog はそれに基づいた論理体系によってプログラムを表現します。
あまりにもベタな例ですが、「ソクラテスは死ぬ」という三段論法によって、Prolog のプログラムを見てみましょう。
人間(ソクラテス).
死ぬ(X) :- 人間(X).1行目は「ソクラテスは人間である」という表明です。 これは公理に相当します。次は「X が人間ならば、X は死ぬ」というルールです。 ここで、
?- 死ぬ(ソクラテス).と問うと、システムは三段論法を始めます。
- ソクラテスは死ぬか？
- ソクラテスは人間である (1 行目から)
- 人間は死ぬ (2 行目から)
- よってソクラテスは死ぬ
システムは「ソクラテスが死ぬ」ということが分かったので、問われた命題は真である (true) と返します。
もう少し複雑な例を見てみましょう。
兄弟(X, Y) :- 親の子(Z, X), 親の子(Z, Y).
親の子(X, Y) :- 父の子(X, Y).
親の子(X, Y) :- 母の子(X, Y).
母の子(judy, sally).
父の子(tom, sally).
父の子(tom, erica).
父の子(mike, tom).ここでは「兄弟」、「親の子」、「父の子」、「母の子」という関係を定義しています。
兄弟(X, Y) :- 親の子(Z, X), 親の子(Z, Y).とは、X と Y が共通の親Zを持つことを意味しています。 コンマで区切られた複数の述語はそれらが同時に成立することを意味します (アンドの関係)。
親の子(X, Y) :- 父の子(X, Y).
親の子(X, Y) :- 母の子(X, Y).は「親の子」とは「父の子」あるいは「母の子」のいずれかであるとシステムに教えています。 こちらはオアの関係になります。
これらのルールの下で、システムに sally と erica が兄弟であるか聞いてみましょう。
?- 兄弟(sally, erica).システムはこの命題が成立するかどうか推論し、結果 (true) を返します。
オブジェクト指向の解説でもそうですが、知識表現的な例題ばかりでは実際のプログラミングのイメージが掴めないかもしれません。 そこで、実際 (っぽい) プログラミングの例もいくつか紹介しましょう。
まず、最初はパズルを解くプログラムです。 以下のプログラムは有名なハノイの塔パズルの解答を表示します。
hanoi(1, From, To, _) :- write([From, to, To]), nl.
hanoi(N, From, To, Via) :-
N1 is N - 1, hanoi(N1, From, Via, To),
write([From, to, To]), nl,
hanoi(N1, Via, To, From).
?- hanoi(3,t1,t2,t3)最後の行は「3 枚の円盤をハノイの塔のルールに従って、t1 から t2 へ、t3 を経由して移動する手順」と質問しています。 システムは hanoi の述語定義を参照しながら解を推論して、その副作用として、移動手順が (出力を行う write 述語と改行する nl 述語によって) 表示されます。 write なんて思いっきり副作用のある述語を使っているので、ある意味 Prolog らしくないのですが、かえって実際の雰囲気を伝えるかもしれません。
Prolog の文法
Prolog の文法はシンプルです。 すべての基本はルールの定義になります。 ルールは
ヘッド :- ボディ.という形で定義されます。 これは「ボディが真ならばヘッドも真」というルールを定義したことになります。 ボディはコンマで区切った複数の項を含むことができ、その場合はボディの全ての項が真であるときはじめてヘッドが真になります。
また、事実は
ヘッド.となります。 上のソクラテスの例で言うと「死ぬ(X) :- 人間(X).」がルールで、「人間(ソクラテス).」が事実です。 事実は実はルールの一種で
人間(ソクラテス).は
人間(ソクラテス) :- true.の省略形です。 システムへの質問は
?- ヘッドという形で行います。
ヘッドもボディも
名前または
名前(引数,...)という形式をとります。 普通の言語における関数定義のようなものです。 Prolog に特徴的なのはヘッド (関数定義相当) にもボディ (関数呼出し相当) のどちらにも値も変数も置けるという点です。
Prolog の変数は大文字または「_」で始まる名前の識別子です。 変数にはなんでも格納することができます。 それ以外の識別子は「アトム1」と呼ばれます。 アトムは Ruby や Lisp のシンボルのようなものです。 同じ名前のアトムはいつも等しいと見なされます。 その他にも整数や文字列などのデータ型もあります。
再びソクラテスの例に返ると、
?- 死ぬ(ソクラテス).システムと尋ねると「死ぬ(ソクラテス)」に相当するヘッド部を探しますが、直接それは見つかりません。 が、変数を含む「死ぬ(X)」が見つかるのでそれにマッチします。 そこで変数Xにソクラテスを代入して (ほんとは束縛と呼ぶ)、推論を続けます。 ここで、「死ぬ(ソクラテス)」と「死ぬ(X)」マッチさせる行為を「ユニフィケーション」と呼び、Prolog の基本的な動作になります。
「死ぬ(X)」は「人間(X)」が真の時、真になります。 そこでまたユニフィケーションが発生し、「人間(ソクラテス)」という事実を探します。 するとその事実は定義されているので、めでたく最初の命題が真であることが分かりました。 今回は調べた命題全てが真になりましたが、偽になる命題があった場合、真となる命題を求めてユニフィケーションを繰り返します。 これを「バックトラック」と呼びます。 Ruby ユーザーであればバックトラックの働きは正規表現でなじみがあるかもしれませんね。
しかし、バックトラックがいつもありがたいとは限りません。 たとえば「鳥は飛ぶ」というルールがあったとしましょう。
飛ぶ(X) :- 鳥(X).
鳥(ツバメ).
?- 飛ぶ(ツバメ).
trueしかし、中には鳥であるのに飛ばない鳥がいます。 たとえばペンギンとか。 これを
鳥(ペンギン).
飛ぶ(ペンギン) :- false.とするだけでは不十分です。
?- 飛ぶ(ペンギン).と尋ねると「ペンギンは飛ばない」というルールにより、偽になりますが、そこでバックトラックが発生してしまい、「ペンギンは鳥、鳥は飛ぶ、ペンギンは飛ぶ」という三段論法により、システムは「true (ペンギンは飛ぶ)」という結論を出してしまいます。 これは嬉しくありません。 Prolog ではこのような場合のために、「カットオペレータ」というバックトラックを抑制する仕組みが用意されています。 カットオペレータを使うと「ペンギンは飛ばない」というルールは以下のようになります。
飛ぶ(ペンギン) :- !, false.「!」がカットオペレータです。 カットオペレータは「ここを通り過ぎたらバックトラックしない」という意味になります。 ですから、
?- 飛ぶ(ペンギン).という質問に対して、「飛ぶ(ペンギン) :- !, false」がマッチし、偽がカットオペレータを過ぎてから発生していますので、バックトラックが発生せず、全体が偽となります。
カットオペレータは一階述語論理という観点からは邪道なのだそうですが (よく知りませんが)、Prolog で制御構造を実現したり、効率化を行おうと思うとどうしても必要になる機能です。
Prolog の特異性
Prolog の特徴は良くも悪くもその実行モデルでしょう。 多くの「普通の言語」では、コンピュータの実行モデルをある程度反映して、計算したり変数に値を設定したりするのですが、Prolog の「計算」はあくまでも述語論理に基づいたユニフィケーションによって行われます。 もちろん、背後では CPU が動作しているのですが、実際の CPU の動作は完全に抽象化されていて、簡単にうかがい知ることはできません。
抽象化の壁により CPU の動作を考えなくてすむということは、逆に言うと現代の CPU 上で効率良く動作させることが難しいということでもあります。 他の言語では当たり前のように使われる高速化テクニックのほとんどは Prolog では使えません。
一方、Prolog の推論をベースにした計算は、並列計算と相性が良いことも知られています。 ユニフィケーションは実行順序に依存しないので、タスクスケジューリングの自由度が高いからです。 この性質を応用して「並列 Prolog」とでも呼ぶべき KL/1 のような派生言語を生んだりしています。
また、並列言語として名高い Erlang も、関数言語と呼ばれているものの、Prolog からも大きな影響を受けています。 たとえば、変数は大文字で始まり、小文字で始まるものはアトムである点や、パターンマッチによる一種のユニフィケーションなどは Prolog を髣髴とさせます。
まとめ
Prolog のように実行モデルの抽象度が高く、コストが見えない言語は Lisp や Haskell など他にも沢山ありますが、実行モデルの特異性から考えると Prolog は最先鋒でしょう。 従来の計算機モデルに縛られない「特異性」は、第五世代コンピュータなどで採用され、1980 年代頃にはもてはやされましたが、その後「普通のコンピュータ」の性能向上が著しく、論理型言語はすっかり忘れ去られてしまいました。 どのように実行されるかイメージされにくい論理型言語は人間の脳に優しくなかったのかもしれません。 しかし、リーク電流や熱密度などの物理的限界により今までの回路微細化戦略に陰りが見えてきた昨今、再び脚光を浴びることがあるのかもしれません。
あるいは、最近、Prolog の影響を受けたとされる Erlang が注目されている背景にはそのような事情があるのかもしれません。
Prolog に関する情報は以下のサイトなどから入手できます。
- Wikipedia (日本語版)2
- http://ja.wikipedia.org/wiki/Prolog
- Wikipedia (英語版)
- http://en.wikipedia.org/wiki/Prolog
- The GNU Prolog web site
- http://www.gprolog.org/
- SWI-Prolog’s Home
- http://www.swi-prolog.org/
著者について
まつもとゆきひろは自他ともに認める日本を代表する言語オタクです。
言語好きが昂じて自分の言語を設計してしまった大馬鹿者です。
が、オタクとかハッカーとか呼ばれる人種はみんな多かれ少なかれそんなものじゃないでしょうか。