Clever Geek Handbook

プログラマヌ向け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郚で怜蚎したす。


More articles:


All Articles