📊 🚅 🌂 プログラマー向けPROLOG 📐 👼🏻 💅

論理プログラミング言語PROLOG（以下-PROLOGUE）は、ほとんどのプログラマーにとって、混乱を招き、実用に適さないもののようです。同時に、インターネットはシンボリック情報に基づいているため、現代のプログラマーのほとんどがシンボリックデータ構造を処理する必要に直面しており、PROLOGUE論理プログラミング言語はこのために設計されています。この言語は、シンボリック構造、テキストファイルの操作、およびインテリジェントプログラムの構築に最適です。
PROLOGUEでの長年の仕事の後、私はすべての著者が誇らしげに言う-「高いエントリーしきい値」と言う新しい絡み合ったHaskellに出会いました。私の意見では、このしきい値の「高さ」は、混乱した構文と組み込みプロシージャのヒープの結果として形成されました。この「高さ」のもう1つの原因は、読者がプログラムを書いたことがないかのように書かれた多数のマニュアルの著者の慢さです。
私はすぐに「ネイティブ」プロローグに戻りたかった-シンプルでわかりやすい。宣言的セマンティクスなどの山なしで説明すれば、「通常の」プログラマーの論理プログラミングに入る時間は30分を超えないでしょう。
手続き型プログラミングの観点から説明しようとします。
PROLOGUEには、手続き型言語との2つの主な違いがあります。計算を整理する方法とデータを表示する方法です。言語のこれらの側面の両方は、従来のプログラミング言語と根本的に異なります。しかし、論理プログラミングはフォンノイマンアーキテクチャと同じマシン上で実装されることを忘れないでください。
すべての操作がプロシージャの呼び出しに限定されるプログラミング言語を想像してください。さらに、各プロシージャにはいくつかのバリアントが存在し、プログラム自体が、プロシージャのソースデータ実装オプション（本体）の特定のバリアントごとに適切な、より正確に適切なものを選択します。適合性の判断方法-プロシージャ実行の結果に応じて、プログラム実行中の各プロシージャ呼び出しは、論理値（TRUEまたはFALSE）を受け取ります。同じ名前とアリティを持つ一連のプロシージャは、述語と呼ばれます。
PROLOGUE言語の各述語は、2つのパラメーター（名前とアリティ）のパラメーターの数によって識別されます。たとえば、リスト逆述語はnrev / 2として識別され、リスト結合述語はappend / 3です。パラメーターや変数の宣言は必要ありませんが、パラメーターをプロシージャヘッダーのパターンに制限できます。たとえば、述語のあるバリアントでは、最初のパラメーターを[]-空のリスト、別のパラメーター-[A、B、C]-3つの要素のリスト、3番目のパラメーターで[H | T]-空ではない任意のリストとして指定できます。
プロシージャ本体の条件が満たされない場合、実行は停止し、プロシージャ呼び出し、より正確には、プロシージャ本体の次のバージョンの実行が停止し、値FALSEが取得されます。この場合、言語インタープリターはこのプロシージャの次のボディバリアントを起動します。すべてのオプションが不適切であることが判明した場合、前の手順に戻り、オプションも列挙します。したがって、PROLOGUEの計算は、手順の入れ子ツリーを走査することになります。
前の呼び出しに戻ることをバックトラッキングと呼びます。キャンセルされたプロシージャの変数が受け取ったすべての値がキャンセルされるため、これは本質的にロールバックです。バックトラッキングは、この言語のユニークなツールであり、他の一般的なプログラミング言語には類を見ません。バックトラッキングは、推論ツリーを完全にトラバースし、知的問題を解決するための基礎を提供します。

PROLOGUEシステムでプログラムを解釈する（目標を達成する）ためのアルゴリズム。

入口：ターゲットp（A1、A2、...、An）

1.メモリ内で、アリティnのpという名前のプロシージャを見つけます。
2.見つかったプロシージャの見出しでターゲットの入力パラメータを統一します。
3.パラメータの統一に合格した場合、見つかったプロシージャの本体から最初の目標を達成します。
4.統合がパスしない場合、P / nプロシージャの次のバージョンを見つけます。
5. P / nプロシージャの次のバージョンが見つからない場合、FAIL結果を終了します。
6.最初の目標が完了したら、次の目標に進みます。
7.次の目標が達成されない場合は、前の目標に戻り、その実装の次のバージョンを完了します。
8. P / nプロシージャの現在の実装オプションが完了していない場合は、次のオプションに進みます。
9.手順の本体のすべての目標が完了したら、結果がTRUEになるように作業を終了します。

この計算構造に関連して、プロシージャへの各呼び出しは、達成可能または不可能な目標と呼ばれます。 PROLOGUEのすべての計算には論理的な意味があります。計算は推論（証拠）の検索とも呼ばれ、言語PROLOGUEは論理プログラミングの言語です。
おそらく構文上、PROLOGUEはプログラミング言語の中で最も単純です。主な構文手続きは述語です-手続き呼び出しに似た式-名前と引数リスト-
P（x1、... xn）。名前は小文字で、変数は大文字で書きます。
詳細を省略すると、PROLOGUE構文は次のように記述できます。

<PROLOGUE句> :: = <ルール> | <事実> | <リクエスト>
<ルール> :: = <head >>：-'<body>
<ファクト> :: = <ヘッド> '。'
<クエリ> :: = <body> '。'
<body> :: = <target> / '、' <target> / '。'
<head> :: = <述語>
<ターゲット> :: = <述語> | <式>
<述語> :: = <名前> / '（' <term> / '、' <term> / '）' /
<term> :: = <atom> | <predicate> | <list>
<アトム> :: = <変数> | <番号> | <文字列> | <名前>
<リスト> :: = <タイトル付きリスト> | <シンプルリスト>
<タイトル付きリスト> :: = '[' <term> / '、' <term> / '|' <term> ']'
<シンプルリスト> :: = '[' <term> / '、' <term> / ']' | '[' ']'
<式> :: = <用語> / <演算子> <用語> /
<演算子> :: = 'is' | '=' | '==' | '\ =' | '> =' | '= <' | '= \ =' |

構文からわかるように、「is」述語を除き、PROLOGUEには予約名はありませんが、さまざまな組み込み述語が便利で外部環境との通信に使用されます。

例は家族関係です。
関係のルール-配偶者、子供、母親、娘、兄弟、子孫を定義します。家族関係は、バイナリ（単項）述語-ルール（変数を伴う述語）およびファクト（定数を伴う述語）によって定義されます。家族関係は誰にとっても明らかなので、ルールは理解しやすいです。たとえば、最初のルールでは、YがXの子でXが女性の場合、XはYの母です。

母（X、Y）：-子（X、Y）、女性（X）。
娘（X、Y）：-子（Y、X）、女性（X）。
孫（X、Y）：-子（X、Z）、子（Z、Y）。
子孫（X、Y）：-子（X、Y）。
子孫（X、Y）：-孫（X、Z）。

事実は、特定の家族の親relativeを説明しています。

骨髄（ジョン、メリ）。女性（メリ）。
子（ジョン、ジャック）。子（メリ、ジャック）。子供（ジョン、ケイト）。
骨髄（ジャック、ジョーン）。骨髄（ケイト、ディック）。
子供（ジャック、ヘンリー）。子（キャット、ジョシュ）。
男性（ジョン）。女性（メリー）。
男性（ヘンリー）。女性（ジョーン）。
男性（ジョシュ）。男性（ディック）。

1つのルールセット（プログラム）をさまざまなファクトセット（データ）に適用できます。
可能なクエリのセットは、既存のルールのセットによって決定されます。各ルールのヘッダーは、クエリを構築するための基礎です。
リクエストには、確認と検索の2種類があります。
検索クエリの例：
キャットは誰の娘ですか？ -娘（X、キャット）。
ヘンリーは誰の孫ですか？ -孫（X、ヘンリー）
テストリクエストの例：
ディックはメリの赤ちゃんですか？ -子供（メリー、ディック）。

PROLOGUEの主な概念：リスト、再帰、統合、バックトラック。リストは、この言語で使用される主要なデータ構造です。リストは、すべての複雑な計算を整理するための基礎です。リストの主なプロパティの1つは、リストの要素とサイズに制限がないことです。ネストリストも何にも限定されません。言語のリストは、「head」と「tail」の2つの要素の構造として解釈されます。この分離はリストの計算の基礎であるため、最も一般的に使用されるリストパターンは[H | T]です。
リストの最初の要素は任意の構造を持つことができ、2番目の要素もリストです。空のリストには要素が含まれておらず、[]として示されます。
言語の2番目の基本構造単位-述語の形式は-p（A1、A2、..）です。述語は、データを1つのセマンティック単位にグループ化するのに便利です。リストとは異なり、述語引数の数は固定されています。述語の名前は大文字で、言語のすべての定数も大文字です。
変数は常に大文字で始まります。変数に基づいて、リストのパターンを作成できます。

リストパターンの例：
[H | T]は空のリストではありません。
[]-空のリスト。
[A1、A2、A3]-3つの任意の要素のリスト。
[A、A、A | T]-最初の3つの要素が一致するリスト。
[x、10 | T]-記号定数「x」が最初にあり、数値定数10が2番目にあるリスト。
リスト構造の再帰的性質は、再帰的コンピューティングを編成する上で重要な要素です。再帰述語には、少なくとも2つの手順があります-1つは一般的な場合、もう1つは完了用です。
リストの再帰性により、リストに対する操作のアルゴリズムを簡単に定式化できます。
例：リストの長さを計算します。

長さ（[H | T]、N）：-長さ（T、N1）、NはN1 + 1です。
長さ（[]、0）。

例：リストの反転。

nrev（[H | T]、L）：-nrev（T、L1）、追加（L1、[H]、L）。
nrev（[]、[]）。

PROLOGUEには関数がないため、すべての手続き型言語で行われているように、たとえば、リストの長さ（L）を引数として挿入することはできません。
同時に、PROLOGUEは、追跡を除くすべての操作が明示的に記述された完全に命令的な言語と見なすことができます。
一見統一することで、ある種の謎と不可解さが言語に導入されますが、完全に手続き的な説明があります。
統合は、パラメータをパターンに置換することであり、入力パラメータを選択するだけでなく、目的のリストアイテムを自動的に選択して操作するためにも使用されます-リストのヘッド要素を追加および削除します。
例：リストを結合します。

追加（[H | T]、L、[H | L2]）：-追加（T、L、L2）。
追加（[]、L、L）。

2番目の引数はリストである必要があるため、2番目の引数を[H1 | T1]の形式で記述する方が適切ですが、2番目の引数も空のリストになる可能性があるため、述語が複雑になります。
PROLOGUEの変数は論理的です。同じ手順内で繰り返し統一することは不可能です。 L = [a、b、c]、そしてL = [12]と書くことはできません。 1つのプロシージャの本体内のすべての統一は計算プロセス中に修正できないため、変数の論理は統一を複雑にします。つまり、互いに矛盾することはできません。
論理変数の統合は、完全に命令的な説明を持つ予期しない効果をもたらします。
例：リスト結合述語のユースケース。
接続：

追加（[a、b、c]、[d、e、f]、L）。
L = [a、b、c、d、e、f] =>
はい。

リンクリストの検証：

追加（[a、b、c]、[1,2,3]、[a、b、c、1,2,3]）。
はい。

リスト展開：

追加（L1、L2、[a、b、c]）。

L1 = [a、b、c]
L2 = []->;

L1 = [a、b]
L2 = [c]->;

L1 = [a]
L2 = [b、c]->;

L1 = []
L2 = [a、b、c]->;
いや

ここで、「;」記号は、バックトラッキングを開始して別のソリューションを要求することを意味します。

減算リスト：

追加（[a、b]、L、[a、b、c、d]）。
L = [c、d]。

PROLOGUEでは、バックトラッキングを伴う計算（非決定的）とそれを伴わない計算（決定的）を区別するのが慣習です。
非決定的述語の例：数値パズルを解く。

/ *
ドナルド
+
ジェラルド
-ロバート* /

合計（L1、L2、L3）：-
sum1（L1、L2、L3、L1、L2、L3.0、[0,1,2,3,4,5,6,7,8,9]）。

sum1（L1、L2、L3、L11、L12、L13、Ii、Lv）：-
dl（L11、L111、E1）、
dl（L12、L121、E2）、
dl（L13、L131、E3）、
val（E1、Lv、Lv1）、val（E2、Lv1、Lv2）、val（E3、Lv2、Lv3）、
sd（E1、E2、E3、Ii、Io）、
sum1（L1、L2、L3、L111、L121、L131、Io、Lv3）

sum1（L1、L2、L3、[]、_、_、0、_）：-！..

dl（[H | T]、[H | T1]、E）：-dl（T、T1、E）。
dl（[H]、[]、H）。

val（E、L、L）：-nonvar（E）。
val（E、L1、L2）：-del（E、L1、L2）。

sd（A、B、C、Ii、Io）：-
C1はA + B + Ii、
CはC1 mod 10、
IoはC1 // 10。

del（E、[E | T]、T）。
del（E、[H | T]、[H | T1]）：-del（E、T、T1）。

s：-
A1 = [D、O、N、A、L、D]、
A2 = [G、E、R、A、L、D]、
A3 = [R、O、B、E、R、T]、
合計（A1、A2、A3）、
書き込み（A1）、nl、
書き込み（A2）、nl、
書き込み（A3）、nl。

述語sum / 3は、与えられた文字式の数値を選択する基本操作を実行します。計算は、任意の長さの2つの数値を追加するための数式に対して実行されます。既知の番号がある場合は、変数の代わりにそれらを挿入できます。用語の長さが異なる場合、対応するリストの先頭にゼロを挿入できます。
述語sum1 / 8は、最初の3つの引数を使用して結果を書き込みます。4、5、6の番号が付けられた引数は作業変数、7番目の引数は桁上げの初期値、8番目の引数は有効な数字のリストです。
dl / 3述語は、変数のリストから最後の要素を選択して削除します。
述語val / 3は残りのオプションのリストから有効な値を選択しますが、選択された数字オプションは有効なオプションのリストから削除されます。
次の文字の値オプションが以前に設定されていた場合、変更されません。
sd / 5述語は、1つの列の指定された3桁の数字のバリアントをチェックします。

A + B + Ii = C + Io * 10

sd / 5が失敗すると、バックトラッキングが発生します-述語の最後の呼び出しval / 3は、変数E3に新しい値を割り当てます。どのE3値も適合しない場合、バックトラッキングは1ステップ戻ります-E2に新しい値が選択され、次に-オプションE3 E2がE1に適切でない場合。
述語sum1 / 8は、入力変数リストが使い果たされるまで再帰的に実行されます。
s / 0述語は、sum / 3述語を呼び出して1つのパズルバリアントを解決する例です。
この例からわかるように、PROLOGUEプログラムは非常にコンパクトにできますが、暗黙的な関数呼び出しは使用されないため、アルゴリズムはシンプルで透過的です。

このようなパズルを解くためのプログラムを開発することができます。たとえば、すべてのタイプの数値パズルについて、入力データを改善するなど、普遍的なものにすることができます。
これを行うには、字句解析や解析などの操作を行う必要があります。これらの操作については、第2部で検討します。

プログラマー向けPROLOG

More articles: