Prolog
（プロログ）は、非手続き型プログラミング言語の一つ。論理型言語に分類される。名称は、「論理を使ったプログラミング」を意味するフランス語「""」に由来している。
1972年ごろにフランスのアラン・カルメラウアーとフィリップ・ルーセルによって考案された。
成立の事情から、 プログラムは論理式とみなされ、その実行は述語論理によって述語が定義された環境における定理証明に擬して解釈されることが多い。利用者は論理プログラミングの枠組みを、取り分け述語論理を学習することで、この枠組みに極めて忠実なこの言語の基礎的な構造のほとんどを理解できる。その言語仕様はこの枠組み以外には考案者たちも含めてそれ以上の拡張をほとんど行っていないため、他のプログラム言語とは異なり、学習しなくてはならない概念や用語もまた、述語論理のものだけでこと足りる。計算機科学の新しい概念や新しい手法とは無縁である。
のプログラムは一階述語論理に基づいてデータ間の関係を示す命題として記述され、処理系がそれらに単一化(ユニフィケーション)と呼ばれるパターンマッチングを施しながら、与えられた命題が成立するか再帰的手続きによって探索している。
プログラムの実行は述語集合が定義された環境の元で、質問することによってなされるが、これは反駁という述語論理的な証明過程を模して、処理系が用意する導出木と呼ばれるグラフをたどって解を得る過程である。
述語論理を論理的な背景に持つことによって、Prolog のプログラムはその正しさを確認することが比較的容易である。同時に、プログラマは でプログラミングすることが何を意味するかを明確に理解した上で、プログラムを書いていくことができる。
上記は の一つの解釈である。一方、 というプログラム言語を述語論理という枠にはめないで捉える立場もある。導出、単一化、非決定性、双方向性、関係データベースといったこの言語に独特の機能とその表現力、記述力に着目し、そのプログラム言語としての可能性を率直に評価しようとするものだ。
新たに を学びたいと思う人は、他のプログラム言語を全く知らなくても、ソフトウェア科学的な予備知識や概念に不通であっても、単一化という単純なルールをほとんど唯一の基軸として、パズル的な、あるいはゲーム的な感覚にだけ導かれて、プログラムを簡単に書き進むことができる。さらに、どの言語にも比して平坦で、平明な言語構造を持つ はラベル名（アトム、関数名、述語名）に適切な意味性を付与することにより、自然言語の領域にも接近したプログラミングが期待できるほとんど唯一の言語でもある。
十分述語論理的な教養を持った上で を学び、そのプログラムを書くならば、短期間で高度で安定したプログラムを書くことができる。しかし、それを前提としないでも、 は冒険的で、未知の領域に満ちたプログラム言語なのである。
実はこれらの主張は、述語論理的な主張に隠れて、これまであまり強調されたことがなかった。
このような立場や主張が生まれる背景には、 が期待されたほどにはソフトウェア革新の担い手になり得ていない理由が、その後の数理論理学の学問的な評価をもって、プログラム言語としての可能性を十分検証することを放棄して、定理証明といった狭い目的へ封じ込めようとする風潮を生んだことにある、という反省がある。そのことを踏まえて、 が述語論理から成立したことにこだわらず、実在するプログラム言語として自由な視点からこの言語を見直そうとするものである。
は の資産の多くを継承して間違いなく記号処理用の言語であるが、人工知能言語として分類されることも多い。これは、人工知能の世界では述語論理が古くから理論的な柱の一つとなっているからである。述語論理を基礎とするトップ・ダウン式の問題解決と同じく述語論理を基礎とする の駆動機構の相性は当然良いため、人工知能研究に広く利用されてきた。特にエキスパートシステムで多用されるプロダクションシステムにおいては、ルールを自然に自ら動的に変更できる能力を持つことと、後ろ向き推論と呼ばれる推論が の導出過程そのものであることから、その最も主要な記述言語の位置を占めてきた。
は一階の述語論理に対応することから論理型言語に分類される汎用言語であるが、その主張の一行一行を独立して論理式とほとんど等価な表現で行うことから、最も代表的な宣言型言語と見なされている。 のプログラム単位である述語の各節の本体に現れる質問単位である副目標数は平均5個以内と極めて少ない。この副目標と各節の頭部に現れる引数の組み合わせによって得られる関係が述語の意味を構成している考えられる。これが宣言型とされるゆえんである。
Prologの自然な定義では、
ここで示した   が、一つの述語において、高々  くらいまでに収まる。
単一化は1960年代の述語論理理論の発展の鍵となった概念であるが、 が述語論理に導かれて機械による自動証明を実現するためのプログラム言語として成立したことから、必然的にこの言語の必須の最も重要な機構となった。単一化は副目標（質問）と対応する定義節の頭部のパターンが完全に一致するか、調べることで、節の選択を可能にする。基本的な言語仕様の章で詳述するが、 の実行順序等の制御は単一化のからくりを利用してプログラミングされる。
簡単なからくりでかつ極めて強力な単一化であるが実行コストも大きい、すなわち実行速度が遅くなる原因となる。さらに、パターンとして認識することと引き換えに、引数での関数評価は不可能になった。独立して節の本体で式評価を記述しなくてはならないため、数値計算ではやや冗長になる。
これらの点は、単一化の強力さとのトレードオフの関係になっている。
型付けは動的型付けに分類できるが、言語仕様の中に型概念は登場しない。上記の単一化、バックトラッキング、と論理変数の束縛においては独特のものがあり、その実行は型推論の実行過程に酷似している。既に はその引数の引渡し時に単一化という厳密なパターンマッチングを施すことに多大なコストを掛けた。単一化だけでプログラムをコントロールできる言語が であるといっても過言ではない。この単一化のみによる簡素で強力なプログラムコントロールの足を引っ張ることに成り兼ねない、型付けの強化は、 言語とその支持者によって受け入れられることはないだろう。
は言語による思考をモデル化して主語・述語といった意味での文中の述語を特に重視して記述する系である。この一点からも、対象物を中心に記述していくオブジェクト指向とは距離が大きい。述語論理以前にオブジェクトありきとする立場を一般には取らない。
いくつかの処理系では、オブジェクト指向言語としての拡張が行なわれているが、オブジェクトを中心に設計されることは、論理プログラミングを重視して記述される限りほとんどない。分類するならば、非オブジェクト指向言語に分類される。オブジェクト指向に拡張された言語としては
が存在する。
はオブジェクト指向とは疎遠であるが、一方、述部を重視する系であるという点から見ても、モジュラープログラミングとは近い関係にある。 の述語をモジュールとして捉えた場合、多くは再帰的で宣言的であり、情報強度は極めて強く、情報結合度は極めて弱い。引数にはリスト以外の構造体（複合項）が来ることはほとんどなく明解であり、記述単位は数行と極めて短くかつ記述は簡潔である。モジュラープログラミングを突き詰めたものが だといってもよいように見える。しかし、 をモジュラープログラミングとして評価した場合、疑問符の付くであろう部分もないわけではない。それはPrologの引数の入力・出力の関係が多くの場合双方向であり、意味的にも多義性を持つという点である。モジュラープログラミングは「〜を〜する」というような単一機能にまとめることが推奨されたが、この原則に反する。さらにPrologは複数の解を示すことがありうる。この性質を非決定性（後述）というが、実はこのことは定義された述語全体がコルーチンでありうることを意味する。単一の入口点による制御を良しとするモジュラープログラミングの原則にここでも反する。
後に述べるが の述語はその構造が頭部と本体と分かれていて、本体はルールを意味するため、全体として、ルールを持ったデータベース、演繹データベースとして捉えることができる。これはPrologプログラム全体がデータベースであるということだから、データベースの表現としては最強のクラスに属する。一方、事実を表す本体のない（強制的に真）頭部のみの定義節による述語は関係データベースとその集合論的な性質で一致する。収集した情報を一つの述語に対して多数の頭部のみを持った節の集まりとして定義することにより、オンメモリ関係データベースを構築することが可能である。しかし、Prologをデータベース管理システムとして捉えた場合、
codice_1、codice_2、codice_3、codice_4、codice_5 という組込述語を持つこと以外には、管理機構としての特別の組込述語が用意されている訳ではなく、ディクショナリ管理などのための述語定義をユーザが追加する必要がある。
関数型言語等、他のプログラミング言語と比較しての の特長は、上記、一階述語論理に基づくこと、単一化、データベース言語的性格の他に、非決定性と双方向性が挙げられる。
非決定性は、解が唯一とは限らない場合、処理系側から見てひとつの解に決定できない場合、外部からの選択の余地を与える。そういうことが当然可能なこととして述語は定義されていく。インタプリタトップではなく、導出を繰り返すプログラム内部にあっては、処理系側とした所を述語と置き換えて考えると、非決定性の述語の解を決定するのは、前方または後方に連接する質問（副目標）である。前方の副目標群から引数経由で与えられる情報によって副目標は一つの解を作り出すが、この解が真であるとするのは最終的に後方に連接する副目標である。この後方に連接した副目標が全て真となった場合に限り副目標は真となる。後方に連接する副目標のどれかが真にならなかった場合は、それが存在すればであるが別解を用意しなくてはならない。ここでも非決定性の述語、ここでは副目標から見ての解の決定権は、外部にあるということになる。
非決定性は導出の過程、取り分けバックトラックアルゴリズムと一体化しており、 プログラムの制御の根幹のひとつである。ただ、非決定性述語実行時に見られる論理変数の 束縛→解放→再束縛という遷移、すなわち一度束縛されたものが別のものに再度束縛されるということを好ましくないとする見方もある。
双方向性は、述語が実行された場合の返り値は真または偽だけであり、その代わりとして引数内の変数で値の授受を終始するのだが、このとき、入力として使われた変数が出力に、出力として使われていた変数が入力として使うことのできる述語となることがある。この性質を双方向性という。多くの場合、双方向性を持つ述語はそれ自体多義性を持つ。例えば codice_6 という3引数の述語は第一引数と第二引数に具体的なリストが来て呼ばれた時は、リストを結合する意味でよいが、第三引数がリストで第一引数と第二引数が変数の状態で呼ばれた場合その意味は、リストを分解する、がふさわしい。既に存在するリストを、それが結合されて存在したものと考え、それではどのように結合されていったか、あるいは、どのような組み合わせで結合されていったのかを、示していると解釈できる。
このような、双方向性は の述語自らがリバースエンジニアリング的開示能力を持ち、それを示していると捉えることができる。この性質は、Prologを含む論理型プログラム言語の持つ際立った特徴であり、プログラム作成時はもちろん、テスト、デバッグなどの検証の各段階でプログラムコードに対する見通しを向上させる。
プログラマは引数の単一化、再帰/失敗駆動等のプログラムパターンの選択、非決定性、双方向性といった特長をできる限り生かすことなどに配慮しながら、述語の骨格を決めプログラミングを進める。しかし、これらの特長、性質は複合した場合には相当に複雑であり、制御上相反する部分も多々ある。 では、述語論理を逸脱して計算量/資源量/制御の調整に当たる述語「codice_7」（カット）を導入してこの問題に対処しているが、 プログラミングの難しさはこの調整部分に集中している。
 の性格上、その歴史には定理の自動証明の研究が大きく関係している。1930年にジャック・エルブランは自動定理証明やPrologのベースとなる数理論理学上の基本定理であるエルブランの定理を発表した。エルブランの論文には で必須の単一化アルゴリズムもすでに含まれていた。
1950年代以降、計算機上での定理証明の研究が活発になり、ギルモアのアルゴリズム(1960)やデービス・パトナムのアルゴリズム(1958,1960) 、プラウィツによる定理証明への単一化アルゴリズムの導入(1960)などを経て、1965年のロビンソンによる導出原理 や1960年代後半のラブランドによるモデル消去の証明手続きの成果からひとつの結実期を迎えた。その数年後の1971年マルセイユ大学のアラン・カルメラウアーとフィリップ・ルーセルのグループは自動定理証明システムとフランス語の自然言語解析システムとを組み合わせたコンピュータとの自然言語対話システムを作成していた。この際に自然言語解析システムも自動定理証明システムと共通の論理式という枠組みで構築できることに気が付き、論理式をそのままプログラムとして実行できる最初の を1972年に完成させた。これは数千年に及ぶ人類の叡智である論理学の成果をプログラム言語に置き換えたものと言えるが、現在の でプログラムの制御に使われるカットオペレータに相当する機能が最初から導入されるなど、現在の と同様、単なる定理証明システムではなくプログラミング言語として設計されたものだった。以下にその当時の プログラムの一部を示す。論理変数名の最初の文字が "*" で始まるなど、現在の とはシンタックスが異なる。
彼らグループに理論的な助言を与えていたエジンバラ大学のロバート・コワルスキとデービッド・H・D・ウォレンは汎用機 上にマルセイユ大学とはシンタックスが異なる処理系を作り上げた。これは後に と呼ばれることになるが、ISO 標準規格を含む今日動作する 処理系はほとんどがこの系統のシンタックスに従っている。
コワルスキはその後、インペリアル・カレッジ・ロンドンに移り、1979年に集大成ともいえる「」を著し、その後のこの言語と論理プログラミングの研究に決定的な影響を与えた。
コワルスキの活動と の存在によって、英国は 研究の中心地となった。エジンバラ大学のW・F・クロックシンとC・S・メリシュの著わした「」は長く のバイブル本として利用された。エジンバラ大学からSRIインターナショナルに転じたディビッド・ウォレンは1983年 の仮想マシンコードである（WAM）を発表した。この後の 処理系の実装は、一旦C言語などでこの仮想マシンコードを実装して、その上で のソースコードをこのマシンコードに変換するコンパイラを用意するという手順を踏むことによって、開発を簡素化し実装上の標準化を図ることが普通になった。日本の新世代コンピュータ技術開発機構の マシン PSI は1987〜1988年頃に開発された PSI2 からこれを採用したし、その後開発された 処理系の多くはこの方式に従った。
1976年にSRIに留学していた古川康一はカルメラウアーらの 処理系のリストを見つけ帰国時に電子技術総合研究所に持ち帰った。当時電子技術総合研究所で推論機構研究室長をしていた淵一博はこのリストを解析して 処理系を走らせ、ルービックキューブを解くプログラムを作成するなど論理プログラミングに対する理解を深めていった。
1978年MITに留学中の中島秀之が「情報処理」誌に紹介記事を寄稿して、 は日本でも広く知られるようになった。
1970年代終り頃、日本では通産省の電子技術総合研究所の淵一博を中心とするグループが論理プログラミングの重要性を認識して、日本のコンピュータ技術の基礎技術としてこれを取り上げることを提案する。これが最終的に1980年代の新世代コンピュータ技術開発機構の発足と活動につながった。総額約570億円の国家予算を約束されて1982年に新世代コンピュータ技術開発機構（'）は活動を開始する。 を含む論理型言語はこの研究の核言語と位置づけられ世界的な注目を浴びることとなる。約10年間の研究活動中に と論理プログラミングの研究は急激に深化した。実際1980年からの20年間に をメインテーマにした日本語の書籍は約50冊発刊された。ICOT の研究員は積極的に Prolog の啓蒙に努め、講習会、チュートリアル、ワークショップを年に一度ならず開催した。 が主催したロジック・プログラミング・コンファレンスは1983〜1985年頃をピークに若い研究者達を刺激した。研究活動前半の期間では論理型言語の実用性を証明するために、マシンが設計され、三菱電機と沖電気によって製作され、 の他大学等研究機関に配布された。この個人用逐次推論マシン PSI の機械語 KL0 は単一化やバックトラックなど の基本的特徴を完全に備えていた。この KL0 によって、PSI のマイクロコードを制御した。KL0 を基礎として、オペレーティングシステム ' が設計され、これを記述するために、 にオブジェクト指向プログラミングを取り入れた ESPが近山隆により設計されて使われた。ESPは多重継承を特徴とする当時としては先鋭のオブジェクト指向言語であったが、後にカプセル化の不備などが指摘されて、今日あまり話題となることはない。しかし、OSを記述するという課題を通じて、論理型言語にオブジェクト指向言語的要素を加えることによって、可読性が高まりプログラム管理がしやすくなることが確認された。その反面、 のみでオペレーティングシステムを完全に記述してみる絶好の機会を逸したことも確かである。ESPはPSIを前提にせずに利用できるように、C言語で書き直したCESPが開発されたが、これが普及への起爆剤になることはなかった。後に述べるように、PrologのISO標準規格のモジュール仕様としてESPの採用が否決された1995-6年頃以降はほとんど利用されることはなくなった。
ここまで述べたように、Prologは によって持ち上げられた言語 との印象が強いが、 というプログラミング言語から見ての の影響は実は限定的だった。淵所長ら の主研究テーマは並列論理型言語にあり、研究後半では そのものからは離れて行くことになる。PSI に使用した電子基盤を利用して並列推論マシン PIM が製作されて、（GHC）に基づく並列演算処理を追加した KL1 が設計された。この環境に依存する形で、並列論理プログラム言語のKL1は知識プログラミング全般の研究に利用された。PSI と を使った研究も続けられはしたが、割り当てられた研究員の数は極めて少なかった。
1990年代に入ると制約論理プログラミングが注目され処理系が多数誕生した。これは から見ると引数の論理変数間の関係（制約）を記述可能に拡張したものである。制約論理型言語は、変数評価に遅延実行などを持ち込むことが必要となるが、連立方程式をはじめとする多くの課題で より記述が柔軟になる。 の組込述語には引数が変数で渡るとエラーとなるものが多く、このため プログラマは変数が具体化されるように副目標の記述順序に気を配る必要がある。結果としてプログラミングに逐次性が生じる。制約論理プログラミングにおいては、後に変数が具体化されたときに検査されるための変数の間の制約を記述するだけで、この逐次性の拘束を解決して通過することができる。実はこの制約はPrologから見ても自然な拡張であり、むしろ の単一化が制約論理プログラミングの制約を「codice_8」のみに限定したものだと解釈することができる。しかし、簡素で逐次的な性格を強く持つ の処理系に慣れた利用者が、制約論理プログラミングの述語中に更に変数制約の宣言を追加しなくてはならない負担を、受け入れているとは言い難い。制約論理プログラム処理系が のそれに置き換わる気配は、2013年11月現在においてもない。
ISO の標準化作業は1987年頃から作業委員会(WG17)が作られ、日本委員も情報処理学会から15名ほどがこれに加わった。1995年 ISO標準規格がISO/IEC 13211-1 Prolog-Part 1: General Coreとして制定された。さらに、2000年にはISO/IEC 13211-2 Prolog-Part 2: Moduleとしてモジュール仕様が追加して規格化された。モジュール仕様については日本委員から、ICOTによって作成されたESP(Extended Self-contained Prolog)を以てその標準とする案が出されていたが、これは否決された。
ISO標準規格はエジンバラ仕様 を基調に既に一家をなしていた など有力ベンダと主としてヨーロッパの学者を主体にこれに日本などの委員が参加して作成された。この規格は現在 Prolog 処理系の製作者に指針を与え、大きな逸脱を心理的に妨げる役割を果たしているが、組込述語の個々の仕様ではベンダの意向が強く反映されたものの、全体としては最初に述べた論理学的立場を尊重して保守的で極めて小さな仕様となっている。そのため多くの 処理系はこの規格の述語を搭載しつつ、独自の拡張部分を修正したり削除することに消極的である。結果として個々の処理系の互換性の乏しさは残り、それは の弱点として認識されている。
JIS規格も一旦は2001年にJIS X 3013:2001が、"標題 プログラム言語Prolog―第1部：基本部"が要約JISとして発行されたが、2012年1月に何ら実効を見ること無く、「周知としての目的は終了した」として廃止された。
日本において、 の活動時期から1990年代前半に掛けては、いわゆる人工知能ブームの時期であり、人工知能研究への期待はこの時期再び異様に高まった。 マシンによる医療情報エキスパートシステムでの成果は、人工知能の研究の成果の一部は情報処理に於いても利用可能なのではないかとの夢を抱かせた。このような評価の中で は人工知能のアセンブリ言語的な位置づけを期待された。知識情報処理はこの水準の言語を基礎にその上側に築かれるべきだとの意味である。手っ取り早く利用可能な人工知能技術としてエキスパートシステムが選別され、これを支えるナレッジエンジニアの存在とそれを養成するための教育が必要とされた。 はその中心に存在した。日本も例外ではないが、日本以外の国では特に、 の名著は1990年代前半に刊行されている。これは、 の活動とは若干のタイムラグがあるが、この時期社会的に 人工知能向き言語としての に大きな期待が寄せられていたことの証しである。エキスパートシステムはビジネス分野において広範囲に応用可能な基礎技術であったが、このような低水準な分野への適用はあまり試みられず、この分野からの 言語への要請はほとんど見られないまま終った。
機械翻訳などの自然言語処理もまた人工知能の一翼を担う分野であるが、歴史的経緯から人工知能ブーム以前から、この言語に最も期待が掛けられた分野であった。しかし、左再帰問題の回避でトップダウン解析の明解さをいきなり殺がれた。さらに句構造文法への適用においては、 が得意とする、句構造に分解して意味に相当するグラフを形成することの他に、極めて膨大な辞書を構造体として定義する必要が展望された。この辞書作成は とは直接関係しないタスクであることから、次第に は句構造文法によるアプローチの前線から後退してしまった。統計的言語処理のアプローチでは、単一化等に多くの計算量を費やす は大量データを扱うのに不向きとされて、利用されることはほとんどない。自然言語処理のテキストの多くが を用いて解説されているにも関わらず、期待が大きかった割に実務的には、表面に現れている成果はIBM社のワトソン程度にとどまり、自然言語処理はむしろ 評価の足を引っ張る傾向にさえある。
日本においては、 解散後数年を経て、論理プログラミングと は急激に下火となる。先にあげたコワルスキの成果があまりにも完成されたものでその研究成果の範囲を越えることが難しかったこと、歴史的にプログラム言語でありながら論理学からの逸脱を厳しく制限され、自由なアイデアによるプログラミング言語としての発展・展開が困難に見えたことも研究者・技術者を離れさせた。そして、人工知能ブームもまた去って行った。企業等で続けられた研究開発も発表される機会が産業応用シンポジウム（INAP）などに限定され、人々の目に の成果が触れることは極端に少なくなった。 の多大な研究成果がネット上に閲覧可能な状態で置かれたが、 言語の処理系はインターネット時代の技術・流れに乗れず、初心者・初学者が利用するためのネット上での情報も他の有力言語に比べて少なく、新しい利用者を惹きつけることができなかった。パソコンのオペレーティングシステムとして が一般に普及し始めると、初心者教育にウィンドウの部品の展開を題材とするのに適したオブジェクト指向言語に人気が集中し、 は動作の遅い外れた言語のイメージを持たれるようになる。さらに21世紀に入ると がクラス概念を持たないため、マイクロソフト社による アーキテクチュアの共通言語基盤（CLR）の対象言語から外され、この傾向に拍車をかけた。ついには枯れた言語というニュアンスを含んでではあるが、「化石言語」と揶揄されるまでに至ったのである。
盛時の勢いは失ったものの、 は各教育機関で主として論理学の教材として利用され続け、今日まで数万人の人が の講座を受講している。実務的に利用される機会が少ないにも関わらず、その素養を持つ人が大量に存在するという特異な位置にあるプログラム言語となっている。また、多くのプログラミング言語でその言語上にPrologインタプリタを制作してみることが難度の高い学習課題の一つとして採用され、その結果としてもPrologを理解しているプログラマは増加する傾向がある。プログラムは、ホーン節、もしくは単に節と呼ばれる形式の項を並べたものである。
節は、頭部と本体部からなり、
または
の二形式があり得る。これはそれぞれ、
頭部.　　　　　　の形式が「AはBである」、
頭部 :- 本体部.　　の形式が「AならばBである」という命題の形式に対応する。
節も項であって、項は関数子といくつかの引数からなる。
節の関数子は ':-' であり、頭部と本体部はその引数である。関数子が':-'の二引数の項が節である。
の形式は実は、
が省略されたものと見なされ、やはり ':-' を関数子として二引数の項である。
頭部は項が連接することはできない(ホーン節)が、本体部は項が連接する、そういう項であり得る。
codice_9
副目標,副目標, ... 副目標　は、これ全体を目標という。目標は副目標...副目標の連言である。
ここで
codice_10
と置けば、
であり、やはりこの節の形式も、関数子 ':-' の二引数の項であることが分かる。
複数の副目標はカンマで区切られているが、このカンマは論理積を意味する。
節は、その頭部の形式、すなわち関数子とその引数の数が同一の形式を持つ述語と呼ばれる単位で管理される。
プログラムは項の集合であり、節の集合であると同時に、述語の集合でもある。
Prologはこの項、節、述語だけでその形式を表現できる点で、他のプログラム言語とは著しく異なる。これはPrologの理論的な背景が論理学にあり、この中の概念のみで構成されて、発展してきたからである。
このような節の集合をあらかじめ用意してそれを定義した上で、ある命題が真であるかどうか問うことを質問という。
節の集合、つまり述語の集合をあらかじめ用意する方法については、後出の"Prologプログラミング"で述べる。
Prologの処理系は、人間の入力した質問に対して、頭部が形式的に一致する節があるか調べ、あった場合はその本体部に記述されている命題と一致する節があるか再帰的に調べる。
ここでは定義されたもの(処理系があらかじめ用意した組込述語も含めて)だけが、真になり、定義されていないものは必ず偽となる(閉世界仮説)。
具体的な例を見よう。
「ソクラテスは人間である」「人間は死ぬ」を で記述すると以下のようになる。ここで X は変数である。
codice_11 は「AはBである」の命題の形式に対応し、ここでは、Aはソクラテス、Bは人間である。同様に、
codice_12 は「AならばBである」であり、Aはcodice_13に、Bはcodice_14に対応している。
システムに対して以下のように入力すると、true が返される。
これは「ソクラテスは死ぬか」と質問したことに対して、システムが内部で推論を行なって、既知の知識から答えを出したものである。
それではここでの既知の知識とはなんであろうか。それは、
であり、内部で行っている推論とは、?- 死ぬ(ソクラテス). から 死ぬ(X) :- 人間(X). により導出されて、
が、確認される過程である。
今度は以下のように入力してみる。これは、「死ぬのは誰か」と質問したことと同じになる。この場合もシステムが内部で推論を行なって、死ぬ（X）を満たすXを表示する。
他のプログラム言語に比べると質問を基本的骨格としている点でユニークであるが、更に、 は複数の計算結果があり得るという点でも極めてユニークなプログラム言語である。先のプログラム例を拡張して
とした場合、死ぬ（X）を満たすXは複数（ソクラテスとアリストテレス）がありうる。
述語 人間　に複数の節を設けて、その引数にソクラテス、アリストテレスと列記して行くだけで、質問に対して複数の解を処理系が列挙するようになる。
他の言語でこういう機能を実現する時に見られるような、手続き的なループや情報を管理する配列の添字管理のようなものは全く現れない。
多くの 処理系ではこのような複数解が存在する時に新たな解を得る場合は
と ";"（セミコロン）記号を用いて他の解を得る。";"はこの解は真ではない、という質問者の意思表示である。
ここではインタプリタのトップからの質問、すなわち対話環境にあるから、codice_15が処理系からの質問者に対する応答、質問となっている。
質問者は「この解は真ではない」と否定することができる一方、呈示された解(ソクラテスまたはアリストテレス)を真と決定することもできる。このように処理系から見て外部からの介入によって真を得ることを非決定性という。
この非決定性がコンピュータ言語としての の際立った特徴の一つである。
もうすこし具体的なプログラムの例を以下に示す。「codice_16」から行末までは注釈である。
codice_17 は要素XがリストYのメンバーであるかを調べるプログラムであると同時に、「要素XがリストYのメンバーである」という関係も宣言的に表している。実行例を以下に示す。
要素XがリストYのメンバーであれば成功する。
要素XがリストYのメンバーでなければ失敗する。
Xの部分を変数のままにすると、リストYのメンバーである要素が結果として返る。すなわち、ジェネレータとして働く。
二つのリストの共通メンバーを求めるには単純に","で区切って並べればよい。この","はANDの意味を持つ。
要素Xを指定しリストYを変数のままにすると、それらがメンバーであるリストが結果として返る。
上の"_G001"は処理系が作成した仮の変数で、リストの後半が不定であることを示す。
が扱うデータは項（）と呼ばれる。項は定数、変数、複合項のいずれかである。複合項でのアトム部分を関数子（）、引数の数をアリティ（）と呼ぶ。アトムはアリティが0個の複合項とみなすこともできる。アリティが異なれば同じ関数子でも別のものとして扱われる。アリティは英語に由来し、英語の語彙としても馴染みの少ないものであるが、適切な訳語が見つからず現在もこの表現が使われている。
前置・中置・後置記法された複合項は、複合項の関数子を前置・中置・後置記法の演算子として定義したものだが、これは表記法の問題でしかない。ではユーザが任意の演算子を定義できる。いくつかの演算子が事前に定義されており、例えば、算術式での"+","-","*","/"などが代表である。 codice_34 は実は複合項 codice_37 として処理系に解釈され、そのような構造体を表現するものとして実装される。また、codice_35 は codice_39 に等しい。このことから、のプログラムは複数の項、すなわち述語 :- の集合、として記述されていると考えることができるため、プログラムをデータとして自身で処理することは比較的容易にできる。
ユーザが演算子を定義するには、組込述語op/3を使う。下記のようにプログラム中でop/3の実行して宣言を要求することもできるし、インタプリタのトップから ?- op(600,xfx,は). のように実行して直接宣言することもできる。opの第一引数は項の結合強度を、第二引数はオペレータの型を表す。演算子は第三引数で指定する。
codice_40を
と定義すると、述語は は/2,が/2 に変わってしまって、全く別の定義だと言えるが、我々には意味的に同様のものと理解できる。これは中置記法の例であるが、以下のように、前置記法の"必ず"、後置記法の"ならば" を加えて意味的に補強することも可能だろう。( _ :- _ の中にその義を含むから、本来その必要はないが)
Prologは動的型付き言語であり、型を宣言することはしない。論理変数は関数または述語の引数の中にしか現れず、この変数の型を指定する(例えば integer:X のような)記述をしたとしても、その変数を型に制約することはできない。
質問がなされ述語が呼び出された時に処理系は単一化のルールによって論理変数を可能であれば束縛するが、その際、型を検査することはしない。その引数が例えば、整数であるか、あるいは浮動小数点数に束縛されているかは、組込述語 integer/1 float/1 でそれを随時質問することによって検査することができるのみである。
複合項の中で特別な扱いを受けているものとしてリストがあり、LISP以来の記号処理プログラミングの伝統に則りPrologでも極めて多用される。実際のところ、Prologのデータ構造は単位節定義とリスト以外にはないと言っても過言ではない。
"リスト"'はいくつかの項を順に並べたもので、その先頭要素を取り出せば、残りはまたリストであるというように再帰的である。例えば codice_41 のように、要素となる項を「codice_42」で区切り「codice_43」と「codice_44」で囲った形で表現する。要素のないリストは codice_45 と表記し、空リスト、あるいは nil と呼ぶ。
リストをグラフとして示すと、
リスト [a,b,5] の構造は
のようになるだろう。
Prologのリストの表記として、要素を"|"で区切る方法がある。この記法があるためにのリスト処理は視覚的で読みやすい。先頭からいくつかの要素の後に"|"が来て、その後にはリストか[]が来る。 例： codice_46 は、先頭の要素 codice_47と残りの要素 codice_48 をつなげた codice_49 と等価である。 ただし、codice_50ではない。Prologの複雑なリスト処理をそれでも宣言的と見なすことができるのは、専らこの記法あってのことである。
この記法はPrologのプログラムではリストを先頭要素と残りリストに分解する場合に多用される。codice_51の場合、Hは単一の項(複合項であることも含めて)を表すパターンだから、codice_52 に分解される。後に示されるプログラム例の章には、リスト要素の加算,append,組合せ,クイックソート 他、多数の事例がある。重複するからここでは二例だけを示す。
Prologを代表する述語 member/2 の[H|T]と[_|T] と append/3の[H|X]と[H|Z] の所にこの記法が使われている。
codice_53にあっては、第一番目の定義節から
codice_54となるから、最初の解である
が表示されるのである。
以下では、二つのリストを単一化することを通して、リスト記法の各部分がどのような関係にあるかの理解を深めよう。
最後の例の[a,b|c,5,6]のcodice_55はリストと看做されない。
'|' を使ってリストを区切る用法もグラフ化すると、リスト [a|[b,c,5,6]] = [H|T] の構造は
である。
リストは簡単に成長させることができる。
codice_56では単一化のからくりを巧みに使って、リストの先頭に要素を追加している。
リストの要素をひとつ切り取るには、反対に
リスト要素の切り貼りはこのようなパターンで行われる。リストは先頭から要素を加え、先頭から要素を検査し、先頭から要素を取り去るのに適したデータ構造を持っている。
ここまで示してきた通り、リストは読みやすいように特別な表記法を与えられた複合項であるが、実は一般の複合項と同様の構造で実現されている。
リストは関数子名がcodice_57 と決められていて、以下の例のように実現されたアリティが2の複合項である。 例： codice_58 は複合項 codice_59 と等価である。
形式記述言語の多くがそうであるように、Prologはその制御の大半が再帰処理によっている。リストは再帰的な構造データの中でも最も簡素で扱いやすいものであり、制御構造とデータ構造の一致という点からもリストが多用される十分な理由がある。
複合項もまた再帰的構造データではあるが、生成、分解、置換などの際の扱いが複雑になるため、グラフやオートマトンなどの定義/表示以外にはあまり使われない。'.'(a,'.'(b,[]))の構造で分る通り、リストも実は複合項である。リストは生成、分解、置換などが容易くできる構造を持つ特別な複合項であり、それ故に特別な表記法を与えて、さらなる便宜を供しているのである。
Prologではリストの内包表記はできない。codice_3 や codice_5 の表現が意味的にそれに近いが、ここでの表記をリストを表す項として、遅延して評価するために持ち回ることはできない。
例えば
であるが、findallを関数表現として、
と表記したとしても、この項だけ例外的に単一化を免れ関数評価する特別な機構を付加しない限り、この第一引数はリストと看做されることはなく、エラーとなり、Lに期待する [2,4,8,10] は得られない。このことから単一化がリストの内包表記を阻んでいる理由の一つであることが解る。
Prologには集合を表す特別な表現がなく、リストでこれを代用するのが普通である。この問題については、Prologプログラミングの
章で詳述する。
の実行は述語を定義された処理系に対してユーザが質問することによってなされる。質問とは、
のようなものである。ここでの質問は「ふねはタラオの親か」という意味だ。「ふねとタラオは親子関係である」という読み方もある。
このような質問に処理系が答えることができるためにはその知識が必要である。Prologではこの知識を述語という形式で与える。そのことを述語を定義するという。
定義された述語には一般に処理系によって最低限必要なものとしてユーザに対してあらかじめ用意された組込述語(ユーザは定義しなくてもよい)と、ユーザが自ら定義したユーザ定義述語の二種類がある。ユーザは自ら定義した述語群をファイルに保存して、そのファイルを組込述語であるcodice_62述語によって処理系に読み込ませる。
サザエさんの家系図に関する述語群が
上記のように、エディタなどで書かれて、ファイルcodice_63に存在するとして、
を実行することによって、サザエさんの家系図に関する述語群がユーザから参照できるようになる。
はプロンプトと呼ばれ、質問を受け付ける準備ができていることを示す。プログラムを実行するのには、一般にProlog処理系の起動後、最初のプロンプトが表示されてからユーザ自身で質問(目標)という形でプログラムを実行する。
実務的なプログラムではこの質問によって述語定義の融合、頭部の単一化、本体部の導出の長い連鎖となり、最終的にその質問が真か偽の結果を残して終了する。
これが普通の使い方だが、処理系の起動時にコマンド引数などで最初に実行する質問を引き渡して、起動後停止することなく、質問が実行される場合もある。
ここでcodice_64という質問を与えてみる。この組込述語は現在実行可能な状態にある述語すべてのソースコードを表示する。
このように定義済みであることが分かった。これが先のcodice_65の効果である。
最初の親子(波平,サザエ). から 夫婦(マスオ,サザエ). までが事実であり、形式的には本体がなく、単位節と呼ばれる。
その下の member は二番目の節に再帰的に本体があり、これはルールと呼ばれる。
ルールcodice_66を使った質問をしてみる。
となる。サザエは集合{波平 サザエ マスオ} の要素であるかという質問に真と答えている。
さらに簡単な質問をしてみる。単に事実を問うものだ。
この質問で第二引数に X 乃ち論理変数が使われた。処理系はこのXに適切な値が入ることで、この質問を真となって終わらせようとする。
X に カツオが入った時、
で真となるし、ワカメが入った時、
で真となる。
この二つの質問を 論理変数 X を順に束縛することで満たしているのが上の ?- 親子(ふね,X). での実行結果である。
質問の詳しい説明は後のプログラム例「家系図」以下にある。
Prologの処理系は質問がなされ、それに回答を繰返すことによって処理が進むという作りになっている。
しかし、質問することなしに、処理系の起動時にプログラムを実行することももちろんできる。最初に現在処理系で使われている代表的な二つの方法を示す。
1) ソースプログラムの中に起動する質問を記述する。
2) 処理系の起動時に -f ファイル名 オプションを指定すると共に、-t オプション等で、最初の質問の述語名を直接指定する。(例えば mainなど )
・ codice_68
必ずしも処理系起動時と限らないのだが、consultされるファイルの途中に特別な述語 codice_69 を指定して、自動で質問が実行できるようになっている処理系が多い。
ファイル'sazaesan.pl'の第一行目に
が書かれているとすれば、
を実行した直後に
%%% サザエさん家系図の読み込み %%%
と表示される。'sazaesan.pl'の第一行が読み込まれ、処理系が :- から始まる特殊な節を見つけると、
という質問をユーザからの入力なしに実行する。
この機能を利用して、処理系の起動時にコマンドラインに -f オプションなどで初期読み込み述語ファイル名が指定できる作りになっている処理系が多く、
この ':-' 述語をファイル内の適宜な場所に記述することによって、質問の自動起動が可能となる。
しかしながら質問で変数束縛の状態表示を期待している場合は、質問ー応答モードを脱して動いてしまっているから、codice_69以下での質問に対する実行が完了した場合でも質問ー応答する場合のようにはうまくいかない。";"や改行待ちとなる非決定性の制御にも移行しない。このような変数束縛の表示はwriteのような出力述語を続けて記述してユーザが表示させる必要があるだろう。
自動実行を理解しやすくするために、'sazaesan.pl'に少し codice_69 節を追加してみる。
これを'sazaesan.pl'とは別のファイル'temp1.pro'に書いて置くとする。
組込述語 writef/2 や fail;true 制御についてここでは詳しくは述べないが、
最後に処理系を終了させる組込述語 halt. を実行させることにより、
のような、バッチ処理プログラムとして実行することができる。
起動述語として例えばプログラムの起動時コマンドオプションで -t main を指定する場合は、予め、
のように述語として定義して置けばよい。
組込述語 consult/1 の事例を示したが、Prologの処理系は共通の組込述語群とその処理系独自の組込述語群を持っており、後者が統一されない状態であることは歴史の中で触れた。ユーザは各処理系のマニュアルを注意深く読む必要がある。
でプログラムを記述する単位は述語（）で、他の言語での関数やサブルーチンに相当する。つまり、プログラムは述語の集まりで、述語はあるまとまった機能を表現している。述語は1つ以上の節（）と呼ばれる項からできている。節は以下の形をしている。
あるいは、
1つの述語に属する節は、同じ述語名(関数子名)と引数の数(アリティ)を持つ頭部からできている。述語名とアリティが異なれば別の述語とみなすため、述語を指定するときは"述語名/アリティ"と表記されることもある (例： codice_72) 。
1つの述語は成功、あるいは失敗のいずれかの結果を返す。副目標〜副目標の間の "," はANDを意味する演算子であり、1つの節が成功するのは本体部がすべて成功した場合である。
本体部の実行は、副目標がANDの関係で連接する場合、記述された順に行われる。頭部のみの節はcodice_73と同じ意味でありcodice_74が省略された形式だと考えればよい。
1つの述語が複数の節からなる場合、上から順に実行され、どれかが成功したら述語自体は成功する。つまり同じ述語内の節の関係はORの関係となる。節同士はOR関係であり、それぞれ情報の共有という観点からは完全に独立している。
一つの節の中の副目標から、同じ述語の別の節中の情報にアクセスするためには、新たにこの述語を目標(質問)として呼び出す必要があり、この場合、制御や変数束縛等は完全に初期状態での実行となる。
一度trueになった節で一旦は変数に値が束縛(代入)されていたとしても、バックトラックして、それより下の節に制御が移った場合は、制御の移った節からバックトラックした(すなわち偽となった)節の変数束縛を利用することはできない。
述語は親となる目標(副目標)によって謂わば質問として呼び出される。これに対して、述語の各節は予め備えている状態にある。質問されることによって、頭部の単一化を行い、これに成功した節の、本体の副目標を順次、今度はこれが親となって質問する。そういう備えができている。それが述語が定義されているということである。
の基本的なアイデアは、ホーン節をプログラムと見なして実行する、ということであるため、純粋なのプログラムは手続き的にもホーン節に従って宣言的にも解釈ができる。1つの節の解釈は以下のようになる。
手続き的に見ると、"副目標"〜"副目標"がすべて成功する場合、節は本体部を順番に実行する関数やサブルーチンのように見なせ、再帰呼び出し可能な手続き型/関数型言語と動きはさほど違わない。他の言語との大きな違いは、本体部のいずれかが失敗した場合、最後に選択した節にバックトラックし次の節から再度実行を続けることである。
の動作をプログラムが指定した条件での解の探索として見ると、深さ優先の解探索ととらえることができる。
C言語など通常のプログラミング言語の変数は値の格納場所であって、計算が進むに従って内容が変化する。 などの論理型言語での変数は数学的な変数に近いもので、何らかの値につけた名前である。値は決まっているか決まっていないか(代入されているか代入されていないか)のいずれかで、一度決まってしまえば値が他の値で置き換わることはない。値が変わるのはバックトラックにより代入が解かれた後に再度値が決まった(代入された)場合のみである。この変数は他のプログラム言語のそれのようにプログラム中に宣言することはできず、述語或いは述語呼び出しの引数の位置にのみ現れる。
通常のプログラミング言語の変数と区別するために"論理変数"と呼ばれることもある。論理変数が述語または質問の引数の位置にのみ現れるという意味を理解しやすくするために以下の例を示す。
codice_75のX,Y,Zは一見プログラムの中に宣言しているように見えるが、全て組込述語codice_76の引数である。Prologにおいてcodice_8とは単一化を施すという意味である。
変数の値の変化の例：
論理変数は、格納場所ではなく、質問がなされる度に定義節を写して生成される一時的な論理域に存在するもので、プログラムの他の箇所からその値が参照されることはあり得ない。
第一節にXが二箇所、第二節にはXとRが二箇所現れている。それぞれの変数が最終的に同一のものに代入されることの宣言である。
また上記の定義では第一節と第二節にXという論理変数が現れているが、この二つの論理変数名が同一であることには意味がない。第一節のXに値が代入されて解が得られた後、バックトラックされて第二節に移行したから値が解放されて、Xは代入されていないのではなくて、第二節のXは第一節のXとは元々無関係だから、代入されていないことになる。
論理変数の名前が同一であることが意味を持つのは、質問されて、述語のひとつの定義節と融合された時、その融合された定義節側の頭部、本体の中に、同名の論理変数があるかないかだけである。質問した側の副目標の引数の論理変数がどのような表現になっているかについては没交渉である。融合の際の頭部の単一化でさえ、論理変数同士の単一化であっても、ソースプログラムで変数名が同じあるか否かは問われない。この点については、次の節の単一化を参照。
ここで起こっている質問としての副目標(または目標)と定義節との融合は、述語定義のコードからは離れて、対応する節がその姿を写されて実行されるのであって、その実行と述語定義のコードは直接的な関係を持たない。
したがって、この質問、導出過程で論理変数が束縛されても、述語定義の他の定義節の論理変数に影響を及ぼしようがないのである。
の動作の基本は単一化と後に述べるバックトラックである。
単一化(ユニフィケーション)は、述語呼び出し時に使用される、呼び出し側、呼び出される側双方向の強力なパターンマッチングだが、そのルールは簡単である。
すなわち、二つの項の単一化において、
以上挙げた以外の場合は、単一化は全て失敗する。したがって、アトムと複合項の単一化は常に失敗する。述語呼び出し時の候補節では、一つでも頭部にある引数の単一化に失敗すると、その候補節は選択されない。
1 と 2 は意味的に統合可能であり、単一化ルールを三つとすることもある。Wikipediaのユニフィケーションの説明ではそうなっている。しかし、変数の単一化は値が代入されないという意味で特殊であり、Prologでは同一性のみ主張できる変数の制約そのものであり、Prologの最も独自性の強い部分であることから、ここでは独立したルールとして扱う。
単一化によって論理変数がある値に決まることを、代入という。一般のプログラム言語の代入と表現は同じであるが、Prologの代入はある値をその論理変数を通じて覗くことができる。あるいは、この値が参照(利用)可能な状態になるといったニュアンスに近い。なぜなら、この代入がバックトラックによって「解かれる」と論理変数は再び何も参照できなくなる。
単一化は処理系が述語を質問として呼び出す(目標が実行される)たびに、暗にPrologシステム内で実行されつづけているのだが、利用者が明示的に二項の単一化を指定することもできる。それが先の論理変数の事例に現れた = である。述語 = は左右に二つの引数を持ち、この二つの項の単一化を試みる述語である。
ここで、明示的な二項の単一化(=/2)を組み合わせて単一化の説明を試みよう。
単一化は極めて強力なパターンマッチングではあるが、実行コストも多大である。Prolog処理系の実行速度が他のプログラム言語のそれに比べて遅いことの主要な原因は単一化にある。
通常のプログラミング言語との比較で考えると、の単一化は以下の機能を含んでいる。
バックトラックは他のプログラム言語と比較してPrologを特徴づける部分である。バックトラックとは後戻りくらいの意味だが、現在まで日本語として適切な訳を見つけられず、このバックトラックがもっぱら使用されている。プログラムのコードとして明示的に指示がないにも関わらず、暗に実行コードが既に実行を済ませた部分に後戻りして実行を始める、そういう制御のことをバックトラックと呼んでいる。
質問が とされたとする。
これから、p3(副目標という)が実行されると考えよう。p1,p2は成功裡に終了している。(ここでは副目標を抽象化して P の形式で表すこととする)
このp3が成功(真となる)すると実行はp4が呼び出され、その定義の第一節に移る。
ところがp3が失敗(偽となる)すると、p2,p1の順に、まだ実行されていない、候補節が残っているものを探し、それがあれば、そこから実行される。
この後戻りして、実行する制御のことをバックトラックという。
p2に候補節がなく、p1にまだ候補節があってここから実行される時には、p3を含むp2以降に生じた変数の代入は完全に解消されている。
p1にももはや実行されていない候補節がない場合、最初の質問codice_78が偽となる。
ここで候補節が残っている、または残っていないと書いたが、既に概要のところで述べられた非決定性の述語だけが、この候補節が残っている状態に成り得る。副目標の述語定義が決定性である場合は当然候補節は残っていない訳だから、?- p1,p2,p3, ... に於いて、p2が決定性の述語だったとすれば、p3がバックトラックすれば次はp2をスキップしてp1の残り候補節を探すことになる。
述語Q の定義が以下の場合に ?- q. が実行されて、上記のようにP3が失敗したとする。
p3が失敗して、もはやp2,p1にまだ実行されていない候補節がない場合、次の実行は第二節のp6に移る。つまり、qの第一節は失敗して、第二節(まだ実行されていない)に移る。のように、Prologの実行制御を把握するためには、pcodice_79の真偽だけではなく、pcodice_80,pcodice_81...や、そのpcodice_79を呼び出しているqの実行状況まで視野に入れる必要がある。
たとえば、以下の述語に対して、
以下の codice_83 というゴールを指定すると結果は次のようになる (";"を1回入力しバックトラックを行わせた例) 。
複数の解がありうる述語member/2に於いて、処理系は質問者に最初の解候補 Z = ワカメ を示したが、
質問者は";"を入力することによってこれを否定した(非決定性)。
続いて処理系が Z = マスオ という解候補を示し、
質問者はそれを受け入れて、改行した。これがこの実行の解釈である。
具体的に、member/2で解候補が選択される過程を追ってみると、
まず最初の節の頭部 で単一化が成功し、codice_84 で codice_85 自体も成功する。
この状態でバックトラックを行わせると、次の節である2番目の節の頭部
これは、最初の節の頭部
で単一化が成功し、codice_86 で codice_85 は成功する。質問者は"."を入力することによって、これが解であることを受け入れた。
非決定性の述語の解の決定権をここでは質問者が持っている。しかし、このように質問者が介在することはPrologプログラミングの中では寧ろ特殊な場合であって、多くの場合、非決定性の述語の解を最終的に決定するのは後続する副目標である。
これは、タラオの親はワカメかマスオかという質問になっている。解はもちろんマスオだが、これを決定したのは、質問者ではなくcodice_88という副目標であり、codice_89 という定義から導かれる論理が member(A,[ワカメ,マスオ]) の解をマスオに導いた。このようにcodice_72からの視点で述べると、解を決定したのは質問者であったり、後続の副目標であったりした。すなわちcodice_72にとっての外部である。述語自体は解を決定できないから、外部の導きによって最終的な解を選択するのだと考えればよい。非決定性述語の非決定性とはそんな意味である。
バックトラックは通常のプログラム言語には存在しないProlog独特の機能だが、強いて他のプログラム言語の中から類似したプログラミング要素を探すと、
が挙げられる。
ループの簡単な例を以下に示す。この例ではリストの先頭から0以上100以下の数値が見つかるまで繰り返す。
確かにこれはループではあるが、codice_92の数を取り出すというものだ。実際にはcodice_93はcodice_94で、-2は、codice_95で偽となってバックトラックしているのだが、Prologプログラマはそのような細部を行ったり来たり目で追うことはしない。
手続き型言語では探索機能を実装することは大きなタスクとなるが、Prologは非決定性述語を中心にプログラムを書くものであり、すなわちプログラミングとはバックトラックしながら探索することである。
codice_34などの数式は単なる複合項にすぎない。数式を評価するには"is"などの述語を使う。以下にいくつかの述語の例を示す。
引数の単一化は codice_99 に相当し、数式として評価可能の項が渡されても、評価されず単一化される点に注意が必要である。
f2はエラーになってしまう。再帰により与えられる引数は 5-1, 5-1-1, ..., 5-1-1-1-1-1, ... であり、codice_102 に帰着することなく再帰が続くため。
X is Y の数式Yの中に解決されていない変数を含むことはできない。例えば、
のようなエラーとなる。すなわち、
のような実行はできない。X = 2 であっても良さそうに見えるが、isの第二引数の評価はそれを式として計算するのみである。
このことは、述語 is/2 には、双方向性がないことを意味する。Prologプログラマは可能であれば数式評価を避けようとする傾向があるが、それはこの評価がどこかに存在する述語定義は、多くの場合に双方向性を失うからである。
比較演算子の第一・第二引数のどちらにも数式を書くことができる。それらは評価された上で比較される。比較演算子としては、
>, =, =, @=, @=< などがあり、
となる。
は一階述語論理をベースにしているが、実用的なプログラミングのため、述語論理の範囲外の機能も用意されている。カットや否定の組み込みはその例である。
最初にカットと否定を含む典型的な定義例を掲げて置く。
1)-3)までの定義(仕様)は、判り易いとは言い難いが、Prologのコードは明解である。
400で割り切れるものは、100でも4でも割り切れるから、これを最初の節で定義する。codice_7があるので「それで確定」である。codice_7(カット)の効果で第二節の定義が採用される可能性はなくなる。
第二節で4で割り切れるものの中で、100で割り切れるものを「除外」している。codice_105は否定であるが、除外と読んだ方が判りやすい。この閏年の定義は典型的でかつ易しい例であるが、特にcodice_7の使われ方、役割、意味は遥かに多義的で複雑である。以下それを順に述べる。
のバックトラックは強力な機能だが、実際のプログラムでは不要なバックトラックを制限したい場合もある。"!" (カット) はバックトラックを制限するための述語である。カットが最初に実行された時には無条件で成功するが、バックトラックでカットに制御が戻ってきたとき、カットを含む述語は無条件に失敗する。つまり、1つの述語内でカット以前に制御が戻ることはない。
たとえば、通常のプログラミング言語での if p then q else r の動きは、カットを使って以下のように書ける。
一度、pが成功して、qに進んだら、qの真偽に関わらず、後にpやrが実行される可能性はなくなる。
プログラマにとって、カットが重宝なのは、条件p の否定を省略できる点にもある。
pに副作用がない場合、p,!,q とした場合と同じ意味になる。
最初に示した閏年の定義で見てみよう。
codice_107を挟んで上がカットを使った記述。下は、カットの使用を避けた記述である。共にcodice_108で抽象したパターンを描いて添えてある。
カットを避けた表現は論理式として正統な記述で推奨されるものではあるが、以下のように、
次々と、条件を否定して行かなくてはならないのでは、プログラマにとって負担が大きくなる。解読も困難になって行く。
カットを使った場合と比較する。
このように正確な条件を記述することが大きな負担となる場合、その負担を解消するためにカットが使用されることが実は多い。
これも同様の例である。文字 a を繰り返し表示したい。
ここで、
となるが、
のようにfにバックトラックして来ると、動作は怪しげなことになる。少なくとも多倍長整数をサポートする処理系では
Nが -1,-2,-3・・・・・と無限に小さくなっていって反応しなくなる。
このような現象を避けるために、普通第一節に
上記のようにカットを入れる。これで、Nが正の整数から順次減少してきて、遂に0になり第一節が一度成功したことで、仮にバックトラックを強制されたとしても、第二節に制御が下りる可能性はなくなる。
ただし、この場合でも、カットなしで済ませる方法はある。
でよい。問題は、正しい論理を付加することによって、ここでの例では N > 0 を記述することによって、実行の制御をすることが本当に安全かということである。!を挿入する方がずっと安全ということも考えられるのである。
通常の処理系では、バックトラックで戻ってくる場合に備えて、それまでに実行した各ゴールの情報や値を設定した変数を、ほとんどの場合スタック上に、アトムテーブルや述語定義の情報はメモリー上のヒープ領域と呼ばれる必要になったデータ構造を切り取って使用するための管理領域に記憶している。カットを実行すると、それらスタックやヒープ領域に置かれた情報の中で、最早決して使用されることがない情報を選別して解放することが可能になることが多い。この解放可能の領域を再度利用可能とするためには、領域を整理して使用可能域を再生(ガベージコレクション)する。このような手順を経た上ではあるが、カットは一時的に使用しているメモリを削減する。プログラマが ! を挿入することで、陽にまたは暗に、処理系に対してこのメモリー解放の要求のサインを出していると考えられることもある。さらにインタプリタ/コンパイラなどに対して、処理系に備えがあればではあるが、最適化を施すことの要求となる場合もある。
カットは非決定性の述語と定義されたものを決定性に転じるためにも多用される。実例を見よう。
appendの定義であるが、第一引数かつ第二引数に変数が来ると非決定性に働く。
である。appendの第一節の本体にカットを加えると、非決定性の性質が事実上消える。
元々のappendの定義を壊さず、
でもよい。appendを決定性に使用したい場合は、以後appendの代わりに専ら 決定性appned を使えばよい。
次に、appendの第二節の末尾にカットが来る場合を考える。
このカットも非決定性を決定性に転じる場合に使われるがそう簡単な話ではない。最初にこれでは決定性述語とはならない。
最初の解 X = [], Y = [1,2]; は第一節でいきなり真になってしまう。したがって、これはまだカットとは関係がない。
第二解は、通常通り第三引数の先頭要素が第一引数に移動して、それで第一引数が[1|X],第二引数tがY,第三引数が[2]となって、移動した後のappendが実行され、
先ほどの[1|X]のXの部分に[]が来るため、X = [1], Y = [2] が取得できる。
これで一旦成功することになる。成功すると、そのとたんにカットが働く。そのカットの働きで、もう第二節の本体の副目標から次の選択肢を得る指示は与えられない。?- append(X,Y,[2]). にはもう一解存在するのだが、
その解はカットの働きで、この append(X,Y,[2]) で呼び出している副目標が偽となるため、返される機会は来ない。
末尾にカットが在る場合をまとめると、
このカットに到達するのは、ひとつでも解が得られたときであるが、解が得られこのカットに至った場合、カット以前にある副目標によって、次の選択肢として予定されている節選択の可能性は一切なくなる。上記の表現で言い換えれば、次の解を返す指示を出せなくなる。
そして、末尾にカットのある節の後にこの述語の選択節がある場合ももちろんその節が選択されることはない。
説明の順序が前後したが、実行結果の否定のためには述語"\+"が用意されている。 codice_109 はゴールPが成功したときに失敗し、失敗したとき成功する。この述語は本当の否定 "Pは偽である" ではなく "Pは証明できない" という失敗による否定で、ある種の非単調論理による推論を行う。これは以下のように定義した述語と同じ動きをする。ここで codice_110 は必ず失敗する組込述語である。
この否定は、カットなしには定義する方法がない。
論理プログラミングにおいては、「計算は、書き換えの系列として記述される」。ところがPrologにあっては、この
書き換え(導出)という表現が好ましくなく場面が現出する。それはカットが導出されるような場面だ。
のような副目標 p を
を q2 の第一節を導出して、
と展開して良いであろうか。これは誤りである。実際にはこのカットは働かない。カットはそれが記述された節の本体の連接の範囲の中のみで有効である。
この問題を別の観点から述べると、カットの重要な性質としてそのカットを別の副目標として置換(述語の再定義)することはできないということになる。さらに実例を示そう。
の第一節に現れるカットをcutに置き換えたとしたら、カットの働きを失う。
最も単純な置換例が上記であるが、これでは、バックトラック後に第二節の実行を妨げられない。
ここで分ることは、カットは ! が書かれた「節の実行制御」としてのみ有効ということである。
カットを検証する時、取るべきプログラマの視点について最後に記す。
プログラマは定義された述語の各節の本体にのみ焦点を合わせる。そして、その部分に現れるカットによって
バックトラックしなくなる本体のカットより前の部分と利用されることがなくなる後続する定義節の存在は
視野に入れる必要があるが、
導出される謂わば子タスクとしての副目標内に現れるカットは考慮の対象から完全に外す必要がある。
カットが論理プログラミングをどんなに逸脱していても、その利用が不可避である以上、このカットの有効範囲の認識はPrologの基本中の基本である。
の述語はの基本データタイプである項で表現でき、述語自身の引数として別の述語を与える高階述語を作成できる。
たとえば、引数で述語を与えそれを単純に実行させたい場合、ゴールとして変数をそのまま書けばいい。
または
本来はcodice_111が使われたが、その後、目標codice_112とだけ書くことでcodice_113と解釈されるようになった。述語名evalはLISPで同様の機能の関数の関数名としてこれが使われた伝統を引いてこの述語名が使わることがある。このように、
任意の述語を実行時に作成して実行することができるため、リストのすべての要素に特定の述語を適用し結果のリストを返す codice_114 や、リストの要素を与えられた述語の結果で選択する codice_115 などの高階述語を容易に作成できる。同様の高階述語には codice_116 、codice_117 、codice_118 などがある。
また、純粋なのメタインタプリタは以下のように書ける。codice_119 は頭部が P にユニフィケーション可能な節の本体部 Q を取得する述語である。
純粋なのメタインタプリタには組込述語がないとされるため、上記の通りであるが、実際のProlog処理系には組込述語が存在するため、上記定義では、第三節のcodice_120の部分でPが組込述語の頭部になった時、この副目標が偽となっとしまうことがある。
このcodice_120を実行する前に、ユーザ定義述語か、組込述語かを検査し、別の節に分離する必要がある。組込述語についてはcodice_120することなしに、単にcodice_123すればよい。
データとプログラムの形式が同じであることや、任意の演算子がユーザ定義可能なこと、自身が強力な構文解析機能を持つことなどもあり、このようなメタインタプリタをもとにの一部機能を拡張した別言語のインタプリタを作成することは、比較的容易である。
関数型言語で高階関数を代表するmap()はPrologでも高階述語を使って定義可能である。しかし、関数型では出力は返り値だけであったが、Prologでは引数のどれかである。入力も複数あり得る。
しかもどの引数が入力であるか、あるいは出力であるかを示すモード宣言は、ほとんどの処理系で採用されていない。したがって、Prologでmap述語を構成するためには、対象となるリストの項はどの引数に当たるのかを陽に示さなくてはならない。
以下に、map述語を二つ示す。map/4とmap/5である。
どちらも、対象リストの要素が反映して副目標の実行が変化して、それをリストに収集している。map/4は収集されるのが実行された_副目標 自体であるのに対して、map/5では実行された _副目標 自体ではなく、実行した時々に構成された _収集項 がリストに積み上がる。
以下にこのmap述語使用例を示す。
となる。
上記事例で map は、_副目標の引数 _文字列,S,Len,Y が map述語の中で巧みに結びつけられているが、やはり難解である。これではfindall/3を直接使って、
と記述してしまっても差がない。member/2が副目標として追加されただけの差である。一般に に於いて高階述語を使ったmap述語はあまり使用されないが、Prologにはこのように強力なメタ述語 codice_5 や codice_3 が既に存在している。しかも、関数型言語のように引数が事前評価されることはなく、引数に関数を置いて渡すこともできないため、map述語の効用は関数型言語のようには大きくない。
Prologはルールを持つデータベースであり、演繹データベースであるといえる。このルールの部分を全てtrueのみに限定した単位節のみからなる述語をデータベースと呼び、関係データベースに模して解釈されることが多い。このPrologのデータベースとリレーションナルデータベースは集合論的に類似しているが、異なる部分もあり、この部分がSQLなどデータベース照会言語との変換などで問題となる。
ここでは主としてふたつのデータベースの相違点に焦点を当てて、プログラミング手法を考えてみる。
関係データベースはテーブルの集まりであり、
テーブルとは属性(最終的に列となる)の定義域集合の全ての可能な値の組み合わせ(直積)の部分集合である。
属性が、四季と果物の二つ集合 codice_126 の直積は
codice_127 であるが、
この部分集合であるテーブル「季節の果物」はcodice_128 であるとする。
この直積の組み合わせの中で、真となる関係、あるいはその更に一部がテーブルだと考えればよいだろう。
これが関係データベースのテーブルの実体である。一方このテーブルをProlog単位節で表すと
となる。
Prologデータベースの第一節は「春といちごは季節の果物関係にある」というものであり、述語名として季節、果物が暗示されてはいるものの、実は第一引数が季節であり、第二引数が果物であるという情報はどこにもない。「季節」や「果物」といった属性(列)から出発した関係データベースとは明らかに異なる。
この相違に起因する問題がSQL問い合わせをProlog述語に変換する際に生じる。
以下のような、SQLに問い合わせを考える。
これに相当するPrologの質問は
であるが、問題点がふたつある。
例えば、「産地」などの属性も実はあるのかも知れない。つまり、何引数の述語を用意すれば良いのかさえ、わからないのである。
関係データベースに対するSQLのQueryとPrologの述語に対する質問を比較してみると、Prologの質問側には属性の情報が欠落しているということが分る。
一方、関係データベースのテーブルは属性(の集合)が出発点になっているのだから、この属性情報は既に根幹に定義されていて、SQLがこれを利用することは容易であるし、自然なことである。
したがって、Prolog述語がSQLと対等の関係でデータベースに質問し、相互に変換するためには、Prolog側に、
のような、補助情報を定義して置く必要がある。
ここでは、codice_129を管理情報の述語名として用いたが、Prologの規格によってこの役割を果たすcodice_130が規定されている訳ではないから、codice_129でなくてはならない、ということではない。
このような定義を前提にすれば、
length/2を使って変数だけからなる _引数のリスト を生成して、それと質問の引数である _値 をnth1/3を使って単一化している。変数と変数の間に = の制約を築いておく。 属性名と値を結びつける/4 がそれだ。
codice_132 は二引数の組込述語であるが、この述語は関数名を第一項に第二項以後を引数を順序に持つリストを複合項に変換するメタ述語と呼ばれる範疇の述語である。
となる。
これで属性名(列名)を与えての照会が、
可能となった。
次に、鍵名とその値を与えての参照は、
このようにテーブル情報/3のような補助的情報を与えることを前提に、SQLに対応する述語を定義していくことによって、Prolog述語はオンメモリデータベースシステムとしての機能性を得ていくことになる。
実行例
ここでは説明を簡素化するために、選択する属性値を一つに限定したが、一般には鍵、選択項それぞれをリストとして、複数の鍵の指定と、複数の選択項の値が得られるように設計されるべきであろう。
関係データベースとProlog述語の関係をProlog述語を関係データベースと見なすことでProlog処理系内にこれを築くことについて述べた。関係データベースの環境がPrologで記述され、かつSQLはPrologの述語とその呼び出しに変換される。
これとは別に、
Prologの節の中で文字列としてのSQLを生成し、これを外部インターフェイスを経由して、関係データベース管理システムに送り解集合をワークエリアに用意させて、これを順にフェッチしていくということは、多くのProlog処理系でライブラリを用意して実現している。
この場合は必ずしもPrologによって完全なデータベース環境を築く必要はなく、データベース的なデータ管理は外部の関係データベース管理システムに頼ることになる。Prolog側ではアプリケーションの要求に応じて、SQLのパターンに対応する述語を用意する。この述語は、テーブル名、属性名、とそれぞれの値といった情報を引数に持ち、その情報から、 select, from, where, and, join, group by, といったSQLのキーワードとその情報を組み合わせるロジックを担う。そして一旦、SQLの関数を組み合わせて並べたリストを生成する。さらに、それを組込述語 atomic_list_concat/3　などで、結合して、SQL文字列が生成される。
生成されたSQL文字列を処理系のライブラリで用意されたインターフェイス述語を呼び出して、その引数として渡す。求めるデータを関係データベース管理システムが選択して返してくるまでこの呼び出しで待つことになる。
それでは、Prologの中で、SQLの表現を展開することはできるであろうか。オペレータ定義を駆使して、
のような定義をして、
のように、SQLに模した表現でPrologにデータを取得することは部分的には実現できる。これができれば、このSQLに見立てられる関数構造をSQL文字列に変換して、それを関係データベースのインターフェイスに与えればよい。
しかし以下のような表現はどのようにオペレータ定義を工夫してもできない。
ここでは詳細には述べないが 季節,果物 の表現をPrologでは取れない。季節と果物の間のカンマを境に、それ以前と以後が副目標として分離されてしまう。
このように括弧で括れば、Prolog述語として定義可能になるが、今度はこの括弧が SQL の構文違反になる。このように双方の構文規則に整合しない癖があり、SQLとPrologとの間に完全に互換性のある構文を得ることは難しい。
Prologでは特別な集合表現は用意されていない。
例えば、{_,_, ... ,_} が集合を表すというような規則はなく、リストが代用されることが普通である。
リストが集合に利用されると、不都合な点が二つ存在する。
リストでは当たり前に存在する [1,1,4] は集合では [1,4] であり、しかも [4,1] でも集合として等しい。
集合演算の引数として、[1,1,4]が与えられた時に、これを、[1,4]または[4,1]と理解するかエラーと考えるかの選択がまず存在する。
もしもPrologに集合型が存在したならば、codice_133 であり、同じく codice_134 であったとすれば、 codice_135 、というような単一化の拡張があり得たかも知れない。しかしながら、Prologはこのような道を歩まず、アトムと数だけを例外として、型を考慮しない単一化の道を進んだ。そういうことで、
型付けのないPrologではこのように利用者が集合としてリストを見なすことが集合プログラミングの前提になる。さらに、四季を表す集合を例に取ると、集合が[春,夏,秋,冬]の順序で渡されるとは限らないことを常に意識している必要がある。集合を表すリスト [春,夏,秋,冬] と [秋,春,冬,夏] は集合としては等しいと考えられるが
リストとしては集合として等しいからといって単一化できるとは限らない。
Prologの組込述語として is_set/1, subset/2, subtract/3, intersection/3, union/3, さらにメタ述語として setof/3 などが集合演算のために用意されている。プログラマはできる限り、この組込述語のみで集合演算を行うように心がけることによって、リストと集合の意味の齟齬に起因する誤謬を、回避することができる。
Prologには同一の集合を定義する述語が用意されていないため、組込述語subset/3を使って 集合として等しい/2 を定義してみよう。
これで、
となる。ただし、論理変数を複数導入した例では、解が
のみで、順序に関わりなく充足しているというべきで、X = 2,Y = 1 という解は得られない。この点は特に注意を要する。
この集合として同一を中置演算子として定義してみる。
これで
となる。演算子の導入は後々までプログラミングに影響を与えるものだから、極めて慎重に行う必要はあるが。
既に、言語の基本仕様の中でリストの内包表記はできないことを書いた。それでは、これがリストではなく集合であるとどうであろうか。整数 codice_136 を共通の性質で括ったとする。その一つの括り方が codice_137 であるが、これをPrologでは以下のように表現する。
これを codice_137 の外延的な表記と見做すことは自然である。則ち、述語とは集合であるという視点である。
さらに、以下のようなPrologの非決定性のルール節定義
は、集合 codice_137 の内包的な表記と見做すことができる。ただしどちらの例も、リストの内包表記ができないことを述べた場合と同様、この表現を集合型として引数に持ち回って利用するというようなことはできない。
このように述語を集合と見做すという視点は、Prologは述語論理に基礎を持つ言語であり、それ故に述語と集合の極めて親近した関係から、根拠を持つと考えられる。
Prologプログラミングの中で常に留意するべきものとして副作用がある。
副作用を考える場合、それではPrologに於いて作用とは何かを示す必要があるだろう。これは、目標(副目標)の実行に伴う真偽値のことである。Prologが質問に対して返すものは真か偽のみである。これ以外に処理系の動作に影響のある変化が起こった時、それを副作用という。ただし真か偽に決まるための論理変数の単一化による代入は副作用ではないとする。
大域変数など、破壊代入を伴う機能は提供されないというのがPrologの原則であるが、大域変数を用意してプログラマに手続き言語的な便宜を供している処理系もある。また、次期ISO標準規格の議論の中でも大域変数の使用が提案されている。
しかし、以下の副作用についての解説では、大域変数は利用できないこととして話を進める。
組込述語もなく、もちろんカットもなく、ユーザが定義した述語だけで実行される純Prologに於いては、副作用は生じない。述語論理のイメージに近い純Prologはこの系の規範となる。したがってPrologプログラマにとって、この純Prologからの逸脱を象徴する副作用は厄介な存在である。
副作用を大別すると、
・ 述語定義に変更を与えるもの。
・ 入出力に伴うもの。
・ 処理系が管理するプロパティ情報の参照や変更。
がある。
最初に述語定義に変更を与えたため起こる副作用の例を示そう。年齢合計/1は年齢/2を関係データベースと見做し、この第二引数を全て合計したいという述語である。
これは強制的な失敗とバックトラックを使って述語定義とその解消を繰り返して、年齢を合計(集約)するものだ。見れば分るとおりどの言語のそれにも増しても冗長なコードである。このようなコードだけは決して書きたくないとほとんどのPrologプログラマは思っていて、実際にこのタイプの述語定義が書かれることはない。それでは、どのように集約プログラムを書くのだろうか。
この年齢合計は、以下のように定義するのが普通である。
findall/3で一旦リストに年齢を取り出した上で、これを再帰的に加算する。洗練された表現であるし、一般にはこれで良しとする。しかし、実はfindall/3自体に上記のようなassert/retractのからくりが含まれている。findallは第二引数が真になった場合、第一引数によって指定された項を収集するものだが、その収集する場が乃ち副作用であるという関係になる。findallが組込述語になっていて、C言語などでその記述がされている場合は、普通に破壊代入を使ってこれを実現していると見て間違いない。findall/3を利用しているプログラマは意識していないかもしれないが、findall/3にはこのような副作用が含まれ、しかし、それが利用者には隠蔽されているのである。
副作用という観点から少し外れるが、Prologと関係データベースの関係にもう一度触れる。
Prologの述語の定義節はそれぞれが論理的に全く独立で何の連関もない。連関がないものを集約できるわけもない。述語の節定義を関係データベースと見做した年齢/2であるが、そのことの本質的な無理が露呈していると考えることもできる。findall/3は連関がないものを、順序性を持つリストに組み立てることによって連関を付けたのである。
述語を関係データベースと見做した場合、更新や削除は当然副作用である。
これは、先ほどの一時年齢合計/2の場合とは異なり、確信犯的に副作用を使用していると云って良い。
述語定義に変更を与える副作用としては、組込述語のasserta/1,assertz/1,retract/1などがあり、これが実行された前と後では、同じ目標を与えたとしても真偽値に変化があったり、引数の単一化の決まり方に変化が起こり、プログラマの予期に反する結果が起こる可能性がある。また上記の例のように冗長な表現になる。それらがこのタイプの副作用が嫌われる理由である。
入出力に伴う副作用は、組込述語の read,get,get_char,write,put,put_charなどの実行でおこり、オペレーションシステムに管理されるファイル指示子が変化してしまったり、画面に表示、用紙に印字されるなど、元に戻すことが極めて難しい変化が起こる。キーボードからの入力も副作用である。この中でもファイルの指示子などは一度進んでしまうと、簡単には元に戻することができない場合もあり、再実行を指向するバックトラックによる制御と整合しなくなることも多い。
入出力に伴う副作用の例を示す。
read/1で整数を得る。奇数なら終了するのだが、偶数だと第一節は失敗する。ここでは、_奇数に偶数が入力されて偽となったのである。だからといってファイルの指示子が元に戻ることはない。第二節に移行して、
read(_整数) が実行されると、既に読み込んだ情報の次の指示子に基づいて入力が得られる。この結果、第一節で読み込んた偶数はリストに取得されることなく飛ばされてしまう。
ここでは最も単純な例を挙げたが、ほとんどの入出力部分には多かれ少なかれ、このような危険が潜んでいる。
上記副作用プログラムの適切な述語定義を示す。これでread/1が一箇所に絞られたから読み飛ばしの危険がなくなる。
処理系が管理するプロパティ等の情報もほとんどの場合副作用である。処理系の挙動を制御するために使うものが多いが、事実上の大域変数の破壊代入である。目標(質問)の実行から停止までの間に、度々変更するような使い方をするならば、プログラムの分かりやすさを損なう。一般にこのタイプの副作用があまり問題にならないのは、設定の変更が滅多に起こるものではないからである。使い方が難しいこともあり、あまり頻繁に使用されるというものではない。しかし、prolog_propertyといった述語で管理される情報は増える傾向にある。
述語定義に変更を加えるもの、入出力に伴うもの、処理系の管理するプロパティの書き換え。どれを取っても、副作用が生じると論理的な必然だけでは理解することが済まなくなり、コードの見通しが悪くなる。
現在のPrologの規格では、手続き型のほとんどの言語とは異なり、大域変数などの破壊代入(既に保持されている値を上書きする形で更新される代入)は基本的にできないことになっている。もちろん破壊代入が許される場合はここを舞台に起こる変化は全て副作用である。いつ記述されたか必ずしも明らかにできない変数に代入された値が、後に利用されることはプログラムの理解を著しく損ねる。Prologでは原則、目標の引数に現れた値は全ての解を得て完了した時点で、二度とこれを利用出来なくなる。多くの場合情報を積んであったスタックがPOPされてしまう。
実務的なプログラムでは、Prologの単一化と導出、バックトラックを使って記述されるロジックを基礎に、その間に、表示を代表とする副作用述語を挿入記述することによって、実用的な機能を実現している。
定理証明やデータベースの参照に於いては、このような副作用の挿入記述なしに、インタプリタ上で解を確認したり、真偽値を得ることだけで、目的を達成できる。しかし、他のほとんどのプログラムでは、必要な箇所で、適切な時期に、整理したデータの開示を要求される。
このような表示はPrologに於いても、ほとんど全てが副作用であって、「Prologプログラムとはロジックの上に副作用をちりばめることだ」と言っても過言ではない。現実に、データベースの更新の例を挙げて述べた表現のように、「確信犯的」に副作用述語が利用されている。
そのこともまた事実であるが、Prologコミュニティではプログラムコードの副作用を極力少なく書くことが強く奨励されている。多くのプログラマが副作用に注意し、これを減らす努力をするし、大域変数が許された処理系の利用者も最小限にしかこれを使わない。ほとんどのPrologプログラムには、破壊代入に見られるような一命令で与えられる変化で全体の制御が変わってしまうという部分はない。これは、副作用として現れた変化を利用することはしないという姿勢、意識がPrologプログラマの間で貫かれ、共有されているからである。
Prologの制御の焦点は、単に述語の引数の単一化にある。副作用の存在が、実際のPrologプログラムの中で、単一化を注視することだけでプログラムを理解することの妨げになっている例を見ることは、ほとんどない。
は構文解析を行うのに向いたプログラミング言語である。元々、は論理を利用した自然言語処理のために開発された。実際、文脈自由文法のトップダウン構文解析の動きは自身の動きと同じである。
には限定節文法（）と呼ばれる特別な表記法が用意されている。文脈自由文法を拡張したもので、文法を記述する場合は codice_140 ではなく codice_141 を用いる。
文法での非終端記号はの項で、終端記号は非終端記号と区別するためリスト内の項で表現する。付加的な条件や動作を指定したい場合、文法の最後に任意の述語を codice_142 で囲んで記述する。限定節文法の例を以下に示す。この例では数式を解析し計算を行う。
これはバッカス・ナウア記法で書かれた以下の文法規則に計算の動作を付加したものと同じ意味を持つ。
実行結果は以下のようになる。
このように直接計算を行うのではなく抽象構文木を作成するような文法規則を作成することもできる。構文木はの項として素直に表現できるため、その後の機械語へのコンパイルや最適化などを行うことも可能である。
次の、極めて簡単な日本語の解析例を見てみよう。先程の計算例では頭部の引数は変数であったが、文法的な解析結果を項として積み上げるために、ここでは変数でなく、直接ここに項の構造を記述してしまうことにする。
注目するべきことは、本体が極めて簡素で読み易いことだ。
ここでの例は厳密な文法であるとは言えないが、以下のような解析や文の生成が可能になる。
二番目の例は与えられた語リストの途中で文の解析が完了した場合は、質問の第三引数Cには残りの未解析部分のリストが返されることを示している。
最後の例はBに変数を置き、可能な全ての文を生成させている。第一引数に積み上がった項が第二引数の語リストの「意味」であると考えられる。
限定節文法の文法規則は、Prologの構文とは全く独立したもののように見えるが、実際には節を見やすくするための糖衣構文である。他のプログラミング言語でのマクロ展開のように、文法規則読み込み時にの述語に変換される。
変換規則は codice_143 で定義されている。たとえば、
codice_144
の文法規則は
codice_145
の節に変換され、付加された変数間で解析の情報が受け渡される。
のプログラム例を以下に示す。
"Hello World"は1970年代から「コンピュータはプログラム言語を使って、こんなにも簡単に動くものですよ」ということを感じさせる課題として好んで使われ、今日では教則本の冒頭にこれを置くことが半ば様式化してしまった。しかしPrologの述語は基本的に真偽値を問うものであって、入出力は副作用として疎ましい存在であり、冒頭にHello World述語を持ってくることには反対意見が強い。
そういう事情を理解した上で、ここでは、この課題をPrologプログラミングの導入として利用してみよう。
Prologは質問すると、処理系が答えを返す系である。"Hello World!"という表示は処理系が行うのだから、その前に質問がなくてはならない。質問を "hi" とする。
writeは引数が一個の組込述語である。引数の内容を表示する。codice_146の後の"\n"は改行することを意味する。
実行例で見てみよう。Prologインタプリタは一般にプロンプトとして "?- "　が表示された後に、ユーザーが質問を入れる。
述語名が hi であっても hi(a) :- や hi(1,2,3) :- の定義もあるかもしれない。Prologではこれらを区別するために、それぞれcodice_147 codice_148 codice_149 のようにスラッシュの後に引数の数を書いて区別する。ここでは codice_147 である。
質問 codice_151 に対して、定義済みの codice_151 が呼び出されて、その中でさらに codice_153 が呼び出された。
ここでは "Hello World!\n" は組込述語 codice_154 の中に直接記述されたが、一般にはこのような原初的な情報はデータベース述語によって管理され、そこから引き出されて使われる。
codice_155 は先頭が英大文字だから論理変数である。codice_156はプログラマが定義したデータベース述語である。
副目標codice_157は述語定義 codice_156 と融合され、各引数が単一化される。第一引数はatom同士でしかもcodice_151で完全一致、第二引数はcodice_155とcodice_161が単一化されて、これは単一化のルールにより無条件に論理変数codice_155はcodice_163となる。そのcodice_155、乃ちcodice_163をcodice_154する。
さらにこのプログラムに bye を追加してみよう。
述語 codice_167 の本体 (codice_69 の右側) の最後にある codice_169 は0引数の組込述語で処理系を終了させる。
実行例
Hello World からの導入はこんなところだろう。
よく知られる漫画作品・「サザエさん」の家系図(部分)をPrologで表現する。
このように、本体がない、あるいは本体のtrueが省略された定義を、単位節と呼ぶ。親子、夫婦の両述語はともに第一引数または第二引数をキーとしてデータを参照することができる一種のデータベースと考えることができる。
このような単位節データベースは全ての知識の基礎であって、必ずしもすぐにプログラムとして利用されなくても価値がある。ノートに書き付けるように身の回りの知識を定義していけばよい。
備忘録としての単位節データベースへ実際に問いかける例を示そう。「サザエの親は誰か」という質問をする。
ここで一旦処理系は停止する。この解に満足な時はただ改行する。
1) 波平に満足できない。
2) 波平以外の解がほしい。
そんな場合には停止中のカーソルにセミコロン(;)を入力すると、次の解を示してくる。_親 = ふね だ。他にも親はいないものかと
さらにセミコロンを入力すると、もうこれ以上解はないと、この処理系では入力したセミコロンをピリオドに置き換えて表示して
質問は終わりとなる。
前題の家系図が既に定義済みという前提で、祖父-孫 関係を定義してみよう。
祖父・孫の関係になれるのは波平とタラオだけである。'祖父-孫'という述語名はハイフンのような記号を含むアトムとなるため、
シングルクォートで囲む必要がある例として示した。述語名はこれに限らず、 祖父孫 でも 祖父と孫 でも 祖父孫関係 あるいは単に 祖父 でも、特にこうしなくてはいけないというルールはない。処理系への知識の与え方は基本的に自由である。
今度は、「孫」を定義する。上記の定義に倣うなら '祖父母-孫' 関係ということになるが、ここでは単に「孫」とする。
実行例を示そう。
一般に質問する時は、入力の負担を減らすために、最少の文字数となる XとかA,Bなど英大文字一文字を論理変数に置くことが多い。
Xを使うことが多いのは、方程式の解となる変数をXとする習慣を引き継いだものと考えられる。
もちろん家系図の時のように ?- 孫(_祖父母,タラオ). と質問しても構わないし、常にそういう習慣があるならそれが望ましい。
孫を具体的な人と人の関係として定義して見たが、以下のような定義も可能である。このような定義をルールという。
Aは孫から見ると親であるが、祖父または祖母から見ると親ではないので、_親 とはせずに、英大文字の A で抽象化した。
本体の二つの副目標である親子/2のそれぞれの引数に共通のAが存在することが重要である。孫の親と祖父または祖母の子が同一人物のAであることを示している。だから
行の先頭に % がある一行目は「註釈行」でありプログラム実行の対象とはならない。述語形式とは限らない自由な文を書くこともできる。
_祖父または祖母の子 と _孫の親 とは単一化できていないため、変数名から同一が類推できるとしても、処理系は A の時のように同一のものと扱わない。
それならば、_祖父または祖母の子 と _孫の親 を単一化させてしまえばよい。それを実行したのが下のコードである。
単一化述語である =/2 で二つの変数が実は同じものであるが明確になる。二つの視点からそれぞれ別の変数シンボルになってしまうことは屡々ある。そのような場合は単一化で解決する。
家系図の中で、このような二つの親子関係が連接して、孫関係を充たすのは、
である。
与えられたリスト要素を加算する。再帰的な定義である。
1要素少ないRの加算計がS1ならばSはS1にNを加えたものだ、という宣言である。
実行例: このように定義しておけば、以下の質問は
となる。
加算は以下のように、二つの述語に分離して、引数をひとつ増やした述語を作ると累算部分がはっきりしてわかりやすい。加算を担うのは後の方、引数が3個ある方の述語だ。述語名は引数の数が違うから同じ リスト要素の加算 で構わない。リストから数を取り出すと、この第二引数に加算していく。
リスト要素の加算/3 の第一節の %1 の下の
というところがProlog独特のテクニックである。
第一引数のリストが空になったとき、第二引数に累計が存在するのだが、
最初の %1 述語リスト要素の加算/2の副目標
の第二引数では初期値0と値を決めて引数に渡しているため、この第二引数から値を受け取ることは不可能である。
そこで、第三引数として一つ余分な引数を設けて、そちらを変数にして置けば、最終的にその引数が単一化されることによって値を受け取ることができるという訳だ。その第二引数と第三引数の単一化を行っているのが、%2 の リスト要素の加算/3の第一節の
である。
この述語の第二節第三引数がともにSで同一であることも重要である。
この部分が束縛されないまま、単に同一の変数であることが示されている。
質問の第一引数が[]になれば、この述語の第二節が融合されて、質問側に用意されている第二引数の加算計がこれに単一化される。
これまで第三引数は全て同一ということになっているため、この第三引数経由で加算値が質問の第二引数に返される。
単位節(本体のない事実上のデータベース定義)要素の加算。
実例として次の単位節データベースを考える。
ここでは年齢の合計を計算する。
簡単なデータベースの参照は、
Prologの述語の中のそれぞれの節に現れる要素は他の節から完全に独立である。すなわち一つの節の中の値は別の節からは参照できない。
山田を得たとき、大島を得たとき、清川を得たときはそれぞれ独立している。以前の変数の束縛は解かれてしまっている。
大島の20を得たときには、山田の35の情報は失ってしまっているということになる。
これでは加算のような集約問題を解決できない。
このことを可能にするために、メタ述語 findall/3 が存在する。
findall/3 はSQLのselect文に似た述語であり、述語を実行した際に任意の値をリストに集めることができる。
本来、情報の連関のない述語 年齢/2 のそれぞれの節を、連関を持つデータ構造であるリストに取り込むことによって、集約を可能とする。
実行例:
理解を深めるために、findall以下を直接質問として呼び出してみよう。
となる。findallは強力な述語であるが、対象となる定義節数が極めて多い場合、例えば、1000万節を越えるような場合、スタックオーバーフロー等のエラーが発生する危険が生じる。内部メモリにリストとして情報の連鎖を生成するのだから、やむを得ないことではあるが、注意が必要である。
算術平均ともいい、一般に平均値といった場合これを指す。標本はリストとして保持しているとする。基本的には加算と同じだが、同時にリストの標本数も数える。第二、第三引数にそれぞれ初期値 codice_170 を置き、これに標本数と値を加算していく。
この述語では要素数や累計を求められていないため、これを入手するための変数は用意されていない。その代わりにリストが空の時に相加平均が計算されて単一化される。これが平均値の述語定義だが、多くの場合ここまでプログラマが定義する必要はない。下記のように、組込述語を含めて、定義済みの述語を組み合わせて相加平均は定義される。上記の要素数のカウント部分は独立して codice_171 という組込述語となっている。したがって、相加平均の定義は
で構わない。
相加平均が使われる定義の一つ標準偏差の定義である。標準偏差本体の定義の前にこの相加平均の計算が完了している必要がある。
is/2評価の中に現れる関数codice_172で平方根を求める。
リストの最大値を求める。併せて、カットの典型的な用法について説明する。最初に初期値を設定して、それと再帰的に比較する。 初期値はリストの中の要素であれば、何でも構わないのだが、ここでは第一要素を使う。
_要素がこれまでの最大値を超えない時は最後の節が選択される。超えた場合は第二節の「codice_173」のカットが働き最後の節が選択されることはなくなる。引数が3の最大値の第二節に「codice_7」がある。これがないと、
というようなことが起こりうる。バックトラックして来たときにそれまでで最大としたものを、「codice_175」の入力で「それではない」と否定されて、撤回してしまう。せっかく見つけ出したそれまでの最大値であるべきものがこれまでの最大値として使われないためである。「codice_7」を入れることが有効な場所を、最初の定義も含めて示す。
などが考えられる。ただし、案3は　最初の codice_177 で質問した場合は ! が有効になるが、codice_178 の方で質問した場合は、「codice_7」はないので、有効にならない。最大値/2の方で質問するように注意する必要がある。
の本体に必ずしも「codice_7」が存在しない理由は、第一引数が codice_45 で呼ばれた場合、さらに他の節が選択されることはこの定義の場合はあり得ないからだ。最初の最大値の定義の、
最後の節の本体に「codice_182」を加えれば「codice_7」を排除することができる。
最後に、最も宣言的な最大値の定義を示す。「選択した値以外の全ての要素が選択した値以下である時、選択した値が最大値である」がその意味である。
select/3とforall/2は共に組込述語となっている。select/3は第二引数のリストの先頭から要素を非決定性に取り出し、第一引数に単一化すると共に第三引数にその要素を除いたリストを単一化する。
forall/2は 第一引数の評価を真とするものに全てに対して、第二引数の評価は真となる、というものである。
行列も集合同様、Prologでは特別な記法は用意されてはいない。そのため一般に行列を、リストを要素として持つリストとして表現することが多い。
例えば 3 × 3 の単位行列
formula_1
は 1,0,0],[0,1,0],[0,0,1 のように表す。
全体が3要素のリスト、そのそれぞれの要素がまた3要素のリストである。
ここでは、findall/3を二重に使った行列の転置の定義を示す。
この定義の難しさは、列数を得るための表現にある。ここでは行列の転置述語の第一引数を細工してこれを得たが、代償として、対象行列を[_最初の行|_残りの行]と表現したため、この引数が何を意味するのかわかりにくいコードとなった。
行列が1,2,3],[4,5,6],[7,8,9],[10,11,12として与えられた時の行列の転置は
実行例
となる。
行列の転置の再帰的な定義は
findall/3の定義に比べると、定義自体は簡素なのだが、可読性はかなり悪い。
行列の掛算は普通第二引数の行列を一旦、行列の転置/2 で転置し、掛け合わせる3つの述語 行列の掛算_1/3 行列の掛算_2/3 行列の掛算_3/3 によって積を得る。述語名の末尾に _1 _2 _3 を付加して別の述語とするのは、引数が同じで同一の述語名が使えない時の方便である。一般に、述語の意味する言葉を述語名とすることが望ましいが、行列述語などを含めて数学的なアルゴリズムでは、部分的な計算を言葉で表現することが困難な場合も多い。それでこのような述語の命名がしばしば見られる。
実行例
正方行列の右下がり対角要素リストと左下がり対角要素リストを得る。正方行列の対角要素とは、
formula_2
1、5、9 が右下がり対角要素であり、3、5、7 が左下がり対角要素であるとする。これを codice_184 と codice_171 と codice_6 の組み合わせで定義する。
組込述語 codice_184 は非決定性の述語で第一引数が論理変数の場合は、1、2、3、…、n とバックトラックされる度に順に値を生成する。codice_184 の codice_189 は1からこのカウントを開始するの意味である。
上記二つの定義では、要素位置を示す論理変数 codice_190 が現れるが、この論理変数に対して何ら演算を施してはいない。このように要素位置等の数値による管理からプログラマが解放される機会が多いことも の大きな特長である。
実行例を示す。
行列がガウス行列であるかどうか検査します。ここではガウス行列検査/1を述語名を冗長に取って、その事によって、宣言的に述語定義することで、Prologのプログラムが、ガウス行列の解説になっているように工夫されています。
実は、最初に現れる0でない要素がない、すなわち、全ての要素が0であるような行があり得ますが、codice_191がない訳ですから
codice_192が偽になります。これは、最終的に、
codice_193の中のcodice_194の中に現れますから、偽になればリストLに採用されません。乃ち、この判定では全て要素が0の行は無視されます。
このcodice_195のように、配列と違って添字を使わないリストで行列を表現するため、Prologの行列の処理では、大小比較以外の数値計算が全く現れないこともあります。
が集合をどのように扱うかについては、既に プログラミングの章で述べた。
ある集合が別の集合の部分集合であるか確かめる述語 codice_196 を定義する。
この述語は組込述語 codice_197 として定義済みであり、その定義は
であると考えられる。codice_198 のメンバーは必ず codice_199 のメンバーであると宣言している。
組込述語 codice_200 は第一引数の副目標が真になる場合は、第二引数の副目標も必ず真になると宣言するメタ述語である。「全ての・・・について、」がその意味と考えればよい。
codice_201は
「全ての部分集合の要素は、全体集合の要素である」という意味となる。
これとは別に再帰を使った codice_196 の定義もある。
実行例を示す。
となる。集合では「その要素が・・・」と語られることが常であるが、「その要素が」をProlog述語として表現したものが
codice_72である。
階乗は整数の性質に含まれる数の連関を使うだけで計算できる数少ない例の一つである。Nの階乗を codice_204 として定義する。
ここでの階乗の定義のように、計算対象となる要素が、常に1ずつ減っていく、そして、それだけで計算が完了するというのは特別な例なのであって、そのような固定した性質がない集合の計算では計算対象をリストに取ることが多い。既にそのような例としては 加算の codice_205 があった。
階乗には以下のように第二引数に累算部分を明示的に取る定義もある。
この定義は最後に副目標としてcodice_206のような再帰表現の締め括りが来ている。このような形式の再帰を[[末尾再帰]]と言って、Prologに於いてはこの末尾再帰の方が、インタプリタ/コンパイラが最適化をしやすい。再帰の実行が深くなったり、巨大数を扱った場合、スタックオーバフローのようなエラーになることを回避しやすい。
このような質問がなされた場合、上側の定義、則ち末尾再帰でない定義では多くの処理系で解が返らない。一方、末尾再帰の定義では、もちろん多倍長整数のサポートが条件ではあるが、456579桁の整数解が返るに相違ない。
このような事情から、一般にPrologプログラマには二つの定義のうち、下の定義の方が好まれる。
10000以下の素数のリストをウィルソンの定理による素数判定を使って得る。この計算では階乗計算が繰り返し使われるのだが、述語に定義節を動的に書き加えることによって、階乗の呼び出し回数を大幅に少なくできる。ただし、述語論理を完全に逸脱したプログラムである。
codice_207 は述語の先頭に定義節を加える組込述語。既に計算した階乗は答えを階乗保存計算の先頭に付け加えることで、以後階乗計算に入るまえに、その解を得ることができるようになる。
述語 codice_208 の定義は階乗保存計算(7). を実行前と後では以下のように変化する。
codice_64 は現在の述語定義を示す、処理系のサービス述語である。
組込述語 codice_207 や codice_211 を使えば、プログラムによるプログラムの生成が可能になる。それだけではなく、プログラムの実行中に追加プログラムコードを生成して、それを即実行することもできる。
リストの要素が重複している時、これを唯ひとつの要素に置き換えたい時がある。
最も基本的な再帰のなかで member/2 を使って後に再びこの要素が現るかどうか検査している。複数同一要素が存在するときには、
最後の位置にある要素だけが選択される。リスト要素の順序の変化に注意が必要である。
リストの重複要素削除には、他にも有力な方法がある。
組込述語 setof/3 と member/2 を組合せて使う。setof/3は名前から想像できるように出来上がるリストを集合とみなす。従ってこの述語のなかには要素が重複したらこれを取り除いてしまう機能を含んでいる。
もうひとつ、これは組込述語 sort/2 の約束事であるが、最終的に整列結果の重複要素は取り除かれる。従って、
これだけで済んでしまう。
リスト要素が全て同じ。検査述語であると同時に、リストに変数を含む場合はそれを第二引数と単一化して全て同じ要素になるように企てる働きをする。
さらに第二引数が変数で呼ばれたら、第一引数のリスト要素が全て同じ場合にのみ真となり、その要素と第二引数が単一化される。
第一引数のリストのなかにひとつでも第二引数と異なった要素が現れたら、則ち偽となる。偽にならず、第一引数が[]まで到達したら、全ての要素は第二引数と同じであったことになる。
実行例
最後の例は、Prologの単一化の = による制約表現とその制約解消過程が面白い。
上記、codice_212は大変有用な述語であるが、仕様上重大な疑問がある。それは第一節の定義で、空リストの要素という矛盾を認めている点である。この問題は単に矛盾であるばかりでなく、
となり、L1 = [] を解として含んでしまう。これは受け入れがたい。空リストになるかどうかの検査が常に必要になり不便でもある。そこで、
codice_213を定義しよう。定義は述語名そのまま、
と定義する。これで
重複するから一部省略するが、codice_212に於ける質問例の動作通りになる。
なお、codice_212を以下のように変更すると、
というような実行となり、思い通りの結果にならない。結局この定義に於いても、
codice_216という意味の判り難い副目標が必要ということになる。
N個の空白からなるアトムを生成する。述語名がシングルクォートで括られているのはその先頭文字に英大文字が来ているからである。ここでは組込述語 codice_171 によって要素数N個の変数のリストを生成し、
その要素全てを空白文字とした上で、文字のリストからアトムを生成するために、組込述語 codice_218 を使っている。
実例を示す。
上に示した定義は、全ての要素が同じ/2が既に用意されていることを前提に、空白からなるアトムを作ったが、
でよく、この定義の空白と指定された部分を抽象して、同一文字からなるアトムの定義は
でよい。
'N個の空白からなるアトムを生成する'/2の再帰的な定義は組込述語 atom_concat/3 を使って実現する。
上に示した非再帰的な定義とどちらが判りやすいか、取捨に悩むことが多い。
事務計算などでは、123という整数を8桁の数値表現で、しかも頭部を空白ではなく0で埋めることを要求されることがある。
これを上記 codice_219 を使って定義する。最初に枠を取り、頭部の桁不足の部分は codice_219 を使って codice_170 を埋めている。
codice_222、codice_218 ともに組込述語で、それぞれ、数値を分解して数字リストに、アトムを分解して文字リストとする。
頭部の枠リストの桁（要素数）は述語 codice_6 が決定する。
実行例
ヘッドゼロサプレスの定義は、
変数名を変更したが実質的には codice_219 の第二引数を変更するだけの違いである。
以下二つとも事務計算では必須の述語である。最初の述語が必要になるのは帳票からOCRで文字列を読み取りデジタルテキスト化されたものが入力になる場合であろう。
codice_226はnumber_chars/2に寄り掛かった定義になっている。
codice_227は、ここでは整数に限定しているが、実数を対象にする場合は、整数部と少数部に分離し、整数部にだけこの述語を適用すればよい。
codice_228に於いて、Lに下3桁ずつ、積んで行き、しかも最終的に上位桁から下位の順に展開できている。これは、プログラム事例の後に出てくるcodice_229の中で見ることができるPrologの特徴的な技法である。
codice_230はカンマ区切りの厄介なところで、1000で除した剰余が2桁以下の時に頭部に0を強制している。しかし、最上位の3桁はその限りではない。そのための述語がcodice_231である。
ユークリッドの互除法によって最大公約数を求める。
数値演算の場合、他の言語とそれほど変わらない。Prologの特徴を求めるならば出力用の引数が必要とされることだろう。
実行例
n以下の全ての素数をリストに集める。エラトステネスの篩を述語として定義し、これを呼び出す。
最初の述語 codice_232 の冒頭で、2から始まりnまで連続する整数のリストを組込述語 codice_5 と codice_234 を使って生成する。代表的な生成パターンである。
このリストを対象に小さい順に素数を探し、その素数の倍数をリストから削除して再帰的にエラトステネスの篩は実行される。
codice_235 の定義の中で codice_5　を使うと codice_237 は実は不要である。
どちらの定義が読みやすいかについては、常に問題となる。
この codice_5 を codice_235 の中に持つ
が最も宣言的なエラトステネスの篩の定義かも知れない。
codice_240 の方は、codice_5 で生成される新たなリストが第一引数に置き換えられて再び駆動される。このような新しい対象を生成しつつ、ダイナミックに繰り返すパターンは、再帰的な定義以外に方法がない。
実行例
Prologでは、文字列という場合、一般にアトムを指すが、codice_242（文字コードのリスト）を指す場合もあり、少々曖昧である。ここではアトムを指すとする。
codice_243 という極めてスーパーな非決定性の組込述語がこの機能の全てを司る。開始点は0オリジンであることに注意が必要である。Prologの組込述語では1オリジンを使うものが多いのだが、この述語は0オリジンである。
codice_243 の仕様は (1) 第一引数に検索対象アトムがくる、(2) 第二引数には検索語の開始点がくる、(3) 第三引数には検索語の文字数、(4) 第四引数には検索が成功した時の残り文字列長、(5) 第五引数に検索語がくる。
codice_243は文字の出現順序は保たれるが、対象文字列を一文字ずつ開始点、終了点のポインターをずらしながら試行錯誤で、全ての切り取ることができる副文字列が試さながら実行される。従って、対象文字列が長く、第二、第三、第四引数が変数の場合は、検索を完了するまでに時間を要する。
文字列の検索にはcodice_246の代わりに組込述語のcodice_247を使う定義もある。こちらの方が引数に変位が現れず若干は抽象的な定義である。
codice_247は二つのアトムを結合することと、アトムを二つの文字列に分解すること、この二つ意味を双方向に持っている。
実行例
上記検索パターン通じて、目標に _検索語 がふたつ冗長に現れ、単一化を二重に行っている部分もあるが、将来、検索語に何らかの記号パターン(正規表現のような)が利用される可能性を考えて、ここではあえて検索語と検索結果の検索語が同じになることを承知の上で、一引数余分に確保している。
検索語に変数がきたらどうなるか。ここではYとする。この場合、codice_249は検索文字列の候補を挙げてくるだけである。その後に連接した二つのcodice_246で制限を付けている。
このように検索語を与えなくても、検索する可能性を持つことはPrologによる文字列処理の特長である。
codice_243は第一引数が変数で実行されるとエラーとなる。第二引数以下の情報から双方向に第一引数を生成することはしない。
論理的には第一引数Aにabcdeが返ってきても良さそうなケースだが、述語定義の仕様から、エラーとなってしまう。
ISO規格を含めて、ほとんどの処理系では正規表現がサポートされていない。Prologは文字列操作を得意とする言語だが、それでも複雑な置換パターンでは長い定義となることが多い。
最初に、置換対象が一つの単純な置換を考えてみよう。
codice_252 はリスト要素を結合して新しいアトムを生成する。
実行例を示す。
これはうまく行くが、複数置換対象が存在する場合を見てみよう。
置換対象が複数あっても、一ヶ所だけ置換するという場合もある。その場合には選択的に置換できるこの定義で良い。
しかしこの例もそうだが、対象となる副文字列全てを置換したいことも多い。結論を言ってしまえば、このようなバックトラックを使ったパターン(失敗駆動)では全置換は定義できない。
一般に置換では、置換対象文字列が存在しなかった時、その副目標(質問)を偽としないで、元の文字列をそのまま残す。codice_253 の第二節 文字列の全置換(_文字列,_,_,_文字列). はそのために必要である。
ちょっとわかりにくいが、codice_253 は再帰的な述語である。置換対象までとその後文字列に分割して、後文字列を再帰的に置換したものと、それまでの文字列を置換しながら結合する。
実行例
これで二ヶ所の生垣を八重垣に置換することができる。
リストの結合とは引数として与えられた二つのリストを最初のリストの最終要素の次から第二リストの最初の要素から順に付け加えて行って、一つのリストに纏めることを言う。この述語はほとんどの処理系で組込述語 codice_6 として特に利用者が定義しなくても済むが、述語定義技法としての観点からも を代表する述語であるため、ここでは codice_6 述語が でどのように定義されるかを紹介する。
appendは2つのリストを結合する
実行例
appendの意味は結合に留まらない。第一引数、第二引数に変数が来るとリストを分解する。
実は非決定性の述語としての代表でもある。
となる。さらに以下のように使用するとappendは実はmemberのスーパーセットであることがわかる。
ここで注目するべきことは、このような使い方の codice_6 に於いては、切り出したい情報とその情報のリスト前部、リスト後部の情報を同時に取得できることである。例えば切り出した情報（上の定義例では codice_258）の前部や後部にXが含まれていないか検査などが可能になる。これは codice_66 においては不可能なことである。
codice_6 は多義的な述語であり、同時に codice_261 を代表する述語でもあるため、機能に見合った述語名をリストの結合、リストの分解という具合に与えるか、それとも、通りのよい codice_6 一本で貫くか迷うことが多い。ここではこの述語定義を理解、記憶してもらうためにもっぱら codice_6 で通したが、それぞれ別の述語名を与えて利用するのが本来の の姿であろう。
引数が3のappendを示したが、4引数以上のものも便利である。
このように、中間のリストの前のリスト、後のリストという分解が簡単にできる。この append/4 の定義は append/3 の定義を利用して
である。
さらに append/4 ができれば、 append/5 は
となっていく。一引数少ない append の定義ができていれば、このように、それを第一節の本体に使って簡単に定義を追加できる。
四引数のcodice_6の定義ができたところで、これを使って二文字以上の要素が昇順に並ぶリストを検索する。
この探索は、対象がアトムではなくリストになる点で、codice_265のそれに比べで強力である。
第二引数のリストが単純な性格を持ち、その性質が完結しているか検査する述語を書くような場合であるが、その程度の難度の検索ではcodice_266は強力である。
次に二文字以上の要素が昇順に並ぶのだが、各昇順文字リストのグループとしては最長の文字リストを検索する。
codice_267は第一引数のリストの最終要素が第二引数と単一化される。ここでは最後の要素と次のリストの先頭要素を比較している。
検索文字列が先頭からだったり、末尾まで続いている場合には、第一引数や第三引数が[]になる。codice_267は偽となりそれぞれ、
それを否定しているから、ここの検査条件は真になる。
先に文字列の検索を組込述語 codice_243 を使うことで例題とした。ここでは一旦、アトムとしての文字列を文字を要素とするリストに変換して検索する例を示す。この場合、検索語も文字のリストに変換する。
「検索語の前方文字リスト、検索文字リスト、検索語の後方文字リストを文字リストから文字列に変換」がシングルクォートで囲まれて定義されているのは、途中に「、」が含まれているからである。規格で定められてはいないが、全角の記号は将来全角文字のみで処理系が利用される可能性から、記号扱いにしている処理系が多い。
述語 文字リストの検索/5 では、上記のリストの結合 codice_6 が、リストの結合というより分解として二つ連続して利用されている。
すでに文字列の検索を codice_243 を用いた例を示したが、一般に文字列の検索は codice_218 を用いて一旦文字のリストに変換してから検索するほうが定義が柔軟になる。
この述語の利用者は、検索する前に述語 パターン照合/2 を定義する。リストによる検索/4 は append/4 として知られる述語。
append/3 を member/2 として使う
に極めて近いが、Aは単項としか単一化できないのに対して、 リストによる検索/4 のL2は複数項のパターンを切り取ることができる点が違う。
実例を示す。"八重"から始まり"に"で終わる文字列を検索する。
ここでは検索パターンリストに変数を置いている。最初に[八,重]が来て文字がわからないリストが来て、そして最後に[に]が来る。 では、このようにパターンを一つのリストで表現することはできない。それでここは変数にして、codice_273 述語に解決を委ねている。
codice_6 を利用してリスト要素の隣を定義してみよう。極めて宣言的な定義となる。
さらに、リスト要素の両隣は
実行例
二つの隣要素が第三引数と第四引数に出現順に入るのだと決めておけば定義は
となる。これが自然な定義であろう。
しかし、「リスト要素の両隣」がこの述語の仕様であったとすると、左右の順序や出現順はどこにも示唆されていないと
考えることがむしろ素直であり、上記の左右順あるいは右左順の二節とする定義も成立するのである。
リストの要素の反転は codice_275 が組込述語になっているが、ここでは、これを定義してみる。
codice_6 を使った明解な宣言性の強い定義であるが、実行速度が遅いことからこの定義はあまり使わることがない。
普通、リストの反転の定義には、以下のように二つの述語に分解して定義する。ただしこの定義は完全ではない。正しい定義は最後に示す。
codice_229 の方の第二節 codice_278 に着目して欲しい。第二引数で受け取ったリストの前に追加しているが、最初が codice_45 だから、先頭から順に末尾から付加されていくことになる。第一節の主張は、第一引数が codice_45 になった時には、第二引数に反転したリストが積み上がっているはず、ということである。
実行例
さらに、
述語の双方向性も確かめられたと思いがちだが、そうはいかない。
エラー状態が生成されていく過程は興味深いのだが、複雑で難解になり過ぎるため、どのような経過で内部メモリがなくなっていくかはここでは示さない。このような基礎的な述語定義の中に重大なエラーが潜む余地があることは と考えるべきである。
以下はこのエラーに対する対策の一例である。
リスト要素の反転/3 の方の第一節にカットを入れる。これで上記エラーは回避できる。
最初に示した codice_6 を利用した定義ではこのようなことは起こらない。それで、あまり使われることがないとしながらも、こちらの定義を最初に載せた。
codice_282 という文字列を反転して codice_283 という文字列を生成する 文字列の反転/2 を定義する。組込述語 codice_218 と上記定義した codice_285 を組み合わせる。
ここでは一旦文字のリストに変換している。それによってリストの反転/2が利用できた。
ただし、元の文字列の形式に codice_218 をもう一度使って戻さなくてはならない。
codice_218 でリストに変換せずに、文字列の反転/2を定義できるが、以下のような難しい定義となる。
組込述語 codice_288 が使われた。アトムとアトムを結合して別の長いアトムを生成する述語である。
文字列の反転の例を示す。
回文とは先頭から読んでも、末尾から反対に文字をたどって読んでも、同じ文になるある程度意味の通る文のことである。回文は実用性よりも、文字列操作の練習課題としてしばしば利用される。
ここでの定義は回文を生成するのではなく、回文であるかどうかの検査である。ここでは「なかきよのとおのねふりのなふめさめふなのりふねのおとのよきかな」（長き夜の 遠の睡りの 皆目醒め 波乗り船の 音の良きかな）のように、文字の並びを対象とする。
一旦組込述語 codice_218 で文字のリストに変換する。ここまではいわば定石のようなものだが、回文の場合はここから、そのリストを反転し、引数が共通であることを示して、反転前と反転後が同じなのが回文であると宣言している。実例はもちろん
である。
回文にはcodice_246を使った定義もある。
回文の文字列中の前方からN文字目一文字と後方からN文字目一文字の対はどれも同じ文字になる。そういうことをこの定義では述べている。これも細部を述べながら、かつ、宣言性を維持した美しい定義である。
ただし、中間点まで確かめたならば回文と決定できるはずだが、ここでは全文を走査してしまっている。
中間点で打ち切る定義は、codice_246の第二、第四引数を比較する。
codice_292
これで第一引数の走査が中間点に達すると第二引数の走査はしなくなる。
これで中間点を過ぎるとcodice_293が偽となるから第二引数のcodice_294の検査には進まなくなる。
しかし、codice_292の第一引数のcodice_246の方は最後まで走査されてしまう。
この問題も解決しようとすると、
これで中間点に達するとcodice_297が働いて、codice_246へのバックトラックは止まる。
しかし、codice_299の部分は、複雑で宣言性を損ねる記述になっている。codice_292の中の副目標の述語名がcodice_243に統一できなくなっている点でも、読み易さを損ねている。カットの説明を参照されたいが、
ここでのcodice_302を独立した副目標として定義し直すことは、カットの有効範囲の関係からできない。
このような場合、日本語で解説して行くようなつもりで、冗長な述語表現を取ると上手く行く。
この方がずっと宣言的で明解な表現になっている。
ここで codice_304 の定義は具体的に定義する。例えば、
実行例
一つ以上離れた関係を codice_303 の第二節でので定義で、引数の変数を codice_304 を経ながら codice_258 - codice_308 - codice_309 と連鎖することによって表現している。
経路が以下のような定義の時、ある駅から別の駅に到達できるかを示す codice_310 の定義は。
実行例
検索は、codice_311 → codice_312 → codice_313 と進み、第一節の本体で codice_314 が真となることにより、到達可能性は真となる。この定義を見比べると、codice_315/codice_310とcodice_304/codice_303さらに、既に例として見てきたcodice_319/codice_320(あるいは先祖)の関係が同じアルゴリズムであることがわかる。
単位節要素の加算の例に示された"年齢"のような単位節（本体定義なのない節）を定義順に表示するには普通失敗駆動を利用する。
年齢の定義次の通りだとする。
ここでは定義順に氏名,年齢を全て表示する方法を示す。
表示は組込述語 codice_321 を使っている。無条件に偽になる組込述語があるため、バックトラックが起こり順に述語 codice_322 の
各節が呼び出されて表示される。これが失敗駆動だ。最終的には年齢/2の呼び出しは偽となるため、質問は codice_323 で終わる。
実行例
一般に必ず偽となって終わる定義は、これを再利用する際に不都合が生じる場合が多い。真として終了するためには、
と書き加えるのみである。
失敗駆動を用いることなく、再帰を使って上記の年齢を表示することは案外と難しい。
完全に独立した存在である定義節から、情報の連関を付与されたものとしてのリストを得るために、codice_5　をここでも使用した。実はこの codice_5 の中に失敗駆動が含まれている。つまり、ここでは codice_5 を使うことによって失敗駆動を隠蔽していることになる。
codice_327 の定義は以下の通り単純である。
codice_327 自体は究極の再帰プログラミングである。問題はこれをどのように使用するかで、
codice_327 は再帰述語ではあるが、失敗駆動の起点としてのみ利用される。
codice_327に制御が返ってくるのは、後続する副目標が完全に失敗したときである。codice_327まで制御は戻り、再び後続する副目標が実行される。まったく最初と同じ状態に戻って実行される。ということは、本来述語定義や定義された節の引数は実行中に書き換えないことが基本なので、後続の副目標を何度繰り返しても同じ結果となり、停止しないはずである。したがってcodice_327を含む節がプログラマの期待通り停止するためには、その後続の副目標の実行に副作用があることが前提となる。この副作用による変化を読み取ってcodice_327の節を停止するように工夫する。上記の場合、
codice_335
がそれである。
次に、codice_336 という検索述語を codice_327 の前に置いてみる。
codice_338 の選択が春から先に進んでいない。副目標 codice_336 には codice_327 があるためバックトラックしてこないことになる。
前節ですでに用いたが、 には入力述語として古くから、1引数と2引数の codice_341 が存在した。この入力述語の魅力はアトム、数値、リストを含む複合項など、どんな項でも入力可能である点にある。入力された文字列は解析されて、引数と単一化される。
のように使う。注意するべきことは、プロンプト |: の後の入力には正しく項が来なくてはならず、しかも、入力はピリオドで終了する必要がある。
ごく一般的なカンマ区切りの「codice_342」の入力はシングルクォートで囲み「codice_343」でなくてはならないことになる。
これでは実務的には不自由なので、文字列が改行されて終了するまでを、アトムとして受け取る codice_344 を定義してみる。
これで改行によって、それまで入力された文字が一旦リストに収められ、それを codice_218 で変換して、アトムとして受け取ることができるようになった。ただし、入力はアトムだけに限られる。この点は codice_341 が項であったのとは異なる。
codice_347 の第二節に現れる codice_348 であるが、これは改行ではなく[[End Of File|ファイルの終端]]を意味する情報が入力されたことを意味する。この独特なアトムを では伝統的に用いている。
実行例
今度は |: のプロンプトが表示されない。このプロンプトの表示は項入力述語 codice_341 のいわばサービスであって、同じく組込述語であるが、codice_350 では表示されない。
codice_351 は codice_327 によく似ているが、第一節の末尾にカットがあるため、失敗駆動の起点としての繰り返しにはならない。整数入力検査に失敗した場合のみ、整数入力を繰り返す。
codice_353 は組込述語であり、アトム（文字列）を受け取りこれを解析して、 の項に変換している。整数でない情報を受け取った時にその情報を表示させるためには、codice_344 と同じ本体の中で、処理することが必要である。
codice_351 の第二節で表示することは、この節が引数から codice_350 で得た情報を受け取っていない以上不可能である。入力エラーを表示させる際に、入力された文字列も共に表示したいのであるが、第一節の本体内の副目標でない限り、引数からこの情報を受け取ることはできない。
実行例
codice_351 述語は codice_327 を使っても書くことができる。
codice_327 とほとんど同型の再帰述語の整数入力の代わりに codice_327 自体を挿入することによって上記のように失敗駆動的な
整数入力述語が定義できることは実に興味深い。
整数入力の主述語と を代表する述語 codice_327、codice_66、codice_6 を比較した見た。極めて類似したパターンの述語であることが分かる。
ではキュー操作を差分リスト(重リストともいう)を使って表現している。差分リストとは二つのペアとなったリストを設定し、第二リストの全てが、第一リストの末尾に来るようにしたものである。第一リストのなかで第二リストと重ならない部分が、示したい情報・生きた情報である。例を示す。
キュー操作では、もっぱらこの最後の表現を使う（codice_364 → codice_365）。ここでは、直感的理解を深めるためオペレータ「codice_366」を使って（すなわち複合項として）キューを表現してみる。
codice_367 のような構造を不完全データ構造と呼ぶ。codice_368 のように完結していないという意味で。
しかし、すでに多くのプログラム例を見てきたが、codice_6 に代表されるように、 の引数部分はこの不完全データ構造で満ちている。構造の不完全な部分、すなわち変数部分に新たに情報構造を単一化することによって、そしてその末尾に再び不完全データ構造が来るようにすることで構造を成長させる。不完全データ構造の多用は プログラムの最も顕著な特徴である。キューの操作は、以下のようにキューを以前、以後と対にして（ここでは codice_370 codice_371）持ち回ることで利用する。
上記の例では、現在のキューは、最後の codice_372 と単一化された構造であるといえる。キュー codice_372 は現在は空である。codice_374 には codice_375 が取り出せた。ところで、上記のキュー定義では、オペレータ「codice_366」を利用して直感的に差分を強調することによって宣言性を高めた。しかし、 では、引数には極力、リストを排することはできないにしても、構造体を持たず、アトムのみで構成するほうがプログラムの見通しがよくなる。ここで、キュー操作を日本語に書き直しながら、定義を書き直す。
codice_258 と codice_309 がペアであることが不明瞭になってしまったが、これで自然な定義である。
キュー操作が出てきたところでスタック操作について述べる。スタックの定義はさらに簡単である。
利用法は、
上記の例では現在のスタックは、codice_379 であり、内容は codice_380 である。codice_375 は一度プッシュされたがその後ポップされてしまった。
リストによって与えられた集合要素のN個の組合せ。非決定性の述語である。
第二引数が1になる則ち組合せの最後の一個を残りリストXの中からcodice_72を使って順に選択する。これが第一節の意味である。
第二節と第三節はバックトラックして全てのN-1個の組合せを作る非決定性の再帰的述語のパターンである。ここまでで、N-1個の全組み合わせが組み上がることを前提に、第一節でまだ選択されていない最後の一個をこれまたcodice_72によって全ての可能性を選択して付加している。
実行例
全ての組合せを蒐集するには、codice_5 を用いればよい。述語を非決定性に定義することを基本として、必要な場合に codice_5 によって全解をリストに取得する。これは の代表的なプログラムスタイルである。
実行例
異なるn個のものから異なるr個のものを選ぶ、組合せの総数は公式から、
と では定義される。階乗の定義はこのプログラム例の中で既出である。
codice_5 を使い、codice_387 が解を生成するごとに1をリストに格納することによっても、組合せの総数を求めることができる。
ここでは、格納する値を1としたが、実はこれはアトム、数値、変数、何が来てもよい。
実行例
組合せ同様これも非決定性の述語として作る。組込述語のcodice_388を使うことによって、更に洗練された述語に仕上がる。
codice_388はcodice_72に近い述語だが、ひとつ要素を取った残りが第三引数に単一化されている。そういう非決定性の述語である。
のように順列が取れる。これをリストに取りたい場合は、ここでもcodice_194を使って、
となる。
上記、組込述語codice_388を定義してみる。
codice_393を劇的に使うことによって、極めて宣言的に定義が出来上がる。
codice_388には他に、以下のような再帰的な定義がある。
これもcodice_72やcodice_393に似て、洗練された定義だが、直感的に理解させる力は上記のものに遠く及ばない。
Prologの述語定義は再帰的なものが、宣言的であり、直観に訴えるものだとは必ずしも言えない事例である。
項を複写する。ただ、単なる複写ではない、大事な点がある。変数はそのまま複写することはしない。新たに別の変数を作り出して、それを複写元の変数があった構造上の同じ位置に置く。例から示そう。
注意するべきは変数であり、ここではcodice_397, codice_398と明白に別の変数に置き換わって複写されている。それ以外の関数名 "a","z" アトム"あい"は変化していない。
この述語は高階述語を使用し、かつそれが再帰の中で引数として引き継がれて行く場合に使用される。引数として受け取った高階の述語呼び出し項と基本的に同じ構造だが、変数だけは単一化されることのない項を作り出し、それを引数として渡す時の基礎とする。引数を受け取った時点と引き渡す時点の間で変数が単一化された場合、意図した同型の引き渡し述語とならず、再帰が失敗してしまうことを避けるために使用されることが多い。項複写のプログラムを示す前に、この高階述語の使用例を示してしまう。第一引数 codice_112 に述語が渡されることとする。
codice_112 が単一化されてしまうと、次の再帰呼び出しでは、受け取った codice_112 とは単一化された、つまり、異なったデータを渡してしまうこととなる。Pの引数に変数があった場合そのことが起こる。引き続き変数で渡したいPであるが、これを単一化され具体化された値で渡してしまうことになる。往々にしてこの場合呼び出した再帰の副目標はプログラマの意図に反して偽となる。これを避けるために、この述語の入り口で codice_112 を複写して codice_403 を作ってしまってそれを渡すようにする。もう少し具体的な例を示す。
と失敗する。この原因はリストの第一要素2ではcodice_404が得られるが、その状態で次の再帰の引数として、P乃ちsucc(2,3)が使われてしまうからだ。この問題を回避するのがcodice_405である。
項複写はPが実行される前に行わなければならないことが分るだろう。
さて、本題に戻って項複写の定義は
第一引数に複写前の項、第二引数に複写後の項がくる。項複写/2の第二節 codice_406 と変数が異なっている点が重要である。codice_407、codice_408 は組込述語。codice_407 は項を関数とアリティに分解する。codice_408 は項の引数に値を与える。codice_411 も組込述語で引数が複合項であるかどうか検査する。述語 codice_412 は第一文字が数字であるためシングルクォートで囲われている。
実行例
項複写された変数は元の変数とは別のものなので、逆にこの変数を単一化する必要がある場合は、どこに変数があるか、あるいは何に単一化すればよいかわからないという事態が生じる。その可能性に対処するためには項複写を少し拡張する。ここで、codice_413 の引数の数を増やし、第三引数に複写元の項の変数、第四引数に複写先の項の変数をそれぞれ順序正しくリストに取れるようにする。
これで以下の実行例に見られるように、引数の対応を取ることができる。
実行例
この後、L1の中の変数とL2の中の変数はnth1/3の第一引数を共通にして取得する。
別に変数が取られてしまったことが却って都合の悪い場合は、codice_414のように単一化して対応付ければよい。
プログラム例全体を通して、可能な限り述語名を日本語にしてきた。ここでもソートには整列という語があるが、一般にソートが使われる機会が圧倒的に多い。それでここは挿入ソートとした。与えられたリストを昇順にソートする挿入ソートのプログラムを示す。
空のリストから始めて一要素ずつ取り出し、整列した状態で成長するリストの適切な位置に挿入するという述語である。降順の挿入ソートの場合は codice_415 を
のように比較演算子を反転させればよい。ただ、これでは codice_415 が二通りできてしまうため、
のように明確に述語名を分けて定義するべきである。当然これら述語を副目標として呼び出す定義の述語名も codice_417、codice_418 でなくてはならない。
与えられたリストを昇順にソートする[[クイックソート]]のプログラム例を示す。
codice_419とは軸要素のことである。
軸要素より小さい要素を整列、軸要素より大きい要素も整列。それを軸要素を挟んで結合したものが整列したリストだ。
末尾再帰版（codice_420は上に同じ）
Ys-[], Ys-Ys_1, Ys-[X|Ys_2], Ys_2-Ys_1 に差分リストの関係が見られる。美しい定義であり、上記appendを使うクイックソートに較べて若干速いが、差分リストを分かっていない人に対して、言葉で説明して理解させる事は難しい。codice_421の第二・第三引数の位置が前の版のものと変わっている。一般にPrologでは最終引数を出力とすることが多いが、ここでは差分リストの理解を扶けるために逆転した。
限定節文法によって記述されたもの（codice_420は上に同じ）
実行例。
実行例の最後に示すように、ここでの定義では codice_423 を集合と見なしていない。そのため重複する2番目以降の要素を削除することはしていない。
集合解 codice_424 を期待する場合は、codice_420 の定義を
と文字変更する。すなわち、6行目の「codice_426」を「codice_427」に変更する。なぜならば、すでに同一の値は codice_419 自身として存在するからである。さらにそれだけだと同一要素が出現すると codice_420 は失敗してしまうから、同一要素は無視することの宣言である第四節を加える。組込述語 codice_430 は、この集合解が返ってくる仕様に決められている。
最後に昇順または降順を区別する問題は挿入ソートの部分で述べた方針で、このクイックソートも書き直す必要がある。
木構造整列(ヒープソート)はメモリ上のスタックやヒープ領域に木構造を構築することによってソートを実現する。ここでは、標準入力ファイルから値の列が与えられたものを、引数上(スタック上)に木構造を成長させて、読み込みを終了したら、昇順または降順に整列された値を取り出すことのできる述語codice_431を定義してみる。
このcodice_432は標準入力からの整列に適したものであり、それ故に最初にそれを示したが、リストからの整列も可能である。
と書き換えるだけである。
次に、構築が終った木構造から順に昇順に値を取り出す非決定性の述語codice_433とcodice_434を定義し、それを使って昇順または降順に整列したリストを取り出す。
一般にPrologで引数に構造のあるデータが来ることは歓迎されない。関係データベースに比肩する平明さがこの言語の特長となっているからだ。この木構造整列に見られるグラフは例外的なものである。
[[ハノイの塔]]は最も 向きの課題のひとつとして知られる。ここでは、N枚の円盤を三本の柱のうち、一番左の柱から右の柱に移すケースを示す。円盤は下から上に向かうほど小さくなるように積まれ、常にその状態が維持されなくてはならない。
冒頭、codice_435 を中置演算子、codice_436 を後置演算子として定義している。それを使って codice_437 から codice_438 という項を表現して、それを履歴として残している。
このプログラムは が宣言的であることを顕著に示す好例である。この述語で述べられていることは、三回が一組となって同じパターンが繰り返されるということ。さらに最も下の一枚が順に、この課題では右柱に積まれるのだが、新しい最下層の円盤が右柱の最上位に積まれた時には、それより上の塔は中柱、左柱と交互に完全に積み上がっている。それを、[[ハノイの塔]]述語の本体の二番目の副目標で、どちらの柱を起点として以後の移動を開始するかを、引数の位置を入れ替えることだけによって、表現している。このように全体の骨格と僅かな引数の置き換えだけによって、手続的動作の全てを暗示している。このような表現力に対して「宣言的」と言うのである。
実行例
nクイーン問題も 向き問題の代表のひとつである。チェス盤が8×8であることから、8クイーンとして課題になることが多いが、ここでは盤面の大きさを一般化したnクイーンである。チェスのクイーンは縦横斜め、盤面の自分の位置から盤面の端までが全て利き筋となる駒である。この駒を各行に適宜ひとつずつ配置して、全てのクイーンの利き筋に他のクイーンがいないように、全ての列にクイーン配置せよという問題である。一つの解は列番号のリストで得られる。nクイーンの 定義は随分と工夫され、多くの作品がある。ここでは最も一般的な戦略の解法を示す。駒の利き筋という概念を示すために、可能な限り説明的な をコードを試みている。途中に現れる codice_439 という論理変数に、一つずつ解候補のクイーン位置が成長していく。
これは非決定的な述語である。
上記の定義では、表示幅の制限から引数の途中で改行している部分があるが、引数の区切りである「codice_42」の前後であるならば、これは構わない。6クイーンの場合の実行例を示す。
ここでは4つの解が得られたが、8クイーンだと92解になる。
言語 codice_441 を受理する決定性有限オートマトンと非決定性有限オートマトンのシミュレート。
記号ならびが codice_442 のように codice_47 が対になって最後まで並んでいる場合だけ真となる。[[正規表現]]を正しく理解してプログラムテスト等に挑むためには、このようなコードの理解も必要である。
非決定性有限オートマトンを状態集合で記述したが、これを'言語(ab)*' に展開してしまうことも可能である。
例えば 状態集合_1 が {1,2} である場合には、
と展開できる。複数行になるだけで、決定性有限オートマトンと形式的なの違いはなくなってしまう。決定性有限オートマトンは、このような複数の状態を書かないという約束事によって成立している。
上記、有限オートマトンと同等の 述語としての定義は、
とこれも相当に短いコードとなる。
の[[チューリング完全|チューリング完全性]]は、[[チューリングマシン]]をシミュレートすることで示すことができる。
以下のルールは簡単なチューリングマシンの例である。状態遷移と動作を の節として表現している。
このチューリングマシンは単進符号化（codice_189の並びで符号化）した数値にcodice_189を加える。つまり、任意個のcodice_189のセル上をループし、最後にcodice_189を追加する。
この例から、状態間の関係を で表現することで、任意の計算が状態遷移のシーケンスとして宣言的に表現できることが分かる。
以下のプログラムは[[動的計画法]]を使って2つのリストの最長共通部分列問題を多項式時間で求める。節によるデータベースを部分計算の結果の[[メモ化]]に用いている。
実行例:
Prolog言語で記述された簡単なPrologインタプリタを示す。ただしこのcodice_448はカットが働かない。カットが働くインタプリタはこれよりもずっと複雑になる。
codice_449が中核部であるが、本体がtrueの第一節が停止節になっている。第二節は副目標が連言、第三節は副目標が選言になっている場合の定義である。引数が単項になっている第四節が組込述語の定義、第五節がユーザ定義述語の解釈実行の定義である。
codice_450の中で、codice_451を用いて、入力した文字列を解析して項として組み上げることを免れる定義となっている。
codice_452は述語定義されたものから第一引数の頭部と融合可能の定義節の本体を第二引数に単一化する。
が定義済みだとして、
となる。
codice_449の中でのcodice_452の役割は、第一引数の本体と単一化可能の述語の節を探し、その本体を導出することである。この本体を以て解釈実行を再帰的に呼び出し、本体がなくなる、つまりcodice_452の
第二引数にtrueが導かれることによってcodice_449は成功する。則ち最終的に単位節の頭部単一化に成功した場合である。
組込述語は導出できないので、ただ実行する(call)のみである。この組込述語が成功するとcodice_449は成功する。則ち真となる。ここでは副目標が組込述語であるか検査するcodice_458codice_459を呼んで組込述語かどうか検査している。
このcodice_459はSWI-Prologに存在する組込述語であるが、この機能の組込述語は処理系によって規格的に統一されていない代表格のものである。存在しない場合さえあり、その時は、
のようにcodice_458として、全てユーザ述語定義として列挙して置く必要が生じる。
カットを解釈できるPrologインタプリタの制作の指針を述べる。これを理解するには、 5.9 カットと否定 に対するある程度の知識が必要がである。
カットは実行する節以外には効力が及ばないことが述べられているが、このことは、解釈される対象の節のカットはいわばサインであって、解釈実行を処理する節そのものの中にこそ、カットが存在しなくてはならない、ということを意味する。
一度は真と成り通過し、バックトラックして来て、再びこれを実行しようとすれば、その解釈実行の節が偽になる。そのような工夫はどのようなものか。
ここでは、汎く知られている引数を増やして、これに対応する方法を示す。
解釈実行/2の第二引数はカットが実行された場合にのみ、意味を持つ。
只々、最終節のcodice_462を実行できるように、解釈実行の引数をひとつ増やしたということである。
引数をひとつ増やしたということは、このインタプリタは単一化の量が多くなり、その実行は確実に遅くなる。
多くの処理系は の基本機能以外に、[[制約プログラミング]]や[[並行プログラミング]]のための拡張機能や などの各種言語をライブラリとして含んでいる。
[[Category:プログラミング言語]]
[[Category:論理学]]