付録 P

Prolog 超簡易入門と呼ばれるプログラミング言語の仲間のうち、もっとProlog は、も代表的なものである。論理型言語では、「〜ならば〜」という論理式の集まりをプログラムとみなし、論理式の証明をプログラムの実行とみなす。
Prolog などの論理型言語に特徴的な概念としては、（単一化）、（後戻り）、などが挙げられる。

P.1 Prolog でのプログラミング
Prolog では「〜ならば〜」という論理式の集まりをプログラムとみなすが、この「〜」の部分を構成するのが、次のような形式である。
述語 (項 1 , . . . , 項 n )1 と呼ぶ。
「項」は数・文字列などの定数や変数、あるい
このかたちをはリストなどのデータ構造などである。「述語」は直観的には項 1 , . . . , 項 n の間の関係を表す。例えば、father(adam, cain) という素論理式は「Adam は Cainの父である」という関係を表す。
Prolog のプログラムは、（Horn clause）と呼ばれる形式の集まりである。ホーン節とは、素論理式 0 :-素論理式 1 , . . . , 素論理式 n .という形である。（最後に必ずピリオド（.）が必要である。）:-は左向きの矢印（←）と考えれば良い。つまり、これは素論理式 1 , . . . , 素論理式 n がすべて成り立つならば、素論理式 0 も成り立つという規則を表している。
ホーン節の:-の左側には素論理式は一つのみであり、これを（head）と呼ぶ、:-の右側の素論理式の並びは例えば、（body）と呼ぶ。

grandchild(X, Z) :- child(X, Y), child(Y, Z).
は、X と Y, Y と Z の間に child という関係がある（X が Y の子であり、Y が Z の子である）ならば、X と Z の間に grandchild という関係がある（X は Z の孫である）という規則を述べている。ここで X, Y, Z は変数である。Prolog の変数は X,（あるいはアンダースコア “_”）からXs, Y のように、アルファベットのはじまる識別子（名前）を使用する。一方、小文字からはじまる識別子は、述語
1

アトム（Atom）、複合項などと呼ぶこともある。

付録 P, p.1

や構成子などの定数に利用される 2 。変数はどのような項に具体化しても良いので、変数を使用した規則は、実際には無数の規則を表していることになる。
ホーン節のうちボディがないものを（fact）と言う。このときは、:-も省略する。（文末のピリオドは必要である。） 例えば、

child(hidetada, ieyasu).
は hidetada（秀忠）が ieyasu（家康）の子である、という事実を表明している。
ここで hidetada, ieyasu は小文字からはじまるので定数である。
Prolog のプログラムは、このようなホーン節（事実を含む）を集めたものである。例えば徳川家の家系図を表すプログラムの一部は次のようになる。

1234567891011121314

grandchild(X, Z) :- child(X, Y), child(Y, Z).
child(hideyasu, ieyasu).
child(hidetada, ieyasu).
child(yoshinao, ieyasu).
child(yorinobu, ieyasu).
child(yorifusa, ieyasu).
child(iemitsu, hidetada).
child(tadanaga, hidetada).
child(masayuki, hidetada).
child(ietsuna, iemitsu).
child(tsunayoshi, iemitsu).
このようなプログラムをファイルに作成し、処理系にロード 3 する。例えば
Windows 上で動作する SWI-Prolog という処理系ではメニューの「File」—「Consult. . . 」 でプログラムファイルをロードすることができる。
プログラムは、このようなホーン節の集まりに対して質問を発することにより起動される。Prolog の処理系は「?- 」というプロンプトを出力するので、このあとに質問を入力する。（質問も最後に必ずピリオドが必要である。）

123456?- grandchild(hidetada, ieyasu).
No?- grandchild(iemitsu, ieyasu).
Yes
1 番目の質問は、Hidetada（秀忠）は Ieyasu（家康）の孫か? という質問である。
これはプログラム中の規則から導出できないので、処理系は No と答えている。
2 番目の質問は、Iemitsu（家光）は家康の孫か? という質問である。これは、child(hidetada, ieyasu). と child(iemitsu, hidetada). という二つの事
実と
2
3Haskell と全く逆なので注意する。
Prolog では伝統的に consult という。

付録 P, p.2

grandchild(X, Z) :- child(X, Y), child(Y, Z).というホーン節から導出できるので Yes と答えている。
さらに Prolog では質問の中に変数を含めることができる。すると Prolog の処理系は、その質問を成り立たせるを出力する。例えば、?- grandchild(X, ieyasu).という質問に対しては、

X = iemitsuという解を出力する。ここで、リターンキーを押すとこれで終ってしまうが、「;」を入力すると、さらに別解を表示させることができる。

1234567

X = iemitsu ;X = tadanaga ;X = masayuki ;No
質問には一般に複数の素論理式を並べることができる。

?-

素論理式 1 , . . . , 素論理式 n .

このような形をと呼ぶ。直観的には、並べた素論理式がすべて成り立つか?（成り立たせるような変数への代入が存在するか?） という質問を表している。

P.2 単一化（ユニフィケーション）と後戻り
この節では、Prolog のプログラムの実行方法を解説する。解説を簡単にするために、まず、最初にいくつかの言葉を定義しておく。
2 つ以上の（通常変数を含む）素論理式があり、変数に適切な代入をして、これらの素論理式をまったく同一のものにすることができるとき、これらの素論理式は（unifiable）であるという。また、その時の代入を（unifier）という。例えば、次の 2 つの素論理式

p(a, Y, Z) と p(X, b, Z)
は X = a, Y = b を単一化代入として単一化可能である。単一化可能な時は、通常必要なのは最汎（最も一般的な）単一化代入（most general unifier,）である。例えば、上の例では、X = a, Y = b, Z = c という代入も単一化代入であるが、前者の方がより一般的である。実際、この例の場合は X = a, Y = b がMGU になる。
プログラム中のホーン節

付録 P, p.3

P :- Q1 ,Q 2 , . . . , Qn ,のヘッド P が素論理式（G）と単一化可能なとき、このホーン節は G にという。
Prolog のプログラムの実行方法は、次のようにまとめられる。

1. ゴール節中の素論理式に対し、適用できるホーン節を選ぶ。

適用できるホーン節が複数ある時は、プログラム中にホーン節から試みる 4 。

2. 選んだ適用可能なホーン節に対して、その MGU をゴール節の残りの素論理式に適用し、さらにゴール節中の最左素論理式を、上で選んだホーン節のボディに MGU を適用したものと置き換える。（ホーン節のボディがないときは、最左素論理式を消す。）
3. もし適用できるホーン節がなければ、後戻り（）して、ひとつの前のゴール節中の素論理式がある状態からやり直す。そして、その素論理式に適用できるホーン節のうち次の候補を選ぶ。
4. ゴール節に素論理式がなくなれば、プログラムの実行を終了し、その時得られた変数への代入を表示する。素論理式がまだあれば、1 に戻る。
具体的に、?- grandchild(X, ieyasu).というゴール節での動作を説明することにする。まずこのゴール節の最左（1 つしかないが）素論理式は grandchild(X, ieyasu) である。これに適用できるホーン節は、今のプログラムでは、

grandchild(X, Z) :- child(X, Y), child(Y, Z).
しかなく、最汎単一化代入は Z = ieyasu である。するとゴール節は1··· ⃝に変換される。
次に、この最左の child(X, Y) に適用できる最初のホーン節は、

child(hideyasu, ieyasu).
であり、MGU は X = hideyasu, Y = ieyasu である。すると、ゴール節は、

4

Prolog を定理証明系として見た時には、ここで、「最も左」、「先に書かれている」という選択をするために、証明系としての力が弱くなってしまう。つまり、このような制限をしなければ証明できるはずの論理式が証明できなくなってしまう。しかし、プログラミング言語として見た時は、効率を確保するために必要な制限である。

付録 P, p.4

に変換される。しかし、このゴール節に適用できるホーン節はない。
1 のところまでバックトラックし、次の候補である
そこで、上の⃝child(hidetada, ieyasu).
1のの適用を試みる。しばらくのあいだ同様にバックトラックが続き、最終的に⃝ゴール節に対し、
child(iemitsu, hidetada).というホーン節を選ぶ。そのとき MGU は X = iemitsu, Y = hidetada となる。
すると、ゴール節は、に書き換えられる。これはすぐに適用できるホーン節が見つかり、ゴール節が空になって、結果として代入:

X = iemitsuが出力される。ここで; が入力されると、またバックトラックが起こる。
ホーン節の適用は命令型言語・関数型言語の関数呼出しのようなものだと考えることもできるが、単一化により呼び出される側（ホーン節のヘッド）から呼び出す側（ゴール節）に情報が流れることがある、というところが論理型言語に特徴的なところである。例えば、?- child(X, ieyasu).という呼出しに対しては、X = hideyasu（あるいは hidetada, yoshinao . . . ）という情報が、呼び出された側から、呼び出した側に伝えられる。
Prolog の変数は命令型言語の変数と異なり、いったん単一化により値が代入されれば、以降は値を変更されることはない。ただし、（純）関数型言語の変数とも異なり、最初はいったん不定（unknown）な値を取ることができる。このような振舞いをする変数は一般に（logical variable）と呼ばれる。

P.3 Prolog でのリスト処理
Prolog でのリストの記法は要素を, で区切り、角括弧（[と]）で囲んで、[1,2, 3] のように書く。
また、先頭の要素が X で、先頭を除く残りの要素からなるリストが Xs であると表記される。これは Haskell の x:xs という書き方にようなリストは相当する。また、[1, 2, 3] はの略記法である。
Prolog でのリストを連接（append）するプログラムは次のように記述できる。

12myappend([], Y, Y).
myappend([H|X], Y, [H|Z]) :- myappend(X, Y, Z).

付録 P, p.5これは、1 番目の引数と 2 番目の引数を連接した結果が 3 番目の引数になる、という関係を表している。
例えば, [1, 2] と [3, 4] の連接は次のように求められる。

12345?- myappend([1, 2], [3, 4], X).
X = [1, 2, 3, 4] ;No
問 P.3.1 実際に、上のような結果が出ることを、上に示した Prolog の実行方法で1 ステップずつ確認せよ。

上の問を解いてみるとわかるが、変数 X は後ろの要素が不定（変数）のまま、前の要素から順に定まっていく。後ろの要素がもっと後で定まるようなプログラムを書くことも可能である。例えば、

12myconcat([], []).
myconcat([Xs|Xss], Ys) :- myappend(Xs, Zs, Ys), myconcat(Xss, Zs).
これは、リストのリストを平坦なリストに変換するプログラムである。

12345?- myconcat([[1, 2], [3, 4], [5, 6]], Xs).
Xs = [1, 2, 3, 4, 5, 6] ;No
問 P.3.2 実際に、上のような結果が出ることを、上に示した Prolog の実行方法で1 ステップずつ確認せよ。

付録 P, p.6

myappend の第 2 引数の Zs はあとの myconcat の呼出しで値が定まる。myappendの第 3 引数の Ys はしばらくの間、最後が論理変数で終る形で扱われることになる。
このように cdr 部分が論理変数になっているリストを（open list）という。開リストは Prolog でリストを扱う時に良く使われるイディオムである。
さらに Prolog のおもしろいところは myappend の逆向きの計算もできるということである。
123456789101112131415?- myappend(X, Y, [1, 2, 3]).
X = []
Y = [1, 2, 3] ;X = [1]Y = [2, 3] ;X = [1, 2]
Y = [3] ;X = [1, 2, 3]
Y = [] ;No
この例では連接して [1, 2, 3] になる 2 つのリストの、すべての可能性を求めていることになる。ユーザが「;」を入力するたびにバックトラックが起こり別解を表示する。
問 P.3.3 myappend の逆向きの計算ができることを、前節で示した Prolog の実行方法で実際に 1 ステップずつ確認せよ。

付録 P, p.7