Prolog Language
差異リスト
サーチ…
前書き
Prologの相違点リストは、 ある点までのリストの構造を知るための概念です。述語の完全な評価が終わるまで、残りのリストは非結合のままにすることができます。その終わりが不明なリストは、 オープンリストと呼ばれ、 穴で終わります。この手法は、複雑な構文や文法を検証するのに特に便利です。
よく知られたDefinite Clause Grammars（DCG）は差異リストを使ってフードの下で動作しています。
基本的な使用法
述語sumDif/2考えてみましょう。リストの構造がいくつかの制約に一致するかどうかを検証します。第1項は分析するリストを表し、第2項は、制約条件に未知の第1リストの部分を保持する別のリストを表す。
デモンストレーションのために、 sumDif/2はn個の整数を合計する算術式を認識します。
sumDif([X, +|OpenList], Hole) :-
integer(X),
sumDif(OpenList, Hole).
検証するリストの最初の要素は、ここではXで示され、その後に加算記号（ + ）が続く整数です。後で処理する必要のあるリスト（ OpenList ）の残りの部分は、そのレベルで未確認のまま残されます。 Holeは、検証する必要のないリストの一部を表します。
述語sumDif/2別の定義を与えて、算術式の検証を完了しましょう：
sumDif([X|Hole], Hole) :-
integer(X).
オープンリストの先頭にXという整数が直接存在することが期待されます。興味深いことに、 Hole残りの部分は未知のまま残されており、これが差異リストの全目的です。リストの構造は一点まで分かっています。
最後に、欠落している部分は、リストが評価されるときに来ます：
?- sumDif([1,+,2,+,3], []).
true
これは、述語が使用され、リストの最後が記述されているときです。ここで[]は、リストに追加の要素が含まれていないことを示します。
算術式を評価する
括弧の使用法を使って、加算、乗算を行うための文法を定義しましょう。この例にさらに価値を加えるために、算術式の結果を計算します。文法の要約：
式→時間
式→時間 '+'式
時刻→要素
時刻→要素 '*'回
要素→「整数」
要素→ '（'式 '）'
リスト、穴、算術式の値を開く必要があるため、すべての述語は3のアリティを持ちます。
expression(Value, OpenList, FinalHole) :-
times(Value, OpenList, FinalHole).
expression(SumValue, OpenList, FinalHole) :-
times(Value1, OpenList, ['+'|Hole1]),
expression(Value2, Hole1, FinalHole),
plus(Value1, Value2, SumValue).
times(Value, OpenList, FinalHole) :-
element(Value, OpenList, FinalHole).
times(TimesValue, OpenList, FinalHole) :-
element(Value1, OpenList, ['*'|Hole1]),
times(Value2, Hole1, FinalHole),
TimesValue is Value1 * Value2.
element(Value, [Value|FinalHole], FinalHole) :-
integer(Value).
element(Value, ['('|OpenList], FinalHole) :-
expression(Value, OpenList, [')'|FinalHole]).
穴の原理と値の計算方法を正しく説明するには、2番目の節のexpression考えてみましょう。
expression(SumValue, OpenList, FinalHole) :-
times(Value1, OpenList, ['+'|Hole1]),
expression(Value2, Hole1, FinalHole),
plus(Value1, Value2, SumValue).
オープンリストは、述語OpenListによって示される。検証する最初の要素は、加算記号（ + ）の前に来る要素です。最初の要素が検証されると、追加シンボルが直後に続き、リストの続きであるHole1ます。 Hole1は検証する次の要素であり、別のexpressionであることがHole1いるため、 Hole1は述語expression与えられた項です。
値は常に第1項で表されます。この節では、 Value1 （加算記号の前のすべて）とValue2 （加算記号の後のすべて）の合計によって定義されます。
最後に、式を評価することができます。
?- expression(V, [1,+,3,*,'(',5,+,5,')'], []).
V = 31