プロローグの構文とセマンティクス

From Wikipedia, the free encyclopedia

プログラミング言語であるPrologの構文とセマンティクスは Prolog プログラムの記述方法と解釈方法をそれぞれ定義する一連の規則です。ルールはISO 標準ISO/IEC 13211 [1]に記載されていますが、 Prolog の実装には違いがあります。

データ型

Prolog は動的に型付けされます。これには単一のデータ型termがあり、これにはいくつかのサブタイプ ( atomsnumbersvariables、およびcomplex terms )があります。

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

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

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

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

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

複合語の特殊なケース:

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

プロローグプログラム

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

 :- .

「体が真なら頭も真」と読みます。ルールの本体は、ルールのゴールと呼ばれる述語の呼び出しで構成されます。組み込みの述語 ,/2( name を持つ 2 アリティ演算子を意味する,)は、ゴールの結合を表し、disjunction;/2を表します。接続詞と選言は、規則の頭ではなく、本体にのみ表示できます。

本文が空の句はファクトと呼ばれます。事実の例は次のとおりです。

トム)。

これは次のルールと同等です:

(トム)  :-  true .

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

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 と評価されます。

?- 兄弟( sally  erica )。
はい

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

?- 父子( )。

バックトラッキングに関するすべての有効な回答を列挙します。

上記のコードでは、クエリ?- 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.この種の否定は、その引数が"ground" (つまり、変数を含まない)の場合に有効です。引数に変数が含まれていると健全性が失われます。特に、クエリを使用して、正当なものをすべて列挙することはできなくなりました。 ?- legal(X).

セマンティクス

宣言的な読み方では、ルールの順序とルール内のゴールの順序は関係ありません。論理的分離と論理積は交換可能だからです。ただし、手続き的には、効率上の理由から、または評価の順序が重要な不純な組み込み述語のセマンティクスのために、Prolog の実行戦略を考慮することがしばしば重要です。また、Prolog インタープリターは提供された順序で句を統一しようとするため、正しい順序付けに失敗すると、次のように無限再帰につながる可能性があります。

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

この順序を考えると、次の形式のクエリは

?- 述語 1 (アトム)。

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

predicate2 ( X , Y )  :- 
  X  \=  Y , 
  predicate1 ( X ).

同じクエリは、非常に短い時間で No. の結果につながります。

定節文法

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

パーサーの例

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

Backus–Naur 形式で表現された文を考えると、次のようになります。

<>     ::=   <統計部> 
<統計部>    ::=   <> | < stat_part >  <ステートメント> 
<ステートメント>    ::=   < id > = <>  ;
<>   ::=   <オペランド> | <>  <演算子>  <オペランド> 
<>      ::=   < ID > | <数字> 
< ID >           ::=   a | b
 <数字>        ::=   0..9
 <演算子>     ::=   + | - | *

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

( S )                 --> ( S0 )、 文_r ( S0 ,  S )。
文_r ( S ,  S )            -->  []. 
文_r ( S0 ,  seq ( S0 ,  S ))  --> ( S1 ), 文_r ( S1 ,  S ).
 
ステートメント( assign ( Id , E ))  -->  ID ( Id )、 [ = ]、 ( E )、 [;]。
 
( E )  --> ( T )、 式_r ( T  E )。
式_r ( E ,  E )   -->  []. 
式_r ( E0 ,  E )  -->  [ + ], ( T ), 式_r (プラス( E0 , T ),  E ). 
式_r ( E0 ,  E )  --> [ - ]、 用語( T )、 式_r (マイナス( E0  T )、 E )。
 
term ( T )        -->  factor ( F ),  term_r ( F ,  T ). 
term_r ( T ,  T )   -->  []. 
term_r ( T0 ,  T )  -->  [ * ],  factor ( F ),  term_r (( T0 ,  F ),  T ).
 
因子( id ( ID ))    -->  id ( ID )。
factor ( digit ( D ))  -->  [ D ],  {  ( number ( D )  ;  var ( D )),  between ( 0 ,  9 ,  D )}.
 
id ( a )  -->  [ a ]. 
ID ( b )  -->  [ b ]。

このコードは、文 (トークンのリストとして与えられる) とその抽象構文木(AST)の間の関係を定義します。クエリの例:

?- フレーズ(( AST ),  [ a , = , 1 , + , 3 , * , b ,;, b , = , 0 ,;])。
AST  =  seq ( assign ( a ,  plus ( digit ( 1 ),  times ( digit ( 3 ),  id ( b )))),  assign ( b , 数字( 0 )))  ;

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

?- 長さ( Tokens ,  _ ), (( AST ),  Tokens ). 
 トークン =  [ a ,  = ,  a ,  (;)],  AST  =  assign ( a ,  id ( a ))  ; 
 トークン =  [ a ,  = ,  b ,  (;)],  AST  =  assign ( a ,  id ( b ))
 など

も参照

参考文献

  1. ^ ISO/IEC 13211: 情報技術 — プログラミング言語 — Prolog . 国際標準化機構、ジュネーブ。