Prolog/言語仕様

Prologの基本

プログラムは、ホーン節、もしくは単に節と呼ばれる形式の項を並べたものである。

節は、頭部と本体部からなり、

頭部.

または

頭部 :- 本体部.

の二形式があり得る。これはそれぞれ、

頭部.　　　　　　の形式が「AはBである」、

頭部 :- 本体部.　　の形式が「AならばBである」という命題の形式に対応する。

節も項であって、項は関数子といくつかの引数からなる。

節の関数子は ':-' であり、頭部と本体部はその引数である。関数子が':-'の二引数の項が節である。

頭部.

の形式は実は、

頭部 :- true.

が省略されたものと見なされ、やはり ':-' を関数子として二引数の項である。

頭部は項が連接することはできない(ホーン節)が、本体部は項が連接する、そういう項であり得る。

頭部 :- 副目標1,副目標2, ... 副目標n.

副目標₁,副目標₂, ... 副目標_n　は、これ全体を目標という。目標は副目標₁...副目標_nの連言である。

ここで 目標 = ( 副目標1,副目標2, ... 副目標n ) と置けば、

頭部 :- 目標.

であり、やはりこの節の形式も、関数子 ':-' の二引数の項であることが分かる。

複数の副目標はカンマで区切られているが、このカンマは論理積を意味する。

節は、その頭部の形式、すなわち関数子とその引数の数が同一の形式を持つ述語と呼ばれる単位で管理される。

プログラムは項の集合であり、節の集合であると同時に、述語の集合でもある。

Prologはこの項、節、述語だけでその形式を表現できる点で、他のプログラム言語とは著しく異なる。これはPrologの理論的な背景が論理学にあり、この中の概念のみで構成されて、発展してきたからである。

このような節の集合をあらかじめ用意してそれを定義した上で、ある命題が真であるかどうか問うことを質問という。 節の集合、つまり述語の集合をあらかじめ用意する方法については、後出の"Prologプログラミング"で述べる。

Prologの処理系は、人間の入力した質問に対して、頭部が形式的に一致する節があるか調べ、あった場合はその本体部に記述されている命題と一致する節があるか再帰的に調べる。

ここでは定義されたもの(処理系があらかじめ用意した組込述語も含めて)だけが、真になり、定義されていないものは必ず偽となる(閉世界仮説)。

具体的な例を見よう。

「ソクラテスは人間である」「人間は死ぬ」を Prolog で記述すると以下のようになる。ここで X は変数である。

人間(ソクラテス).

死ぬ(X) :- 人間(X).

人間(ソクラテス). は「AはBである」の命題の形式に対応し、ここでは、Aはソクラテス、Bは人間である。同様に、

死ぬ(X) :- 人間(X). は「AならばBである」であり、Aは人間(X)に、Bは死ぬ(X)に対応している。

システムに対して以下のように入力すると、true が返される。

?- 死ぬ(ソクラテス).

これは「ソクラテスは死ぬか」と質問したことに対して、システムが内部で推論を行なって、既知の知識から答えを出したものである。

それではここでの既知の知識とはなんであろうか。それは、

人間(ソクラテス).

死ぬ(X) :- 人間(X).

であり、内部で行っている推論とは、?- 死ぬ(ソクラテス). から 死ぬ(X) :- 人間(X). により導出されて、

?- 人間(ソクラテス).
true

が、確認される過程である。

今度は以下のように入力してみる。これは、「死ぬのは誰か」と質問したことと同じになる。この場合もシステムが内部で推論を行なって、死ぬ（X）を満たすXを表示する。

?- 死ぬ(X).
X = ソクラテス

他のプログラム言語に比べると質問を基本的骨格としている点でユニークであるが、更に、Prolog は複数の計算結果があり得るという点でも極めてユニークなプログラム言語である。先のプログラム例を拡張して

人間(ソクラテス).
人間(アリストテレス).

死ぬ(X) :- 人間(X).

とした場合、死ぬ（X）を満たすXは複数（ソクラテスとアリストテレス）がありうる。

述語 人間　に複数の節を設けて、その引数にソクラテス、アリストテレスと列記して行くだけで、質問に対して複数の解を処理系が列挙するようになる。

他の言語でこういう機能を実現する時に見られるような、手続き的なループや情報を管理する配列の添字管理のようなものは全く現れない。

多くのProlog 処理系ではこのような複数解が存在する時に新たな解を得る場合は

?- 死ぬ(X).
X = ソクラテス ;
X = アリストテレス

と ";"（セミコロン）記号を用いて他の解を得る。";"はこの解は真ではない、という質問者の意思表示である。

ここではインタプリタのトップからの質問、すなわち対話環境にあるから、X = アリストテレスが処理系からの質問者に対する応答、質問となっている。

質問者は「この解は真ではない」と否定することができる一方、呈示された解(ソクラテスまたはアリストテレス)を真と決定することもできる。このように処理系から見て外部からの介入によって真を得ることを非決定性という。

この非決定性がコンピュータ言語としてのProlog の際立った特徴の一つである。

もうすこし具体的なPrologプログラムの例を以下に示す。「%」から行末までは注釈である。

% member(X,Y)はXがリストYの要素として含まれているときに成功する。
% そうでないときは失敗する。

member(X, [X|_]). % Xがリストの先頭要素と同じ場合
member(X, [_|Y]) :- member(X, Y). % それ以外の場合

member(X,Y) は要素XがリストYのメンバーであるかを調べるプログラムであると同時に、「要素XがリストYのメンバーである」という関係も宣言的に表している。実行例を以下に示す。

要素XがリストYのメンバーであれば成功する。

?- member(サザエ, [波平,サザエ,マスオ]).
true.

要素XがリストYのメンバーでなければ失敗する。

?- member(サザエ, [ワカメ,マスオ,タラオ]).
false.

Xの部分を変数のままにすると、リストYのメンバーである要素が結果として返る。すなわち、ジェネレータとして働く。

?- member(X, [ワカメ,マスオ,タラオ]).
X = ワカメ ;
X = マスオ ;
X = タラオ

二つのリストの共通メンバーを求めるには単純に","で区切って並べればよい。この","はANDの意味を持つ。

?- member(X, [波平,サザエ,マスオ]), member(X, [ワカメ,マスオ,タラオ]).
X = マスオ

要素Xを指定しリストYを変数のままにすると、それらがメンバーであるリストが結果として返る。

?- member(波平, Y), member(サザエ, Y), member(マスオ, Y).
Y = [波平,サザエ,マスオ|_G001]

上の"_G001"はProlog処理系が作成した仮の変数で、リストの後半が不定であることを示す。

Prologのプログラミング

質問

Prologの実行は述語を定義された処理系に対してユーザが質問することによってなされる。質問とは、

?- 親子(ふね,タラオ).

のようなものである。ここでの質問は「ふねはタラオの親か」という意味だ。「ふねとタラオは親子関係である」という読み方もある。

このような質問に処理系が答えることができるためにはその知識が必要である。Prologではこの知識を述語という形式で与える。そのことを述語を定義するという。

定義された述語には一般に処理系によって最低限必要なものとしてユーザに対してあらかじめ用意された組込述語(ユーザは定義しなくてもよい)と、ユーザが自ら定義したユーザ定義述語の二種類がある。ユーザは自ら定義した述語群をファイルに保存して、そのファイルを組込述語であるconsult/1述語によって処理系に読み込ませる。

サザエさんの家系図に関する述語群が

親子(波平,サザエ).
親子(ふね,サザエ).
親子(波平,カツオ).
親子(ふね,カツオ).
親子(波平,ワカメ).
親子(ふね,ワカメ).
親子(マスオ,タラオ).
親子(サザエ,タラオ).

夫婦(波平,ふね).
夫婦(マスオ,サザエ).

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

上記のように、エディタなどで書かれて、ファイル'sazaesan.pl'に存在するとして、

?- consult('sazaesan.pl').
true.

を実行することによって、サザエさんの家系図に関する述語群がユーザから参照できるようになる。

?-

はプロンプトと呼ばれ、質問を受け付ける準備ができていることを示す。プログラムを実行するのには、一般にProlog処理系の起動後、最初のプロンプトが表示されてからユーザ自身で質問(目標)という形でプログラムを実行する。

実務的なプログラムではこの質問によって述語定義の融合、頭部の単一化、本体部の導出の長い連鎖となり、最終的にその質問が真か偽の結果を残して終了する。

これが普通の使い方だが、処理系の起動時にコマンド引数などで最初に実行する質問を引き渡して、起動後停止することなく、質問が実行される場合もある。

ここでlistingという質問を与えてみる。この組込述語は現在実行可能な状態にある述語すべてのソースコードを表示する。

?- listing.

親子(波平,サザエ).
親子(ふね,サザエ).
親子(波平,カツオ).
親子(ふね,カツオ).
親子(波平,ワカメ).
親子(ふね,ワカメ).
親子(マスオ,タラオ).
親子(サザエ,タラオ).

夫婦(波平,ふね).
夫婦(マスオ,サザエ).

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

このように定義済みであることが分かった。これが先の?- consult('sazaesan.pl').の効果である。

最初の親子(波平,サザエ). から 夫婦(マスオ,サザエ). までが事実であり、形式的には本体がなく、単位節と呼ばれる。 その下の member は二番目の節に再帰的に本体があり、これはルールと呼ばれる。

ルールmemberを使った質問をしてみる。

?- member(サザエ, [波平,サザエ,マスオ]).
true.

となる。サザエは集合{波平 サザエ マスオ} の要素であるかという質問に真と答えている。

さらに簡単な質問をしてみる。単に事実を問うものだ。

?- 親子(波平,サザエ).
true.

?- 親子(ふね,X).
X = サザエ;
X = カツオ;
X = ワカメ .

?-

この質問で第二引数に X 乃ち論理変数が使われた。処理系はこのXに適切な値が入ることで、この質問を真となって終わらせようとする。

X に カツオが入った時、

?- 親子(ふね,カツオ).
true.

で真となるし、ワカメが入った時、

?- 親子(ふね,ワカメ).
true.

で真となる。

この二つの質問を 論理変数 X を順に束縛することで満たしているのが上の ?- 親子(ふね,X). での実行結果である。

質問の詳しい説明は後のプログラム例「家系図」以下にある。

プログラムの起動と質問の自動実行

Prologの処理系は質問がなされ、それに回答を繰返すことによって処理が進むという作りになっている。

しかし、質問することなしに、処理系の起動時にプログラムを実行することももちろんできる。最初に現在処理系で使われている代表的な二つの方法を示す。

1) ソースプログラムの中に起動する質問を記述する。

    ・ 処理系の起動時に -f ファイル名 オプションを指定して、ファイル名のソースファイルを読みこませる。

    ・ ソースプログラムの中に、:- <<目標>>.のように自動実行する質問を記述する。

2) 処理系の起動時に -f ファイル名 オプションを指定すると共に、-t オプション等で、最初の質問の述語名を直接指定する。(例えば mainなど )

　　 ・ # prolog -f sazaesan.pl -t main

必ずしも処理系起動時と限らないのだが、consultされるファイルの途中に特別な述語 :- を指定して、自動で質問が実行できるようになっている処理系が多い。 ファイル'sazaesan.pl'の第一行目に

:- write('%%% サザエさん家系図の読み込み %%%\n').

親子(波平,サザエ).
親子(ふね,サザエ).
親子(波平,カツオ).
親子(ふね,カツオ).
親子(波平,ワカメ).
親子(ふね,ワカメ).
親子(マスオ,タラオ).
親子(サザエ,タラオ).

夫婦(波平,ふね).
夫婦(マスオ,サザエ).

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

が書かれているとすれば、

?- consult('sazaesan.pl').

を実行した直後に

%%% サザエさん家系図の読み込み %%%

と表示される。'sazaesan.pl'の第一行が読み込まれ、処理系が :- から始まる特殊な節を見つけると、

?- write('%%% サザエさん家系図の読み込み %%%\n').

という質問をユーザからの入力なしに実行する。

この機能を利用して、処理系の起動時にコマンドラインに -f オプションなどで初期読み込み述語ファイル名が指定できる作りになっている処理系が多く、

# prolog -f sazaesan.pl

この ':-' 述語をファイル内の適宜な場所に記述することによって、質問の自動起動が可能となる。

しかしながら質問で変数束縛の状態表示を期待している場合は、質問ー応答モードを脱して動いてしまっているから、:-以下での質問に対する実行が完了した場合でも質問ー応答する場合のようにはうまくいかない。";"や改行待ちとなる非決定性の制御にも移行しない。このような変数束縛の表示はwriteのような出力述語を続けて記述してユーザが表示させる必要があるだろう。

自動実行を理解しやすくするために、'sazaesan.pl'に少し :- 節を追加してみる。

:- write('%%% サザエさん家系図の読み込み %%%\n').

親子(波平,サザエ).
親子(ふね,サザエ).
親子(波平,カツオ).
親子(ふね,カツオ).
親子(波平,ワカメ).
親子(ふね,ワカメ).
親子(マスオ,タラオ).
親子(サザエ,タラオ).

夫婦(波平,ふね).
夫婦(マスオ,サザエ).

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

:- write('%%% 波平の子供は %%%\n').
:- member(波平,X),writef('%t\n',[X]),fail;true.
:- write('%%% 終了します %%%\n').
:- halt.

これを'sazaesan.pl'とは別のファイル'temp1.pro'に書いて置くとする。

組込述語 writef/2 や fail;true 制御についてここでは詳しくは述べないが、

最後に処理系を終了させる組込述語 halt. を実行させることにより、

# prolog -f temp1.pro
% library(swi_hooks) compiled into pce_swi_hooks 0.00 sec, 2,224 bytes
%%% サザエさん家系図の読み込み %%%
%%% 波平の子供は %%%
サザエ
カツオ
ワカメ
%%% 終了します %%%
#

のような、バッチ処理プログラムとして実行することができる。

起動述語として例えばプログラムの起動時コマンドオプションで -t main を指定する場合は、予め、

・・・・・
夫婦(波平,ふね).
夫婦(マスオ,サザエ).

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

main :- member(波平,X),writef('%t\n',[X]),fail;true.

のように述語として定義して置けばよい。

組込述語 consult/1 の事例を示したが、Prologの処理系は共通の組込述語群とその処理系独自の組込述語群を持っており、後者が統一されない状態であることは歴史の中で触れた。ユーザは各処理系のマニュアルを注意深く読む必要がある。

述語

Prologでプログラムを記述する単位は述語（英: predicate）で、他の言語での関数やサブルーチンに相当する。つまり、Prologプログラムは述語の集まりで、述語はあるまとまった機能を表現している。述語は1つ以上の節（英: clause）と呼ばれる項からできている。節は以下の形をしている。

頭部 :- 副目標1, ..., 副目標n.

あるいは、

頭部.

1つの述語に属する節は、同じ述語名(関数子名)と引数の数(アリティ)を持つ頭部からできている。述語名とアリティが異なれば別の述語とみなすため、述語を指定するときは"述語名/アリティ"と表記されることもある (例： member/2) 。

1つの述語は成功、あるいは失敗のいずれかの結果を返す。副目標₁〜副目標_nの間の "," はANDを意味する演算子であり、1つの節が成功するのは本体部がすべて成功した場合である。

本体部の実行は、副目標がANDの関係で連接する場合、記述された順に行われる。頭部のみの節は 頭部 :- true. と同じ意味であり:-trueが省略された形式だと考えればよい。

1つの述語が複数の節からなる場合、上から順に実行され、どれかが成功したら述語自体は成功する。つまり同じ述語内の節の関係はORの関係となる。節同士はOR関係であり、それぞれ情報の共有という観点からは完全に独立している。

一つの節の中の副目標から、同じ述語の別の節中の情報にアクセスするためには、新たにこの述語を目標(質問)として呼び出す必要があり、この場合、制御や変数束縛等は完全に初期状態での実行となる。

一度trueになった節で一旦は変数に値が束縛(代入)されていたとしても、バックトラックして、それより下の節に制御が移った場合は、制御の移った節からバックトラックした(すなわち偽となった)節の変数束縛を利用することはできない。

述語は親となる目標(副目標)によって謂わば質問として呼び出される。これに対して、述語の各節は予め備えている状態にある。質問されることによって、頭部の単一化を行い、これに成功した節の、本体の副目標を順次、今度はこれが親となって質問する。そういう備えができている。それが述語が定義されているということである。

宣言的意味と手続き的意味

Prologの基本的なアイデアは、ホーン節をプログラムと見なして実行する、ということであるため、純粋なPrologのプログラムは手続き的にもホーン節に従って宣言的にも解釈ができる。1つの節の解釈は以下のようになる。

"副目標1"かつ ...、かつ"副目標n"が真であれば、"頭部"は真である (宣言的意味)

"頭部"であることを示すには、"副目標1"かつ...、かつ"副目標n"を示す (手続き的意味)

手続き的に見ると、"副目標₁"〜"副目標_n"がすべて成功する場合、節は本体部を順番に実行する関数やサブルーチンのように見なせ、再帰呼び出し可能な手続き型/関数型言語と動きはさほど違わない。他の言語との大きな違いは、本体部のいずれかが失敗した場合、最後に選択した節にバックトラックし次の節から再度実行を続けることである。

Prologの動作をプログラムが指定した条件での解の探索として見ると、深さ優先の解探索ととらえることができる。

論理変数

C言語など通常のプログラミング言語の変数は値の格納場所であって、計算が進むに従って内容が変化する。Prolog などの論理型言語での変数は数学的な変数に近いもので、何らかの値につけた名前である。値は決まっているか決まっていないか(代入されているか代入されていないか)のいずれかで、一度決まってしまえば値が他の値で置き換わることはない。値が変わるのはバックトラックにより代入が解かれた後に再度値が決まった(代入された)場合のみである。この変数は他のプログラム言語のそれのようにプログラム中に宣言することはできず、述語或いは述語呼び出しの引数の位置にのみ現れる。

通常のプログラミング言語の変数と区別するために論理変数と呼ばれることもある。論理変数が述語または質問の引数の位置にのみ現れるという意味を理解しやすくするために以下の例を示す。

Y=Y,Y=Z,Z=3.のX,Y,Zは一見プログラムの中に宣言しているように見えるが、全て組込述語=/2の引数である。Prologにおいて=とは単一化を施すという意味である。

変数の値の変化の例：

?- X=Y, Y=Z, Z=3.
X = 3,
Y = 3,
Z = 3
true.

?- W=5, W=3.
false.

論理変数は、格納場所ではなく、質問がなされる度に定義節を写して生成される一時的な論理域に存在するもので、プログラムの他の箇所からその値が参照されることはあり得ない。

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

第一節にXが二箇所、第二節にはXとRが二箇所現れている。それぞれの変数が最終的に同一のものに代入されることの宣言である。

また上記の定義では第一節と第二節にXという論理変数が現れているが、この二つの論理変数名が同一であることには意味がない。第一節のXに値が代入されて解が得られた後、バックトラックされて第二節に移行したから値が解放されて、Xは代入されていないのではなくて、第二節のXは第一節のXとは元々無関係だから、代入されていないことになる。

論理変数の名前が同一であることが意味を持つのは、質問されて、述語のひとつの定義節と融合された時、その融合された定義節側の頭部、本体の中に、同名の論理変数があるかないかだけである。質問した側の副目標の引数の論理変数がどのような表現になっているかについては没交渉である。融合の際の頭部の単一化でさえ、論理変数同士の単一化であっても、ソースプログラムで変数名が同じあるか否かは問われない。この点については、次の節の単一化を参照。

ここで起こっている質問としての副目標(または目標)と定義節との融合は、述語定義のコードからは離れて、対応する節がその姿を写されて実行されるのであって、その実行と述語定義のコードは直接的な関係を持たない。

したがって、この質問、導出過程で論理変数が束縛されても、述語定義の他の定義節の論理変数に影響を及ぼしようがないのである。

単一化

Prolog の動作の基本は単一化と後に述べるバックトラックである。

単一化(ユニフィケーション)は、述語呼び出し時に使用される、呼び出し側、呼び出される側双方向の強力なパターンマッチングだが、そのルールは簡単である。

すなわち、二つの項の単一化において、

1. 2項がそれぞれ変数の場合は、以後この二つの変数は同一のものと看做される。同時に単一化は成功する。
2. 2項の一方が変数であり、他方が変数以外の項である場合は、変数はこの変数以外の項と同一のものとなる。単一化は成功する。
3. 2項がそれぞれアトムの場合は、二つのアトムが完全に一致した場合に単一化は成功する。
4. 2項がそれぞれ複合項の場合は、二つの複合項の関数名とそれぞれの引数の形式が一致した上で、全ての引数要素に対して、再帰的に単一化が成功する場合のみ、単一化は成功する。

以上挙げた以外の場合は、単一化は全て失敗する。したがって、アトムと複合項の単一化は常に失敗する。述語呼び出し時の候補節では、一つでも頭部にある引数の単一化に失敗すると、その候補節は選択されない。

1 と 2 は意味的に統合可能であり、単一化ルールを三つとすることもある。Wikipediaのユニフィケーションの説明ではそうなっている。しかし、変数の単一化は値が代入されないという意味で特殊であり、Prologでは同一性のみ主張できる変数の制約そのものであり、Prologの最も独自性の強い部分であることから、ここでは独立したルールとして扱う。

単一化によって論理変数がある値に決まることを、代入という。一般のプログラム言語の代入と表現は同じであるが、Prologの代入はある値をその論理変数を通じて覗くことができる。あるいは、この値が参照(利用)可能な状態になるといったニュアンスに近い。なぜなら、この代入がバックトラックによって「解かれる」と論理変数は再び何も参照できなくなる。

単一化は処理系が述語を質問として呼び出す(目標が実行される)たびに、暗にPrologシステム内で実行されつづけているのだが、利用者が明示的に二項の単一化を指定することもできる。それが先の論理変数の事例に現れた = である。述語 = は左右に二つの引数を持ち、この二つの項の単一化を試みる述語である。

ここで、明示的な二項の単一化(=/2)を組み合わせて単一化の説明を試みよう。

?- X = Y,    % X と Y が同値と制約された。
   Y = 3.    % Y から 3 が参照可能になった。同値制約されている X もまた、3 が参照可能になった。

X = 3,
Y = 3.
?-

単一化は極めて強力なパターンマッチングではあるが、実行コストも多大である。Prolog処理系の実行速度が他のプログラム言語のそれに比べて遅いことの主要な原因は単一化にある。

通常のプログラミング言語との比較で考えると、Prologの単一化は以下の機能を含んでいる。

• 変数への値のアサイン
• 変数の同値制約(変数同士の単一化)
• パラメータの受け渡し
• リストの作成/リストの分解/リスト各要素の読み出し・設定
• 複合項(通常言語での構造体やレコード)の値の読み出し/値の設定
• 条件分岐(通常言語のif文やswitch文)

バックトラック

バックトラックは他のプログラム言語と比較してPrologを特徴づける部分である。バックトラックとは後戻りくらいの意味だが、現在まで日本語として適切な訳を見つけられず、このバックトラックがもっぱら使用されている。プログラムのコードとして明示的に指示がないにも関わらず、暗に実行コードが既に実行を済ませた部分に後戻りして実行を始める、そういう制御のことをバックトラックと呼んでいる。

質問が

 ?- p1,p2,p3,p4,p5.

とされたとする。

これから、p3(副目標という)が実行されると考えよう。p1,p2は成功裡に終了している。(ここでは副目標を抽象化して P_n の形式で表すこととする) このp3が成功(真となる)すると実行はp4が呼び出され、その定義の第一節に移る。 ところがp3が失敗(偽となる)すると、p2,p1の順に、まだ実行されていない、候補節が残っているものを探し、それがあれば、そこから実行される。 この後戻りして、実行する制御のことをバックトラックという。

p2に候補節がなく、p1にまだ候補節があってここから実行される時には、p3を含むp2以降に生じた変数の代入は完全に解消されている。 p1にももはや実行されていない候補節がない場合、最初の質問?- p1,p2,p3,p4,p5.が偽となる。

ここで候補節が残っている、または残っていないと書いたが、既に概要のところで述べられた非決定性の述語だけが、この候補節が残っている状態に成り得る。副目標の述語定義が決定性である場合は当然候補節は残っていない訳だから、?- p1,p2,p3, ... に於いて、p2が決定性の述語だったとすれば、p3がバックトラックすれば次はp2をスキップしてp1の残り候補節を探すことになる。

述語Q の定義が以下の場合に ?- q. が実行されて、上記のようにP3が失敗したとする。

q :- p1,p2,p3,p4,p5.
q :- p6,p7.

p3が失敗して、もはやp2,p1にまだ実行されていない候補節がない場合、次の実行は第二節のp6に移る。つまり、qの第一節は失敗して、第二節(まだ実行されていない)に移る。のように、Prologの実行制御を把握するためには、pnの真偽だけではなく、pn-1,pn-2,...や、そのpnを呼び出しているqの実行状況まで視野に入れる必要がある。

たとえば、以下の述語に対して、

member(X, [X|_]). % Xがリストの先頭要素と同じ場合
member(X, [_|Y]) :- member(X, Y). % それ以外の場合

以下の member(Z, [ワカメ,マスオ]) というゴールを指定すると結果は次のようになる (";"を1回入力しバックトラックを行わせた例) 。

?- member(Z, [ワカメ,マスオ]).
Z = ワカメ ;
Z = マスオ

複数の解がありうる述語member/2に於いて、処理系は質問者に最初の解候補 Z = ワカメ を示したが、

質問者は";"を入力することによってこれを否定した(非決定性)。

続いて処理系が Z = マスオ という解候補を示し、

質問者はそれを受け入れて、改行した。これがこの実行の解釈である。

具体的に、member/2で解候補が選択される過程を追ってみると、

まず最初の節の頭部

member(X, [X|_])

で単一化が成功し、 Z=ワカメ で member/2 自体も成功する。

この状態でバックトラックを行わせると、次の節である2番目の節の頭部

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

で単一化が成功し、その本体部( ... の部分)を

:- member(Z, [マスオ]).

として実行することになる。

これは、最初の節の頭部

member(X, [X|_])

で単一化が成功し、 Z=マスオ で member/2 は成功する。質問者は"."を入力することによって、これが解であることを受け入れた。

非決定性の述語の解の決定権をここでは質問者が持っている。しかし、このように質問者が介在することはPrologプログラミングの中では寧ろ特殊な場合であって、多くの場合、非決定性の述語の解を最終的に決定するのは後続する副目標である。

タラオの親は(L,A) :- member(A,L),親子(A,タラオ).

?- タラオの親は([ワカメ,マスオ],X).
X = マスオ.

これは、タラオの親はワカメかマスオかという質問になっている。解はもちろんマスオだが、これを決定したのは、質問者ではなく親子(A,タラオ)という副目標であり、親子(マスオ,タラオ). という定義から導かれる論理が member(A,[ワカメ,マスオ]) の解をマスオに導いた。このようにmember/2からの視点で述べると、解を決定したのは質問者であったり、後続の副目標であったりした。すなわちmember/2にとっての外部である。述語自体は解を決定できないから、外部の導きによって最終的な解を選択するのだと考えればよい。非決定性述語の非決定性とはそんな意味である。

バックトラックは通常のプログラム言語には存在しないProlog独特の機能だが、強いて他のプログラム言語の中から類似したプログラミング要素を探すと、

• ループ(通常言語のfor,while等)
• 探索機能

が挙げられる。

ループの簡単な例を以下に示す。この例ではリストの先頭から0以上100以下の数値が見つかるまで繰り返す。

?- member(X, [3000, 1254, -2, 3598, 88, 9618]), X>=0, X=<100.
X = 88

確かにこれはループではあるが、0以上100以下の数を取り出すというものだ。実際には3000,1254はX=<100で、-2は、X>=0で偽となってバックトラックしているのだが、Prologプログラマはそのような細部を行ったり来たり目で追うことはしない。

手続き型言語では探索機能を実装することは大きなタスクとなるが、Prologは非決定性述語を中心にプログラムを書くものであり、すなわちプログラミングとはバックトラックしながら探索することである。

数式

X+Y*3 などの数式は単なる複合項にすぎない。数式を評価するには"is"などの述語を使う。以下にいくつかの述語の例を示す。

• X is Y :評価と単一化をおこなう (評価は第二引数のみであり第一引数は評価せずに単一化を行う)
• X=:=Y :評価と比較をおこなう (第一・第二引数ともに評価してから単一化を行う)
• X = Y :単一化をおこなう (数式を評価しない)
• X==Y :項の比較をおこなう (数式を評価しない)

?- 3+5.
false.

?- X is 3+5.
X = 8
true.

?- 8 is 3+5.
true.

?- 7 is 3+5.
false.

?- X is sin(pi)^2+cos(pi)^2.
X = 1.0.

?- X is 1.0.    %　数はそのまま評価される。
X = 1.0.

?- 2+6 is 3+5.   % is/2の第一引数は評価されず単一化されるため 項 6+2 と 8 の単一化となり、偽となる。
false.

?- 3+5 =:= 2+6.
true.

?- 2+6 =:= 3+5.
true.

?- X = 3+5.
X = 3+5
true.

?- 3+5==2+6.
false.

?- 3+5==3+5.
true.

引数の単一化は X = Y に相当し、数式として評価可能の項が渡されても、評価されず単一化される点に注意が必要である。

f1(0).
f1(M) :-
        M_2 is M - 1,
        f1(M_2).

f2(0).
f2(M) :-
        f2(M - 1).    % 仮に、M - 1 のMが5に具体化されたとしても、複合項 5-1 が引数として評価されることになる。


?- f1(5).
true.

?- f2(5).
ERROR: Out of global stack

f2はエラーになってしまう。再帰により与えられる引数は 5-1, 5-1-1, ..., 5-1-1-1-1-1, ... であり、 f2(0). に帰着することなく再帰が続くため。

X is Y の数式Yの中に解決されていない変数を含むことはできない。例えば、

add1(X,Y) :- Y is X + 1.

?- add1(X,3).
ERROR: is/2: Arguments are not sufficiently instantiated

のようなエラーとなる。すなわち、

?- 3 is X + 1.

のような実行はできない。X = 2 であっても良さそうに見えるが、isの第二引数の評価はそれを式として計算するのみである。 このことは、述語 is/2 には、双方向性がないことを意味する。Prologプログラマは可能であれば数式評価を避けようとする傾向があるが、それはこの評価がどこかに存在する述語定義は、多くの場合に双方向性を失うからである。

比較演算子の第一・第二引数のどちらにも数式を書くことができる。それらは評価された上で比較される。比較演算子としては、

>, <, >=, =<, @>, @<, @>=, @=< などがあり、

?- 3+5 > 2+1.
true.

?- sin(pi / 2) =< 2.0.
true.

?- 2+3 @>= 2.
true.

となる。

カットと否定

Prologは一階述語論理をベースにしているが、実用的なプログラミングのため、述語論理の範囲外の機能も用意されている。カットや否定の組み込みはその例である。

最初にカットと否定を含む典型的な定義例を掲げて置く。

% 閏年の定義
% 1) 西暦年が4で割り切れる年は閏年
% 2) ただし、西暦年が100で割り切れる年は平年
% 3) ただし、西暦年が400で割り切れる年は閏年

閏年(_西暦年) :-
    0 is _西暦年 mod 400,!.
閏年(_西暦年) :-
    0 is _西暦年 mod 4,
    \+(0 is _西暦年 mod 100).

1)-3)までの定義(仕様)は、判り易いとは言い難いが、Prologのコードは明解である。

400で割り切れるものは、100でも4でも割り切れるから、これを最初の節で定義する。!があるので「それで確定」である。!(カット)の効果で第二節の定義が採用される可能性はなくなる。

第二節で4で割り切れるものの中で、100で割り切れるものを「除外」している。\+( )は否定であるが、除外と読んだ方が判りやすい。この閏年の定義は典型的でかつ易しい例であるが、特に!の使われ方、役割、意味は遥かに多義的で複雑である。以下それを順に述べる。

Prologのバックトラックは強力な機能だが、実際のプログラムでは不要なバックトラックを制限したい場合もある。"!" (カット) はバックトラックを制限するための述語である。カットが最初に実行された時には無条件で成功するが、バックトラックでカットに制御が戻ってきたとき、カットを含む述語は無条件に失敗する。つまり、1つの述語内でカット以前に制御が戻ることはない。 たとえば、通常のプログラミング言語での if p then q else r の動きは、カットを使って以下のように書ける。

x :- p, !, q.
x :- r.

一度、pが成功して、qに進んだら、qの真偽に関わらず、後にpやrが実行される可能性はなくなる。

プログラマにとって、カットが重宝なのは、条件p の否定を省略できる点にもある。

x :- p,q.
x :- \+(p),r.

pに副作用がない場合、p,!,q とした場合と同じ意味になる。

最初に示した閏年の定義で見てみよう。

閏年(_西暦年) :-
    0 is _西暦年 mod 400,!.
閏年(_西暦年) :-
    0 is _西暦年 mod 4,
    \+(0 is _西暦年 mod 100).

x :- p,!.
x :- q,\+(r).

%%%%

閏年(_西暦年) :-
    0 is _西暦年 mod 400.
閏年(_西暦年) :-
    \+(0 is _西暦年 mod 400),
    0 is _西暦年 mod 4,
    \+(0 is _西暦年 mod 100).

x :- p.
x :- \+(p),q,\+(r).

%%%%を挟んで上がカットを使った記述。下は、カットの使用を避けた記述である。共にx,p,q,rで抽象したパターンを描いて添えてある。

カットを避けた表現は論理式として正統な記述で推奨されるものではあるが、以下のように、

x :- p1,p2,q1.
x :- \+((p1,p2)),p3,q2.
x :- \+((p1,p2)),\+(p3),q3.

次々と、条件を否定して行かなくてはならないのでは、プログラマにとって負担が大きくなる。解読も困難になって行く。

カットを使った場合と比較する。

x :- p1,p2,!,q1.
x :- p3,!,q2.
x :- q3.

このように正確な条件を記述することが大きな負担となる場合、その負担を解消するためにカットが使用されることが実は多い。

これも同様の例である。文字 a を繰り返し表示したい。

f(0).
f(N) :-
    write(a),
    N_1 is N - 1,
    f(N_1).

ここで、

?- f(30).
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaa

となるが、

?- f(30),fail.
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaa

のようにfにバックトラックして来ると、動作は怪しげなことになる。少なくとも多倍長整数をサポートする処理系では Nが -1,-2,-3・・・・・と無限に小さくなっていって反応しなくなる。 このような現象を避けるために、普通第一節に

f(0) :- !.
f(N) :-
    write(a),
    N_1 is N - 1,
    f(N_1).

上記のようにカットを入れる。これで、Nが正の整数から順次減少してきて、遂に0になり第一節が一度成功したことで、仮にバックトラックを強制されたとしても、第二節に制御が下りる可能性はなくなる。

ただし、この場合でも、カットなしで済ませる方法はある。

f(0).
f(N) :-
    N > 0,
    write(a),
    N_1 is N - 1,
    f(N_1).

でよい。問題は、正しい論理を付加することによって、ここでの例では N > 0 を記述することによって、実行の制御をすることが本当に安全かということである。!を挿入する方がずっと安全ということも考えられるのである。

通常のProlog処理系では、バックトラックで戻ってくる場合に備えて、それまでに実行した各ゴールの情報や値を設定した変数を、ほとんどの場合スタック上に、アトムテーブルや述語定義の情報はメモリー上のヒープ領域と呼ばれる必要になったデータ構造を切り取って使用するための管理領域に記憶している。カットを実行すると、それらスタックやヒープ領域に置かれた情報の中で、最早決して使用されることがない情報を選別して解放することが可能になることが多い。この解放可能の領域を再度利用可能とするためには、領域を整理して使用可能域を再生(ガベージコレクション)する。このような手順を経た上ではあるが、カットは一時的に使用しているメモリを削減する。プログラマが ! を挿入することで、陽にまたは暗に、処理系に対してこのメモリー解放の要求のサインを出していると考えられることもある。さらにインタプリタ/コンパイラなどに対して、処理系に備えがあればではあるが、最適化を施すことの要求となる場合もある。

カットは非決定性の述語と定義されたものを決定性に転じるためにも多用される。実例を見よう。

append([],L,L).
append([U|X],Y,[U|Z]) :- append(X,Y,Z).

appendの定義であるが、第一引数かつ第二引数に変数が来ると非決定性に働く。

?- append(X,Y,[1,2]).
X = [], Y = [1,2];
X = [1], Y = [2];
X = [1,2], Y = [];
false.

である。appendの第一節の本体にカットを加えると、非決定性の性質が事実上消える。

append([],L,L) :- !.
append([U|X],Y,[U|Z]) :- append(X,Y,Z).

?- append(X,Y,[1,2]).
X = [], Y = [1,2];
false.

元々のappendの定義を壊さず、

決定性append(X,Y,Z) :- append(X,Y,Z),!.

でもよい。appendを決定性に使用したい場合は、以後appendの代わりに専ら 決定性appned を使えばよい。

次に、appendの第二節の末尾にカットが来る場合を考える。

append([],L,L).
append([U|X],Y,[U|Z]) :- append(X,Y,Z),!.

このカットも非決定性を決定性に転じる場合に使われるがそう簡単な話ではない。最初にこれでは決定性述語とはならない。

?- append(X,Y,[1,2]).
X = [], Y = [1,2];
X = [1], Y = [2];
false.

最初の解 X = [], Y = [1,2]; は第一節でいきなり真になってしまう。したがって、これはまだカットとは関係がない。 第二解は、通常通り第三引数の先頭要素が第一引数に移動して、それで第一引数が[1|X],第二引数tがY,第三引数が[2]となって、移動した後のappendが実行され、

?- append(X,Y,[2]).
X = [], Y = [2]

先ほどの[1|X]のXの部分に[]が来るため、X = [1], Y = [2] が取得できる。

これで一旦成功することになる。成功すると、そのとたんにカットが働く。そのカットの働きで、もう第二節の本体の副目標から次の選択肢を得る指示は与えられない。?- append(X,Y,[2]). にはもう一解存在するのだが、

?- append(X,Y,[2]).
X = [], Y = [2]  % ここまでは使用された。
X = [2], Y = []  % この解を返す指示は来ない。

その解はカットの働きで、この append(X,Y,[2]) で呼び出している副目標が偽となるため、返される機会は来ない。

末尾にカットが在る場合をまとめると、

このカットに到達するのは、ひとつでも解が得られたときであるが、解が得られこのカットに至った場合、カット以前にある副目標によって、次の選択肢として予定されている節選択の可能性は一切なくなる。上記の表現で言い換えれば、次の解を返す指示を出せなくなる。

そして、末尾にカットのある節の後にこの述語の選択節がある場合ももちろんその節が選択されることはない。

説明の順序が前後したが、実行結果の否定のためには述語"\+"が用意されている。 \+(P) はゴールPが成功したときに失敗し、失敗したとき成功する。この述語は本当の否定 "Pは偽である" ではなく "Pは証明できない" という失敗による否定で、ある種の非単調論理による推論を行う。これは以下のように定義した述語と同じ動きをする。ここで fail は必ず失敗する組込述語である。

\+(P) :- P, !, fail.
\+(_).

この否定は、カットなしには定義する方法がない。

論理プログラミングにおいては、「計算は、書き換えの系列として記述される」。ところがPrologにあっては、この 書き換え(導出)という表現が好ましくなく場面が現出する。それはカットが導出されるような場面だ。

p :- q1,q2,q3,q4.

q2 :- q5,!.
q2.

のような副目標 p を

?- p.

を q2 の第一節を導出して、

?- q1,q5,!,q3,q4.   % 誤り

と展開して良いであろうか。これは誤りである。実際にはこのカットは展開前と同様には働かない。カットはそれが記述された節の本体の連接の範囲の中のみで有効である。

この問題を別の観点から述べると、カットの重要な性質としてそのカットを別の副目標として置換(述語の再定義)することはできないということになる。さらに実例を示そう。

p(X) :- true,!,X = 1.
p(X) :- X = 2.

の第一節に現れるカットをcutに置き換えたとしたら、カットの働きを失う。

p(X) :- true,cut,X = 1.
p(X) :- X = 2.

cut :- !.

最も単純な置換例が上記であるが、これでは、バックトラック後に第二節の実行を妨げられない。

?- p(X).
X = 1;
X = 2.

ここで分ることは、カットは ! が書かれた「節の実行制御」としてのみ有効ということである。

カットを検証する時、取るべきプログラマの視点について最後に記す。

プログラマは定義された述語の各節の本体にのみ焦点を合わせる。そして、その部分に現れるカットによって バックトラックしなくなる本体のカットより前の部分と利用されることがなくなる後続する定義節の存在は 視野に入れる必要があるが、 導出される謂わば子タスクとしての副目標内に現れるカットは考慮の対象から完全に外す必要がある。

カットが論理プログラミングをどんなに逸脱していても、その利用が不可避である以上、このカットの有効範囲の認識はPrologの基本中の基本である。

高階述語とメタインタプリタ

Prologの述語はPrologの基本データタイプである項で表現でき、述語自身の引数として別の述語を与える高階述語を作成できる。

たとえば、引数で述語を与えそれを単純に実行させたい場合、ゴールとして変数をそのまま書けばいい。

eval(P) :- P.

または

eval(P) :- call(P).

本来はcall/2が使われたが、その後、目標Pとだけ書くことでcall(P)と解釈されるようになった。述語名evalはLISPで同様の機能の関数の関数名としてこれが使われた伝統を引いてこの述語名が使われることがある。このように、

任意の述語を実行時に作成して実行することができるため、リストのすべての要素に特定の述語を適用し結果のリストを返す maplist/2 や、リストの要素を与えられた述語の結果で選択する sublist/3 などの高階述語を容易に作成できる。同様の高階述語には findall/3 、 setof/3 、 bagof/3 などがある。

また、純粋なPrologのメタインタプリタは以下のように書ける。 clause(P, Q) は頭部が P にユニフィケーション可能な節の本体部 Q を取得する述語である。

execute(true) :- !. % trueならば成功
execute((P,Q)) :- !, execute(P), execute(Q). % P1,... ,Pnの各要素を左から順に試みる
execute(P) :- clause(P, Q), execute(Q). % ゴールPの定義を取得し、本体Qを試みる

純粋なPrologのメタインタプリタには組込述語がないとされるため、上記の通りであるが、実際のProlog処理系には組込述語が存在するため、上記定義では、第三節のclause(P, Q),の部分でPが組込述語の頭部になった時、この副目標が偽となっとしまうことがある。

このclause(P, Q),を実行する前に、ユーザ定義述語か、組込述語かを検査し、別の節に分離する必要がある。組込述語についてはclause(P, Q),することなしに、単にP,すればよい。

データとプログラムの形式が同じであることや、任意の演算子がユーザ定義可能なこと、Prolog自身が強力な構文解析機能を持つことなどもあり、このようなメタインタプリタをもとにPrologの一部機能を拡張した別言語のインタプリタを作成することは、比較的容易である。

関数型言語で高階関数を代表するmap()はPrologでも高階述語を使って定義可能である。しかし、関数型では出力は返り値だけであったが、Prologでは引数のどれかである。入力も複数あり得る。

しかもどの引数が入力であるか、あるいは出力であるかを示すモード宣言は、ほとんどの処理系で採用されていない。したがって、Prologでmap述語を構成するためには、対象となるリストの項はどの引数に当たるのかを陽に示さなくてはならない。

以下に、map述語を二つ示す。map/4とmap/5である。

map(_副目標,_要素,_対象リスト,_収集された副目標リスト) :-
        findall(_収集解,(
                    member(_要素,_対象リスト),
                    _副目標),_収集された副目標リスト).


map(_副目標,_要素,_対象リスト,_収集項,_収集項のリスト) :-
        findall(_収集項,(
                    member(_要素,_対象リスト),
                    _副目標),_収集項のリスト).

どちらも、対象リストの要素が反映して副目標の実行が変化して、それをリストに収集している。map/4は収集されるのが実行された_副目標 自体であるのに対して、map/5では実行された _副目標 自体ではなく、実行した時々に構成された _収集項 がリストに積み上がる。

以下にこのmap述語使用例を示す。

?- map(sub_atom(_文字列,S,Len,_,S),
       [_文字列,S,Len], [[abcde,0,2],[efgh,2,1],[qazxyz,1,2]], L).

L = [sub_atom(abcde,0,2,3,ab),sub_atom(efgh,2,1,1,g),sub_atom(qazxyz,1,2,3,az)]


?- map(sub_atom(_文字列,S,Len,_,S),
       [_文字列,S,Len], [[abcde,0,2],[efgh,2,1],[qazxyz,1,2]],S, L).

L = [ab,g,az]

となる。

上記事例で map は、_副目標の引数 _文字列,S,Len,Y が map述語の中で巧みに結びつけられているが、やはり難解である。これではfindall/3を直接使って、

?- findall(Y,(
         member([_文字列,S,Len],[[abcde,0,2],[efgh,2,1],[qazxyz,1,2]]),
         sub_atom(_文字列,S,Len,_,Y)),L).

L = [ab,g,az]

と記述してしまっても差がない。member/2が副目標として追加されただけの差である。一般に Prolog に於いて高階述語を使ったmap述語はあまり使用されないが、Prologにはこのように強力なメタ述語 findall や setof が既に存在している。しかも、関数型言語のように引数が事前評価されることはなく、引数に関数を置いて渡すこともできないため、map述語の効用は関数型言語のようには大きくない。

関係データベース

Prologはルールを持つデータベースであり、演繹データベースであるといえる。このルールの部分を全てtrueのみに限定した単位節のみからなる述語をデータベースと呼び、関係データベースに模して解釈されることが多い。このPrologのデータベースとリレーションナルデータベースは集合論的に類似しているが、異なる部分もあり、この部分がSQLなどデータベース照会言語との変換などで問題となる。

ここでは主としてふたつのデータベースの相違点に焦点を当てて、プログラミング手法を考えてみる。

関係データベースはテーブルの集まりであり、

テーブルとは属性(最終的に列となる)の定義域集合の全ての可能な値の組み合わせ(直積)の部分集合である。

属性が、四季と果物の二つ集合 {春,夏,秋,冬} {みかん,りんご,もも,いちご} の直積は

{(春,みかん),(春,りんご),(春,もも),(春,いちご),(夏,みかん),(夏,りんご),(夏,もも),(夏,いちご),(秋,みかん),(秋,りんご),(秋,もも),(秋,いちご),(冬,みかん),(冬,りんご),(冬,もも),(冬,いちご)} であるが、

この部分集合であるテーブル「季節の果物」は季節の果物 :: {(春,いちご),(夏,もも),(秋,りんご),(冬,みかん)} であるとする。

この直積の組み合わせの中で、真となる関係、あるいはその更に一部がテーブルだと考えればよいだろう。

これが関係データベースのテーブルの実体である。一方このテーブルをProlog単位節で表すと

季節の果物(春,いちご).
季節の果物(夏,もも).
季節の果物(秋,りんご).
季節の果物(冬,みかん).

となる。

Prologデータベースの第一節は「春といちごは季節の果物関係にある」というものであり、述語名として季節、果物が暗示されてはいるものの、実は第一引数が季節であり、第二引数が果物であるという情報はどこにもない。「季節」や「果物」といった属性(列)から出発した関係データベースとは明らかに異なる。

この相違に起因する問題がSQL問い合わせをProlog述語に変換する際に生じる。

以下のような、SQLに問い合わせを考える。

select 季節 from 季節の果物 where 果物 = 'もも'

これに相当するPrologの質問は

?- 季節の果物(X,もも).

X = 夏

であるが、問題点がふたつある。

1. 第一引数が果物なのか、第二引数が果物なのか定かでない。季節についても同様である。
2. 実はSQLの質問からだけでは季節の果物テーブルの属性がここに現れた「季節」と「果物」だけであるかどうか決められない。

例えば、「産地」などの属性も実はあるのかも知れない。つまり、何引数の述語を用意すれば良いのかさえ、わからないのである。

関係データベースに対するSQLのQueryとPrologの述語に対する質問を比較してみると、Prologの質問側には属性の情報が欠落しているということが分る。 一方、関係データベースのテーブルは属性(の集合)が出発点になっているのだから、この属性情報は既に根幹に定義されていて、SQLがこれを利用することは容易であるし、自然なことである。

したがって、Prolog述語がSQLと対等の関係でデータベースに質問し、相互に変換するためには、Prolog側に、

テーブル定義(季節の果物,1,季節).
テーブル定義(季節の果物,2,果物).

のような、補助情報を定義して置く必要がある。

ここでは、テーブル定義/3を管理情報の述語名として用いたが、Prologの規格によってこの役割を果たす述語名/アリティが規定されている訳ではないから、テーブル定義/3でなくてはならない、ということではない。

このような定義を前提にすれば、

属性名での照会(_テーブル名,_選択する属性名,_値) :-
        テーブルの引数をリストとして得る(_テーブル名,_引数のリスト),
        属性名と値を結びつける(_テーブル名,_選択する属性名,_値,_引数のリスト),
        テーブルを照会する(_テーブル名,_引数のリスト).

テーブルの引数をリストとして得る(_テーブル名,_引数のリスト) :-
        count(テーブル定義(_テーブル名,_,_),_アリティ),
        length(_引数のリスト,_アリティ).

属性名と値を結びつける(_テーブル名,_選択する属性名,_値,_引数のリスト) :-
        テーブル定義(_テーブル名,_何番目の引数,_選択する属性名),
        nth1(_何番目の引数,_引数のリスト,_値).

テーブルを照会する(_テーブル名,_引数のリスト) :-
        _テーブル =.. [_テーブル名|_引数のリスト],
        call(_テーブル).

count(P,Count) :-
        findall(1,P,L),
        length(L,Count).

length/2を使って変数だけからなる _引数のリスト を生成して、それと質問の引数である _値 をnth1/3を使って単一化している。変数と変数の間に = の制約を築いておく。 属性名と値を結びつける/4 がそれだ。

=.. は二引数の組込述語であるが、この述語は関数名を第一項に第二項以後を引数を順序に持つリストを複合項に変換するメタ述語と呼ばれる範疇の述語である。

?- P =.. [季節の果物,冬,みかん].

P = 季節の果物(冬,みかん).

となる。

これで属性名(列名)を与えての照会が、

?- 属性名での照会(四季の果物,果物,X).

X = いちご;
X = もも;
X = りんご;
X = みかん

可能となった。

次に、鍵名とその値を与えての参照は、

鍵による照会(_テーブル名,_鍵名,_鍵の値,_選択する属性名,_値) :-
        テーブルの引数をリストとして得る(_テーブル名,_引数のリスト),
        '鍵名と鍵値、選択する属性名と値を結びつける'(_テーブル名,_鍵名,_鍵の値,_選択する属性名,_値,_引数のリスト),
         テーブルを照会する(_テーブル名,_引数のリスト).

テーブルの引数をリストとして得る(_テーブル名,_引数のリスト) :-
        count(テーブル定義(_テーブル名,_,_),_アリティ),
        length(_引数のリスト,_アリティ).

'鍵名と鍵値、選択する属性名と値を結びつける'(_テーブル名,_鍵名,_鍵の値,_選択する属性名,_値,_引数のリスト) :-
        属性名と値を結びつける(_テーブル名,_鍵名,_鍵の値,_引数のリスト),
        属性名と値を結びつける(_テーブル名,_選択する属性名,_値,_引数のリスト).

属性名と値を結びつける(_テーブル名,_選択する属性名,_値,_引数のリスト) :-
        テーブル定義(_テーブル名,_何番目の引数,_選択する属性名),
        nth1(_何番目の引数,_引数のリスト,_値).

テーブルを照会する(_テーブル名,_引数のリスト) :-
        _テーブル =.. [_テーブル名|_引数のリスト],
        call(_テーブル).

count(P,Count) :-
        findall(1,P,L),
        length(L,Count).

このようにテーブル情報/3のような補助的情報を与えることを前提に、SQLに対応する述語を定義していくことによって、Prolog述語はオンメモリデータベースシステムとしての機能性を得ていくことになる。

実行例

?- 鍵による照会(季節の果物,果物,もも,季節,_値).

_値 = 夏

ここでは説明を簡素化するために、選択する属性値を一つに限定したが、一般には鍵、選択項それぞれをリストとして、複数の鍵の指定と、複数の選択項の値が得られるように設計されるべきであろう。

関係データベースとProlog述語の関係をProlog述語を関係データベースと見なすことでProlog処理系内にこれを築くことについて述べた。関係データベースの環境がPrologで記述され、かつSQLはPrologの述語とその呼び出しに変換される。

これとは別に、 Prologの節の中で文字列としてのSQLを生成し、これを外部インターフェイスを経由して、関係データベース管理システムに送り解集合をワークエリアに用意させて、これを順にフェッチしていくということは、多くのProlog処理系でライブラリを用意して実現している。

この場合は必ずしもPrologによって完全なデータベース環境を築く必要はなく、データベース的なデータ管理は外部の関係データベース管理システムに頼ることになる。Prolog側ではアプリケーションの要求に応じて、SQLのパターンに対応する述語を用意する。この述語は、テーブル名、属性名、とそれぞれの値といった情報を引数に持ち、その情報から、 select, from, where, and, join, group by, といったSQLのキーワードとその情報を組み合わせるロジックを担う。そして一旦、SQLの関数を組み合わせて並べたリストを生成する。さらに、それを組込述語 atomic_list_concat/3　などで、結合して、SQL文字列が生成される。

生成されたSQL文字列を処理系のライブラリで用意されたインターフェイス述語を呼び出して、その引数として渡す。求めるデータを関係データベース管理システムが選択して返してくるまでこの呼び出しで待つことになる。

それでは、Prologの中で、SQLの表現を展開することはできるであろうか。オペレータ定義を駆使して、

select * into _解 from _関係表名 where _属性名 = _値 :- ・・・

のような定義をして、

?- select * into X from 季節の果物 where 果物 = もも.
X = [[夏,もも]]

のように、SQLに模した表現でPrologにデータを取得することは部分的には実現できる。これができれば、このSQLに見立てられる関数構造をSQL文字列に変換して、それを関係データベースのインターフェイスに与えればよい。

しかし以下のような表現はどのようにオペレータ定義を工夫してもできない。

select 季節,果物 into X from 季節の果物 where 果物 = もも.

ここでは詳細には述べないが 季節,果物 の表現をPrologでは取れない。季節と果物の間のカンマを境に、それ以前と以後が副目標として分離されてしまう。

select (季節,果物) into X from 季節の果物 where 果物 = もも.

このように括弧で括れば、Prolog述語として定義可能になるが、今度はこの括弧が SQL の構文違反になる。このように双方の構文規則に整合しない癖があり、SQLとPrologとの間に完全に互換性のある構文を得ることは難しい。

集合

Prologでは特別な集合表現は用意されていない。

例えば、{_,_, ... ,_} が集合を表すというような規則はなく、リストが代用されることが普通である。

リストが集合に利用されると、不都合な点が二つ存在する。

1. リストは要素の重複が許されるが、集合は重複が存在しない。
2. リストは要素の順序に意味があり、それを前提にして使用されている。一方、集合の要素には出現順位のような概念はない。

リストでは当たり前に存在する [1,1,4] は集合では [1,4] であり、しかも [4,1] でも集合として等しい。 集合演算の引数として、[1,1,4]が与えられた時に、これを、[1,4]または[4,1]と理解するかエラーと考えるかの選択がまず存在する。

もしもPrologに集合型が存在したならば、集合::[1,4] = U1 であり、同じく 集合::[4,1] = U2 であったとすれば、 U1 = U2 、というような単一化の拡張があり得たかも知れない。しかしながら、Prologはこのような道を歩まず、アトムと数だけを例外として、型を考慮しない単一化の道を進んだ。そういうことで、

型付けのないPrologではこのように利用者が集合としてリストを見なすことが集合プログラミングの前提になる。さらに、四季を表す集合を例に取ると、集合が[春,夏,秋,冬]の順序で渡されるとは限らないことを常に意識している必要がある。集合を表すリスト [春,夏,秋,冬] と [秋,春,冬,夏] は集合としては等しいと考えられるが

?- [春,夏,秋,冬] = [秋,春,冬,夏].
false.

リストとしては集合として等しいからといって単一化できるとは限らない。

Prologの組込述語として is_set/1, subset/2, subtract/3, intersection/3, union/3, さらにメタ述語として setof/3 などが集合演算のために用意されている。プログラマはできる限り、この組込述語のみで集合演算を行うように心がけることによって、リストと集合の意味の齟齬に起因する誤謬を、回避することができる。

Prologには同一の集合を定義する述語が用意されていないため、組込述語subset/3を使って 集合として等しい/2 を定義してみよう。

集合として等しい(_集合_1,_集合_2) :-
        subset(_集合_1,_集合_2),
        subset(_集合_2,_集合_1).

これで、

?- 集合として等しい([春,夏,秋,冬],[秋,冬,夏,春]).
true.

?- 集合として等しい([春,夏,秋,冬],[秋,冬,夏]).
false.

となる。ただし、論理変数を複数導入した例では、解が

?- 集合として等しい([1,2,3],[X,3,Y]).
X = 1,
Y = 2.

?-

のみで、順序に関わりなく充足しているというべきで、X = 2,Y = 1 という解は得られない。この点は特に注意を要する。

この集合として同一を中置演算子として定義してみる。

:- op(700,xfx,===).

(L1 === L2) :- 集合として等しい(L1,L2).

これで

?- [2,1,3] === [1,2,3].
true.

となる。演算子の導入は後々までプログラミングに影響を与えるものだから、極めて慎重に行う必要はあるが。

既に、言語の基本仕様の中でリストの内包表記はできないことを書いた。それでは、これがリストではなく集合であるとどうであろうか。整数 5,7,9 を共通の性質で括ったとする。その一つの括り方が 5以上10以下の奇数 であるが、これをPrologでは以下のように表現する。

'5以上10以下の奇数'(5).
'5以上10以下の奇数'(7).
'5以上10以下の奇数'(9).

これを 5以上10以下の奇数 の外延的な表記と見做すことは自然である。則ち、述語とは集合であるという視点である。

さらに、以下のようなPrologの非決定性のルール節定義

'5以上10以下の奇数'(N) :-
        between(5,10,N),
        1 is N mod 2.

は、集合 5以上10以下の奇数 の内包的な表記と見做すことができる。ただしどちらの例も、リストの内包表記ができないことを述べた場合と同様、この表現を集合型として引数に持ち回って利用するというようなことはできない。

このように述語を集合と見做すという視点は、Prologは述語論理に基礎を持つ言語であり、それ故に述語と集合の極めて親近した関係から、根拠を持つと考えられる。

副作用について

Prologプログラミングの中で常に留意するべきものとして副作用がある。

副作用を考える場合、それではPrologに於いて作用とは何かを示す必要があるだろう。これは、目標(副目標)の実行に伴う真偽値のことである。Prologが質問に対して返すものは真か偽のみである。これ以外に処理系の動作に影響のある変化が起こった時、それを副作用という。ただし真か偽に決まるための論理変数の単一化による代入は副作用ではないとする。

大域変数など、破壊代入を伴う機能は提供されないというのがPrologの原則であるが、大域変数を用意してプログラマに手続き言語的な便宜を供している処理系もある。また、次期ISO標準規格の議論の中でも大域変数の使用が提案されている。

しかし、以下の副作用についての解説では、大域変数は利用できないこととして話を進める。

組込述語もなく、もちろんカットもなく、ユーザが定義した述語だけで実行される純Prologに於いては、副作用は生じない。述語論理のイメージに近い純Prologはこの系の規範となる。したがってPrologプログラマにとって、この純Prologからの逸脱を象徴する副作用は厄介な存在である。

副作用を大別すると、

・ 述語定義に変更を与えるもの。

・ 入出力に伴うもの。

・ 処理系が管理するプロパティ情報の参照や変更。

がある。

最初に述語定義に変更を与えたため起こる副作用の例を示そう。年齢合計/1は年齢/2を関係データベースと見做し、この第二引数を全て合計したいという述語である。

年齢(尾崎,65).
年齢(山下,37).

:- dynamic(一時年齢合計/1).

年齢合計(_年齢合計) :-
    assertz(一時年齢合計(0)),
    年齢(_,_年齢),
    retract(一時年齢合計(_年齢合計_1)),
    _年齢合計_2 is _年齢合計_1 + _年齢,
    assertz(一時年齢合計(_年齢合計_2)),
    fail.
年齢合計(_年齢合計) :-
    retract(一時年齢合計(_年齢合計)).

これは強制的な失敗とバックトラックを使って述語定義とその解消を繰り返して、年齢を合計(集約)するものだ。見れば分るとおりどの言語のそれにも増しても冗長なコードである。このようなコードだけは決して書きたくないとほとんどのPrologプログラマは思っていて、実際にこのタイプの述語定義が書かれることはない。それでは、どのように集約プログラムを書くのだろうか。

この年齢合計は、以下のように定義するのが普通である。

年齢合計(_年齢合計) :-
    findall(_年齢,年齢(_,_年齢),_年齢のリスト),
    加算(_年齢のリスト,_年齢合計).

加算([],0).
加算([_年齢|R],_年齢合計) :-
    加算(R,_年齢合計_2),
    _年齢合計 is _年齢 + _年齢合計_2.

findall/3で一旦リストに年齢を取り出した上で、これを再帰的に加算する。洗練された表現であるし、一般にはこれで良しとする。しかし、実はfindall/3自体に上記のようなassert/retractのからくりが含まれている。findallは第二引数が真になった場合、第一引数によって指定された項を収集するものだが、その収集する場が乃ち副作用であるという関係になる。findallが組込述語になっていて、C言語などでその記述がされている場合は、普通に破壊代入を使ってこれを実現していると見て間違いない。findall/3を利用しているプログラマは意識していないかもしれないが、findall/3にはこのような副作用が含まれ、しかし、それが利用者には隠蔽されているのである。

副作用という観点から少し外れるが、Prologと関係データベースの関係にもう一度触れる。

Prologの述語の定義節はそれぞれが論理的に全く独立で何の連関もない。連関がないものを集約できるわけもない。述語の節定義を関係データベースと見做した年齢/2であるが、そのことの本質的な無理が露呈していると考えることもできる。findall/3は連関がないものを、順序性を持つリストに組み立てることによって連関を付けたのである。

述語を関係データベースと見做した場合、更新や削除は当然副作用である。

氏名をキーとした年齢の更新(_氏名,_更新する年齢) :-
    retract(年齢(_氏名,_)),
    assertz(年齢(_氏名,_更新する年齢)).

これは、先ほどの一時年齢合計/2の場合とは異なり、確信犯的に副作用を使用していると云って良い。

述語定義に変更を与える副作用としては、組込述語のasserta/1,assertz/1,retract/1などがあり、これが実行された前と後では、同じ目標を与えたとしても真偽値に変化があったり、引数の単一化の決まり方に変化が起こり、プログラマの予期に反する結果が起こる可能性がある。また上記の例のように冗長な表現になる。それらがこのタイプの副作用が嫌われる理由である。

入出力に伴う副作用は、組込述語の read,get,get_char,write,put,put_charなどの実行でおこり、オペレーションシステムに管理されるファイル指示子が変化してしまったり、画面に表示、用紙に印字されるなど、元に戻すことが極めて難しい変化が起こる。キーボードからの入力も副作用である。この中でもファイルの指示子などは一度進んでしまうと、簡単には元に戻することができない場合もあり、再実行を指向するバックトラックによる制御と整合しなくなることも多い。

入出力に伴う副作用の例を示す。

奇数が入力されるまで整数をリストに得る([]) :-
    read(_奇数),
    1 is _奇数 mod 2.
奇数が入力されるまで整数をリストに得る([_整数|R]) :-
    read(_整数),
    奇数が入力されるまで整数をリストに得る(R).

read/1で整数を得る。奇数なら終了するのだが、偶数だと第一節は失敗する。ここでは、_奇数に偶数が入力されて偽となったのである。だからといってファイルの指示子が元に戻ることはない。第二節に移行して、 read(_整数) が実行されると、既に読み込んだ情報の次の指示子に基づいて入力が得られる。この結果、第一節で読み込んた偶数はリストに取得されることなく飛ばされてしまう。

ここでは最も単純な例を挙げたが、ほとんどの入出力部分には多かれ少なかれ、このような危険が潜んでいる。

上記副作用プログラムの適切な述語定義を示す。これでread/1が一箇所に絞られたから読み飛ばしの危険がなくなる。

奇数が入力されるまで整数をリストに得る(_偶数リスト) :-
    read(_整数),
    奇数が入力されるまで整数をリストに得る(_整数,_偶数リスト).

奇数が入力されるまで整数をリストに得る(_奇数,[]) :- 奇数(_奇数),!.
奇数が入力されるまで整数をリストに得る(_偶数,[_偶数|R]) :-
    奇数が入力されるまで整数をリストに得る(R).

奇数(_奇数) :- \+(0 is _奇数 mod 2).

処理系が管理するプロパティ等の情報もほとんどの場合副作用である。処理系の挙動を制御するために使うものが多いが、事実上の大域変数の破壊代入である。目標(質問)の実行から停止までの間に、度々変更するような使い方をするならば、プログラムの分かりやすさを損なう。一般にこのタイプの副作用があまり問題にならないのは、設定の変更が滅多に起こるものではないからである。使い方が難しいこともあり、あまり頻繁に使用されるというものではない。しかし、prolog_propertyといった述語で管理される情報は増える傾向にある。

述語定義に変更を加えるもの、入出力に伴うもの、処理系の管理するプロパティの書き換え。どれを取っても、副作用が生じると論理的な必然だけでは理解することが済まなくなり、コードの見通しが悪くなる。

現在のPrologの規格では、手続き型のほとんどの言語とは異なり、大域変数などの破壊代入(既に保持されている値を上書きする形で更新される代入)は基本的にできないことになっている。もちろん破壊代入が許される場合はここを舞台に起こる変化は全て副作用である。いつ記述されたか必ずしも明らかにできない変数に代入された値が、後に利用されることはプログラムの理解を著しく損ねる。Prologでは原則、目標の引数に現れた値は全ての解を得て完了した時点で、二度とこれを利用出来なくなる。多くの場合情報を積んであったスタックがPOPされてしまう。

実務的なプログラムでは、Prologの単一化と導出、バックトラックを使って記述されるロジックを基礎に、その間に、表示を代表とする副作用述語を挿入記述することによって、実用的な機能を実現している。 定理証明やデータベースの参照に於いては、このような副作用の挿入記述なしに、インタプリタ上で解を確認したり、真偽値を得ることだけで、目的を達成できる。しかし、他のほとんどのプログラムでは、必要な箇所で、適切な時期に、整理したデータの開示を要求される。 このような表示はPrologに於いても、ほとんど全てが副作用であって、「Prologプログラムとはロジックの上に副作用をちりばめることだ」と言っても過言ではない。現実に、データベースの更新の例を挙げて述べた表現のように、「確信犯的」に副作用述語が利用されている。

そのこともまた事実であるが、Prologコミュニティではプログラムコードの副作用を極力少なく書くことが強く奨励されている。多くのプログラマが副作用に注意し、これを減らす努力をするし、大域変数が許された処理系の利用者も最小限にしかこれを使わない。ほとんどのPrologプログラムには、破壊代入に見られるような一命令で与えられる変化で全体の制御が変わってしまうという部分はない。これは、副作用として現れた変化を利用することはしないという姿勢、意識がPrologプログラマの間で貫かれ、共有されているからである。

Prologの制御の焦点は、単に述語の引数の単一化にある。副作用の存在が、実際のPrologプログラムの中で、単一化を注視することだけでプログラムを理解することの妨げになっている例を見ることは、ほとんどない。

Prologによる構文解析

Prologは構文解析を行うのに向いたプログラミング言語である。元々、Prologは論理を利用した自然言語処理のために開発された。実際、文脈自由文法のトップダウン構文解析の動きはProlog自身の動きと同じである。

限定節文法

Prologには限定節文法（英: definite clause grammar）と呼ばれる特別な表記法が用意されている。文脈自由文法を拡張したもので、文法を記述する場合は :-/2 ではなく -->/2 を用いる。

 head --> body.

文法での非終端記号はPrologの項で、終端記号は非終端記号と区別するためリスト内の項で表現する。付加的な条件や動作を指定したい場合、文法の最後に任意のProlog述語を { } で囲んで記述する。限定節文法の例を以下に示す。この例では数式を解析し計算を行う。

expression(E) --> term(X), [+], expression(Y), {E is X + Y}.
expression(E) --> term(X), [-], expression(Y), {E is X - Y}.
expression(E) --> term(E).

term(T) --> num(X), [*], term(Y), {T is X * Y}.
term(T) --> num(X), [/], term(Y), {T is X / Y}.
term(T) --> num(T).

num(N) --> [+], num(N).
num(N) --> [-], num(X), {N is -X}.
num(N) --> [N], {number(N), between(0, 9, N)}.

これはバッカス・ナウア記法で書かれた以下の文法規則に計算の動作を付加したものと同じ意味を持つ。

<expression> ::= <term> "+" <expression> | <term> "-" <expression> | <term>
<term> ::= <num> "*" <term> | <num> "/" <term> | <num>
<num> ::= "+" <num> | "-" <num> | 0..9

実行結果は以下のようになる。

?- expression(Z,[-, 2, +, 9, *, 2, +, 3, *, 5],[]).
Z = 31

このように直接計算を行うのではなく抽象構文木を作成するような文法規則を作成することもできる。構文木はPrologの項として素直に表現できるため、その後の機械語へのコンパイルや最適化などを行うことも可能である。

次の、極めて簡単な日本語の解析例を見てみよう。先程の計算例では頭部の引数は変数であったが、文法的な解析結果を項として積み上げるために、ここでは変数でなく、直接ここに項の構造を記述してしまうことにする。

文(文(_主部,_述部)) --> 主部(_主部), 述部(_述部).

主部(主部(_名詞句)) --> 名詞句(_名詞句).

名詞句(名詞句(_名詞,_後置詞)) --> 名詞(_名詞),後置詞(_後置詞).

名詞(名詞(サザエ)) --> [サザエ].
名詞(名詞(マスオ)) --> [マスオ].

後置詞(後置詞(が)) --> [が].
後置詞(後置詞(は)) --> [は].

述部(述部(_動詞)) --> 動詞(_動詞).
述部(述部(_形容詞)) --> 形容詞(_形容詞).

動詞(動詞(泳ぐ)) --> [泳ぐ].

形容詞(形容詞(美しい)) --> [美しい].
形容詞(形容詞(速い)) --> [速い].

注目するべきことは、本体が極めて簡素で読み易いことだ。

ここでの例は厳密な文法であるとは言えないが、以下のような解析や文の生成が可能になる。

?- 文(A,[サザエ,は,速い],B).
A = 文(主部(名詞句(名詞(サザエ), 後置詞(は))), 述部(形容詞(速い))),
B = [] ;
false.

?- 文(A,[サザエ,は,速い,マスオ,が,泳ぐ],B).
A = 文(主部(名詞句(名詞(サザエ), 後置詞(は))), 述部(形容詞(速い))),
B = [マスオ, が, 泳ぐ] ;
false.

?- 文(A,B,C).
A = 文(主部(名詞句(名詞(サザエ), 後置詞(が))), 述部(動詞(泳ぐ))),
B = [サザエ, が, 泳ぐ|C] ;
A = 文(主部(名詞句(名詞(サザエ), 後置詞(が))), 述部(形容詞(美しい))),
B = [サザエ, が, 美しい|C] ;
A = 文(主部(名詞句(名詞(サザエ), 後置詞(が))), 述部(形容詞(速い))),
B = [サザエ, が, 速い|C] ;
A = 文(主部(名詞句(名詞(サザエ), 後置詞(は))), 述部(動詞(泳ぐ))),
B = [サザエ, は, 泳ぐ|C] ;
A = 文(主部(名詞句(名詞(サザエ), 後置詞(は))), 述部(形容詞(美しい))),
B = [サザエ, は, 美しい|C] ;
A = 文(主部(名詞句(名詞(サザエ), 後置詞(は))), 述部(形容詞(速い))),
B = [サザエ, は, 速い|C] ;
A = 文(主部(名詞句(名詞(マスオ), 後置詞(が))), 述部(動詞(泳ぐ))),
B = [マスオ, が, 泳ぐ|C] ;
A = 文(主部(名詞句(名詞(マスオ), 後置詞(が))), 述部(形容詞(美しい))),
B = [マスオ, が, 美しい|C] ;
A = 文(主部(名詞句(名詞(マスオ), 後置詞(が))), 述部(形容詞(速い))),
B = [マスオ, が, 速い|C] ;
A = 文(主部(名詞句(名詞(マスオ), 後置詞(は))), 述部(動詞(泳ぐ))),
B = [マスオ, は, 泳ぐ|C] ;
A = 文(主部(名詞句(名詞(マスオ), 後置詞(は))), 述部(形容詞(美しい))),
B = [マスオ, は, 美しい|C] ;
A = 文(主部(名詞句(名詞(マスオ), 後置詞(は))), 述部(形容詞(速い))),
B = [マスオ, は, 速い|C].

二番目の例は与えられた語リストの途中で文の解析が完了した場合は、質問の第三引数Cには残りの未解析部分のリストが返されることを示している。

最後の例はBに変数を置き、可能な全ての文を生成させている。第一引数に積み上がった項が第二引数の語リストの「意味」であると考えられる。

限定節文法の文法規則は、Prologの構文とは全く独立したもののように見えるが、実際にはProlog節を見やすくするための糖衣構文である。他のプログラミング言語でのマクロ展開のように、文法規則読み込み時にPrologの述語に変換される。

変換規則は expand_term/2 で定義されている。たとえば、

p(X,Y) --> q(X), r(X,Y), s(Y).

の文法規則は

p(X,Y,S0,S) :- q(X,S0,S1), r(X,Y,S1,S2), s(Y,S2,S).

の節に変換され、付加された変数間で解析の情報が受け渡される。