Prologの構文と意味論

プログラミング言語であるPrologの構文と意味は、それぞれPrologプログラムの記述方法と解釈方法を定義する規則の集合である。この規則はISO標準ISO/IEC 13211 ^{[1]に定められているが、} Prologの実装には違いがある。

Prolog は動的に型付けされます。Prolog には、用語という単一のデータ型があり、これには、アトム、数値、変数、複合項といういくつかのサブタイプがあります。

アトムは、固有の意味を持たない汎用名です。これは、Prolog リーダーによって単一のユニットとして解析される一連の文字で構成されます。アトムは通常、Prolog コード内の単なる単語であり、特別な構文なしで記述されます。ただし、スペースやその他の特定の特殊文字を含むアトムは、一重引用符で囲む必要があります。大文字で始まるアトムも、変数と区別するために引用符で囲む必要があります。 と記述された空のリスト[]もアトムです。アトムの他の例としてはx、blue、'Taco'、 などがあります'some atom'。

数値は浮動小数点数または整数です。多くの Prolog 実装では、無制限の整数と有理数も提供されています。

変数は、大文字またはアンダースコアで始まる、文字、数字、およびアンダースコア文字で構成される文字列で表されます。変数は、任意の用語のプレースホルダーであるという点で、ロジックの変数によく似ています。変数は、統合によってインスタンス化 (特定の用語と等しくなるようにバインド) できます。単一のアンダースコア ( _) は匿名変数を示し、「任意の用語」を意味します。他の変数とは異なり、アンダースコアは述語定義内で出現するすべての場所で同じ値を表すわけではありません。

複合項は、「ファンクタ」と呼ばれるアトムと、これも項であるいくつかの「引数」で構成されます。複合項は通常、ファンクタの後に括弧で囲まれたコンマで区切られた引数項のリストが続く形で記述されます。引数の数は項のアリティと呼ばれます。アトムは、アリティが 0の複合項と見なすことができます。

複合項の例としては、truck_year('Mazda', 1986)と が挙げられます'Person_Friends'(zelda,[tom,jim])。演算子として宣言された関数を持つ複合項は、前置記法または中置記法で記述できます。たとえば、項-(z)、+(a,b)、 は、それぞれ、 、と=(X,Y)記述することもできます。ユーザーは、ドメイン固有の表記を可能にするために、任意の関数を異なる優先順位を持つ演算子として宣言できます。表記法f/n は、関数fとアリティn を持つ項を表すためによく使用されます。 -za+bX=Y

複合語の特殊なケース:

• リストは帰納的に定義されます。アトム[]はリストです。関数子 (ドット) とアリティ 2 を持つ複合項 ( .2 番目の引数がリスト) は、それ自体がリストです。リストを表す特別な構文が存在します。は.(A, B)と同等です[A|B]。たとえば、リストは.(1, .(2, .(3, [])))と書くことも[1 | [2 | [3 | []]]]、より簡潔に と書くこともでき ます[1,2,3]。
• 文字列: 引用符で囲まれた文字のシーケンスは、(数値の) 文字コードのリストに相当します。通常、ローカル文字エンコーディング、またはシステムが Unicode をサポートしている場合はUnicodeになります。

Prologプログラムは、節によって定義された関係を記述します。純粋なPrologは、一階述語論理のチューリング完全なサブセットであるホーン節に制限されています。節には、事実とルールの2種類があります。ルールは次の形式です。

頭 ：- 体。

は、「本体が true の場合、ヘッドは true です」と読みます。ルールの本体は述語の呼び出しで構成され、これはルールの目標と呼ばれます。組み込みの述語 ,/2(名前を持つ 2 項演算子を意味します,)は目標の結合を表し、 は選言;/2を表します。結合と選言はルールの本体にのみ表示でき、ヘッドには使用できません。

空の本体を持つ節は、ファクトと呼ばれます。ファクトの例は次のとおりです。

猫（トム）。

これは次の規則と同等です:

猫(トム)  :- 本当です。

別の例は次のとおりです。

Xは 3 + 2です。 

実行すると結果は次のようになります

 X = 5
 はい。

組み込み述語はtrue/0常に true です。

Prolog プログラムの実行は、ユーザーがクエリと呼ばれる単一の目標を投稿することで開始されます。論理的には、Prolog エンジンは否定されたクエリの解決反駁を見つけようとします。Prolog が使用する解決方法はSLD 解決と呼ばれます。否定されたクエリを反駁できる場合、適切な変数バインディングが配置されたクエリはプログラムの論理的帰結であることがわかります。その場合、生成されたすべての変数バインディングがユーザーに報告され、クエリは成功したとみなされます。操作上、Prolog の実行戦略は他の言語の関数呼び出しの一般化と考えることができますが、1 つの違いは、複数の節の先頭が特定の呼び出しに一致できることです。その場合、システムは選択ポイントを作成し、目標を最初の選択肢の節の先頭と統合し、その最初の選択肢の目標を続行します。プログラムの実行中にいずれかの目標が失敗した場合、最新の選択ポイントが作成されてから行われたすべての変数バインディングが元に戻され、その選択ポイントの次の選択肢から実行が続行されます。この実行戦略は、時系列バックトラッキングと呼ばれます。

mother_child ( trude 、 sally )。
 
父の子(トム、 サリー)。
父の子(トム、 エリカ)。
父の子(マイク、 トム)。
 
兄弟( X 、 Y )       :- 親の子( Z 、 X )、 親の子( Z 、 Y )。
 
親の子( X 、 Y )  :- 父の子( X 、 Y )。
親の子( X 、 Y )  :- 母の子( X 、 Y )。

この結果、次のクエリは true として評価されます。

?- 兄弟（サリー、 エリカ）。
はい

これは次のようにして得られます。最初は、クエリに一致する節ヘッドはsibling(sally, erica)最初のものだけなので、クエリを証明することは、適切な変数バインディングが配置されたその節の本体、つまり結合 を証明することと同じです(parent_child(Z,sally), parent_child(Z,erica))。証明する次の目標は、この結合の一番左のもの、つまり ですparent_child(Z, sally)。2 つの節ヘッドがこの目標と一致します。システムは選択ポイントを作成し、本体が である最初の選択肢を試しますfather_child(Z, sally)。この目標は、事実 を使って証明できるfather_child(tom, sally)ため、バインディングZ = tomが生成され、証明する次の目標は、上記の結合の 2 番目の部分 です。parent_child(tom, erica)これも、対応する事実によって証明できます。すべての目標を証明できたので、クエリは成功します。クエリには変数が含まれていないため、バインディングはユーザーに報告されません。次のような変数を含むクエリ:

?-  father_child (父、 子)。

バックトラック時に有効な回答をすべて列挙します。

上記のコードを使用すると、クエリ?- sibling(sally, sally).も成功することに注目してください。必要に応じて、関連する制限を記述する追加の目標を挿入することもできます。

反復アルゴリズムは、再帰述語によって実装できます。Prolog システムでは通常、末尾再帰、またはより一般的には末尾呼び出しを示す決定論的述語に対して、末尾呼び出し最適化 (TCO)と呼ばれるよく知られた最適化手法を実装します。末尾位置で呼び出しを実行する前に、節のスタック フレームが破棄されます。したがって、決定論的末尾再帰述語は、他の言語のループのように、一定のスタック スペースで実行されます。

ルール内のカット（ ）は!、Prologがカットの後ろの述語をバックトラックするのを防ぎます。

述語( X )  :-  1 ( X )、 !、 2 ( X )。

最初に見つかったXforの値one(X)が true であるが、two(X)それが false になる場合は失敗します。

匿名変数は_値にバインドされることはなく、述語内で複数回使用できます。

たとえば、リスト内で特定の値を検索する場合:

( V 、 [ V | _ ] )を含みます。
( V 、[ _ | T ] )を含みます:- ( V 、T )を含みます。    

組み込みのProlog述語は、否定を失敗として\+/1提供し、非単調な推論を可能にします。ルールの 目標は\+ illegal(X)

合法( X )  :-  \+ 違法( X )。

は次のように評価されます。Prolog は を証明しようとしますillegal(X)。その目標の証明が見つかると、元の目標 (つまり\+ illegal(X)) は失敗します。証明が見つからない場合、元の目標は成功します。したがって、クエリはGoal が証明可能でない場合成功する\+/1ので、プレフィックス演算子は「証明不可能」演算子と呼ばれます。この種の否定は、その引数が「根拠」である場合 (つまり、変数を含まない場合) は有効です。引数に変数が含まれている場合、有効性は失われます。特に、クエリを使用して、合法なものすべてを列挙することはできなくなります。 ?- \+ Goal.?- legal(X).

宣言的な読み方では、論理和と論理積は可換であるため、ルールの順序とルール内の目標の順序は無関係です。ただし、手続き的には、効率上の理由から、または評価の順序が重要となる不純な組み込み述語の意味論のせいで、Prolog の実行戦略を考慮することが重要になることがよくあります。また、Prolog インタープリタは、提供された順序で節を統合しようとするため、正しい順序付けを行わないと、次の例のように無限再帰が発生する可能性があります。

述語1 ( X )  :-
  述語2 ( X 、X )。
述語2 ( X 、Y )  :-
  述語1 ( X )、
  X  \=  Y 。

この順序付けにより、

?- 述語1 (アトム)。

スタックがなくなるまで繰り返し実行されます。ただし、最後の 3 行が次のように変更された場合:

predicate2 ( X , Y )  :- 
  X  \=  Y 、
  predicate1 ( X )。

同じクエリを実行すると、非常に短時間で「いいえ」という結果が返されます。

確定節文法 ( DCG )と呼ばれる特別な表記法があります。-->/2の代わりに を介して定義された規則は、:-/2プリプロセッサ ( expand_term/2、他の言語のマクロに類似した機能) によって、いくつかの簡単な書き換え規則に従って展開され、通常の Prolog 節になります。最も注目すべきは、書き換えによって述語に 2 つの追加引数が装備され、他の言語のモナドと同様に、これらを使用して暗黙的に状態をスレッド化できることです。 DCG は、リストの差異への便利なインターフェイスも提供するため、パーサーやリスト ジェネレーターの作成によく使用されます。

より大きな例では、解析に Prolog を使用する可能性を示します。

バッカス・ナウア形式で表現された文があるとします。

<文>     ::=   <統計部分> 
<統計部分>    ::=   <文> | <統計部分> <文> <文> ::= < id > = <式>  ;
 <式> ::  = <オペランド> | <式> <演算子> <オペランド> <オペランド> ::= < id > | <数字> < id > ::=   a | b
 <数字> ::=   0..9
 <演算子> ::=   + | - | *

           
       
                     

これは、1 つのトークンの先読みを行う予測パーサーに対応する DCG を使用して Prolog で記述できます。

sentence ( S )                 -->  statement ( S0 )、 sentence_r ( S0 、 S )。
sentence_r ( S 、 S )            -->  []。
sentence_r ( S0 、 seq ( S0 、 S ))  -->  statement ( S1 )、 sentence_r ( S1 、 S )。
 
ステートメント( assign ( Id , E ))  -->  id ( Id )、 [ = ]、 式( E )、 [;]。
 
式( E )  --> 項( T )、 式 r ( T 、 E )。
式 r ( E 、 E )   -->  []。
式 r ( E0 、 E )  -->  [ + ]、 項( T )、 式 r ( plus ( E0 、T )、 E )。
式 r ( E0 、 E )  -->  [ - ]、 項( T )、 式 r ( minus ( E0 、 T )、 E )。
 
term ( T )        -->  factor ( F )、 term_r ( F 、 T )。
term_r ( T 、 T )   -->  []。
term_r ( T0 、 T )  -->  [ * ]、 factor ( F )、 term_r ( times ( T0 、 F )、 T )。
 
factor ( id ( ID ))    -->  id ( ID ). 
factor ( digit ( D ))  -->  [ D ],  {  ( number ( D )  ;  var ( D )),  between ( 0 ,  9 ,  D )}.
 
id ( a )  -->  [ a ]. 
id ( b )  -->  [ b ].

このコードは、文（トークンのリストとして指定）とその抽象構文木（AST）の関係を定義します。クエリの例:

?-  phrase ( sentence ( AST )、 [ a 、= 、1 、+ 、3 、* 、b 、;、b 、= 、0 、;]). 
AST  =  seq ( assignment ( a 、 plus ( digit ( 1 )、 times ( digit ( 3 )、 id ( b )))),  assignment ( b 、 digit ( 0 )))  ;

AST は Prolog 用語を使用して表現され、最適化を適用したり、そのような式をマシン コードにコンパイルしたり、そのようなステートメントを直接解釈したりするために使用できます。述語の関係的な性質によくあるように、これらの定義は文の解析と生成の両方に使用でき、また、特定のツリーが特定のトークンのリストに対応しているかどうかを確認するためにも使用できます。公平な列挙のために反復深化を使用すると、最終的に任意の固定文とそれに対応する AST が生成されます。

?-  length (トークン、 _ )、 phrase (文( AST )、 トークン)。
 トークン =  [ a 、 = 、 a 、 (;)]、 AST  =  assign ( a 、 id ( a ))  、
 トークン =  [ a 、 = 、 b 、 (;)]、 AST  =  assign ( a 、 id ( b ))
 など。

• Prolog実装の比較