Prolog
プログラム例
[編集]Prologのプログラム例を以下に示す。
Hello world
[編集]"Hello World"は1970年代から「コンピュータはプログラム言語を使って、こんなにも簡単に動くものですよ」ということを感じさせる課題として好んで使われ、今日では教則本の冒頭にこれを置くことが半ば様式化してしまった。しかしPrologの述語は基本的に真偽値を問うものであって、入出力は副作用として疎ましい存在であり、冒頭にHello World述語を持ってくることには反対意見が強い。
そういう事情を理解した上で、ここでは、この課題をPrologプログラミングの導入として利用してみよう。
Prologは質問すると、処理系が答えを返す系である。"Hello World!"という表示は処理系が行うのだから、その前に質問がなくてはならない。質問を "hi" とする。
hi :-
write('Hello World!\n').
writeは引数が一個の組込述語である。引数の内容を表示する。world!の後の"\n"は改行することを意味する。
実行例で見てみよう。Prologインタプリタは一般にプロンプトとして "?- " が表示された後に、ユーザーが質問を入れる。
?- hi.
Hello World!
述語名が hi であっても hi(a) :- や hi(1,2,3) :- の定義もあるかもしれない。Prologではこれらを区別するために、それぞれhi/0 hi/1 hi/3 のようにスラッシュの後に引数の数を書いて区別する。ここでは hi/0 である。
質問 hi に対して、定義済みの hi が呼び出されて、その中でさらに write('Hello World!\n') が呼び出された。
ここでは "Hello World!\n" は組込述語 write/1 の中に直接記述されたが、一般にはこのような原初的な情報はデータベース述語によって管理され、そこから引き出されて使われる。
hi :-
answer(hi,S),
write(S).
answer(hi,'Hello World!\n').
S は先頭が英大文字だから論理変数である。answer/2はプログラマが定義したデータベース述語である。
副目標answer(hi,S)は述語定義 answer/2 と融合され、各引数が単一化される。第一引数はatom同士でしかもhiで完全一致、第二引数はSと'Hello Wolrld!\n'が単一化されて、これは単一化のルールにより無条件に論理変数Sは'Hello World!\n'となる。そのS、乃ち'Hello World!\n'をwrite/1する。
さらにこのプログラムに bye を追加してみよう。
hi :-
answer(hi,S),
write(S).
bye :-
answer(bye,S),
write(S),
halt.
answer(hi,'Hello World!\n').
answer(bye,'See you again!\n').
述語 bye/0 の本体 (:- の右側) の最後にある halt は0引数の組込述語で処理系を終了させる。
実行例
?- hi.
Hello World!
?- bye.
See you again!
#
Hello World からの導入はこんなところだろう。
家系図
[編集]よく知られる漫画作品・「サザエさん」の家系図(部分)をPrologで表現する。
親子(波平,サザエ).
親子(ふね,サザエ).
親子(波平,カツオ).
親子(ふね,カツオ).
親子(波平,ワカメ).
親子(ふね,ワカメ).
親子(マスオ,タラオ).
親子(サザエ,タラオ).
夫婦(波平,ふね).
夫婦(マスオ,サザエ).
このように、本体がない、あるいは本体のtrueが省略された定義を、単位節と呼ぶ。親子、夫婦の両述語はともに第一引数または第二引数をキーとしてデータを参照することができる一種のデータベースと考えることができる。
このような単位節データベースは全ての知識の基礎であって、必ずしもすぐにプログラムとして利用されなくても価値がある。ノートに書き付けるように身の回りの知識を定義していけばよい。
備忘録としての単位節データベースへ実際に問いかける例を示そう。「サザエの親は誰か」という質問をする。
?- 親子(_親,サザエ).
_親 = 波平
ここで一旦処理系は停止する。この解に満足な時はただ改行する。
?- 親子(_親,サザエ).
_親 = 波平 ;
_親 = ふね.
?-
1) 波平に満足できない。 2) 波平以外の解がほしい。 そんな場合には停止中のカーソルにセミコロン(;)を入力すると、次の解を示してくる。_親 = ふね だ。他にも親はいないものかと さらにセミコロンを入力すると、もうこれ以上解はないと、この処理系では入力したセミコロンをピリオドに置き換えて表示して 質問は終わりとなる。
孫の定義
[編集]前題の家系図が既に定義済みという前提で、祖父-孫 関係を定義してみよう。
'祖父-孫'(波平,タラオ).
祖父・孫の関係になれるのは波平とタラオだけである。'祖父-孫'という述語名はハイフンのような記号を含むアトムとなるため、 シングルクォートで囲む必要がある例として示した。述語名はこれに限らず、 祖父孫 でも 祖父と孫 でも 祖父孫関係 あるいは単に 祖父 でも、特にこうしなくてはいけないというルールはない。処理系への知識の与え方は基本的に自由である。
今度は、「孫」を定義する。上記の定義に倣うなら '祖父母-孫' 関係ということになるが、ここでは単に「孫」とする。
孫(波平,タラオ).
孫(ふね,タラオ).
実行例を示そう。
?- 孫(X,タラオ).
X = 波平 ;
X = ふね.
?-
一般に質問する時は、入力の負担を減らすために、最少の文字数となる XとかA,Bなど英大文字一文字を論理変数に置くことが多い。 Xを使うことが多いのは、方程式の解となる変数をXとする習慣を引き継いだものと考えられる。 もちろん家系図の時のように ?- 孫(_祖父母,タラオ). と質問しても構わないし、常にそういう習慣があるならそれが望ましい。
孫を具体的な人と人の関係として定義して見たが、以下のような定義も可能である。このような定義をルールという。
孫(_祖父または祖母,_孫) :-
親子(_祖父または祖母,A),
親子(A,_孫).
Aは孫から見ると親であるが、祖父または祖母から見ると親ではないので、_親 とはせずに、英大文字の A で抽象化した。 本体の二つの副目標である親子/2のそれぞれの引数に共通のAが存在することが重要である。孫の親と祖父または祖母の子が同一人物のAであることを示している。だから
% これでは具合が悪い!
孫(_祖父または祖母,_孫) :-
親子(_祖父または祖母,_祖父または祖母の子),
親子(_孫の親,_孫).
行の先頭に % がある一行目は「註釈行」でありプログラム実行の対象とはならない。述語形式とは限らない自由な文を書くこともできる。
_祖父または祖母の子 と _孫の親 とは単一化できていないため、変数名から同一が類推できるとしても、処理系は A の時のように同一のものと扱わない。
それならば、_祖父または祖母の子 と _孫の親 を単一化させてしまえばよい。それを実行したのが下のコードである。
孫(_祖父または祖母,_孫) :-
親子(_祖父または祖母,_祖父または祖母の子),
親子(_孫の親,_孫),
_祖父または祖母の子 = _孫の親.
単一化述語である =/2 で二つの変数が実は同じものであるが明確になる。二つの視点からそれぞれ別の変数シンボルになってしまうことは屡々ある。そのような場合は単一化で解決する。
家系図の中で、このような二つの親子関係が連接して、孫関係を充たすのは、
?- 孫(X,Y).
X = 波平,
Y = タラオ;
X = ふね,
Y = タラオ .
?-
である。
リスト要素の加算
[編集]与えられたリスト要素を加算する。再帰的な定義である。
リスト要素の加算([],0).
リスト要素の加算([N|R],S) :-
リスト要素の加算(R,S1),
S is S1 + N.
1要素少ないRの加算計がS1ならばSはS1にNを加えたものだ、という宣言である。
実行例: このように定義しておけば、以下の質問は
?- リスト要素の加算([1,2,3,4,5,6,7,8,9,10],X).
X = 55
となる。
加算は以下のように、二つの述語に分離して、引数をひとつ増やした述語を作ると累算部分がはっきりしてわかりやすい。加算を担うのは後の方、引数が3個ある方の述語だ。述語名は引数の数が違うから同じ リスト要素の加算 で構わない。リストから数を取り出すと、この第二引数に加算していく。
% 1
リスト要素の加算(L,S) :-
リスト要素の加算(L,0,S).
% 2
リスト要素の加算([],S,S).
リスト要素の加算([N|R],S1,S) :-
S2 is S1 + N,
リスト要素の加算(R,S2,S).
リスト要素の加算/3 の第一節の %1 の下の
リスト要素の加算([],S,S).
というところがProlog独特のテクニックである。
第一引数のリストが空になったとき、第二引数に累計が存在するのだが、
最初の %1 述語リスト要素の加算/2の副目標
リスト要素の加算(L,0,S).
の第二引数では初期値0と値を決めて引数に渡しているため、この第二引数から値を受け取ることは不可能である。
そこで、第三引数として一つ余分な引数を設けて、そちらを変数にして置けば、最終的にその引数が単一化されることによって値を受け取ることができるという訳だ。その第二引数と第三引数の単一化を行っているのが、%2 の リスト要素の加算/3の第一節の
リスト要素の加算([],S,S).
である。
この述語の第二節第三引数がともにSで同一であることも重要である。
リスト要素の加算([N|R],S1,S) :-
S2 is S1 + N,
リスト要素の加算(R,S2,S).
この部分が束縛されないまま、単に同一の変数であることが示されている。
質問の第一引数が[]になれば、この述語の第二節が融合されて、質問側に用意されている第二引数の加算計がこれに単一化される。
リスト要素の加算([],S,S).
これまで第三引数は全て同一ということになっているため、この第三引数経由で加算値が質問の第二引数に返される。
単位節要素の加算(集約問題)
[編集]単位節(本体のない事実上のデータベース定義)要素の加算。 実例として次の単位節データベースを考える。
年齢(山田,35).
年齢(大島,20).
年齢(清川,28).
ここでは年齢の合計を計算する。 簡単なデータベースの参照は、
?- 年齢(A,B).
A = 山田,
B = 35;
A = 大島,
B = 20;
A = 清川,
B = 28 .
?-
Prologの述語の中のそれぞれの節に現れる要素は他の節から完全に独立である。すなわち一つの節の中の値は別の節からは参照できない。 山田を得たとき、大島を得たとき、清川を得たときはそれぞれ独立している。以前の変数の束縛は解かれてしまっている。
大島の20を得たときには、山田の35の情報は失ってしまっているということになる。
これでは加算のような集約問題を解決できない。
このことを可能にするために、メタ述語 findall/3 が存在する。 findall/3 はSQLのselect文に似た述語であり、述語を実行した際に任意の値をリストに集めることができる。
年齢(山田,35).
年齢(大島,20).
年齢(清川,28).
年齢合計(X) :-
findall(N,年齢(_,N),L),
リスト要素の加算(L,X).
本来、情報の連関のない述語 年齢/2 のそれぞれの節を、連関を持つデータ構造であるリストに取り込むことによって、集約を可能とする。
実行例:
?- 年齢合計(X).
X = 83
理解を深めるために、findall以下を直接質問として呼び出してみよう。
?- findall(N,年齢(_,N),L),
リスト要素の加算(L,X).
L = [35,20,28],
X = 83
となる。findallは強力な述語であるが、対象となる定義節数が極めて多い場合、例えば、1000万節を越えるような場合、スタックオーバーフロー等のエラーが発生する危険が生じる。内部メモリにリストとして情報の連鎖を生成するのだから、やむを得ないことではあるが、注意が必要である。
相加平均
[編集]算術平均ともいい、一般に平均値といった場合これを指す。標本はリストとして保持しているとする。基本的には加算と同じだが、同時にリストの標本数も数える。第二、第三引数にそれぞれ初期値 0 を置き、これに標本数と値を加算していく。
相加平均(_標本リスト,_相加平均) :-
相加平均(_標本リスト,0,0,_相加平均).
相加平均([],_標本数,_累計,_相加平均) :-
_標本数 > 0,
_相加平均 is _累計 / _標本数.
相加平均([_値|R],_標本数累計_1,_累計_1,_相加平均) :-
_標本数累計_2 is _標本数累計_1 + 1,
_累計_2 is _累計_1 + _値,
相加平均(R,_標本数累計_2,_累計_2,_相加平均).
この述語では要素数や累計を求められていないため、これを入手するための変数は用意されていない。その代わりにリストが空の時に相加平均が計算されて単一化される。これが平均値の述語定義だが、多くの場合ここまでプログラマが定義する必要はない。下記のように、組込述語を含めて、定義済みの述語を組み合わせて相加平均は定義される。上記の要素数のカウント部分は独立して length という組込述語となっている。したがって、相加平均の定義は
相加平均(_標本リスト,_相加平均) :-
length(_標本リスト,_標本数),
リスト要素の加算(_標本リスト,_合計),
_相加平均 is _合計 / _標本数.
で構わない。
標準偏差
[編集]相加平均が使われる定義の一つ標準偏差の定義である。標準偏差本体の定義の前にこの相加平均の計算が完了している必要がある。
標準偏差(L,V) :-
length(L,N),
相加平均(L,M),
標準偏差(L,N,M,0.0,V).
標準偏差([],N,M,S,V) :-
V is sqrt(S / (N - 1)),!.
標準偏差([A|R],N,M,S,V) :-
S1 is (A - M) ^ 2,
S2 is S + S1,
標準偏差(R,N,M,S2,V).
is/2評価の中に現れる関数sqrt()で平方根を求める。
最大値、カットの用法
[編集]リストの最大値を求める。併せて、カットの典型的な用法について説明する。最初に初期値を設定して、それと再帰的に比較する。 初期値はリストの中の要素であれば、何でも構わないのだが、ここでは第一要素を使う。
最大値(_標本リスト,_最大値) :-
_標本リスト = [_第一要素|R],
最大値(R,_第一要素,_最大値).
最大値([],_最大値,_最大値).
最大値([_要素|R],_最大値_1,_最大値) :-
_要素 > _最大値_1,!, % ! の位置に注意。
最大値(R,_要素,_最大値).
最大値([_要素|R],_最大値_1,_最大値) :-
最大値(R,_最大値_1,_最大値).
_要素がこれまでの最大値を超えない時は最後の節が選択される。超えた場合は第二節の「_要素 > _最大値_1,!」のカットが働き最後の節が選択されることはなくなる。引数が3の最大値の第二節に「!」がある。これがないと、
最大値(_標本リスト,_最大値) :-
_標本リスト = [_第一要素|R],
最大値(R,_第一要素,_最大値).
最大値([],_最大値,_最大値).
最大値([_要素|R],_最大値_1,_最大値) :-
_要素 > _最大値_1,
最大値(R,_要素,_最大値).
最大値([_要素|R],_最大値_1,_最大値) :-
最大値(R,_最大値_1,_最大値).
?- 最大値([2,4,6,8,3],X).
X = 8;
X = 6;
X = 8;
X = 4;
X = 8;
X = 6;
X = 8;
X = 3;
X = 2;
false.
?-
というようなことが起こりうる。バックトラックして来たときにそれまでで最大としたものを、「;」の入力で「それではない」と否定されて、撤回してしまう。せっかく見つけ出したそれまでの最大値であるべきものがこれまでの最大値として使われないためである。「!」を入れることが有効な場所を、最初の定義も含めて示す。
%%% 案1 %%%
最大値(_標本リスト,_最大値) :-
_標本リスト = [_第一要素|R],
最大値(R,_第一要素,_最大値).
最大値([],_最大値,_最大値).
最大値([_要素|R],_最大値_1,_最大値) :-
_要素 > _最大値_1,!, % ! の位置に注意。
最大値(R,_要素,_最大値).
最大値([_要素|R],_最大値_1,_最大値) :-
最大値(R,_最大値_1,_最大値).
%%% 案2 %%%
最大値(_標本リスト,_最大値) :-
_標本リスト = [_第一要素|R],
最大値(R,_第一要素,_最大値).
最大値([],_最大値,_最大値).
最大値([_要素|R],_最大値_1,_最大値) :-
_要素 > _最大値_1,
最大値(R,_要素,_最大値),!. % この節の末尾に ! がくる。
最大値([_要素|R],_最大値_1,_最大値) :-
最大値(R,_最大値_1,_最大値).
%%% 案3 %%%
最大値(_標本リスト,_最大値) :-
_標本リスト = [_第一要素|R],
最大値(R,_第一要素,_最大値),!. % ここに ! を打つ。非決定性述語 最大値/3 を事実上決定性述語とすることができる。
最大値([],_最大値,_最大値).
最大値([_要素|R],_最大値_1,_最大値) :-
_要素 > _最大値_1,
最大値(R,_要素,_最大値).
最大値([_要素|R],_最大値_1,_最大値) :-
最大値(R,_最大値_1,_最大値).
などが考えられる。ただし、案3は 最初の 最大値 で質問した場合は ! が有効になるが、最大値/3 の方で質問した場合は、「!」はないので、有効にならない。最大値/2の方で質問するように注意する必要がある。
最大値([],_最大値,_最大値).
の本体に必ずしも「!」が存在しない理由は、第一引数が [] で呼ばれた場合、さらに他の節が選択されることはこの定義の場合はあり得ないからだ。最初の最大値の定義の、
最大値(_標本リスト,_最大値) :-
_標本リスト = [_第一要素|R],
最大値(R,_第一要素,_最大値).
最大値([],_最大値,_最大値).
最大値([_要素|R],_最大値_1,_最大値) :-
_要素 > _最大値_1, % 今度は ! がない。
最大値(R,_要素,_最大値).
最大値([_要素|R],_最大値_1,_最大値) :-
_要素 =< _最大値_1,
最大値(R,_最大値_1,_最大値).
最後の節の本体に「_要素 =< _最大値」を加えれば「!」を排除することができる。
最後に、最も宣言的な最大値の定義を示す。「選択した値以外の全ての要素が選択した値以下である時、選択した値が最大値である」がその意味である。
最大値(_標本リスト,_最大値) :-
_選択した値 = _最大値,
select(_選択した値,_標本リスト,_選択した値を除くリスト),
forall(member(_要素,_選択した値を除くリスト),_要素 =< _選択した値),!.
select/3とforall/2は共に組込述語となっている。select/3は第二引数のリストの先頭から要素を非決定性に取り出し、第一引数に単一化すると共に第三引数にその要素を除いたリストを単一化する。
forall/2は 第一引数の評価を真とするものに全てに対して、第二引数の評価は真となる、というものである。
行列
[編集]行列も集合同様、Prologでは特別な記法は用意されてはいない。そのため一般に行列を、リストを要素として持つリストとして表現することが多い。
例えば 3 × 3 の単位行列 は [[1,0,0],[0,1,0],[0,0,1]] のように表す。
全体が3要素のリスト、そのそれぞれの要素がまた3要素のリストである。
ここでは、findall/3を二重に使った行列の転置の定義を示す。
行列の転置([_最初の行|_残りの行],_転置行列) :-
length(_最初の行,_列数),
findall(_転置された行,(
between(1,_列数,_nth1),
findall(_値,(
member(_行,[_最初の行|_残りの行]),
nth1(_nth1,_行,_値)),
_転置された行)),
_転置行列).
この定義の難しさは、列数を得るための表現にある。ここでは行列の転置述語の第一引数を細工してこれを得たが、代償として、対象行列を[_最初の行|_残りの行]と表現したため、この引数が何を意味するのかわかりにくいコードとなった。
行列が[[1,2,3],[4,5,6],[7,8,9],[10,11,12]]として与えられた時の行列の転置は
実行例
?- 行列の転置([[1,2,3],[4,5,6],[7,8,9],[10,11,12]],_転置行列).
_転置行列 = [[1,4,7,10],[2,5,8,11],[3,6,9,12]]
となる。
行列の転置の再帰的な定義は
行列の転置(L,[L1|R2]) :-
行列の転置(L,L2,L1),
行列の転置(L2,R2).
行列の転置([],[],[]) :- !.
行列の転置([[A|R1]|R2],[R1|R3],[A|R4]) :-
行列の転置(R2,R3,R4).
findall/3の定義に比べると、定義自体は簡素なのだが、可読性はかなり悪い。
行列の掛算
[編集]行列の掛算は普通第二引数の行列を一旦、行列の転置/2 で転置し、掛け合わせる3つの述語 行列の掛算_1/3 行列の掛算_2/3 行列の掛算_3/3 によって積を得る。述語名の末尾に _1 _2 _3 を付加して別の述語とするのは、引数が同じで同一の述語名が使えない時の方便である。一般に、述語の意味する言葉を述語名とすることが望ましいが、行列述語などを含めて数学的なアルゴリズムでは、部分的な計算を言葉で表現することが困難な場合も多い。それでこのような述語の命名がしばしば見られる。
行列の掛算(_行列_1,_行列_2,_行列の積) :-
行列の転置(_行列_2,_転置された行列),
行列の掛算_1(_行列_1,_転置された行列,_行列の積).
行列の掛算_1([],_,[]) :- !.
行列の掛算_1([L_1|R1],LL_2,[S1|R3]) :-
行列の掛算_2(L_1,LL_2,S1),
行列の掛算_1(R1,LL_2,R3).
行列の掛算_2(_,[],[]) :- !.
行列の掛算_2(L_1,[L_2|R2],[S|R3]) :-
行列の掛算_3(L_1,L_2,S),
行列の掛算_2(A,R2,R3).
行列の掛算_3([],[],0) :- !.
行列の掛算_3([A|R1],[B|R2],S) :-
S1 is A * B,
行列の掛算_3(R1,R2,S2),
S is S1 + S2.
実行例
?- 行列の掛算([[3,4,8],[2,6,5]],[[7,8],[2,6],[5,4]],X).
X = [[69,80],[51,72]].
正方行列の対角要素
[編集]正方行列の右下がり対角要素リストと左下がり対角要素リストを得る。正方行列の対角要素とは、
1、5、9 が右下がり対角要素であり、3、5、7 が左下がり対角要素であるとする。これを nth1 と length と append の組み合わせで定義する。
右下がり対角要素リスト(_正方行列,_右下がり対角要素リスト) :-
findall(V,(
nth1(_nth1,_正方行列,L),
nth1(_nth1,L,V)),
_右下がり対角要素リスト).
左下がり対角要素リスト(_正方行列,_左下がり対角要素リスト) :-
findall(V,(
nth1(_nth1,_正方行列,L),
length([_|R],_nth1),
append(_,[V|R],L)),
_左下がり対角要素リスト),!.
組込述語 nth1 は非決定性の述語で第一引数が論理変数の場合は、1、2、3、…、n とバックトラックされる度に順に値を生成する。nth1 の 1 は1からこのカウントを開始するの意味である。
上記二つの定義では、要素位置を示す論理変数 _nth1 が現れるが、この論理変数に対して何ら演算を施してはいない。このように要素位置等の数値による管理からプログラマが解放される機会が多いことも Prolog の大きな特長である。
実行例を示す。
?- 右下がり対角要素リスト([[1,2,3,4],[5,6,7,8],[9,10,11,12],[13,14,15,16]],L).
L = [1,6,11,16]
?- 左下がり対角要素リスト([[1,2],[3,4]],L).
L = [2,3]
ガウス行列検査
[編集]行列がガウス行列であるかどうか検査します。ここではガウス行列検査/1を述語名を冗長に取って、その事によって、宣言的に述語定義することで、Prologのプログラムが、ガウス行列の解説になっているように工夫されています。
ガウス行列検査(_ガウス行列) :-
'ガウス行列とは、行が下がるごとに、最初に現れる0でない要素が右に移っていく行列のことをいいます'(_ガウス行列).
'ガウス行列とは、行が下がるごとに、最初に現れる0でない要素が右に移っていく行列のことをいいます'(_ガウス行列) :-
行が下がるごとに最初に現れる0でない要素が(_ガウス行列,_最初に現れる0でない要素の変位のリスト),
右に移っていく行列のことをいいます(_最初に現れる0でない要素の変位のリスト).
行が下がるごとに最初に現れる0でない要素が(_ガウス行列,_最初に現れる0でない要素の変位のリスト) :-
findall(_最初に現れる0でない要素の変位,(
append(_,[_ガウス行列の行|_],_ガウス行列),
最初に現れる0でない要素の変位が(_ガウス行列の行,_最初に現れる0でない要素の変位)),
_最初に現れる0でない要素の変位のリスト).
最初に現れる0でない要素の変位が(_ガウス行列の行,_最初に現れる0でない要素の変位) :-
append(_0のみのならび,[_0でない要素|_],_ガウス行列の行),
\+(_0でない要素 = 0),
length(_0のみのならび,_最初に現れる0でない要素の変位),!.
右に移っていく行列のことをいいます([A]).
右に移っていく行列のことをいいます([A,B|R]) :-
A < B,
右に移っていく行列のことをいいます([B|R]).
実は、最初に現れる0でない要素がない、すなわち、全ての要素が0であるような行があり得ますが、_0でない要素がない訳ですから
append(_0のみのならび,[_0でない要素|_],_ガウス行列の行),が偽になります。これは、最終的に、
行が下がるごとに最初に現れる0でない要素が/2の中のfindall/3の中に現れますから、偽になればリストLに採用されません。乃ち、この判定では全て要素が0の行は無視されます。
このガウス行列検査/1のように、配列と違って添字を使わないリストで行列を表現するため、Prologの行列の処理では、大小比較以外の数値計算が全く現れないこともあります。
部分集合
[編集]Prolog が集合をどのように扱うかについては、既に Prolog プログラミングの章で述べた。
ある集合が別の集合の部分集合であるか確かめる述語 部分集合 を定義する。
この述語は組込述語 subset として定義済みであり、その定義は
subset(_subsets,_sets) :-
forall(member(_element,_subsets),member(_element,_sets)).
であると考えられる。_subsets のメンバーは必ず _sets のメンバーであると宣言している。
組込述語 forall は第一引数の副目標が真になる場合は、第二引数の副目標も必ず真になると宣言するメタ述語である。「全ての・・・について、」がその意味と考えればよい。
forall(member(_element,_subsets),member(_element,_sets))は
「全ての部分集合の要素は、全体集合の要素である」という意味となる。
これとは別に再帰を使った 部分集合 の定義もある。
部分集合([],_).
部分集合([_要素|R],_集合) :-
member(_要素,_集合),
部分集合(R,_集合).
実行例を示す。
?- 部分集合([2,4],[4,1,2,6]).
true.
?- 部分集合([3,4],[4,1,2,6]).
false.
となる。集合では「その要素が・・・」と語られることが常であるが、「その要素が」をProlog述語として表現したものが
member/2である。
階乗
[編集]階乗は整数の性質に含まれる数の連関を使うだけで計算できる数少ない例の一つである。Nの階乗を 階乗/2 として定義する。
階乗(0,1) :- !.
階乗(N,_階乗) :-
N_1 is N - 1,
階乗(N_1,_階乗_1),
_階乗 is _階乗_1 * N.
ここでの階乗の定義のように、計算対象となる要素が、常に1ずつ減っていく、そして、それだけで計算が完了するというのは特別な例なのであって、そのような固定した性質がない集合の計算では計算対象をリストに取ることが多い。既にそのような例としては 加算の リスト要素の加算 があった。
階乗には以下のように第二引数に累算部分を明示的に取る定義もある。
階乗(N,_階乗) :-
階乗(N,N,_階乗).
階乗(1,_階乗,_階乗) :- !.
階乗(N,_階乗_1,_階乗) :-
N_1 is N - 1,
_階乗_2 is _階乗_1 * N,
階乗(N_1,_階乗_2,_階乗).
この定義は最後に副目標として階乗(N_1,_階乗_2,_階乗)のような再帰表現の締め括りが来ている。このような形式の再帰を末尾再帰と言って、Prologに於いてはこの末尾再帰の方が、インタプリタ/コンパイラが最適化をしやすい。再帰の実行が深くなったり、巨大数を扱った場合、スタックオーバフローのようなエラーになることを回避しやすい。
?- 階乗(100000,X).
このような質問がなされた場合、上側の定義、則ち末尾再帰でない定義では多くの処理系で解が返らない。一方、末尾再帰の定義では、もちろん多倍長整数のサポートが条件ではあるが、456579桁の整数解が返るに相違ない。
このような事情から、一般にPrologプログラマには二つの定義のうち、下の定義の方が好まれる。
階乗保存計算
[編集]10000以下の素数のリストをウィルソンの定理による素数判定を使って得る。この計算では階乗計算が繰り返し使われるのだが、述語に定義節を動的に書き加えることによって、階乗の呼び出し回数を大幅に少なくできる。ただし、述語論理を完全に逸脱したプログラムである。
:- dynamic(階乗保存計算/2).
'ウィルソンの定理を使って素数を判定する関数is_primeを実装し、100000以下の素数をリストに得る'(_10000以下の素数リスト) :-
findall(_p,(
between(1,10000,_p),
is_prime(_p)),
_10000以下の素数リスト).
is_prime(_p) :-
'ウィルソンの定理とは pが素数 <=> (p-1)!+1 (mod p) == 0'(_p).
'ウィルソンの定理とは pが素数 <=> (p-1)!+1 (mod p) == 0'(_p) :-
_p > 0,
Y is _p - 1,
階乗保存計算(Y,Z),
0 is (Z + 1) mod _p,!.
階乗保存計算(0,1) :- !.
階乗保存計算(1,1) :- !.
階乗保存計算(N,X) :-
N2 is N - 1,
階乗保存計算(N2,Y),
X is N * Y,
asserta((階乗保存計算(N,X) :- !)).
asserta は述語の先頭に定義節を加える組込述語。既に計算した階乗は答えを階乗保存計算の先頭に付け加えることで、以後階乗計算に入るまえに、その解を得ることができるようになる。
述語 階乗保存計算 の定義は階乗保存計算(7). を実行前と後では以下のように変化する。
?- listing(階乗保存定義/2).
階乗保存計算(0, 1) :- !.
階乗保存計算(1, 1) :- !.
階乗保存計算(A, C) :-
B is A + -1,
階乗保存計算(B, D),
C is A * D,
asserta((階乗保存計算(A, C):-!)).
true.
?- 階乗保存計算(7,X).
X = 5040
?- listing(階乗保存計算/2).
階乗保存計算(7, 5040) :- !.
階乗保存計算(6, 720) :- !.
階乗保存計算(5, 120) :- !.
階乗保存計算(4, 24) :- !.
階乗保存計算(3, 6) :- !.
階乗保存計算(2, 2) :- !.
階乗保存計算(0, 1) :- !.
階乗保存計算(1, 1) :- !.
階乗保存計算(A, C) :-
B is A + -1,
階乗保存計算(B, D),
C is A * D,
asserta((階乗保存計算(A, C):-!)).
true.
listing は現在の述語定義を示す、処理系のサービス述語である。
組込述語 asserta や assertz を使えば、プログラムによるプログラムの生成が可能になる。それだけではなく、プログラムの実行中に追加プログラムコードを生成して、それを即実行することもできる。
リストの重複要素を削除する
[編集]リストの要素が重複している時、これを唯ひとつの要素に置き換えたい時がある。
リストの重複要素を削除する([],[]).
リストの重複要素を削除する([A|R1],R2) :-
member(A,R1),
リストの重複要素を削除する(R1,R2).
リストの重複要素を削除する([A|R1],[A|R2]) :-
\+(member(A,R1)),
リストの重複要素を削除する(R1,R2).
?- リストの重複要素を削除する([3,4,2,3,5],L).
L = [4,2,3,5].
最も基本的な再帰のなかで member/2 を使って後に再びこの要素が現るかどうか検査している。複数同一要素が存在するときには、 最後の位置にある要素だけが選択される。リスト要素の順序の変化に注意が必要である。
リストの重複要素削除には、他にも有力な方法がある。
組込述語 setof/3 と member/2 を組合せて使う。setof/3は名前から想像できるように出来上がるリストを集合とみなす。従ってこの述語のなかには要素が重複したらこれを取り除いてしまう機能を含んでいる。
リストの重複要素を削除する(L1,L2) :-
setof(_要素,member(_要素,L1),L2).
もうひとつ、これは組込述語 sort/2 の約束事であるが、最終的に整列結果の重複要素は取り除かれる。従って、
リストの重複要素を削除する(L1,L2) :-
sort(L1,L2).
これだけで済んでしまう。
リストの全ての要素が同じ
[編集]リスト要素が全て同じ。検査述語であると同時に、リストに変数を含む場合はそれを第二引数と単一化して全て同じ要素になるように企てる働きをする。 さらに第二引数が変数で呼ばれたら、第一引数のリスト要素が全て同じ場合にのみ真となり、その要素と第二引数が単一化される。
全ての要素が同じ([],_).
全ての要素が同じ([A|R],A) :-
全ての要素が同じ(R,A).
第一引数のリストのなかにひとつでも第二引数と異なった要素が現れたら、則ち偽となる。偽にならず、第一引数が[]まで到達したら、全ての要素は第二引数と同じであったことになる。
実行例
?- 全ての要素が同じ([2,2,2],2).
true.
?- 全ての要素が同じ([2,2,3],2).
false.
?- 全ての要素が同じ([2,2,2],X).
X = 2
?- 全ての要素が同じ([X,Y,Z],0).
X = 0,
Y = 0,
Z = 0,
?- 全ての要素が同じ([A,2,B],X).
A = 2,
B = 2,
X = 2.
最後の例は、Prologの単一化の = による制約表現とその制約解消過程が面白い。
'全ての要素が同じ(但し空リストを除く)'
[編集]上記、全ての要素が同じ/2は大変有用な述語であるが、仕様上重大な疑問がある。それは第一節の定義で、空リストの要素という矛盾を認めている点である。この問題は単に矛盾であるばかりでなく、
?- append(L1,L2,[1,1,3,2]),全ての要素が同じ(L1,A).
L1 = [], L2 = [1,1,3,2];
L1 = [1], L2 = [1,3,2];
L1 = [1,1], L2 = [3,2];
false.
?-
となり、L1 = [] を解として含んでしまう。これは受け入れがたい。空リストになるかどうかの検査が常に必要になり不便でもある。そこで、
'全ての要素が同じ(但し空リストは除く)'/2を定義しよう。定義は述語名そのまま、
'全ての要素が同じ(但し空リストは除く)'(L,A) :-
全ての要素が同じ(L,A),
\+(L = []).
と定義する。これで
?- '全ての要素が同じ(但し空リストは除く)'([X,Y,Z],0).
X = 0,
Y = 0,
Z = 0,
?- '全ての要素が同じ(但し空リストは除く)'([A,2,B],X).
A = 2,
B = 2,
X = 2.
重複するから一部省略するが、全ての要素が同じ/2に於ける質問例の動作通りになる。
なお、全ての要素が同じ/2を以下のように変更すると、
全ての要素が同じ([A],A).
全ての要素が同じ([A|R],A) :-
全ての要素が同じ(R,A).
?- 全ての要素が同じ(L,3).
L = [3];
L = [3];
L = [3,3];
L = [3,3];
・・・
というような実行となり、思い通りの結果にならない。結局この定義に於いても、
全ての要素が同じ([A],A).
全ての要素が同じ([A|R],A) :-
\+(R=[]),
全ての要素が同じ(R,A).
\+(R=[])という意味の判り難い副目標が必要ということになる。
N個の空白からなるアトムを生成する
[編集]N個の空白からなるアトムを生成する。述語名がシングルクォートで括られているのはその先頭文字に英大文字が来ているからである。ここでは組込述語 length によって要素数N個の変数のリストを生成し、
その要素全てを空白文字とした上で、文字のリストからアトムを生成するために、組込述語 atom_chars を使っている。
'N個の空白からなるアトムを生成する'(N,_アトム) :-
length(L,N),
全ての要素が同じ(L,' '),
atom_chars(_アトム,L).
実例を示す。
?- 'N個の空白からならアトムを生成する'(8,Atom).
Atom = ' '
上に示した定義は、全ての要素が同じ/2が既に用意されていることを前提に、空白からなるアトムを作ったが、
'N個の空白からなるアトムを生成する'(N,_アトム) :-
findall(' ',between(1,N,_),L),
atom_chars(_アトム,L).
でよく、この定義の空白と指定された部分を抽象して、同一文字からなるアトムの定義は
'N個の同一文字からなるアトムを生成する'(N,_文字,_アトム) :-
findall(_文字,between(1,N,_),L),
atom_chars(_アトム,L).
でよい。
'N個の空白からなるアトムを生成する'/2の再帰的な定義は組込述語 atom_concat/3 を使って実現する。
'N個の空白からなるアトムを生成する'(1,' ') :- !.
'N個の空白からなるアトムを生成する'(N,_アトム) :-
N_1 is N - 1,
'N個の空白からなるアトムを生成する'(N_1,_アトム_1),
atom_concat(' ',_アトム_1,_アトム).
上に示した非再帰的な定義とどちらが判りやすいか、取捨に悩むことが多い。
ヘッドゼロサプライ
[編集]事務計算などでは、123という整数を8桁の数値表現で、しかも頭部を空白ではなく0で埋めることを要求されることがある。
これを上記 全ての要素が同じ を使って定義する。最初に枠を取り、頭部の桁不足の部分は 全ての要素が同じ を使って 0 を埋めている。
ヘッドゼロサプライ(_桁数,_数値,_ヘッドゼロサプライ数値表現) :-
length(_桁数枠のリスト,_桁数),
number_chars(_数値,_数字のリスト),
append(_頭部の枠リスト,_数字のリスト,_桁数枠のリスト),
全ての要素が同じ(_頭部の枠リスト,'0'),
atom_chars(_ヘッドゼロサプライ数値表現,_桁数枠のリスト).
number_chars、atom_chars ともに組込述語で、それぞれ、数値を分解して数字リストに、アトムを分解して文字リストとする。
頭部の枠リストの桁（要素数）は述語 append が決定する。
実行例
?- ヘッドゼロサプライ(8,123,X).
X = '000000123'
?-
ヘッドゼロサプレスの定義は、
ヘッドゼロサプレス(_桁数,_数値,_ヘッドゼロサプレス数値表現) :-
length(_桁数枠のリスト,_桁数),
number_chars(_数値,_数字のリスト),
append(_頭部の枠リスト,_数字のリスト,_桁数枠のリスト),
全ての要素が同じ(_頭部の枠リスト,' '),
atom_chars(_ヘッドゼロサプレス数値表現,_桁数枠のリスト).
変数名を変更したが実質的には 全ての要素が同じ の第二引数を変更するだけの違いである。
数値とカンマ区切り文字列の変換
[編集]以下二つとも事務計算では必須の述語である。最初の述語が必要になるのは帳票からOCRで文字列を読み取りデジタルテキスト化されたものが入力になる場合であろう。
カンマ区切り文字列を数値に変換(_文字列,_数値) :-
findall(_カンマではない文字,
カンマではない文字(_文字列,_カンマではない文字),_数字文字ならび),
number_chars(_数値,_数字文字ならび).
カンマではない文字(_文字列,_文字) :-
sub_atom(_文字列,_,1,_,_文字),
\+(_文字=',').
整数を3桁ずつカンマ区切りした文字列に変換(_数値,_数値文字列) :-
整数を3桁ずつアトムに変換しながら区切る(_数値,[],L),
atomic_list_concat(L,',',_数値文字列).
整数を3桁ずつアトムに変換しながら区切る(0,L,L) :- !.
整数を3桁ずつアトムに変換しながら区切る(N,L1,L) :-
整数の下位3桁を文字列に変換する(N,_桁数を調整した数値文字列,_下位3桁を取り除いた整数),
整数を3桁ずつアトムに変換しながら区切る(_下位3桁を取り除いた整数,[_桁数を調整した数値文字列|L1],L).
整数の下位3桁を文字列に変換する(N,_桁数を調整した数値文字列,_下位3桁を取り除いた整数) :-
_Nを1000で割った剰余 is N mod 1000,
_下位3桁を取り除いた整数 is N // 1000,
atom_number(_数値文字列,_Nを1000で割った剰余),
桁を3桁に(_下位3桁を取り除いた整数,_数値文字列,_桁数を調整した数値文字列).
桁を3桁に(0,A,A) :- !.
桁を3桁に(_,A,A) :-
atom_length(A,3),!.
桁を3桁に(_,A,C) :-
atom_concat('000',A,B),
sub_atom(B,_,3,0,C).
カンマ区切り文字列を数値に変換/2はnumber_chars/2に寄り掛かった定義になっている。
整数を3ケタカンマ区切り数値文字列に変換/2は、ここでは整数に限定しているが、実数を対象にする場合は、整数部と少数部に分離し、整数部にだけこの述語を適用すればよい。
整数を3桁ずつアトムに変換しながら区切る/3に於いて、Lに下3桁ずつ、積んで行き、しかも最終的に上位桁から下位の順に展開できている。これは、プログラム事例の後に出てくるリスト要素の反転の中で見ることができるPrologの特徴的な技法である。
整数の下位3桁を文字列に変換する/3はカンマ区切りの厄介なところで、1000で除した剰余が2桁以下の時に頭部に0を強制している。しかし、最上位の3桁はその限りではない。そのための述語が桁を3桁に/3である。
ユークリッドの互除法によって最大公約数を求める
[編集]ユークリッドの互除法によって最大公約数を求める。
数値演算の場合、他の言語とそれほど変わらない。Prologの特徴を求めるならば出力用の引数が必要とされることだろう。
最大公約数(N,_最大公約数,_最大公約数) :-
0 is N mod _最大公約数.
最大公約数(N,M,_最大公約数) :-
M_2 is N mod M,
最大公約数(M,M_2,_最大公約数).
実行例
?- 最大公約数(49,28,X).
X = 7
?-
エラトステネスの篩
[編集]n以下の全ての素数をリストに集める。エラトステネスの篩を述語として定義し、これを呼び出す。
最初の述語 n以下の素数 の冒頭で、2から始まりnまで連続する整数のリストを組込述語 findall と between を使って生成する。代表的な生成パターンである。
このリストを対象に小さい順に素数を探し、その素数の倍数をリストから削除して再帰的にエラトステネスの篩は実行される。
n以下の素数(_n以下,_n以下の全ての素数) :-
findall(_数,between(2,_n以下,_数),_2以上_n以下の数リスト),
エラトステネスの篩(_2以上_n以下の数リスト,_n以下の全ての素数).
エラトステネスの篩([],[]) :- !.
エラトステネスの篩([A|R1],[A|R2]) :-
エラトステネスの篩(A,R1,L),
エラトステネスの篩(L,R2).
エラトステネスの篩(_,[],[]) :-!.
エラトステネスの篩(N,[A|R1],R2) :-
0 is A mod N,
エラトステネスの篩(N,R1,R2),!.
エラトステネスの篩(N,[A|R1],[A|R2]) :-
エラトステネスの篩(N,R1,R2).
エラトステネスの篩 の定義の中で findall を使うと エラトステネス/3 は実は不要である。
エラトステネスの篩([],[]).
エラトステネスの篩([M|R1],[M|R2]) :-
findall(N,(
member(N,R1),
\+(0 is N mod M)),
L),
エラトステネスの篩(L,R2).
どちらの定義が読みやすいかについては、常に問題となる。
この findall を エラトステネスの篩 の中に持つ
エラトステネスの篩([],[]) :- !.
エラトステネスの篩([M|R1],[M|R2]) :-
エラトステネスの篩(M,R1,L),
エラトステネスの篩(L,R2).
エラトステネスの篩(M,R1,L) :-
findall(N,(
member(N,R1),
\+(0 is N mod M)),
L).
が最も宣言的なエラトステネスの篩の定義かも知れない。
エラトステネスの篩/2 の方は、findall で生成される新たなリストが第一引数に置き換えられて再び駆動される。このような新しい対象を生成しつつ、ダイナミックに繰り返すパターンは、再帰的な定義以外に方法がない。
実行例
?- n以下の素数(32,L).
L = [2,3,5,7,11,13,17,19,23,29,31]
?- エラトステネスの篩([2,3,4,5,6,7,8,9,10,11,12,13,14],L).
L = [2,3,5,7,11,13]
?-
文字列の検索
[編集]Prologでは、文字列という場合、一般にアトムを指すが、String（文字コードのリスト）を指す場合もあり、少々曖昧である。ここではアトムを指すとする。
文字列の検索(_文字列,_検索語,_検索語の前方文字列,_検索語,_検索語の後方文字列) :-
sub_atom(_文字列,_開始点,_文字列長,_残り文字列長,_検索語),
sub_atom(_文字列,0,_開始点,_,_検索語の前方文字列),
sub_atom(_文字列,_,_残り文字列長,0,_検索語の後方文字列).
sub_atom という極めてスーパーな非決定性の組込述語がこの機能の全てを司る。開始点は0オリジンであることに注意が必要である。Prologの組込述語では1オリジンを使うものが多いのだが、この述語は0オリジンである。
sub_atom の仕様は (1) 第一引数に検索対象アトムがくる、(2) 第二引数には検索語の開始点がくる、(3) 第三引数には検索語の文字数、(4) 第四引数には検索が成功した時の残り文字列長、(5) 第五引数に検索語がくる。
sub_atomは文字の出現順序は保たれるが、対象文字列を一文字ずつ開始点、終了点のポインターをずらしながら試行錯誤で、全ての切り取ることができる副文字列が試さながら実行される。従って、対象文字列が長く、第二、第三、第四引数が変数の場合は、検索を完了するまでに時間を要する。
文字列の検索にはsub_atom/5の代わりに組込述語のatom_concat/2を使う定義もある。こちらの方が引数に変位が現れず若干は抽象的な定義である。
文字列の検索(_文字列,_検索語,_検索語の前方文字列,_検索語,_検索語の後方文字列) :-
atom_concat(_検索語の前方文字列,_残り文字列,_文字列),
atom_concat(_検索語,_検索語の後方文字列,_残り文字列).
atom_concat/2は二つのアトムを結合することと、アトムを二つの文字列に分解すること、この二つ意味を双方向に持っている。
実行例
?- 文字列の検索(abd126fgabyz,ab,X,Y,Z).
X = '',
Y = ab,
Z = d126fgabyz;
X = abd126fg,
Y = ab,
Z = z;
False
上記検索パターン通じて、目標に _検索語 がふたつ冗長に現れ、単一化を二重に行っている部分もあるが、将来、検索語に何らかの記号パターン(正規表現のような)が利用される可能性を考えて、ここではあえて検索語と検索結果の検索語が同じになることを承知の上で、一引数余分に確保している。
検索語に変数がきたらどうなるか。ここではYとする。この場合、文字列検索/5は検索文字列の候補を挙げてくるだけである。その後に連接した二つのsub_atom/5で制限を付けている。
?- 文字列の検索(abd126fgabyz,Y,X,Y,Z),sub_atom(Y,0,2,_,fg),sub_atom(Y,_2,_,by).
X = abd126,
Y = fgaby,
Z = yz.
このように検索語を与えなくても、検索する可能性を持つことはPrologによる文字列処理の特長である。
sub_atomは第一引数が変数で実行されるとエラーとなる。第二引数以下の情報から双方向に第一引数を生成することはしない。
?- sub_atom(A,0,5,0,abcde).
ERROR: sub_atom/5: Arguments are not sufficiently instantiated
論理的には第一引数Aにabcdeが返ってきても良さそうなケースだが、述語定義の仕様から、エラーとなってしまう。
文字列の置換
[編集]ISO規格を含めて、ほとんどの処理系では正規表現がサポートされていない。Prologは文字列操作を得意とする言語だが、それでも複雑な置換パターンでは長い定義となることが多い。
最初に、置換対象が一つの単純な置換を考えてみよう。
文字列の置換(_対象文字列,_置換される副文字列,_置換する副文字列,_置換された文字列) :-
sub_atom(_対象文字列,_開始点,_長さ,_残り長さ,_置換される副文字列),
sub_atom(_対象文字列,0,_開始点,_,_前文字列),
sub_atom(_対象文字列,_,_残り長さ,0,_後文字列),
atomic_list_concat([_前文字列,_置換する副文字列,_後文字列],_置換された文字列).
atomic_list_concat はリスト要素を結合して新しいアトムを生成する。
実行例を示す。
?- 文字列の置換(いろははほへと,はは,はに,_置換された文字列).
_置換された文字列 = いろはにほへと
これはうまく行くが、複数置換対象が存在する場合を見てみよう。
?- 文字列の置換(生垣作るその生垣を,生垣,八重垣,_置換された文字列).
_置換された文字列 = 八重垣作るその生垣を;
_置換された文字列 = 生垣作るその八重垣を;
false.
置換対象が複数あっても、一ヶ所だけ置換するという場合もある。その場合には選択的に置換できるこの定義で良い。
しかしこの例もそうだが、対象となる副文字列全てを置換したいことも多い。結論を言ってしまえば、このようなバックトラックを使ったパターン(失敗駆動)では全置換は定義できない。
文字列の全置換(_対象文字列,_置換される副文字列,_置換する副文字列,_置換された文字列) :-
置換対象の選択(_対象文字列,_置換される副文字列,_前文字列,_後文字列),
文字列の全置換(_後文字列,_置換される副文字列,_置換する副文字列,_置換された後文字列),
atomic_list_concat([_前文字列,_置換する副文字列,_置換された後文字列],_置換された文字列),!.
文字列の全置換(_文字列,_,_,_文字列).
置換対象の選択(_対象文字列,_置換される副文字列,_前文字列,_後文字列) :-
sub_atom(_対象文字列,_開始点,_長さ,_残り長さ,_置換される副文字列),
sub_atom(_対象文字列,0,_開始点,_,_前文字列),
sub_atom(_対象文字列,_,_残り長さ,0,_後文字列).
一般に置換では、置換対象文字列が存在しなかった時、その副目標(質問)を偽としないで、元の文字列をそのまま残す。文字列の全置換 の第二節 文字列の全置換(_文字列,_,_,_文字列). はそのために必要である。
ちょっとわかりにくいが、文字列の全置換 は再帰的な述語である。置換対象までとその後文字列に分割して、後文字列を再帰的に置換したものと、それまでの文字列を置換しながら結合する。
実行例
?- 文字列の全置換(生垣作るその生垣を,生垣,八重垣,_置換された文字列).
_置換された文字列 = 八重垣作るその八重垣を
これで二ヶ所の生垣を八重垣に置換することができる。
リストの結合
[編集]リストの結合とは引数として与えられた二つのリストを最初のリストの最終要素の次から第二リストの最初の要素から順に付け加えて行って、一つのリストに纏めることを言う。この述語はほとんどの処理系で組込述語 append として特に利用者が定義しなくても済むが、述語定義技法としての観点からも Prolog を代表する述語であるため、ここでは append 述語が Prolog でどのように定義されるかを紹介する。
リストの結合(L1,L2,L) :- append(L1,L2,L).
appendは2つのリストを結合する
append([],L,L).
append([E|L1],L2,[E|L]) :- append(L1,L2,L).
実行例
?- append([a,b],[1,2,3],L).
L = [a,b,1,2,3]
appendの意味は結合に留まらない。第一引数、第二引数に変数が来るとリストを分解する。 実は非決定性の述語としての代表でもある。
?- append(X,[2,3],[1,2,3]).
X = [1]
?- append(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 = [];
false
となる。さらに以下のように使用するとappendは実はmemberのスーパーセットであることがわかる。
?- append(L1,[X|L2],[ワカメ,マスオ,タラオ]).
L1 = [],
X = ワカメ,
L2 = [マスオ,タラオ];
L1 = [ワカメ],
X = マスオ,
L2 = [タラオ];
L1 = [ワカメ,マスオ],
X = タラオ,
L2 = [];
false
ここで注目するべきことは、このような使い方の append に於いては、切り出したい情報とその情報のリスト前部、リスト後部の情報を同時に取得できることである。例えば切り出した情報（上の定義例では X）の前部や後部にXが含まれていないか検査などが可能になる。これは member においては不可能なことである。
append は多義的な述語であり、同時に Prolog を代表する述語でもあるため、機能に見合った述語名をリストの結合、リストの分解という具合に与えるか、それとも、通りのよい append 一本で貫くか迷うことが多い。ここではこの述語定義を理解、記憶してもらうためにもっぱら append で通したが、それぞれ別の述語名を与えて利用するのが本来の Prolog の姿であろう。
リストの結合(L1,L2,L) :- append(L1,L2,L).
リストの分解(L1,L2,L) :- append(L1,L2,L).
四引数以上のリストの結合
[編集]引数が3のappendを示したが、4引数以上のものも便利である。
?- append(L1,[X,Y],L3,[a,b,c,d]).
L1 = [],
X = a,
Y = b,
L3 = [c,d];
L1 = [a],
X = b,
Y = c,
L3 = [d];
L1 = [a,b],
X = c,
Y = d,
L3 = [];
false.
このように、中間のリストの前のリスト、後のリストという分解が簡単にできる。この append/4 の定義は append/3 の定義を利用して
append([],L2,L3,L4) :-
append(L2,L3,L4).
append([E|L1],L2,L3,[E|L4]) :-
append(L1,L2,L3,L4).
である。
さらに append/4 ができれば、 append/5 は
append([],L2,L3,L4,L5) :-
append(L2,L3,L4,L5).
append([E|L1],L2,L3,L4,[E|L5]) :-
append(L1,L2,L3,L4,L5).
となっていく。一引数少ない append の定義ができていれば、このように、それを第一節の本体に使って簡単に定義を追加できる。
append/4を使った探索
[編集]四引数のappendの定義ができたところで、これを使って二文字以上の要素が昇順に並ぶリストを検索する。
この探索は、対象がアトムではなくリストになる点で、member/2,append/3,select/3のそれに比べで強力である。
二文字以上の要素が昇順に並ぶリストを検索する(_文字リスト,_前リスト,_二文字以上の要素が昇順に並ぶリスト,_後リスト) :-
append(_前リスト,_二文字以上の要素が昇順に並ぶリスト,_後リスト,_文字リスト),
要素が昇順に並んでいる(_二文字以上の要素が昇順に並ぶリスト).
要素が昇順に並んでいる([A,B]) :-
A @=< B.
要素が昇順に並んでいる([A,B|R]) :-
A @=< B,
要素が昇順に並んでいる([B|R]).
append([],L2,L3,L4) :-
append(L2,L3,L4).
append([U|L1],L2,L3,[U|L4]) :-
append(L1,L2,L3,L4).
第二引数のリストが単純な性格を持ち、その性質が完結しているか検査する述語を書くような場合であるが、その程度の難度の検索ではappend/4は強力である。
次に二文字以上の要素が昇順に並ぶのだが、各昇順文字リストのグループとしては最長の文字リストを検索する。
二文字以上の要素が昇順に並ぶリストを検索する(_文字リスト,_前リスト,_二文字以上の要素が昇順に並ぶリスト,_後リスト) :-
append(L1,L2,L3,_文字リスト),
\+((last(_前リスト,A),_二文字以上の要素が昇順に並ぶリスト=[B|_],A @< B)),
\+((last(_二文字以上の要素が昇順に並ぶリスト,C),_後リスト=[D|_],C @< D)),
要素が昇順に並んでいる(_二文字以上の要素が昇順に並ぶリスト).
last([A],A) :- !.
last([A|R],B) :-
last(R,B).
要素が昇順に並んでいる([A,B]) :-
A @=< B.
要素が昇順に並んでいる([A,B|R]) :-
A @=< B,
要素が昇順に並んでいる([B|R]).
last/2は第一引数のリストの最終要素が第二引数と単一化される。ここでは最後の要素と次のリストの先頭要素を比較している。
検索文字列が先頭からだったり、末尾まで続いている場合には、第一引数や第三引数が[]になる。last/2は偽となりそれぞれ、
\+((last(_前リスト,A),_二文字以上の要素が昇順に並ぶリスト=[B|_],A @< B)),
\+((last(_二文字以上の要素が昇順に並ぶリスト,C),_後リスト=[D|_],C @< D)),
それを否定しているから、ここの検査条件は真になる。
文字リストに変換して文字列を検索
[編集]先に文字列の検索を組込述語 sub_atom を使うことで例題とした。ここでは一旦、アトムとしての文字列を文字を要素とするリストに変換して検索する例を示す。この場合、検索語も文字のリストに変換する。
文字列の検索(_文字列,_検索語,_検索語の前方文字列,_検索語,_検索語の後方文字列) :-
文字列と検索語を文字リストに変換(_文字列,_検索語,_文字リスト,_検索文字リスト),
文字リストの検索(_文字リスト,_検索文字リスト,_検索語の前方文字リスト,_検索文字リスト,_検索語の後方文字リスト),
'検索語の前方文字リスト、検索文字リスト、検索語後方の文字リストを文字リストから文字列に変換'(_検索語の前方文字リスト,_検索文字リスト,_検索語の後方文字リスト,_検索語の前方文字列,_検索語,_検索語の後方文字列).
文字列と検索語を文字リストに変換(_文字列,_検索語,_文字リスト,_検索文字リスト) :-
atom_chars(_文字列,_文字リスト),
atom_chars(_検索語,_検索文字リスト).
文字リストの検索(_文字リスト,_検索文字リスト,_検索語の前方文字リスト,_検索文字リスト,_検索語の後方文字リスト) :-
append(_検索語の前方文字リスト,L2,_文字リスト),
append(_検索文字リスト,_検索語の後方文字リスト,L2),
'検索語の前方文字リスト、検索文字リスト、検索語後方の文字リストを文字リストから文字列に変換'(_検索語の前方文字リスト,_検索文字リスト,検索語の後方文字リスト,_検索語の前方文字列,_検索語,_検索語の後方文字列) :-
atom_chars(_検索語の前方文字列,_検索語の前方文字リスト),
atom_chars(_検索語,_検索文字リスト),
atom_chars(_検索語の後方文字列,_検索語の後方文字リスト).
「検索語の前方文字リスト、検索文字リスト、検索語の後方文字リストを文字リストから文字列に変換」がシングルクォートで囲まれて定義されているのは、途中に「、」が含まれているからである。規格で定められてはいないが、全角の記号は将来全角文字のみで処理系が利用される可能性から、記号扱いにしている処理系が多い。
述語 文字リストの検索/5 では、上記のリストの結合 append が、リストの結合というより分解として二つ連続して利用されている。
文字列を検索パターンを用いて検索
[編集]すでに文字列の検索を sub_atom を用いた例を示したが、一般に文字列の検索は atom_chars を用いて一旦文字のリストに変換してから検索するほうが定義が柔軟になる。
:- dynamic(パターン照合/2).
文字リストに変換しての検索(_文字列,_検索パターンリスト,_前文字列,_適合文字列,_後文字列) :-
atom_chars(_文字列,_文字リスト),
リストによる検索(_前文字列リスト,_適合文字リスト,_後文字リスト,_文字リスト),
パターン照合(_検索パターンリスト,_適合文字リスト),
atom_chars(_前文字列,_前文字リスト),
atom_chars(_適合文字列,_適合文字リスト),
atom_chars(_後文字列,_後文字リスト).
リストによる検索([],L2,L3,L4) :-
append(L2,L3,L4).
リストによる検索([A|R1],L2,L3,[A|R4]) :-
リストによる検索(R1,L2,L3,R4).
この述語の利用者は、検索する前に述語 パターン照合/2 を定義する。リストによる検索/4 は append/4 として知られる述語。
append/3 を member/2 として使う
?- append(L1,[A|L2],[1,2,3,4]).
に極めて近いが、Aは単項としか単一化できないのに対して、 リストによる検索/4 のL2は複数項のパターンを切り取ることができる点が違う。
実例を示す。"八重"から始まり"に"で終わる文字列を検索する。
?- assertz((パターン照合(L,L) :-
L = [八,重|R],append(L1,[に],R))).
?- 文字リストに変換しての検索(八雲立つ出雲八重垣妻籠みに八重垣作るその八重垣を,L,_前文字列,_適合文字列,_後文字列).
_前文字列 = 八雲立つ出雲,
L = [八,重,垣,妻,籠,み,に],
_適合文字列 = 八重垣妻籠みに,
_後文字列 = 八重垣作るその八重垣を;
false.
ここでは検索パターンリストに変数を置いている。最初に[八,重]が来て文字がわからないリストが来て、そして最後に[に]が来る。Prolog では、このようにパターンを一つのリストで表現することはできない。それでここは変数にして、パターン照合 述語に解決を委ねている。
リスト要素の隣／リスト要素の両隣
[編集]append を利用してリスト要素の隣を定義してみよう。極めて宣言的な定義となる。
リスト要素の隣(_リスト,_要素,_隣の要素) :-
append(_,[_隣の要素,_要素|_],_リスト).
リスト要素の隣(_リスト,_要素,_隣の要素) :-
append(_,[_要素,_隣の要素|_],_リスト).
さらに、リスト要素の両隣は
リスト要素の両隣(_リスト,_要素,_隣の要素_1,_隣の要素_2) :-
append(_,[_隣の要素_1,_要素,_隣の要素_2|_],_リスト).
リスト要素の両隣(_リスト,_要素,_隣の要素_1,_隣の要素_2) :-
append(_,[_隣の要素_2,_要素,_隣の要素_1|_],_リスト).
実行例
?- リスト要素の隣([a,b,c],X,Y).
X = a,
Y = b;
X = b,
Y = a;
X = b,
Y = c;
X = c,
Y = b
?- リスト要素の隣([a,b,c,d,e,f,g],b,f).
false.
?- リスト要素の隣([a,b,c,d,e,f,g],e,d).
true.
?- リスト要素の両隣([a,b,c,d,e,f,g],e,Y,Z).
Y = d,
Z = f;
Y = f,
Z = d
二つの隣要素が第三引数と第四引数に出現順に入るのだと決めておけば定義は
リスト要素の両隣(_リスト,_要素,_左隣の要素,_右隣の要素) :-
append(_,[_左隣の要素,_要素,_右隣の要素|_],_リスト).
となる。これが自然な定義であろう。
しかし、「リスト要素の両隣」がこの述語の仕様であったとすると、左右の順序や出現順はどこにも示唆されていないと 考えることがむしろ素直であり、上記の左右順あるいは右左順の二節とする定義も成立するのである。
リスト要素の反転
[編集]リストの要素の反転は reverse が組込述語になっているが、ここでは、これを定義してみる。
リスト要素の反転([],[]).
リスト要素の反転([A|R1],L) :-
リスト要素の反転(R1,L2),
append(L2,[A],L).
append を使った明解な宣言性の強い定義であるが、実行速度が遅いことからこの定義はあまり使われることがない。
普通、リストの反転の定義には、以下のように二つの述語に分解して定義する。ただしこの定義は完全ではない。正しい定義は最後に示す。
リスト要素の反転(L1,L2) :-
リスト要素の反転(L1,[],L2).
リスト要素の反転([],L,L).
リスト要素の反転([A|R1],L1,L) :-
リスト要素の反転(R1,[A|L1],L).
リスト要素の反転 の方の第二節 A に着目して欲しい。第二引数で受け取ったリストの前に追加しているが、最初が [] だから、先頭から順に末尾から付加されていくことになる。第一節の主張は、第一引数が [] になった時には、第二引数に反転したリストが積み上がっているはず、ということである。
実行例
?- リスト要素の反転([a,b,c],L).
L = [c,b,a]
さらに、
?- リスト要素の反転(L,[a,b,c]).
L = [c,b,a]
述語の双方向性も確かめられたと思いがちだが、そうはいかない。
?- リスト要素の反転(L,[a,b,c]).
L = [c,b,a];
%%% 解を示さなくなり、やがて、多くの処理系で内部メモリが足りなくなりエラーとなる(スタックオーバーフロー) %%%
エラー状態が生成されていく過程は興味深いのだが、複雑で難解になり過ぎるため、どのような経過で内部メモリがなくなっていくかはここでは示さない。このような基礎的な述語定義の中に重大なエラーが潜む余地があることは Prologの弱点 と考えるべきである。
以下はこのエラーに対する対策の一例である。
リスト要素の反転(L1,L2) :-
リスト要素の反転(L1,[],L2).
リスト要素の反転([],L,L) :- !.
リスト要素の反転([A|R1],L1,L) :-
リスト要素の反転(R1,[A|L1],L).
リスト要素の反転/3 の方の第一節にカットを入れる。これで上記エラーは回避できる。
最初に示した append を利用した定義ではこのようなことは起こらない。それで、あまり使われることがないとしながらも、こちらの定義を最初に載せた。
文字列の反転
[編集]"文字列" という文字列を反転して "列字文" という文字列を生成する 文字列の反転/2 を定義する。組込述語 atom_chars と上記定義した リストの反転 を組み合わせる。
文字列の反転(_文字列,_反転した文字列) :-
atom_chars(_文字列,_文字のリスト),
リストの反転(_文字のリスト,_反転した文字のリスト),
atom_chars(_反転した文字列,_反転した文字のリスト),
ここでは一旦文字のリストに変換している。それによってリストの反転/2が利用できた。
ただし、元の文字列の形式に atom_chars をもう一度使って戻さなくてはならない。
atom_chars でリストに変換せずに、文字列の反転/2を定義できるが、以下のような難しい定義となる。
文字列の反転(_文字列,_反転した文字列) :-
文字列の反転(0,_文字列,_反転した文字列).
文字列の反転(N文字目,_文字列,_文字) :-
sub_atom(_文字列,N文字目,1,0,_文字).
文字列の反転(N文字目,_文字列,_副文字列) :-
sub_atom(_文字列,N文字目,1,_,_反転した文字列),
N_1文字目 is N文字目 - 1,
文字列の反転(N_1文字目,_文字列,_反転した文字列_1),
atom_concat(_反転した文字列_1,_文字,_反転した文字列).
組込述語 atom_concat が使われた。アトムとアトムを結合して別の長いアトムを生成する述語である。
文字列の反転の例を示す。
?- 文字列の反転(文字列,X).
X = 列字文
?-
回文
[編集]回文とは先頭から読んでも、末尾から反対に文字をたどって読んでも、同じ文になるある程度意味の通る文のことである。回文は実用性よりも、文字列操作の練習課題としてしばしば利用される。
ここでの定義は回文を生成するのではなく、回文であるかどうかの検査である。ここでは「なかきよのとおのねふりのなふめさめふなのりふねのおとのよきかな」（長き夜の 遠の睡りの 皆目醒め 波乗り船の 音の良きかな）のように、文字の並びを対象とする。
回文(_回文) :-
atom_chars(_回文,Chars),
リストの反転(Chars,Chars).
一旦組込述語 atom_chars で文字のリストに変換する。ここまではいわば定石のようなものだが、回文の場合はここから、そのリストを反転し、引数が共通であることを示して、反転前と反転後が同じなのが回文であると宣言している。実例はもちろん
?- 回文(なかきよのとおのねふりのなふめさめふなのりふねのおとのよきかな).
true.
?-
である。
回文にはsub_atom/5を使った定義もある。
回文(_回文) :-
forall(sub_atom(_回文,N,1,_,_文字),sub_atom(_回文,_,1,N,_文字)).
回文の文字列中の前方からN文字目一文字と後方からN文字目一文字の対はどれも同じ文字になる。そういうことをこの定義では述べている。これも細部を述べながら、かつ、宣言性を維持した美しい定義である。
ただし、中間点まで確かめたならば回文と決定できるはずだが、ここでは全文を走査してしまっている。
中間点で打ち切る定義は、sub_atom/5の第二、第四引数を比較する。
回文(_回文) :-
forall((sub_atom(_回文,N,1,R,_文字),N =< R),sub_atom(_回文,_,1,N,_文字)).
forall/2
これで第一引数の走査が中間点に達すると第二引数の走査はしなくなる。
これで中間点を過ぎるとN >= Rが偽となるから第二引数のsub_atom(_回文,_,1,N,_文字)の検査には進まなくなる。
しかし、forall/2の第一引数のsub_atom/5の方は最後まで走査されてしまう。
この問題も解決しようとすると、
回文(_回文) :-
forall((sub_atom(_回文,N,1,R,_文字),N =< R; !,fail),sub_atom(_回文,_,1,N,_文字).
これで中間点に達すると!,failが働いて、sub_atom/5へのバックトラックは止まる。
しかし、; !,failの部分は、複雑で宣言性を損ねる記述になっている。forall/2の中の副目標の述語名がsub_atomに統一できなくなっている点でも、読み易さを損ねている。カットの説明を参照されたいが、
ここでのN =< R; !,failを独立した副目標として定義し直すことは、カットの有効範囲の関係からできない。
このような場合、日本語で解説して行くようなつもりで、冗長な述語表現を取ると上手く行く。
回文(_回文) :-
回文とは中間点まで先頭からN文字目と末尾からN文字目の文字が同一の文字列である(_回文).
回文とは中間点まで先頭からN文字目と末尾からN文字目の文字が同一の文字列である(_回文) :-
forall(中間点までのN文字目(_回文,N,_文字),末尾からN文字目(_回文,N,_文字)).
中間点までのN文字目(_回文,N,_文字) :-
sub_atom(_回文,N,1,R,_文字),N =< R; !,fail.
末尾からN文字目(_回文,N,_文字) :-
sub_atom(_回文,_,1,N,_文字).
この方がずっと宣言的で明解な表現になっている。
above、到達可能性
[編集]above(X,Y) :-
on(X,Y).
above(X,Y) :-
on(X,Z),
above(Z,Y).
ここで on の定義は具体的に定義する。例えば、
on(波平,サザエ).
on(サザエ,カツオ).
実行例
?- above(波平,X).
X = サザエ;
X = カツオ;
False
?= above(波平,カツオ).
True
一つ以上離れた関係を above の第二節でので定義で、引数の変数を on を経ながら X - Z - Y と連鎖することによって表現している。
経路が以下のような定義の時、ある駅から別の駅に到達できるかを示す 到達可能性 の定義は。
経路(渋谷,神泉).
経路(神泉,駒場東大前).
経路(駒場東大前,池の上).
経路(池の上,下北沢).
到達可能性(_駅_1,_駅_2) :-
経路(_駅_1,_駅_2).
到達可能性(_駅_1,_駅_2) :-
経路(_駅_1,_駅_3),
到達可能性(_駅_3,_駅_2).
実行例
?- 到達可能性(神泉,下北沢).
true.
検索は、(神泉,駒場東大前) → (駒場東大前,池の上) → (池の上,下北沢) と進み、第一節の本体で :- 経路(池の上,下北沢). が真となることにより、到達可能性は真となる。この定義を見比べると、経路/到達可能性とon/aboveさらに、既に例として見てきた親子/孫(あるいは先祖)の関係が同じアルゴリズムであることがわかる。
失敗駆動
[編集]単位節要素の加算の例に示された"年齢"のような単位節（本体定義なのない節）を定義順に表示するには普通失敗駆動を利用する。 年齢の定義次の通りだとする。
年齢(山田,35).
年齢(大島,20).
年齢(清川,28).
ここでは定義順に氏名,年齢を全て表示する方法を示す。
年齢表示 :-
年齢(_氏名,_年齢),
writef('%t,%t\n',[_氏名,_年齢]),
fail.
表示は組込述語 writef を使っている。無条件に偽になる組込述語があるため、バックトラックが起こり順に述語 年齢 の
各節が呼び出されて表示される。これが失敗駆動だ。最終的には年齢/2の呼び出しは偽となるため、質問は False で終わる。
実行例
?- 年齢表示.
山田,35
大島,20
清川,28
false.
?-
一般に必ず偽となって終わる定義は、これを再利用する際に不都合が生じる場合が多い。真として終了するためには、
年齢表示 :-
年齢(_氏名,_年齢),
writef('%t,%t\n',[_氏名,_年齢]),
fail.
年齢表示.
と書き加えるのみである。
失敗駆動を用いることなく、再帰を使って上記の年齢を表示することは案外と難しい。
年齢表示 :-
findall([_氏名,_年齢],年齢(_氏名,_年齢),L),
再帰による年齢表示(L).
再帰による年齢表示([]).
再帰による年齢表示([[_氏名,_年齢]|R]) :-
writef('%t\n',[_氏名,_年齢]),
再帰による年齢表示(R).
完全に独立した存在である定義節から、情報の連関を付与されたものとしてのリストを得るために、findall をここでも使用した。実はこの findall の中に失敗駆動が含まれている。つまり、ここでは findall を使うことによって失敗駆動を隠蔽していることになる。
repeat
[編集]repeat の定義は以下の通り単純である。
repeat.
repeat :- repeat.
repeat 自体は究極の再帰プログラミングである。問題はこれをどのように使用するかで、
?- repeat,read(X),write(X),nl,X=end_of_file.
|: abc.
abc
|: 123.
123
|: end_of_file.
end_of_file
X = end_of_file
repeat は再帰述語ではあるが、失敗駆動の起点としてのみ利用される。
repeatに制御が返ってくるのは、後続する副目標が完全に失敗したときである。repeatまで制御は戻り、再び後続する副目標が実行される。まったく最初と同じ状態に戻って実行される。ということは、本来述語定義や定義された節の引数は実行中に書き換えないことが基本なので、後続の副目標を何度繰り返しても同じ結果となり、停止しないはずである。したがってrepeatを含む節がプログラマの期待通り停止するためには、その後続の副目標の実行に副作用があることが前提となる。この副作用による変化を読み取ってrepeatの節を停止するように工夫する。上記の場合、
X = end_of_file.
がそれである。
次に、四季 という検索述語を repeat の前に置いてみる。
四季(春).
四季(夏).
四季(秋).
四季(冬).
?- 四季(_季節),repeat,read(X),write(X),nl,X=end_of_file.
|: abc.
abc
|: 123.
123
|: end_of_file.
end_of_file
_季節 = 春,
X = end_of_file,
季節 の選択が春から先に進んでいない。副目標 四季 には repeat があるためバックトラックしてこないことになる。
行入力
[編集]前節ですでに用いたが、Prolog には入力述語として古くから、1引数と2引数の read が存在した。この入力述語の魅力はアトム、数値、リストを含む複合項など、どんな項でも入力可能である点にある。入力された文字列は解析されて、引数と単一化される。
?- read(X).
|: 33.
X = 33.
?- read(X).
|: a(b,c).
X = a(b,c).
?- read(X).
33abc.
ERROR: Stream user_input:
?- read(a(b,c)).
33.
false.
?- read(a(b,c)).
a(b,c).
true.
?-
のように使う。注意するべきことは、プロンプト |: の後の入力には正しく項が来なくてはならず、しかも、入力はピリオドで終了する必要がある。
ごく一般的なカンマ区切りの「abc,def」の入力はシングルクォートで囲み「'abc,def'.」でなくてはならないことになる。
これでは実務的には不自由なので、文字列が改行されて終了するまでを、アトムとして受け取る 行入力 を定義してみる。
行入力(_行文字列) :-
get_char(C),
行入力_1(C,Chars),
atom_chars(_行文字列,Chars) .
行入力_1('\n',[]) :- !.
行入力_1(end_of_file,[]) :- !.
行入力_1(C,[C|R]) :-
get_char(C2),
行入力_1(C2,R).
これで改行によって、それまで入力された文字が一旦リストに収められ、それを atom_chars で変換して、アトムとして受け取ることができるようになった。ただし、入力はアトムだけに限られる。この点は read が項であったのとは異なる。
行入力_1 の第二節に現れる end_of_file であるが、これは改行ではなくファイルの終端を意味する情報が入力されたことを意味する。この独特なアトムを Prolog では伝統的に用いている。
実行例
?- 行入力(X).
abc,def
X = 'abc,def'
今度は |: のプロンプトが表示されない。このプロンプトの表示は項入力述語 read のいわばサービスであって、同じく組込述語であるが、get_char では表示されない。
入力検査
[編集]整数入力 は repeat によく似ているが、第一節の末尾にカットがあるため、失敗駆動の起点としての繰り返しにはならない。整数入力検査に失敗した場合のみ、整数入力を繰り返す。
整数入力(_整数) :-
行入力(_行入力),
整数入力検査(_行入力,_整数),!.
整数入力(_整数) :-
整数入力(_整数).
整数入力検査(_行入力,_整数) :-
read_term_from_atom(_行入力,_整数,[]),
integer(_整数),!.
整数入力検査(_行入力,_) :-
writef('入力された文字列%tは整数ではありません。再入力をお願いします。\n',[_行入力]),
fail.
read_term_from_atom は組込述語であり、アトム（文字列）を受け取りこれを解析して、Prolog の項に変換している。整数でない情報を受け取った時にその情報を表示させるためには、行入力 と同じ本体の中で、処理することが必要である。
整数入力 の第二節で表示することは、この節が引数から get_char で得た情報を受け取っていない以上不可能である。入力エラーを表示させる際に、入力された文字列も共に表示したいのであるが、第一節の本体内の副目標でない限り、引数からこの情報を受け取ることはできない。
実行例
?- 整数入力(X).
33
X = 33
?- 整数入力(X).
abc
入力されたabcは整数ではありません。再入力をお願いします。
8
X = 8
?-
整数入力 述語は repeat を使っても書くことができる。
整数入力(_整数) :-
repeat,
行入力(_行入力),
整数入力検査(_行入力,_整数),!.
repeat とほとんど同型の再帰述語の整数入力の代わりに repeat 自体を挿入することによって上記のように失敗駆動的な
整数入力述語が定義できることは実に興味深い。
整数入力(_整数) :-
行入力(_行入力),
整数入力検査(_行入力,_整数),!.
整数入力(_整数) :-
整数入力(_整数).
repeat.
repeat :-
repeat.
member(H,[H|T]).
member(H,[_|T]) :-
member(H,T).
append([],L,L).
append([U|X],Y,[U|Z]) :-
append(X,Y,Z).
整数入力の主述語と Prolog を代表する述語 repeat、member、append を比較した見た。極めて類似したパターンの述語であることが分かる。
キュー操作
[編集]Prolog ではキュー操作を差分リスト(重リストともいう)を使って表現している。差分リストとは二つのペアとなったリストを設定し、第二リストの全てが、第一リストの末尾に来るようにしたものである。第一リストのなかで第二リストと重ならない部分が、示したい情報・生きた情報である。例を示す。
第一リスト 第二リスト 示したい情報
[1,2,3,4] [3,4] [1,2]
[x,y,z] [y,z] [x]
[1,2,3|X] [3|X] [1,2]
[1,2,3|X] [2,3|X] [1]
[1,2,3|X] X [1,2,3]
キュー操作では、もっぱらこの最後の表現を使う（[1,2,3|X] X → [1,2,3]）。ここでは、直感的理解を深めるためオペレータ「-」を使って（すなわち複合項として）キューを表現してみる。
makeEmptyQueue(X-X).
emptyQueue(X-Y) :- X == Y.
dequeue(_要素,[_要素|X]-Y,X-Y).
enqueue(_要素,X-[_要素|Y],X-Y).
[1,2,3|X] のような構造を不完全データ構造と呼ぶ。[1,2,3,4] のように完結していないという意味で。
しかし、すでに多くのプログラム例を見てきたが、append に代表されるように、Prolog の引数部分はこの不完全データ構造で満ちている。構造の不完全な部分、すなわち変数部分に新たに情報構造を単一化することによって、そしてその末尾に再び不完全データ構造が来るようにすることで構造を成長させる。不完全データ構造の多用は Prolog プログラムの最も顕著な特徴である。キューの操作は、以下のようにキューを以前、以後と対にして（ここでは A,B B,C）持ち回ることで利用する。
?- makeEmptyQueue(A), ・・・ ,enqueue(2,A,B), ・・・ ,dequeue(E,B,C), ・・・
上記の例では、現在のキューは、最後の C と単一化された構造であるといえる。キュー C は現在は空である。E には 2 が取り出せた。ところで、上記のキュー定義では、オペレータ「-」を利用して直感的に差分を強調することによって宣言性を高めた。しかし、Prolog では、引数には極力、リストを排することはできないにしても、構造体を持たず、アトムのみで構成するほうがプログラムの見通しがよくなる。ここで、キュー操作を日本語に書き直しながら、定義を書き直す。
空のキューを生成する(X,X).
キューは空である(X,Y) :- X == Y.
キューから要素を取り出す(_要素,[_要素|X],Y,X,Y).
キューに要素を追加する(_要素,X,[_要素|Y],X,Y).
X と Y がペアであることが不明瞭になってしまったが、これで自然な定義である。
スタック操作
[編集]キュー操作が出てきたところでスタック操作について述べる。スタックの定義はさらに簡単である。
スタックを生成する([]).
スタックに要素を追加する(_pushされる要素,_push前のスタック,[_pushされる要素|_push前のスタック]).
スタックから要素を取り出す([_popされる要素|_pop後のスタック],_popされる要素,_pop後のスタック).
利用法は、
?- スタックを生成する(A), ・・ ,スタックに要素を追加する(2,A,B), ・・ ,スタックに要素を追加する(3,B,C), ・・ ,スタックから要素を取り出す(C,E,D), ・・・
上記の例では現在のスタックは、D であり、内容は [3] である。2 は一度プッシュされたがその後ポップされてしまった。
組合せ
[編集]リストによって与えられた集合要素のN個の組合せ。非決定性の述語である。
組合せ(X,1,[A]) :-
member(A,X).
組合せ([A|Y],N,[A|X]) :-
N > 1,
N_1 is N - 1,
組合せ(Y,N_1,X).
組合せ([_|Y],N,A) :-
N > 1,
組合せ(Y,N,A).
第二引数が1になる則ち組合せの最後の一個を残りリストXの中からmember/2を使って順に選択する。これが第一節の意味である。
第二節と第三節はバックトラックして全てのN-1個の組合せを作る非決定性の再帰的述語のパターンである。ここまでで、N-1個の全組み合わせが組み上がることを前提に、第一節でまだ選択されていない最後の一個をこれまたmember/2によって全ての可能性を選択して付加している。
実行例
?- 組合せ([a,b,c,d],3,X).
X = [a,b,c];
X = [a,b,d];
X = [a,c,d];
X = [b,c,d];
false
全ての組合せを蒐集するには、findall を用いればよい。述語を非決定性に定義することを基本として、必要な場合に findall によって全解をリストに取得する。これは Prolog の代表的なプログラムスタイルである。
全ての組合せ(L,N,LL) :-
findall(X,組合せ(L,N,X),LL).
実行例
?- 全ての組合せ([a,b,c,d],3,LL).
LL = [[a,b,c],[a,b,d],[a,c,d],[b,c,d]]
組合せの総数
[編集]異なるn個のものから異なるr個のものを選ぶ、組合せの総数は公式から、
nCr(N,R,X) :-
U is N - R + 1,
階乗(U,N,K1),
階乗(R,K2),
X is K1 // K2 .
と Prolog では定義される。階乗の定義はこのプログラム例の中で既出である。
findall を使い、組合せ が解を生成するごとに1をリストに格納することによっても、組合せの総数を求めることができる。
nCr(N,R,X) :-
findall(1,組合せ(N,R,_),L),
length(L,X).
ここでは、格納する値を1としたが、実はこれはアトム、数値、変数、何が来てもよい。
実行例
?- nCr(4,3,X).
X = 4
順列
[編集]組合せ同様これも非決定性の述語として作る。組込述語のselect/3を使うことによって、更に洗練された述語に仕上がる。
順列(_,0,[]).
順列(L,N,[A|L2]) :-
select(A,L,R),
N_1 is N - 1,
順列(R,N_1,L2).
select/3はmember/2に近い述語だが、ひとつ要素を取った残りが第三引数に単一化されている。そういう非決定性の述語である。
?- 順列([a,b,c],2,L).
L = [a, b] ;
L = [a, c] ;
L = [b, a] ;
L = [b, c] ;
L = [c, a] ;
L = [c, b] ;
false.
のように順列が取れる。これをリストに取りたい場合は、ここでもfindall/3を使って、
?- findall(L,順列([a,b,c],2,L),LL).
LL = [[a,b],[a,c],[b,a],[b,c],[c,a],[c,b]].
となる。
select
[編集]上記、組込述語select/3を定義してみる。
select(_取り出す要素,_リスト,_残り要素のリスト) :-
append(_前リスト,[_取り出す要素|_後リスト],_リスト),
append(_前リスト,_後リスト,_残り要素のリスト).
append/3を劇的に使うことによって、極めて宣言的に定義が出来上がる。
select/3には他に、以下のような再帰的な定義がある。
select(E,[E|R],R).
select(E,[A|R2],[A|R3]) :-
select(E,R2,R3).
これもmember/2やappend/3に似て、洗練された定義だが、直感的に理解させる力は上記のものに遠く及ばない。
Prologの述語定義は再帰的なものが、宣言的であり、直観に訴えるものだとは必ずしも言えない事例である。
項複写
[編集]項を複写する。ただ、単なる複写ではない、大事な点がある。変数はそのまま複写することはしない。新たに別の変数を作り出して、それを複写元の変数があった構造上の同じ位置に置く。例から示そう。
?- 項複写(a(あい,X,z(Y)),U).
U = a(あい, _G1017, z(_G1020)).
注意するべきは変数であり、ここではX -> _61017, Y -> _61020と明白に別の変数に置き換わって複写されている。それ以外の関数名 "a","z" アトム"あい"は変化していない。
この述語は高階述語を使用し、かつそれが再帰の中で引数として引き継がれて行く場合に使用される。引数として受け取った高階の述語呼び出し項と基本的に同じ構造だが、変数だけは単一化されることのない項を作り出し、それを引数として渡す時の基礎とする。引数を受け取った時点と引き渡す時点の間で変数が単一化された場合、意図した同型の引き渡し述語とならず、再帰が失敗してしまうことを避けるために使用されることが多い。項複写のプログラムを示す前に、この高階述語の使用例を示してしまう。第一引数 P に述語が渡されることとする。
foo(P,X) :-
項複写(P,Q),
call(P),
・・・
foo(Q,X).
P が単一化されてしまうと、次の再帰呼び出しでは、受け取った P とは単一化された、つまり、異なったデータを渡してしまうこととなる。Pの引数に変数があった場合そのことが起こる。引き続き変数で渡したいPであるが、これを単一化され具体化された値で渡してしまうことになる。往々にしてこの場合呼び出した再帰の副目標はプログラマの意図に反して偽となる。これを避けるために、この述語の入り口で P を複写して Q を作ってしまってそれを渡すようにする。もう少し具体的な例を示す。
リスト要素をPの第一引数と単一化してPを適用してPの第二引数を収集する([],_,[]).
リスト要素をPの第一引数と単一化してPを適用してPの第二引数を収集する([A|R1],P,[B|R3]) :-
arg(1,P,A),
call(P),
arg(2,P,B),
リスト要素をPの第一引数と単一化してPを適用してPの第二引数を収集する(R1,P,R3).
?- リスト要素をPの第一引数と単一化してPを適用してPの第二引数を収集する([2,3,5],succ(X,Y),L).
false.
と失敗する。この原因はリストの第一要素2ではsucc(2,3),が得られるが、その状態で次の再帰の引数として、P乃ちsucc(2,3)が使われてしまうからだ。この問題を回避するのが項複写/2である。
リスト要素をPの第一引数と単一化してPを適用してPの第二引数を収集する([],_,[]).
リスト要素をPの第一引数と単一化してPを適用してPの第二引数を収集する([A|R1],P,[B|R3]) :-
項複写(P,P1),
arg(1,P,A),
call(P),
arg(2,P,B),
リスト要素をPの第一引数と単一化してPを適用してPの第二引数を収集する(R1,P1,R3).
?- リスト要素をPの第一引数と単一化してPを適用してPの第二引数を収集する([2,3,5],succ(X,Y),L).
L = [3,4,6].
項複写はPが実行される前に行わなければならないことが分るだろう。
さて、本題に戻って項複写の定義は
項複写(P,P1) :-
compound(P),
同一構造を生成(P,P1,A),
項引数複写(1,A,P,P1),!.
項複写(P,P1) :-
var(P),!.
項複写(P,P).
同一構造を生成(P,P1,A) :-
functor(P,F,A),
functor(P1,F,A).
項引数複写(M,N,P,P1) :-
M > N,!.
項引数複写(M,N,P,P1) :-
'1引数を再帰的に項複写'(M,P,P1),
M1 is M + 1,
項引数複写(M1,N,P,P1).
'1引数を再帰的に項複写'(M,P,P1) :-
arg(M,P,T),
arg(M,P1,T1),
項複写(T,T1).
第一引数に複写前の項、第二引数に複写後の項がくる。項複写/2の第二節 P,P1 と変数が異なっている点が重要である。functor、arg は組込述語。functor は項を関数とアリティに分解する。arg は項の引数に値を与える。compound も組込述語で引数が複合項であるかどうか検査する。述語 1引数を再帰的に項複写 は第一文字が数字であるためシングルクォートで囲われている。
実行例
?- 項複写(a(b,U,c(V,W),d),X).
U = _1,
V = _2,
W = _3,
X = a(b,_4,c(_5,_6),d)
項複写された変数は元の変数とは別のものなので、逆にこの変数を単一化する必要がある場合は、どこに変数があるか、あるいは何に単一化すればよいかわからないという事態が生じる。その可能性に対処するためには項複写を少し拡張する。ここで、項複写 の引数の数を増やし、第三引数に複写元の項の変数、第四引数に複写先の項の変数をそれぞれ順序正しくリストに取れるようにする。
項複写(P,P1,VL1,VL2) :-
compound(P),
同一構造を生成(P,P1,A),
項複写(1,A,P,P1,VL1,VL2),!.
項複写(P,P1,[P],[P1]) :-
var(P),!.
項複写(P,P,[],[]).
同一構造を生成(P,P1,A) :-
functor(P,F,A),
functor(P1,F,A).
項引数複写(M,N,P,P1,[],[]) :-
M > N,!.
項引数複写(M,N,P,P1,VL1,VL2) :-
ひとつの引数を再帰的に項複写(M,P,P1,V3,V4),
M1 is M + 1,
項引数複写(M1,N,P,P1,VL5,VL6),
append(VL3,VL5,VL1),
append(VL4,VL6,VL2),!.
ひとつの引数を再帰的に項複写(M,P,P1,V3,V4) :-
arg(M,P,T),
arg(M,P1,T1),
項複写(T,T1,V3,V4).
これで以下の実行例に見られるように、引数の対応を取ることができる。
実行例
?- 項複写(a(b,U,c(V,W),d),X,L1,L2),V = 8.
U = _1,
V = 8,
W = _3,
X = a(b,_4,c(8,_6),d),
L1 = [U,8,W],
L2 = [_4,_5,_6]
この後、L1の中の変数とL2の中の変数はnth1/3の第一引数を共通にして取得する。
・・・
nth1(_nth1,L1,A),
nth1(_nth1,L2,B),
・・・
別に変数が取られてしまったことが却って都合の悪い場合は、 A = B のように単一化して対応付ければよい。
挿入ソート
[編集]プログラム例全体を通して、可能な限り述語名を日本語にしてきた。ここでもソートには整列という語があるが、一般にソートが使われる機会が圧倒的に多い。それでここは挿入ソートとした。与えられたリストを昇順にソートする挿入ソートのプログラムを示す。
挿入ソート(L1,L2) :-
挿入ソート(L1,[],L2).
挿入ソート([],L,L).
挿入ソート([A|R],L1,L) :-
挿入(A,L1,L2),
挿入ソート(R,L2,L).
挿入(A,[],[A]).
挿入(A,[B|R],[A,B|R]) :-
A @=< B,!.
挿入(A,[B|R1],[B|R2]) :-
A @> B,
挿入(A,R1,R2).
空のリストから始めて一要素ずつ取り出し、整列した状態で成長するリストの適切な位置に挿入するという述語である。降順の挿入ソートの場合は 挿入 を
挿入(A,[],[A]).
挿入(A,[B|R],[A,B|R]) :-
A @>= B,!.
挿入(A,[B|R1],[B|R2]) :-
A @< B,
挿入(A,R1,R2).
のように比較演算子を反転させればよい。ただ、これでは 挿入 が二通りできてしまうため、
昇順挿入(A,[],[A]).
昇順挿入(A,[B|R],[A,B|R]) :-
A @=< B,!.
昇順挿入(A,[B|R1],[B|R2]) :-
A @> B,
昇順挿入(A,R1,R2).
降順挿入(A,[],[A]).
降順挿入(A,[B|R],[A,B|R]) :-
A @>= B,!.
降順挿入(A,[B|R1],[B|R2]) :-
A @< B,
降順挿入(A,R1,R2).
のように明確に述語名を分けて定義するべきである。当然これら述語を副目標として呼び出す定義の述語名も 昇順挿入ソート、降順挿入ソート でなくてはならない。
クイックソート
[編集]与えられたリストを昇順にソートするクイックソートのプログラム例を示す。
quicksort([],[]).
quicksort([X|Xs], Ys) :-
partition(Xs, X, Smaller, Bigger),
quicksort(Smaller, L1),
quicksort(Bigger, L2),
append(L1, [X|L2], Ys).
partition([], _, [], []).
partition([X|Xs], Pivot, [X|Smalls], Bigs) :-
X @< Pivot,
partition(Xs, Pivot, Smalls, Bigs).
partition([X|Xs], Pivot, Smalls, [X|Bigs]) :-
X @>= Pivot,
partition(Xs, Pivot, Smalls, Bigs).
Pivotとは軸要素のことである。
軸要素より小さい要素を整列、軸要素より大きい要素も整列。それを軸要素を挟んで結合したものが整列したリストだ。
末尾再帰版（partitionは上に同じ）
quicksort(Xs, Ys) :-
quicksort(Xs, Ys, []).
quicksort([], Ys, Ys).
quicksort([X|Xs], Ys, Ys_1) :-
partition(Xs, X, Smaller, Bigger),
quicksort(Smaller, Ys, [X|Ys_2]),
quicksort(Bigger, Ys_2, Ys_1).
Ys-[], Ys-Ys_1, Ys-[X|Ys_2], Ys_2-Ys_1 に差分リストの関係が見られる。美しい定義であり、上記appendを使うクイックソートに較べて若干速いが、差分リストを分かっていない人に対して、言葉で説明して理解させる事は難しい。quicksort/3の第二・第三引数の位置が前の版のものと変わっている。一般にPrologでは最終引数を出力とすることが多いが、ここでは差分リストの理解を扶けるために逆転した。
限定節文法によって記述されたもの（partitionは上に同じ）
quicksort(Xs,Ys) :-
quicksort(Xs,Ys,[]).
quicksort([]) --> [].
quicksort([X|Xs]) -->
{ partition(Xs, X, Smaller, Bigger) },
quicksort(Smaller), [X], quicksort(Bigger).
実行例。
?- quicksort([3,2,1,6],L).
L = [1,2,3,6]
?= quicksort([a,b,1,2],L).
L = [1,2,a,b]
?- quicksort([聖,徳,太子],L).
L = [太子,徳,聖]
?- quicksort([2,3,3,1,1,4],L).
L = [1,1,2,3,3,4]
実行例の最後に示すように、ここでの定義では Xs を集合と見なしていない。そのため重複する2番目以降の要素を削除することはしていない。
集合解 L = [1,2,3,4] を期待する場合は、partition の定義を
partition([], _, [], []).
partition([X|Xs], Pivot, [X|Smalls], Bigs) :-
X @< Pivot,
partition(Xs, Pivot, Smalls, Bigs).
partition([X|Xs], Pivot, Smalls, [X|Bigs]) :-
X @> Pivot,
partition(Xs, Pivot, Smalls, Bigs).
partititon([_|Xs], Pivot, Smalls, Bigs) :-
X = Pivot,
partition(Xs, Pivot, Smalls, Bigs).
と文字変更する。すなわち、6行目の「X @>= Pivot」を「X @> Pivot」に変更する。なぜならば、すでに同一の値は Pivot 自身として存在するからである。さらにそれだけだと同一要素が出現すると partition は失敗してしまうから、同一要素は無視することの宣言である第四節を加える。組込述語 sort は、この集合解が返ってくる仕様に決められている。
最後に昇順または降順を区別する問題は挿入ソートの部分で述べた方針で、このクイックソートも書き直す必要がある。
木構造整列
[編集]木構造整列(ヒープソート)はメモリ上のスタックやヒープ領域に木構造を構築することによってソートを実現する。ここでは、標準入力ファイルから値の列が与えられたものを、引数上(スタック上)に木構造を成長させて、読み込みを終了したら、昇順または降順に整列された値を取り出すことのできる述語木構造整列/1を定義してみる。
木構造整列(_木構造) :-
read(_値),
木構造整列(_値,[],_木構造).
木構造整列(end_of_file,_木構造,_木構造) :- !.
木構造整列(_値_1,_木構造_1,_木構造) :-
挿入(_値_1,_木構造_1,_木構造_2),
read(_値_2),
木構造整列(_値_2,_木構造_2,_木構造).
挿入(_値,[],_木構造) :-
木構造([],_値,[],_木構造).
挿入(_値,_木構造_1,_木構造_2) :-
木構造(_左部分木_1,_値_1,_右部分木_1,_木構造_1),
挿入(_値,_左部分木_1,_値_1,_右部分木_1,_左部分木_2,_右部分木_2),
木構造(_左部分木_2,_値_1,_右部分木_2,_木構造_2).
挿入(_値,_左部分木_1,_値_1,_右部分木,_左部分木_2,_右部分木) :-
_値 @=< _値_1,
挿入(_値,_左部分木_1,_左部分木_2).
挿入(_値,_左部分木,_値_1,_右部分木_1,_左部分木,_右部分木_2) :-
_値 @> _値_1,
挿入(_値,_右部分木_1,_右部分木_2).
木構造(_左部分木,_値,_右部分木,_木構造) :-
functor(_木構造,木,3),
arg(1,_木構造,_左部分木),
arg(2,_木構造,_値),
arg(3,_木構造,_右部分木).
この木構造整列は標準入力からの整列に適したものであり、それ故に最初にそれを示したが、リストからの整列も可能である。
木構造整列(_リスト,_木構造) :-
木構造整列(_リスト,[],_木構造).
木構造整列([],_木構造,_木構造) :- !.
木構造整列([_値_1|R],_木構造_1,_木構造) :-
挿入(_値_1,_木構造_1,_木構造_2),
木構造整列(R,_木構造_2,_木構造).
と書き換えるだけである。
次に、構築が終った木構造から順に昇順に値を取り出す非決定性の述語木構造整列からの昇順取り出し/2と木構造整列からの降順取り出し/2を定義し、それを使って昇順または降順に整列したリストを取り出す。
木構造整列からの昇順取り出し(_木構造,_値) :-
木構造(_左部分木,_,_右部分木,_木構造),
整列木構造からの昇順取り出し(_左部分木,_値).
木構造整列からの昇順取り出し(_木構造,_値) :-
木構造(_,_値,_,_木構造).
木構造整列からの昇順取り出し(_木構造,_値) :-
木構造(_左部分木,_,_右部分木,_木構造),
木構造整列からの昇順取り出し(_右部分木,_値).
木構造整列からの降順取り出し(_木構造,_値) :-
木構造(_左部分木,_,_右部分木,_木構造),
整列木構造からの降順取り出し(_右部分木,_値).
木構造整列からの降順取り出し(_木構造,_値) :-
木構造(_,_値,_,_木構造).
木構造整列からの降順取り出し(_木構造,_値) :-
木構造(_左部分木,_,_右部分木,_木構造),
木構造整列からの降順取り出し(_左部分木,_値).
木構造整列からの昇順リスト(_木構造,_昇順に整列したリスト) :-
findall(_値,木構造整列からの昇順取り出し(_木構造,_値),_昇順に整列したリスト).
木構造整列からの降順リスト(_木構造,_降順に整列したリスト) :-
findall(_値,木構造整列からの降順取り出し(_木構造,_値),_降順に整列したリスト).
一般にPrologで引数に構造のあるデータが来ることは歓迎されない。関係データベースに比肩する平明さがこの言語の特長となっているからだ。この木構造整列に見られるグラフは例外的なものである。
ハノイの塔
[編集]ハノイの塔は最も Prolog 向きの課題のひとつとして知られる。ここでは、N枚の円盤を三本の柱のうち、一番左の柱から右の柱に移すケースを示す。円盤は下から上に向かうほど小さくなるように積まれ、常にその状態が維持されなくてはならない。
:- op(500,xfx,から).
:- op(400,xf,へ).
ハノイの塔(N,_移動履歴) :-
length(Ln,N),
ハノイの塔(Ln,左柱,中柱,右柱,_移動履歴).
ハノイの塔([_],_左,_中,_右,[_左 から _右 へ]).
ハノイの塔([_|Ln],_左,_中,_右,_移動履歴) :-
ハノイの塔(Ln,_左,_右,_中,_移動履歴_1),
ハノイの塔(Ln,_中,_左,_右,_移動履歴_2),
append(_移動履歴_1,[_左 から _右 へ|_移動履歴_2],_移動履歴).
冒頭、から を中置演算子、へ を後置演算子として定義している。それを使って _移動前の位置 から _移動後の位置 という項を表現して、それを履歴として残している。
このプログラムは Prolog が宣言的であることを顕著に示す好例である。この述語で述べられていることは、三回が一組となって同じパターンが繰り返されるということ。さらに最も下の一枚が順に、この課題では右柱に積まれるのだが、新しい最下層の円盤が右柱の最上位に積まれた時には、それより上の塔は中柱、左柱と交互に完全に積み上がっている。それを、ハノイの塔述語の本体の二番目の副目標で、どちらの柱を起点として以後の移動を開始するかを、引数の位置を入れ替えることだけによって、表現している。このように全体の骨格と僅かな引数の置き換えだけによって、手続的動作の全てを暗示している。このような表現力に対して「宣言的」と言うのである。
実行例
?- ハノイの塔(4,L),
member(A,L),
writef('%t\n',[A]),
fail;
true.
左柱 から 中柱 へ
左柱 から 右柱 へ
中柱 から 右柱 へ
左柱 から 中柱 へ
右柱 から 左柱 へ
右柱 から 中柱 へ
左柱 から 中柱 へ
左柱 から 右柱 へ
中柱 から 右柱 へ
中柱 から 左柱 へ
右柱 から 左柱 へ
中柱 から 右柱 へ
左柱 から 中柱 へ
左柱 から 右柱 へ
中柱 から 右柱 へ
true.
?-
nクイーン
[編集]nクイーン問題も Prolog 向き問題の代表のひとつである。チェス盤が8×8であることから、8クイーンとして課題になることが多いが、ここでは盤面の大きさを一般化したnクイーンである。チェスのクイーンは縦横斜め、盤面の自分の位置から盤面の端までが全て利き筋となる駒である。この駒を各行に適宜ひとつずつ配置して、全てのクイーンの利き筋に他のクイーンがいないように、全ての列にクイーン配置せよという問題である。一つの解は列番号のリストで得られる。nクイーンの Prolog 定義は随分と工夫され、多くの作品がある。ここでは最も一般的な戦略の解法を示す。駒の利き筋という概念を示すために、可能な限り説明的な Prolog をコードを試みている。途中に現れる Qs という論理変数に、一つずつ解候補のクイーン位置が成長していく。
nクイーン(_nクイーン,_一解) :-
'1からnまでの数リストを得る(縦横の利き筋検査はこれを行ごとに一つずつ選択することで回避される)'(_nクイーン,_数リスト),
行ごとに順に駒を置き利き筋を調べて一解を得る(_数リスト,[],_一解).
行ごとに順に駒を置き利き筋を調べて一解を得る([],_一解,_一解).
行ごとに順に駒を置き利き筋を調べて一解を得る(_位置リスト,Qs,_一解) :-
'駒の位置と残り駒の位置リストを得る(この選択自体が縦横の利き筋検査になっている)'(_駒の位置,
_位置リスト,_残り駒の位置リスト),
斜めの利き筋に駒はない(_駒の位置,1,Qs),
行ごとに順に駒を置き利き筋を調べて一解を得る(_残り駒の位置リスト,[_駒の位置|Qs],_一解).
'駒の位置と残り駒の位置リストを得る(この選択自体が縦横の利き筋検査になっている)'(_駒の位置,
[_駒の位置|_残り駒の位置リスト],_残り駒の位置リスト).
'駒の位置と残り駒の位置リストを得る(この選択自体が縦横の利き筋検査になっている)'(X,[H|T],[H|T1]) :-
'駒の位置と残り駒の位置リストを得る(この選択自体が縦横の利き筋検査になっている)'(X,T,T1).
斜めの利き筋に駒はない(_,_,[]).
斜めの利き筋に駒はない(Q,_隔たり,[Q1|Qs]) :-
Q + _隔たり =\= Q1,
Q - _隔たり =\= Q1,
_隔たり_2 is _隔たり + 1,
斜めの利き筋に駒はない(Q,_隔たり_2,Qs).
'1からnまでの数リストを得る(縦横の利き筋検査はこれを行ごとに一つずつ選択することで回避される)'(_nクイーン,_数リスト) :-
findall(M,between(1,_nクイーン,M),_数リスト).
これは非決定的な述語である。
上記の定義では、表示幅の制限から引数の途中で改行している部分があるが、引数の区切りである「,」の前後であるならば、これは構わない。6クイーンの場合の実行例を示す。
?- nクイーン(6,L).
L = [5, 3, 1, 6, 4, 2] ;
L = [4, 1, 5, 2, 6, 3] ;
L = [3, 6, 2, 5, 1, 4] ;
L = [2, 4, 6, 1, 3, 5] ;
false.
?-
ここでは4つの解が得られたが、8クイーンだと92解になる。
有限オートマトン
[編集]言語 (ab)* を受理する決定性有限オートマトンと非決定性有限オートマトンのシミュレート。
% a
% -------------------------->
% 状態_0 状態_1
% <--------------------------
% b
%
% 言語(ab)*を受理する決定性有限オートマトンの遷移
%
'言語(ab)*を受理する決定性有限オートマトン'(_記号ならび) :-
'言語(ab)*初期状態'(_状態),
'言語(ab)*を受理する決定性有限オートマトン'(_状態,_記号ならび).
'言語(ab)*を受理する決定性有限オートマトン'(_状態,[_記号|R]) :-
'言語(ab)*'(_状態,_記号,_状態_1),
'言語(ab)*を受理する決定性有限オートマトン'(_状態_1,R).
'言語(ab)*を受理する決定性有限オートマトン'(_状態,[]) :-
'言語(ab)*終了状態'(_状態).
'言語(ab)*初期状態'(状態_0).
'言語(ab)*終了状態'(状態_0).
'言語(ab)*'(状態_0,a,状態_1).
'言語(ab)*'(状態_1,b,状態_0).
%
% a
% -------------------------->
% 状態集合_0 {0} 状態集合_1 {1}
% <--------------------------
% b
%
% 言語(ab)*を受理する非決定性有限オートマトンの遷移
%
'言語(ab)*を受理する非決定性有限オートマトン'(_記号ならび) :-
'言語(ab)*初期状態'(_状態),
'言語(ab)*を受理する非決定性有限オートマトン'(_状態,_記号ならび).
'言語(ab)*を受理する非決定性有限オートマトン'(_状態,[_記号|R]) :-
'言語(ab)*'(_状態集合,_記号,_状態集合_1),
状態集合(_状態集合,_状態),
状態集合(_状態集合_1,_状態_1),
'言語(ab)*を受理する決定性有限オートマトン'(_状態_1,R).
'言語(ab)*を受理する非決定性有限オートマトン'(_状態,[]) :-
'言語(ab)*終了状態'(_状態).
'言語(ab)*初期状態'(0).
'言語(ab)*終了状態'(0).
'言語(ab)*'(状態集合_0,a,状態集合_1).
'言語(ab)*'(状態集合_1,b,状態集合_0).
状態集合(状態集合_0,0).
状態集合(状態集合_1,1).
記号ならびが [a,b,a,b,a,b] のように a,b が対になって最後まで並んでいる場合だけ真となる。正規表現を正しく理解してプログラムテスト等に挑むためには、このようなコードの理解も必要である。
非決定性有限オートマトンを状態集合で記述したが、これを'言語(ab)*' に展開してしまうことも可能である。
例えば 状態集合_1 が {1,2} である場合には、
'言語(ab)*'(0,a,1).
'言語(ab)*'(0,a,2).
'言語(ab)*'(1,b,0).
'言語(ab)*'(2,b,0).
と展開できる。複数行になるだけで、決定性有限オートマトンと形式的なの違いはなくなってしまう。決定性有限オートマトンは、このような複数の状態を書かないという約束事によって成立している。
上記、有限オートマトンと同等の Prolog 述語としての定義は、
'(ab)*'([]).
'(ab)*'([a,b|R]) :-
'(ab)*'(R).
とこれも相当に短いコードとなる。
チューリングマシン
[編集]Prolog のチューリング完全性は、チューリングマシンをシミュレートすることで示すことができる。
turing(Tape0, Tape) :-
perform(q0, [], Ls, Tape0, Rs),
reverse(Ls, Ls1),
append(Ls1, Rs, Tape).
perform(qf, Ls, Ls, Rs, Rs) :- !.
perform(Q0, Ls0, Ls, Rs0, Rs) :-
symbol(Rs0, Sym, RsRest),
once(rule(Q0, Sym, Q1, NewSym, Action)),
action(Action, Ls0, Ls1, [NewSym|RsRest], Rs1),
perform(Q1, Ls1, Ls, Rs1, Rs).
symbol([], b, []).
symbol([Sym|Rs], Sym, Rs).
action(left, Ls0, Ls, Rs0, Rs) :-
left(Ls0, Ls, Rs0, Rs).
action(stay, Ls, Ls, Rs, Rs).
action(right, Ls0, [Sym|Ls0], [Sym|Rs], Rs).
left([], [], Rs0, [b|Rs0]).
left([L|Ls], Ls, Rs, [L|Rs]).
以下のルールは簡単なチューリングマシンの例である。状態遷移と動作を Prolog の節として表現している。
rule(q0, 1, q0, 1, right).
rule(q0, b, qf, 1, stay).
このチューリングマシンは単進符号化（1の並びで符号化）した数値に1を加える。つまり、任意個の1のセル上をループし、最後に1を追加する。
?- turing([1,1,1], Ts).
Ts = [1, 1, 1, 1] ;
この例から、状態間の関係を Prolog で表現することで、任意の計算が状態遷移のシーケンスとして宣言的に表現できることが分かる。
動的計画法
[編集]以下のPrologプログラムは動的計画法を使って2つのリストの最長共通部分列問題[1]を多項式時間で求める。Prolog節によるデータベースを部分計算の結果のメモ化に用いている。
:- dynamic(stored/1).
memo(Goal) :-
( stored(Goal) -> true ; Goal, assertz(stored(Goal)) ).
lcs([], _, []) :- !.
lcs(_, [], []) :- !.
lcs([X|Xs], [X|Ys], [X|Ls]) :-
!,
memo(lcs(Xs, Ys, Ls)).
lcs([X|Xs], [Y|Ys], Ls) :-
memo(lcs([X|Xs], Ys, Ls1)),
memo(lcs(Xs, [Y|Ys], Ls2)),
length(Ls1, L1), length(Ls2, L2),
( L1 >= L2 -> Ls = Ls1 ; Ls = Ls2 ).
実行例:
?- lcs([x,m,j,y,a,u,z], [m,z,j,a,w,x,u], Ls).
Ls = [m, j, a, u]
Prologインタプリタ
[編集]Prolog言語で記述された簡単なPrologインタプリタを示す。ただしこの解釈実行/0,解釈実行/1はカットが働かない。カットが働くインタプリタはこれよりもずっと複雑になる。
解釈実行/1が中核部であるが、本体がtrueの第一節が停止節になっている。第二節は副目標が連言、第三節は副目標が選言になっている場合の定義である。引数が単項になっている第四節が組込述語の定義、第五節がユーザ定義述語の解釈実行の定義である。
解釈実行 :-
負節の読み込み(_目標),
解釈実行(_目標),
解釈実行.
負節の読み込み(_負節文字列) :-
write('?- '),
read(_負節文字列).
解釈実行(true) :- !.
解釈実行((_副目標_1,_副目標_2)) :-
!,解釈実行(_副目標_1),解釈実行(_副目標_2).
解釈実行((_副目標_1;_副目標_2)) :-
!,(解釈実行(_副目標_1);解釈実行(_副目標_2)).
解釈実行(_副目標) :-
組込述語(_副目標),!,call(_副目標).
解釈実行(_副目標) :-
clause(_副目標,_本体),解釈実行(_本体).
組込述語(_副目標) :-
predicate_property(_副目標,built).
負節の読み込み/1の中で、read/1を用いて、入力した文字列を解析して項として組み上げることを免れる定義となっている。
clause/2は述語定義されたものから第一引数の頭部と融合可能の定義節の本体を第二引数に単一化する。
append([],L2,L3,L4) :-
append(L2,L3,L4).
append([U|L1],L2,L3,[U|L4]) :-
append(L1,L2,L3,L4).
が定義済みだとして、
?- clause(append(A,B,C,D),Body).
A = [], B = L2, C = L3, D = L4, Body = true;
A = [U|L1], B = L2, C = L3, D = [U|L4], Body = append(L1,L2,L3,L4).
となる。
解釈実行/1の中でのclause/2の役割は、第一引数の本体と単一化可能の述語の節を探し、その本体を導出することである。この本体を以て解釈実行を再帰的に呼び出し、本体がなくなる、つまりclause/2の
第二引数にtrueが導かれることによって解釈実行/1は成功する。則ち最終的に単位節の頭部単一化に成功した場合である。
組込述語は導出できないので、ただ実行する(call)のみである。この組込述語が成功すると解釈実行/1は成功する。則ち真となる。ここでは副目標が組込述語であるか検査する組込述語/1predicate_property/2を呼んで組込述語かどうか検査している。
このpredicate_property/2はSWI-Prologに存在する組込述語であるが、この機能の組込述語は処理系によって規格的に統一されていない代表格のものである。存在しない場合さえあり、その時は、
組込述語(asserta(_)).
組込述語(assertz(_)).
組込述語(retract(_))
組込述語(is(_,_)).
組込述語(read(_)).
・・・
のように組込述語/1として、全てユーザ述語定義として列挙して置く必要が生じる。
Prologインタプリタに於けるカットの処理
[編集]カットを解釈できるPrologインタプリタの制作の指針を述べる。これを理解するには、 5.9 カットと否定 に対するある程度の知識が必要がである。 カットは実行する節以外には効力が及ばないことが述べられているが、このことは、解釈される対象の節のカットはいわばサインであって、解釈実行を処理する節そのものの中にこそ、カットが存在しなくてはならない、ということを意味する。
一度は真と成り通過し、バックトラックして来て、再びこれを実行しようとすれば、その解釈実行の節が偽になる。そのような工夫はどのようなものか。
ここでは、汎く知られている引数を増やして、これに対応する方法を示す。 解釈実行/2の第二引数はカットが実行された場合にのみ、意味を持つ。
cut(_).
cut(既にcutを一度通過した).
解釈実行(Var,_) :- var(Var),!,fail.
解釈実行(!,V) :- !,cut(V).
解釈実行(true,_) :- !.
解釈実行(fail,_) :- !,fail.
解釈実行((A , B),V) :- !,解釈実行(A,V),( \+(var(V)),! ; var(V),解釈実行(B,V)).
解釈実行((A -> B ; C),V) :- !,( 解釈実行(A,V) -> 解釈実行(B,V) ; 解釈実行(C,V)).
解釈実行((A ; B),V) :- !,( 解釈実行(A,V);解釈実行(B,V)).
解釈実行(P,V) :- 組込述語(P),!,call(P) .
解釈実行(P,V) :- !,clause(P,Q),解釈実行(Q,W),( \+(var(W)),!,fail; true).
只々、最終節の( \+(var(W)),!,fail; true)を実行できるように、解釈実行の引数をひとつ増やしたということである。
引数をひとつ増やしたということは、このインタプリタは単一化の量が多くなり、その実行は確実に遅くなる。
- ^ 英: longest common subsequence