|
* 2016年 FLOPS で Ki Yung Ahn と Andrea Vezzosi の論文 Executable Relational Specifications of Polymorphic Type Systems で Prolog による Let多相の型推論器が発表されました。あまり話題にはなっていませんが、昨今の型理論には一階述語論理が用いられており、型システムの実装実験において極めて簡略に記述出来るため、利用されていく可能性があります。
* Prolog向けの集合論的型システムが実用化されれば、関数型言語学会において古くから用いられてきた数式をより形式的にできるようになるかもしれません。
== Prolog言語の基本 ==
{{Wikibooks|Prolog/言語仕様|言語仕様}}
Prologプログラムは、ホーン節、もしくは単に節と呼ばれる形式の項を並べたものである。節は、頭部と本体部からなり、<syntaxhighlight lang="prolog">
頭部.
頭部 :- 本体部.
</syntaxhighlight>
の二形式があり得る。これはそれぞれ<code>頭部.</code>の形式が「A'''は'''Bである」、<code>頭部 :- 本体部.</code>の形式が「A'''ならば'''Bである」という命題の形式に対応する。節も項であって、項は関数子といくつかの引数からなる。節の関数子は <code>:-</code> であり、頭部と本体部はその引数である。関数子が<code>:-</code>の二引数の項が節である。<code>頭部.</code>の形式は実は、頭部 <code>:- true.</code>が省略されたものと見なされ、やはり <code>:-</code> を関数子として二引数の項である。頭部は項が連接することはできない(ホーン節)が、本体部は項が連接する、そういう項であり得る。
<code>頭部 :- 副目標<sub>1</sub>,副目標<sub>2</sub>, ... 副目標<sub>n</sub>.</code>は、これ全体を目標という。目標は副目標<sub>1</sub>...副目標<sub>n</sub>の連言である。ここで<code>目標 = ( 副目標<sub>1</sub>,副目標<sub>2</sub>, ... 副目標<sub>n</sub> )</code>と置けば、<code>頭部 :- 目標.</code>であり、やはりこの節の形式も、関数子 ':-' の二引数の項であることが分かる。複数の副目標はカンマで区切られているが、このカンマは論理積を意味する。節は、その頭部の形式、すなわち関数子とその引数の数が同一の形式を持つ述語と呼ばれる単位で管理される。プログラムは項の集合であり、節の集合であると同時に、述語の集合でもある。Prologはこの項、節、述語だけでその形式を表現できる点で、他のプログラム言語とは著しく異なる。これはPrologの理論的な背景が論理学にあり、この中の概念のみで構成されて、発展してきたからである。このような節の集合をあらかじめ用意してそれを定義した上で、ある命題が真であるかどうか問うことを質問という。節の集合、つまり述語の集合をあらかじめ用意する方法については、後出の"Prologプログラミング"で述べる。Prologの処理系は、人間の入力した質問に対して、頭部が形式的に一致する節があるか調べ、あった場合はその本体部に記述されている命題と一致する節があるか[[再帰]]的に調べる。ここでは定義されたもの(処理系があらかじめ用意した組込述語も含めて)だけが、真になり、定義されていないものは必ず偽となる(閉世界仮説)。
具体的な例を見よう。「ソクラテスは人間である」「人間は死ぬ」を {{lang|en|Prolog}} で記述すると以下のようになる。ここで X は変数である。
<syntaxhighlight lang="prolog">
人間(ソクラテス).
死ぬ(X) :- 人間(X).
</syntaxhighlight>
<code>人間(ソクラテス). </code> は「AはBである」の命題の形式に対応し、ここでは、Aはソクラテス、Bは人間である。同様に、<code>死ぬ(X) :- 人間(X). </code> は「AならばBである」であり、Aは<code>人間(X)</code>に、Bは<code>死ぬ(X)</code>に対応している。システムに対して以下のように入力すると、true が返される。<syntaxhighlight lang="prolog">
?- 死ぬ(ソクラテス).
</syntaxhighlight>
これは「ソクラテスは死ぬか」と質問したことに対して、システムが内部で推論を行なって、既知の知識から答えを出したものである。それではここでの既知の知識とはなんであろうか。それは、<syntaxhighlight lang="prolog">
人間(ソクラテス).
死ぬ(X) :- 人間(X).
</syntaxhighlight>
であり、内部で行っている推論とは、?- 死ぬ(ソクラテス). から 死ぬ(X) :- 人間(X). により導出されて、
<syntaxhighlight lang="prolog">
?- 人間(ソクラテス).
true
</syntaxhighlight>
が、確認される過程である。今度は以下のように入力してみる。これは、「死ぬのは誰か」と質問したことと同じになる。この場合もシステムが内部で推論を行なって、死ぬ（X）を満たすXを表示する。<syntaxhighlight lang="prolog">
?- 死ぬ(X).
X = ソクラテス
</syntaxhighlight>
他のプログラム言語に比べると質問を基本的骨格としている点でユニークであるが、更に、{{lang|en|Prolog}} は複数の計算結果があり得るという点でも極めてユニークなプログラム言語である。先のプログラム例を拡張して
<syntaxhighlight lang="prolog">
人間(ソクラテス).
人間(アリストテレス).
死ぬ(X) :- 人間(X).
</syntaxhighlight>
とした場合、死ぬ（X）を満たすXは複数（ソクラテスとアリストテレス）がありうる。述語 人間 に複数の節を設けて、その引数にソクラテス、アリストテレスと列記して行くだけで、質問に対して複数の解を処理系が列挙するようになる。他の言語でこういう機能を実現する時に見られるような、手続き的なループや情報を管理する配列の添字管理のようなものは全く現れない。多くの{{lang|en|Prolog}} 処理系ではこのような複数解が存在する時に新たな解を得る場合は<syntaxhighlight lang="prolog">
?- 死ぬ(X).
X = ソクラテス ;
X = アリストテレス
</syntaxhighlight>
と ";"（セミコロン）記号を用いて他の解を得る。";"はこの解は真ではない、という質問者の意思表示である。ここではインタプリタのトップからの質問、すなわち対話環境にあるから、<code>X = アリストテレス</code>が処理系からの質問者に対する応答、質問となっている。質問者は「この解は真ではない」と否定することができる一方、呈示された解(ソクラテスまたはアリストテレス)を真と決定することもできる。このように処理系から見て外部からの介入によって真を得ることを非決定性という。この非決定性がコンピュータ言語としての{{lang|en|Prolog}} の際立った特徴の一つである。
もうすこし具体的な{{lang|en|Prolog}}プログラムの例を以下に示す。「<code>%</code>」から行末までは注釈である。<syntaxhighlight lang="prolog">
% member(X,Y)はXがリストYの要素として含まれているときに成功する。
% そうでないときは失敗する。
member(X, [X|_]). % Xがリストの先頭要素と同じ場合
member(X, [_|Y]) :- member(X, Y). % それ以外の場合
</syntaxhighlight>
<code>member(X,Y)</code> は要素XがリストYのメンバーであるかを調べるプログラムであると同時に、「要素XがリストYのメンバーである」という関係も宣言的に表している。実行例を以下に示す。要素XがリストYのメンバーであれば成功する。<syntaxhighlight lang="prolog">
?- member(サザエ, [波平,サザエ,マスオ]).
true.
</syntaxhighlight>
要素XがリストYのメンバーでなければ失敗する。
<syntaxhighlight lang="prolog">
?- member(サザエ, [ワカメ,マスオ,タラオ]).
false.
</syntaxhighlight>
Xの部分を変数のままにすると、リストYのメンバーである要素が結果として返る。すなわち、ジェネレータとして働く。
<syntaxhighlight lang="prolog">
?- member(X, [ワカメ,マスオ,タラオ]).
X = ワカメ ;
X = マスオ ;
X = タラオ
</syntaxhighlight>
二つのリストの共通メンバーを求めるには単純に","で区切って並べればよい。この","はANDの意味を持つ。
<syntaxhighlight lang="prolog">
?- member(X, [波平,サザエ,マスオ]), member(X, [ワカメ,マスオ,タラオ]).
X = マスオ
</syntaxhighlight>
要素Xを指定しリストYを変数のままにすると、それらがメンバーであるリストが結果として返る。
<syntaxhighlight lang="prolog">
?- member(波平, Y), member(サザエ, Y), member(マスオ, Y).
Y = [波平,サザエ,マスオ|_G001]
</syntaxhighlight>
上の"_G001"は{{lang|en|Prolog}}処理系が作成した仮の変数で、リストの後半が不定であることを示す。
== Prologプログラム例 ==
{{Wikibooks|Prolog|プログラム例Prolog}}
=== [[クイックソート]] ===
<syntaxhighlight lang="prolog">
quicksort([],[]).
| 