Prolog

この章では埋め込み言語としてPrologを実装する方法を説明する． 第19章ではデータベースに対する複雑なクエリに答えるプログラムを書く方法を示した． ここでは新たに要素を一つ加える． 規則，すなわち既に知られている事実から別の事実を推論できるようにする仕組みだ． 規則の集合は含意のツリーを定義する． 無限個の事実を含意する規則を扱うには， その含意ツリーで非決定的な検索を行わなければならない．

Prologは埋め込み言語の素晴しい例になる． それはパターンマッチング，非決定性，規則の3要素を組み合わせたものだ． 第18，22章では最初の2つを独立に示した． 今すでに手にしているパターンマッチングと非決定的選択のためのオペレータの上に Prologを構築することで， 多層構造を持つ本物のボトムアップシステムの例が得られる． \reffig{fig:LayersOfAbstraction}には関係する抽象化の層を示した．

この章の第2の狙いはPrologそのものの学習だ． 経験豊かなプログラマにとってPrologの最も役立つ解説はその実装の概論だろう． LispでPrologを書くのは特に興味深い． 2つの言語の間の類似点が明らかになるからだ．

概念

第19章では変数を含む複雑なクエリを受け付け， クエリを真とするデータベース内の全ての束縛を生成するデータベースシステムを書く方法を示した． 以下の例では（clear-dbの呼び出し後）2つの事実を仮定し， その下でデータベースにクエリを発行する．

> (fact painter reynolds)
(REYNOLDS)
> (fact painter gainsborough)
(GAINSBOROUGH)
> (with-answer (painter ?x)
    (print ?x))
GAINSBOROUGH
REYNOLDS
NIL

概念的にはPrologは規則を追加したデータベースシステムだ． 規則により，データベース内を探すだけでなく， 他の既知の事実から推論することでクエリを成立させられる． 例えば次の規則を持っているとき （訳注：「腹を減らしていてテレピン油が臭う人は画家である」），

If (hungry ?x) and (smells-of ?x turpentine) Then (painter ?x)

データベースに(hungry raoul)と(smells-of raoul turpentine)が登録されていれば (painter raoul)が登録されていなくとも クエリ(painter ?x)は$?x = raoul$という束縛で成立する．

Prologでは規則のif節は本体と呼ばれ，then節は頭部と呼ばれる． （論理学では前提と帰結という言葉を使うが， Prologの推論は論理学的な含意とは違うことを強調するために ここで別の言葉を使うのはもっともなことだ．） クエリに対して束縛 \footnote{この意味での束縛を含む，この章で使われる概念の多くは，第18-4節で説明してある．} を作ろうとするとき，プログラムは先ず規則の頭部に注目する． プログラムの答えようとしているクエリに頭部がマッチしたとき， プログラムは規則の本体に対する束縛を生成しようとする． 定義により，本体を成立させる束縛は頭部も成立させる．

規則の本体内で使われる事実は別の規則から推論されたものであってよい．

If (gaunt ?x) or (eats-ravenously ?x) Then (hungry ?x)

そして規則は次のように再帰的であってもよい．

If (surname ?f ?n) and (father ?f ?c) Then (surname ?c ?n)

Prologは，規則の間に既知の事実に至る何らかの経路を見つけられるならば クエリに対して束縛を生成できる． よってPrologは本質的には検索機構だ． Prologは経路を求めて規則の形成する論理学的含意のツリーを探索する．

規則と事実は異なる種類のオブジェクトのように思えるが，概念的には交換して構わないものだ． 規則は実質的に事実とみなせる． 大型で獰猛な獣は珍しいという発見をデータベースに反映させたいときは， (species x), (big x), (fierce x)の成立する全てのxを探し， (rare x)を追加することもできるだろう． しかし，例えば次のような規則を定義することで同じ効果が得られ，

If (species ?x) and (big ?x) and (fierce ?x) Then (rare ?x)

実際に(rare x)を適当な全てのxについて追加する必要もない． 無限個の事実を含意する規則の定義すらできる． そのため，規則が使えれば，問いに答える時点での余分な処理と引き換えにデータベースは小さくなる．

一方，事実は規則の縮退した形式だ． 任意の事実Fは本体が常に真の規則と同じものだ．

If true Then F

実装を簡素にするため，この原則を利用して事実を本体のない規則として表現することにする．

インタプリタ

第18-4節ではif-matchの2通りの定義方法を示した． 最初のものは単純だが非効率的だ． 次に書いたものは処理の大部分をコンパイル時に行っていたので高速だった． ここでも似た戦略を取る． 関連するポイントの導入のため，単純なインタプリタから始める． その後で同じことを行うずっと効率的なプログラムの書き方を示す．

(defmacro with-inference (query &body body)
  `(progn
     (setq *paths* nil)
     (=bind (binds) (prove-query ',(rep_ query) nil)
            (let ,(mapcar #'(lambda (v)
                              `(,v (fullbind ',v binds)))
                          (vars-in query #'atom))
              ,@body
              (fail)))))

(defun rep_ (x)
  (if (atom x)
      (if (eq x '_) (gensym "?") x)
      (cons (rep_ (car x)) (rep_ (cdr x)))))

(defun fullbind (x b)
  (cond ((varsym? x) (aif2 (binding x b)
                           (fullbind it b)
                           (gensym)))
        ((atom x) x)
        (t (cons (fullbind (car x) b)
                 (fullbind (cdr x) b)))))

(defun varsym? (x)
  (and (symbolp x) (eq (char (symbol-name x) 0) #\?)))

\reffig{fig:ToplevelMacroProlog}から\reffig{fig:CodeInvolvingRules}には 単純なPrologインタプリタのコードを示した． 第19-3節のクエリ・インタプリタと同じクエリを受け付けるが， 束縛を生成するのにデータベースでなく規則を使う． クエリ・インタプリタはwith-answerというマクロから起動されるものだった． Prologインタプリタへのインタフェイスもwith-inferenceという名前の似たマクロを使うことになる． with-answer同様に，with-inferenceにはクエリと一連のLispの式を与える． クエリ内の変数はクエスチョンマークで始まるシンボルだ．

(with-inference (painter ?x)
  (print ?x))

with-inferenceの呼び出しは クエリの生成した束縛の集合それぞれについてLispの式を評価するコードに展開される． 例えば上の呼び出しは(painter x)を推論し得る全てのxを表示する．

\reffig{fig:ToplevelMacroProlog}にはwith-inferenceと それが束縛を取得するために呼び出す関数の定義を示した． with-answerとwith-inferenceとの注意すべき違いは， 前者が全てのあり得る束縛を単に集めていただけという点だ． with-inferenceは非決定的な検索を行う． それはwith-inferenceの定義に見られる． ループに展開されるのではなく， 束縛の集合から一つを返す部分に次に検索を再始動するためのfailを続けたコードに展開される． こうして次のように反復が暗黙のうちに行われる．

> (choose-bind x '(0 1 2 3 4 5 6 7 8 9)
    (princ x)
    (if (= x 6) x (fail)))
0123456
6

関数fullbindからはwith-answerとwith-inferenceとの違いがまた一つ分かる． 一連の規則を処理するうちに， 変数が他の変数のリストに束縛されているような束縛リストができ上がることもあり得る． クエリの結果を利用するには束縛を取得するための再帰関数が必要だ． それがfullbindの目的だ．

> (setq b '((?x . (?y . ?z)) (?y . foo) (?z . nil)))
((?X ?Y . ?Z) (?Y . FOO) (?Z))
> (values (binding '?x b))
(?Y . ?Z)
> (fullbind '?x b)
(FOO)

(=defun prove-query (expr binds)
  (case (car expr)
    (and (prove-and (cdr expr) binds))
    (or  (prove-or (cdr expr) binds))
    (not (prove-not (cadr expr) binds))
    (t   (prove-simple expr binds))))

(=defun prove-and (clauses binds)
  (if (null clauses)
      (=values binds)
      (=bind (binds) (prove-query (car clauses) binds)
             (prove-and (cdr clauses) binds))))

(=defun prove-or (clauses binds)
  (choose-bind c clauses
    (prove-query c binds)))

(=defun prove-not (expr binds)
  (let ((save-paths *paths*))
    (setq *paths* nil)
    (choose (=bind (b) (prove-query expr binds)
                   (setq *paths* save-paths)
                   (fail))
            (progn
              (setq *paths* save-paths)
              (=values binds)))))

(=defun prove-simple (query binds)
  (choose-bind r *rlist*
    (implies r query binds)))

クエリに対する束縛はwith-inferenceの展開形の中でprove-queryを呼ぶことで生成される． \reffig{fig:InterpretationOfQueries}にはprove-queryとそれが呼び出す関数の定義を示した． このコードは第19-3節で説明したクエリ・インタプリタと構造的に同型だ． どちらのプログラムもマッチングに同じ関数を使うが， クエリ・インタプリタでは写像や反復を使っていたところで， Prologインタプリタは等価なchooseを使っている．

反復でなく非決定的な検索を使ったことで否定を含むクエリの解釈はさらに複雑になった． 次のようなクエリが与えられたとき，

(not (painter ?x))

クエリ・インタプリタでは(painter ?x)に対して束縛の生成を試みた後， 一つでも生成されたらnilを返せばよかった． 非決定的な検索ではさらに注意を払わなければならない． (painter ?x)の解釈でnotのスコープ外にまでバックトラックされては困るし， 後で探索を再始動するための経路を保存してもらっても困る． よって(painter ?x)を解釈するときは状態を保存するリストには一時的な空リストを使い， 解釈終了後に古いリストを復元することにする．

Prologインタプリタとクエリ・インタプリタでは， 単純なパターン ---(painter ?x)等，述語と引数のみから成る式--- の解釈にも違いがある． クエリ・インタプリタが単純なパターンに対して束縛を生成するときは， lookup（kgaページ）を呼んでいた． ここではlookupを呼ぶのではなく，規則の含意する任意の束縛を得る必要がある．

(defvar *rlist* nil)

(defmacro <- (con &rest ant)
  (let ((ant (if (= (length ant) 1)
                 (car ant)
                 `(and ,@ant))))
    `(length (conc1f *rlist* (rep_ (cons ',ant ',con))))))

(=defun implies (r query binds)
  (let ((r2 (change-vars r)))
    (aif2 (match query (cdr r2) binds)
          (prove-query (car r2) it)
          (fail))))

(defun change-vars (r)
  (sublis (mapcar #'(lambda (v)
                      (cons v (symb '? (gensym))))
                  (vars-in r #'atom))
          r))

規則を定義し，使うためのコードは\reffig{fig:CodeInvolvingRules}に示した． 規則はグローバルなリスト*rlist*に保持される． 規則は本体と頭部のドット対として表現される． 規則が定義された時点で全ての下線（アンダースコア，_）は一意な変数に置き換えられる．

<-の定義はこの種のプログラムでしばしば見られる3つの慣習に従っている．

1. 新しい規則はリストの先頭ではなく末尾に追加され， 定義された順に適用されるようになっている．
2. 規則は頭部を先として表現される． プログラムが規則を扱う順がそうなっているからだ．
3. 本体内に複数の式を入れると暗黙のandで括られる．

<-の展開形内の一番外側にあるlengthは <-がトップレベルから呼ばれたときに巨大なリストの表示を避けるためだけのものだ．

規則の構文は\reffig{fig:SyntaxOfRules}に示した． 規則の頭部は事実に対するパターン，すなわち述語の後に0個以上の引数を続けたリストでなければならない． 本体には第19章のクエリ・インタプリタの扱える任意のクエリが使える． 次のものはこの章の始めの方で示した規則だ．

(<- (painter ?x) (and (hungry ?x)
                      (smells-of ?x turpentine)))

もしくは単に次のように書ける．

(<- (painter ?x) (hungry ?x)
                 (smells-of ?x turpentine))

クエリ・インタプリタと同様， turpentine等の引数は評価されないので引用符を付ける必要がない．

prove-simpleがクエリに対して束縛を生成するとき， 規則に対し非決定的なchooseを適用し，規則とクエリの両方をimpliesに送る． すると関数impliesはクエリと規則の頭部とのマッチを試みる． マッチが成功するとimpliesはprove-queryを呼んで本体に対する束縛を生成する． こうして含意のツリーを再帰的に探索できる．

関数change-varsは規則内の変数を全て新しいものに置き換える． ある規則内で使われている変数?xは別の規則内の?xとは別のものである筈だ． 既存の束縛との衝突を避けるため，規則が使われる度にchange-varsが呼ばれる．

簡便のため，規則内で_（下線）をワイルドカード変数として使える． 規則が定義されたとき，関数repが呼ばれて各々の下線を本物の変数に置き換える． 下線はwith-inferenceに与えるクエリでも使える．

規則

この節では埋め込みPrologのための規則の書き方を示す． 第24-1節の2つの規則から始めよう．

(<- (painter ?x) (hungry ?x)
                 (smells-of ?x turpentine))

(<- (hungry ?x) (or (gaunt ?x) (eats-ravenously ?x)))

次の事実を仮定すれば，

(<- (gaunt raoul))
(<- (smells-of raoul turpentine))
(<- (painter rubens))

規則の生成する束縛が，定義された順に得られる．

> (with-inference (painter ?x)
    (print ?x))
RAOUL
RUBENS
@

マクロwith-inferenceは変数束縛についてwith-answerと全く同じ制限を持つ． （第19-4節を参照）

任意の形の事実が全ての可能な束縛について真となることを含意する規則が書ける． これは例えば何らかの変数が規則の頭部内で使われているが 本体内では使われていないときだ． 次の規則は，?xが暴食家ならば?xは何でも食べることを示す．

(<- (eats ?x ?f) (glutton ?x))

?fは本体内では使われていないので， (eats ?x y)という形の任意の事実が，?xについて束縛を生成するだけで示せる． eatsへの第2引数にリテラル値を与えてクエリを発行すると，

> (<- (glutton hubert))
7
> (with-inference (eats ?x spinach)
    (print ?x))
HUBERT
@

任意のリテラル値が使える． 第2引数に変数を与えると，

> (with-inference (eats ?x ?y)
    (print (list ?x ?y)))
(HUBERT #:G229)
@

gensymが帰って来る． クエリ内の変数の束縛としてgensymを返すのは，任意の値をそこに持ってきても真となることを示している． この規約を明示的に活用してプログラムを書ける．

> (progn
    (<- (eats monster bad-children))
    (<- (eats warhol candy)))
9
> (with-inference (eats ?x ?y)
    (format t "~A eats ~A.~%"
            ?x
            (if (gensym? ?y) 'everything ?y)))
HUBERT eats EVERYTHING.
MONSTER eats BAD-CHILDREN.
WARHOL eats CANDY.
@

最後にある形の事実が任意の引数について真だと指定したいときは， 本体を引数なしの接続詞とすればよい． 式(and)は常に真となる事実の役割を果たす． マクロ<-（\reffig{fig:CodeInvolvingRules}）では 本体が与えられなかったときに(and)が使われる． よって常に真となる規則では本体が省ける．

> (<- (identical ?x ?x))
10
> (with-inference (identical a ?x)
    (print ?x))
A
@

append([ ], Xs, Xs).
append([X | Xs], Ys, [X | Zs]) <- append(Xs, Ys, Zs).

(<- (append nil ?xs ?xs))
(<- (append (?x . ?xs) ?ys (?x . ?zs))
    (append ?xs ?ys ?zs))

Prologの知識をお持ちの方のために， \reffig{fig:PrologSyntaxEquivalence}には Prolog文法からLispによるPrologインタプリタへの翻訳方法を示した． 伝統的なPrologプログラムとしては先ずappendが挙げられるが， \reffig{fig:PrologSyntaxEquivalence}の最後に示したようになる． appendの使って2つの短いリストをつなげて1つの長いリストを作れる． これらのリストのうちどの2つを定めても残りの1つのリストがどうなるべきかが定まる． Lispの関数appendは2つの短いリストを引数に取ってつなげた長いリストを返すが， Prologのappendはより一般性が高い． \reffig{fig:PrologSyntaxEquivalence}の2つの規則は， 関連するどの2つのリストが与えられても3つ目を得られるプログラムを定義する．

> (with-inference (append ?x (c d) (a b c d))
    (format t "Left: ~A~%" ?x))
Left: (A B)
@
> (with-inference (append (a b) ?x (a b c d))
    (format t "Right: ~A~%" ?x))
Right: (C D)
@
> (with-inference (append (a b) (c d) ?x)
    (format t "Whole: ~A~%" ?x))
Whole: (A B C D)
@

それだけでなく，最後のリストを与えられただけでも， 1番目と2番目のリストの可能性を全て見つけることができる．

> (with-inference (append ?x ?y (a b c))
    (format t "Left: ~A Right: ~A~%" ?x ?y))
Left: NIL Right: (A B C)
Left: (A) Right: (B C)
Left: (A B) Right: (C)
Left: (A B C) Right: NIL
@

appendの振舞いはPrologと他のプログラミング言語との大きな違いを示している． Prologの規則の集合は必ずしも確定した値を持たなくともよく， プログラムの他の部分の定める制約と組み合わせたときになって 特定の値を定めるような制約を持つことができる． 例えばmemberを次のように定義すると，

(<- (member ?x (?x . ?rest)))
(<- (member ?x (_ . ?rest)) (member ?x ?rest))

Lispの関数memberと同じように，リストへの要素の所属を調べるのに使える．

> (with-inference (member a (a b)) (print t))
T
@

しかしそれは所属という制約を定めるためにも使える． その制約は他の制約と組み合わさったときに特定のリストを定める． さらに car部がaであるような2要素のリスト全てに真を返す述語caraを定めると，

(<- (cara (a _)))

これとmemberによってPrologは十分に確定した答えを導き出せる．

> (with-inference (and (cara ?lst) (member b ?lst))
    (print ?lst))
(A B)
@

これはかなり自明な例だが，複雑な問題も同じ原則の下に立って構築できる． 部分解を組み合わせてプログラミングを行いたいときにはPrologは役立つかもしれない． 実際，驚く程多様な問題がその方式で表現できる． 例えば\reffig{fig:Quicksort}には 解についての制約の集積として表現されたソートアルゴリズムを示した．

非決定性の必要性

第22章では決定的な検索と非決定的な検索との関係について説明した． 決定的な検索プログラムはクエリを受け取ってそれを満たす解を全て生成することになる． 非決定的検索プログラムはchooseを使って解を1つずつ生成し， 他の解が必要とあらばfailを呼んで検索を再開する．

手にしている規則の生成する束縛がいずれも有限個で，それら全てを一度に知りたいとき， 非決定的検索を選ぶ理由はどこにもない． 2つの戦略の違いは無限個の束縛を生成するクエリを前にすると明らかになる． その束縛の中から有限個の部分集合を得たいのだ． 例えば次の規則は，

(<- (all-elements ?x nil))
(<- (all-elements ?x (?x . ?rest))
        (all-elements ?x ?rest))

(all-elements x y)という形を持つあらゆる事実を含意する． ここでyのメンバはいずれもxとequalだ． バックトラックなしではクエリを次のように扱うことになるだろう．

(all-elements a (a a a))
(all-elements a (a a b))
(all-elements ?x (a a a))

しかしクエリ(all-elements a ?x)を満たす?xには無限個の候補がある． nil，(a)，(a a)等だ． このクエリに対し反復を使って解を生成しようとするとその反復はいつまでも終了しない． そのうち一つが欲しいだけであっても， Lispの式の処理を開始する前にクエリに対し全ての束縛を生成する必要のある実装では 結果はいつまでも得られない．

この理由からwith-inferenceでは束縛の生成を本体の評価と交互に行っている． クエリが無限個の解を持つ場合には， 解を一つずつ生成し，中断した検索を再始動させて次の解を得る手立てしかない． 埋め込みPrologではchooseとfailを使っているため，次のような場合も扱える．

> (block nil
    (with-inference (all-elements a ?x)
      (if (= (length ?x) 3)
          (return ?x)
          (princ ?x))))
NIL
(A)
(A A)
(A A A)

他のPrologの実装と同様， 埋め込みPrologでは非決定性をシミュレートするのにバックトラックを伴う深さ優先探索を行っている． 理論的には「論理プログラミング」は本物の非決定性の下で動作する． 実際にはPrologの実装は必ず深さ優先探索を使う． その選択を行ったことで困るのとは正反対で，典型的なPrologプログラムはそれに依存している． 真に非決定的な世界では次のクエリは解を持つが，

(and (all-elements a ?x) (length ?x 3))

その解が何かを知るには任意の長さの時間がかかる．

Prologは深さ優先の非決定性の実装を使っているだけでなく， zxiページで定義した版と同じものを使っている． そこで説明したように，その実装では必ず終了することが保証されていない． よってPrologプログラマは探索空間でのループを慎重に避けなければならない． 例えばmemberを逆の順で定義していたら，

(<- (member ?x (_ . ?rest)) (member ?x ?rest))
(<- (member ?x (?x . ?rest)))

論理的には同じ意味を持つはずだが，Prologプログラムとしては異なるものになる． memberの元の定義では クエリ(member 'a ?x)に対して解の無限のストリームを生成することになるが， 逆にした定義では無限の再帰が起き，解は一つも得られない．

新しい実装

この節では親しみのあるパターンがまた出てくる． 第18-4節では， プロトタイプを書いた後にif-matchをずっと速くする方法に気付いた． コンパイル時に分かっている情報を活用することで， 実行時に行う処理の少ない新しいヴァージョンに書き改めることができた． 第19章では同じ現象が大規模になって出てきた． クエリ・インタプリタが等価だが速度の速いものに置き換えられた． ここではPrologインタプリタでも同じことをやろうというのだ．

第\ref{fig:NewToplevelMacro}，\ref{fig:CompilationOfQueries}， \ref{fig:CodeForDefiningRules}図ではPrologを別のやり方で定義している． マクロwith-inferenceはPrologインタプリタへの単なるインタフェイスだったが， ここではプログラムの大部分を占める． 新しいPrologインタプリタは概形では古いものと変わらないが， \reffig{fig:CompilationOfQueries}で定義された関数のうち， 実行時に呼ばれるのはproveのみだ． 他の関数はwith-inferenceがその展開形を作るために呼ぶためのものだ．

(defmacro with-inference (query &rest body)
  (let ((vars (vars-in query #'simple?)) (gb (gensym)))
    `(with-gensyms ,vars
       (setq *paths* nil)
       (=bind (,gb) ,(gen-query (rep_ query))
         (let ,(mapcar #'(lambda (v)
                           `(,v (fullbind ,v ,gb)))
                       vars)
           ,@body)
         (fail)))))

(defun varsym? (x)
  (and (symbolp x) (not (symbol-package x))))

\reffig{fig:NewToplevelMacro}にはwith-inferenceの新しい定義を示した． if-matchやwith-answerと同様， パターン変数は最初はgensymに束縛されており， マッチングによって本当の値が与えられる前ということを示している． よってmatchとfullbindが変数を判別するために呼ぶ関数varsym?は， gensymを探すよう変更しなければならない．

(defun gen-query (expr &optional binds)
  (case (car expr)
    (and (gen-and (cdr expr) binds))
    (or  (gen-or (cdr expr) binds))
    (not (gen-not (cadr expr) binds))
    (t   `(prove (list ',(car expr)
                       ,@(mapcar #'form (cdr expr)))
                 ,binds))))

(defun gen-and (clauses binds)
  (if (null clauses)
      `(=values ,binds)
      (let ((gb (gensym)))
        `(=bind (,gb) ,(gen-query (car clauses) binds)
           ,(gen-and (cdr clauses) gb)))))

(defun gen-or (clauses binds)
  `(choose
     ,@(mapcar #'(lambda (c) (gen-query c binds))
               clauses)))

(defun gen-not (expr binds)
  (let ((gpaths (gensym)))
    `(let ((,gpaths *paths*))
       (setq *paths* nil)
       (choose (=bind (b) ,(gen-query expr binds)
                      (setq *paths* ,gpaths)
                      (fail))
               (progn
                 (setq *paths* ,gpaths)
                 (=values ,binds))))))

(=defun prove (query binds)
        (choose-bind r *rules* (=funcall r query binds)))

(defun form (pat)
  (if (simple? pat)
      pat
      `(cons ,(form (car pat)) ,(form (cdr pat)))))

クエリに対する束縛を定めるコードを生成するため， with-inferenceはgen-query（\reffig{fig:CompilationOfQueries}）を呼ぶ． gen-queryが先ず行う処理は，第1引数を見て， それがandやor等のオペレータで始まる複雑なクエリかどうか調べることだ． この処理は単純なクエリに到達するまで再帰的に続き，単純なクエリはproveの呼び出しに展開される． 最初の実装ではそういった論理的構造は実行時に分析されていた． 規則の本体内に使われた複雑な式は，その規則が使われる度に改めて分析する必要があった． 規則とクエリの論理的構造は予め分かっているのだから，これは無駄が多い． 新しい実装では複雑な式をコンパイル時に分解する．

最初の実装と同様に， with-inferenceの呼び出しは， パターン変数を規則の定めた値にそれぞれ束縛して， クエリに伴うLispコードを反復実行するコードに展開される． with-inferenceの展開形はfailで終わっており， 任意の保存された状態が再始動される．

(with-inference (and (big ?x) (red ?x))
  (print ?x))

(with-gensyms (?x)
  (setq *paths* nil)
  (=bind (\#:g1) (=bind (\#:g2) (prove (list 'big ?x) nil)
                       (=bind (\#:g3) (prove (list 'red ?x) \#:g2)
                              (=values \#:g3)))
         (let ((?x (fullbind ?x \#:g1)))
           (print ?x))
         (fail)))

\reffig{fig:compilationofqueries}の残りの関数は複雑なクエリ ---and，orやnotで結合されたもの--- の展開形を生成する． 次のようなクエリがあったとき，

(and (big ?x) (red ?x))

2つの条件が共に満たされるような?xについてのみlispコードを評価したい． よってandを使った式の展開形を生成するには， 第2の条件の展開形を第1の中に入れ子にする． (big ?x)が真のときに(red ?x)を調べ，それも真だったらlispの式を評価する． よって展開形の全体は\reffig{fig:ExpansionOfConjunction}のようになる．

andでは入れ子を使い，orではchooseを使う． 次のようなクエリがあったときは，

(or (big ?x) (red ?x))

どちらかの部分クエリが定めた?xの値に対してLispの式を評価したい． 関数gen-orはそれぞれgen-queryを適用した引数に対してのchooseに展開される． notについては， gen-notはprove-not（\reffig{fig:InterpretationOfQueries}）とほぼ同じだ．

(defvar *rules* nil)

(defmacro <- (con &rest ant)
  (let ((ant (if (= (length ant) 1)
                 (car ant)
                 `(and ,@ant))))
    `(length (conc1f *rules*
                     ,(rule-fn (rep_ ant) (rep_ con))))))

(defun rule-fn (ant con)
  (with-gensyms (val win fact binds)
    `(=lambda (,fact ,binds)
       (with-gensyms ,(vars-in (list ant con) \#'simple?)
         (multiple-value-bind
           (,val ,win)
           (match ,fact
                  (list ',(car con)
                        ,@(mapcar \#'form (cdr con)))
                  ,binds)
           (if ,win
               ,(gen-query ant val)
               (fail)))))))

\reffig{fig:CodeForDefiningRules}には規則を定義するためのコードを示した． 規則はrule-fnの生成するLispコードに直接変換される． <-が規則をLispコードへと展開するようになったので， 規則の定義を並べたファイルのコンパイルは規則をコンパイル済み関数に変える働きを持つ．

rule-functionにパターンを与えると， そのパターンをそれが表現するルールの頭部に対してマッチさせようとする． マッチが成功するとrule-functionは本体に対する束縛を生成しようとする． この処理は本質的にwith-inferenceと同じで， 実際，rule-fnは最後にgen-queryを呼んでいる． 結局rule-functionは規則の頭部内で使われている変数に対する束縛を返す．

Prologの機能の追加

ここまでに提示したコードで大抵の「純粋な」Prologプログラムが実行できる． 最後にカット，算術演算，I/O等を追加する．

Prologの規則にカットを加えると検索木の枝刈りがなされる． 普通，プログラムがfailに出会うと， 最後に通ったchoiceの地点までバックトラックする． 第22-4章のchooseの実装は非決定的選択を行った場所を グローバル変数*paths*に保持していた． failを呼ぶと検索は一番近くの選択場所で再始動するが， その場所は*paths*のcar部に保持されている． カットのせいでさらに複雑になる． プログラムがカットに出会うと， *paths*に保持されていた選択場所のうち近いものを幾つか ---詳しく言えば最後にproveが呼ばれた以降のものを--- 捨てる．

カットの効果は規則を互いに排他的にすることだ． カットを使ってPrologプログラムでcase文の機能が実現できる． 例えばminimumを次のように実装すると，

(<- (minimum ?x ?y ?x) (lisp (<= ?x ?y)))
(<- (minimum ?x ?y ?y) (lisp (> ?x ?y)))

間違った動作はしないが効率が悪い． 次のようなクエリに対し，

(minimum 1 2 ?x)

Prologは1番目の規則から即座に$?x = 1$を定める． 人間はそこで終了とするが， プログラムは第2の規則からさらに解を得ようと時間を浪費する． それは2つの規則が互いに排他的だと知らされていないからだ． 平均的に上の実装のminimumは50%だけ余分な処理を行う． この問題は1番目の規則の後にカットを付けることで解決する．

(<- (minimum ?x ?y ?x) (lisp (<= ?x ?y)) (cut))
(<- (minimum ?x ?y ?y))

するとPrologが1番目の規則の処理を終えたとき， 次の規則を調べる前に処理がここから抜けてクエリまで移る．

埋め込みPrologを修正してカットを扱えるようにするのはとても容易だ． proveを呼ぶ毎に，その時点での*paths*を引数として渡すようにする． プログラムがカットに出会ったときは， *paths*を引数で渡された古い値に設定すればよい． 第\ref{fig:AddingSupportForNewOperators}，\ref{fig:AddingSupportForNewOperators2}図のコードは カットへの対応のために修正したものだ． （変更のあった行は目印のセミコロンを付けた． 全ての変更がカット対応のせいではない．）

単にプログラムの効率を上げるだけのカットはgreen cutと呼ばれる． 最も基本的なカットはgreen cutだった． プログラムの動作を変えるカットはred cutと呼ばれる． 例えば，述語artistを次のように定義したとしよう．

(<- (artist ?x) (sculptor ?x) (cut))
(<- (artist ?x) (painter ?x))

こうすると，彫刻家がいれば，クエリはそこで終了するようになる． 彫刻家がいないときは，画家が芸術家とみなされる．

> (progn (<- (painter 'klee))
         (<- (painter 'soutine)))
4
>(with-inference (artist ?x)
     (print ?x))
KLEE
SOUTINE
@

しかし彫刻家がいるときは，カットは1番目の規則のみで推論を止める．

> (<- (sculptor 'hepworth))
5
> (with-inference (artist ?x)
    (print ?x))
HEPWORTH
@

(defun rule-fn (ant con)
  (with-gensyms (val win fact binds paths)                   ;
    `(=lambda (,fact ,binds ,paths)                          ;
       (with-gensyms ,(vars-in (list ant con) #'simple?)
         (multiple-value-bind
           (,val ,win)
           (match ,fact
                  (list ',(car con)
                        ,@(mapcar #'form (cdr con)))
                  ,binds)
           (if ,win
               ,(gen-query ant val paths)                    ;
               (fail)))))))

(defmacro with-inference (query &rest body)
  (let ((vars (vars-in query #'simple?)) (gb (gensym)))
    `(with-gensyms ,vars
       (setq *paths* nil)
       (=bind (,gb) ,(gen-query (rep_ query) nil '*paths*)   ;
              (let ,(mapcar #'(lambda (v)
                                `(,v (fullbind ,v ,gb)))
                            vars)
                ,@body)
              (fail)))))

(defun gen-query (expr binds paths)                          ;
  (case (car expr)
    (and  (gen-and (cdr expr) binds paths))                  ;
    (or   (gen-or (cdr expr) binds paths))                   ;
    (not  (gen-not (cadr expr) binds paths))                 ;
    (lisp (gen-lisp (cadr expr) binds))                      ;
    (is   (gen-is (cadr expr) (third expr) binds))           ;
    (cut  `(progn (setq *paths* ,paths)                      ;
                  (=values ,binds)))                         ;
    (t    `(prove (list ',(car expr)
                        ,@(mapcar #'form (cdr expr)))
                  ,binds *paths*))))                         ;

(=defun prove (query binds paths)                            ;
  (choose-bind r *rules*
               (=funcall r query binds paths)))              ;

(defun gen-and (clauses binds paths)                           ;
  (if (null clauses)
      `(=values ,binds)
      (let ((gb (gensym)))
        `(=bind (,gb) ,(gen-query (car clauses) binds paths)   ;
           ,(gen-and (cdr clauses) gb paths)))))               ;

(defun gen-or (clauses binds paths)                            ;
  `(choose
     ,@(mapcar #'(lambda (c) (gen-query c binds paths))        ;
               clauses)))

(defun gen-not (expr binds paths)                              ;
  (let ((gpaths (gensym)))
    `(let ((,gpaths *paths*))
       (setq *paths* nil)
       (choose (=bind (b) ,(gen-query expr binds paths)        ;
                 (setq *paths* ,gpaths)
                 (fail))
               (progn
                 (setq *paths* ,gpaths)
                 (=values ,binds))))))

(defmacro with-binds (binds expr)
  `(let ,(mapcar #'(lambda (v) `(,v (fullbind ,v ,binds)))
                 (vars-in expr))
     ,expr))

(defun gen-lisp (expr binds)
  `(if (with-binds ,binds ,expr)
       (=values ,binds)
       (fail)))

(defun gen-is (expr1 expr2 binds)
  `(aif2 (match ,expr1 (with-binds ,binds ,expr2) ,binds)
         (=values it)
         (fail)))

カットはPrologのオペレータfailと組み合わせて使われることがある． 埋め込みPrologではfailが同じ機能を担う． カットを規則に埋め込むと，規則が一方通行になる． そこに入り込んだ時点で，その規則のみを使うと決めたことになるのだ． 規則にcut-failの組を使うのは治安の悪い街の一方通行の路地のようなものだ． そこに入り込んだ時点で，何も得ずに出て行くと決めたことになる． 典型的な例がnot-equalの実装の中に見られる．

(<- (not-equal ?x ?x) (cut) (fail))
(<- (not-equal ?x ?y))

ここで最初の規則は嫌な入力に対する罠だ． (not-equal 1 1)という形の事実を示そうとしたとき， それは最初の規則の頭部にマッチし，はいそれまで，となる． それに対し，クエリ(not-equal 1 2)は最初の規則の頭部にマッチせず， 2番目の規則に進み，そこでマッチが成功する．

> (with-inference (not-equal 'a 'a)
    (print t))
@
> (with-inference (not-equal '(a a) '(a b))
    (print t))
T
@

第\ref{fig:AddingSupportForNewOperators}，\ref{fig:AddingSupportForNewOperators2}図のコードでは 算術演算，I/O，Prologのオペレータisの実装も行っている． \reffig{fig:NewSyntaxOfRules}には規則とクエリの完全な構文を示した．

Lispへの抜け道を作ることで算術演算（を含むあれこれ）が追加された． andやor等のオペレータに加え，オペレータlispを作った． この中では任意のLispの式を使うことができる． Lispの式は中の変数がクエリの生成した束縛に束縛された状態で評価される． Lispの式の評価結果がnilのときは， オペレータlispの呼び出し全体が(fail)と等価になる． そうでなければ(and)と等価になる．

オペレータlispの利用例として， 要素が昇順に並んでいるリストに対して成立するorderedのPrologによる定義を考えよう．

(<- (ordered (?x)))
(<- (ordered (?x ?y . ?ys))
    (lisp (<= ?x ?y))
    (ordered (?y . ?ys)))

日本語で言うと，1要素のリストは整列されており， 2要素以上のリストが整列されているというのは，先頭要素が第2要素以下で， 先頭要素を除いたリストが整列されているときだ．

> (with-inference (ordered '(1 2 3))
    (print t))
T
@
> (with-inference (ordered '(1 3 2))
    (print t))
@

Lispのオペレータを使うことで典型的なPrologの実装が提供する他の機能も提供できる． PrologのI/O用述語はLispのI/OオペレータをLispの式の中で呼び出すことで代替できる． Prologのassertは副作用として新たな規則を定義するが， マクロ<-をLispの式の中で呼び出すことで代替できる．

オペレータisは一種の代入を提供する． パターンとLispの式の2つを引数に取り，パターンを式の返り値に対しマッチさせようとする． マッチに失敗すると，プログラムはfailを呼び出す． 成功すれば新たな束縛の元で処理が進む． よって式(is ?x 1)は?xを1に設定する効果がある． 正確に言えば，?xは1だとの事実を主張している． 例えば階乗の計算でisが必要になる．

(<- (factorial 0 1))
(<- (factorial ?n ?f)
    (lisp (> ?n 0))
    (is ?n1 (- ?n 1))
    (factorial ?n1 ?f1)
    (is ?f (* ?n ?f1)))

この定義を使うには第1引数が数nで第2引数が変数のクエリを与える．

> (with-inference (factorial 8 ?x)
    (print ?x))
40320
@

オペレータlispやisの第2引数の中で使われる変数は 値を返す式への束縛をすでに生成している必要がある． この制限は実際のどのProlog実装でも存在する． 例えば次のクエリは，

(with-inference (factorial ?x 120)                  ; wrong
  (print ?x))

上のようなfactorialの定義では機能しない． オペレータlispの呼び出しが評価されるときには?nが未知だからだ． だから全てのPrologプログラムがappendのような性格を持つ訳ではない． factorialのように，引数の幾つかが実際の値であることを要求するものもある．

例

(setq *rules* nil)

(<- (append nil ?ys ?ys))
(<- (append (?x . ?xs) ?ys (?x . ?zs))
    (append ?xs ?ys ?zs))

(<- (quicksort (?x . ?xs) ?ys)
    (partition ?xs ?x ?littles ?bigs)
    (quicksort ?littles ?ls)
    (quicksort ?bigs ?bs)
    (append ?ls (?x . ?bs) ?ys))
(<- (quicksort nil nil))

(<- (partition (?x . ?xs) ?y (?x . ?ls) ?bs)
    (lisp (<= ?x ?y))
    (partition ?xs ?y ?ls ?bs))
(<- (partition (?x . ?xs) ?y ?ls (?x . ?bs))
    (lisp (> ?x ?y))
    (partition ?xs ?y ?ls ?bs))
(<- (partition nil ?y nil nil))

この節では埋め込みPrologでのPrologプログラムの書き方を示す． \reffig{fig:Quicksort}の規則はクイックソートを定義している． それらの規則は(quicksort x y)という形の事実を含意する． ここでxはリスト，yは同じ要素が昇順にソートされたリストだ． 第2引数に変数を使える．

> (with-inference (quicksort '(3 2 1) ?x)
    (print ?x))
(1 2 3)
@

(<- (echo)
    (is ?x (read))
    (echo ?x))
(<- (echo 'done)
    (cut))
(<- (echo ?x)
    (lisp (prog1 t (format t "~A~%" ?x)))
    (is ?y (read))
    (cut)
    (echo ?y))

I/Oループは埋め込みPrologのテストになっている． オペレータcut，lisp，isを利用しているからだ． ソースは\reffig{fig:AnIOLoopInProlog}に示した． それらの規則はクエリ(echo)を引数なしで示そうとすることで呼び出される． そのクエリが1番目の規則にマッチし，?xがreadの返り値に束縛され， 次にクエリ(echo ?x)を示そうとする． この新しいクエリは2，3番目のどちらのクエリにもマッチし得る． ?x = doneのときは，クエリは2番目の規則で終了する． そうでなければクエリは3番目の規則にしかマッチしないが， そちらは読み込まれた値を印字し，同じ過程を再び繰り返す．

これらが合わさると，doneと入力するまで入力を印字し続けるプログラムが定義される．

> (with-inference (echo))
hi
HI
ho
HO
done
@

このようなプログラムはPrologの抽象モデルに対し逆行しているので読み辛い． echoの理解は，Lispによる内部表現を見た方が分かり易いかもしれない．

(defun echo (&rest args)
  (cond ((null args) (echo (read)))
         ((eq (car args) 'done) nil)
         (t (format t "~A~%" (car args))
            (echo (read)))))

これはCommon Lispでは普通は次のように書くものだ．

(defun echo (&optional (arg (read)))
  (unless (eq arg 'done)
    (format t "~A~%" arg)
    (echo)))

コンパイルという言葉の意味

「コンパイル」という言葉には幾つかの意味がある． 最も広い意味では， コンパイルとはプログラムの何らかの抽象的な記述を低レベルのコードに変換することだ． この章で記述されたプログラムはこの意味で確かにコンパイラだ． 規則をLispの関数に変換するからだ．

狭い意味では，コンパイルとはプログラムをマシン語に変換することだ． 優れたCommon Lispの実装は関数をネイティブなマシン語にコンパイルする． gxzページで触れたように，クロージャを生成するコードがコンパイルされると， コンパイル済みクロージャが得られる． よってここまでに説明したプログラムは狭い意味でもコンパイラだ． 優れたLispの実装では埋め込みPrologはマシン語に変換されるのだ．

しかしここまでに説明したプログラムはまだPrologコンパイラとは呼べない． プログラミング言語については「コンパイル」という言葉にさらに狭い意味がある． 単にマシン語を生成するだけではその意味での定義を満たすには不足だ． あるプログラミング言語のコンパイラは変換と同様に最適化を行わなければならない． 例えばLispコンパイラが次のような式をコンパイルするとき，

(+ x (+ 2 5))

(+ 2 5)を評価するのに実行時まで待つ理由などないが， コンパイラにはそれを実現できる賢さが要求される． プログラムはそれを7に置換する最適化を施され，次のようにコンパイルされることになる．

(+ x 7)

この章の埋め込みPrologでは全てのコンパイルはLispコンパイラによって行われた． そしてLispコンパイラはPrologではなくLispのための最適化を狙っている． Lispコンパイラの行う最適化に誤りはないが，低レベル過ぎる． Lispコンパイラにはコンパイルしているコードが規則を表現するものだとは分からない． 本物のPrologコンパイラはループに変換できる規則を探すが， この章のPrologは定数を与える式やスタックに割り当てられるクロージャを探している．

埋め込み言語によって抽象化を最高に活用できるが，それは魔法ではない． 非常に抽象的な表現から高速なマシン語に至る道のりを歩き通したいならば， やはり誰かがコンピュータに方法を教えなければならない． この章では道のりのかなりの部分を驚く程少ないコードで進んで来たが， それは本物のPrologコンパイラを書くこととは違うのだ．

←： ATNを使ったパージング     ↑： On Lisp     →： オブジェクト指向Lisp