Prolog

この項目では、プログラミング言語について説明しています。その他の用法については「プロローグ」をご覧ください。

テンプレート:Infobox プログラミング言語テンプレート:プログラミング言語 Prolog（プロログ）は、非手続き型プログラミング言語の一つ。論理型言語に分類される。名称は、論理を使ったプログラミングを意味するフランス語「programmation en logique」（英語でprogramming in logic）に由来している^[1]^[2]。

概要

1972年ごろにフランスのアラン・カルメラウアーとフィリップ・ルーセルによって考案された^[1]。

成立の事情から、Prolog プログラムは論理式とみなされ、その実行は述語論理によって述語が定義された環境における定理証明に擬して解釈されることが多い。利用者は論理プログラミングの枠組みを、取り分け述語論理を学習することで、この枠組みに極めて忠実なこの言語の基礎的な構造のほとんどを理解できる。その言語仕様はこの枠組み以外には考案者たちも含めてそれ以上の拡張をほとんど行っていないため、他のプログラム言語とは異なり、学習しなくてはならない概念や用語もまた、述語論理のものだけでこと足りる。計算機科学の新しい概念や新しい手法とは無縁である。

述語論理と論理プログラミング

Prolog のプログラムは一階述語論理に基づいてデータ間の関係を示す命題として記述され、処理系がそれらに単一化(ユニフィケーション)と呼ばれるパターンマッチングを施しながら、与えられた命題が成立するか再帰的手続きによって探索している。

プログラムの実行は述語集合が定義された環境の元で、質問することによってなされるが、これは反駁という述語論理的な証明過程を模して、処理系が用意する導出木と呼ばれるグラフをたどって解を得る過程である。 Prolog のもととなるこの演繹手法は導出と呼ばれ、自動定理証明の研究において Prolog 開発以前からよく知られていた。Prolog は、導出において節を頭部が一つの命題からのみなるホーン節に限定したもので、この場合の導出をSLD導出と呼ぶ。ホーン節に限定しているということは、つまり、Prolog は任意の述語をそのまま扱えるわけではない。Prolog が述語の形式をホーン節に限定した理由は、もし頭部に項の連言を認めるならば、導出時の計算量が爆発的に増大して、全ての解を得ることの保証が難しくなることが必至だからである。

述語論理を論理的な背景に持つことによって、Prolog のプログラムはその正しさを確認することが比較的容易である。同時に、プログラマは Prolog でプログラミングすることが何を意味するかを明確に理解した上で、プログラムを書いていくことができる。

非述語論理的な立場

上記は Prolog の一つの解釈である。一方、Prolog というプログラム言語を述語論理という枠にはめないで捉える立場もある。導出、単一化、非決定性、双方向性、リレーショナルデータベースといったこの言語に独特の機能とその表現力、記述力に着目し、そのプログラム言語としての可能性を率直に評価しようとするものだ。

新たに Prolog を学びたいと思う人は、他のプログラム言語を全く知らなくても、ソフトウェア科学的な予備知識や概念に不通であっても、単一化という単純なルールをほとんど唯一の基軸として、パズル的な、あるいはゲーム的な感覚にだけ導かれて、プログラムを簡単に書き進むことができる。さらに、どの言語にも比して平坦で、平明な言語構造を持つ Prolog はラベル名（アトム、関数名、述語名）に適切な意味性を付与することにより、自然言語の領域にも接近したプログラミングが期待できるほとんど唯一の言語でもある。

十分述語論理的な教養を持った上で Prolog を学び、そのプログラムを書くならば、短期間で高度で安定したプログラムを書くことができる。しかし、それを前提としないでも、Prolog は冒険的で、未知の領域に満ちたプログラム言語なのである。

実はこれらの主張は、述語論理的な主張に隠れて、これまであまり強調されたことがなかった。

このような立場や主張が生まれる背景には、Prolog が期待されたほどにはソフトウェア革新の担い手になり得ていない理由が、その後の数理論理学の学問的な評価をもって、プログラム言語としての可能性を十分検証することを放棄して、定理証明といった狭い目的へ封じ込めようとする風潮を生んだことにある、という反省がある。そのことを踏まえて、Prolog が述語論理から成立したことにこだわらず、実在するプログラム言語として自由な視点からこの言語を見直そうとするものである。

記号処理用言語・人工知能言語

Prolog は LISP の資産の多くを継承して間違いなく記号処理用の言語であるが、人工知能言語として分類されることも多い。これは、人工知能の世界では述語論理が古くから理論的な柱の一つとなっているからである。述語論理を基礎とするトップ・ダウン式の問題解決と同じく述語論理を基礎とする Prolog の駆動機構の相性は当然良いため、人工知能研究に広く利用されてきた。特にエキスパートシステムで多用されるプロダクションシステムにおいては、ルールを自然に自ら動的に変更できる能力を持つことと、後ろ向き推論と呼ばれる推論が Prolog の導出過程そのものであることから、その最も主要な記述言語の位置を占めてきた。

宣言型言語

Prolog は一階の述語論理に対応することから論理型言語に分類される汎用言語であるが、その主張の一行一行を独立して論理式とほとんど等価な表現で行うことから、最も代表的な宣言型言語と見なされている。Prolog のプログラム単位である述語の各節の本体に現れる質問単位である副目標数は平均5個以内と極めて少ない。この副目標と各節の頭部に現れる引数の組み合わせによって得られる関係が述語の意味を構成している考えられる。これが宣言型とされるゆえんである。

<頭部> :- <本体>.  % Prologの節は頭部と本体によって構成される。

% 述語定義は複数の節からなる。本体は幾つかの副目標からなる。
% 副目標の全てが真となった時に節の宣言は成立する(節は真となる)。

述語名(引数_1,引数_2) :- <副目標_1>,<副目標_2>.
述語名(引数_1,引数_2) :- <副目標_3>
・・・

Prologの自然な定義では、ここで示した <副目標_1> <副目標_2> が、一つの述語において、高々 <副目標_5> くらいまでに収まる。

単一化

単一化は1960年代の述語論理理論の発展の鍵となった概念であるが、Prolog が述語論理に導かれて機械による自動証明を実現するためのプログラム言語として成立したことから、必然的にこの言語の必須の最も重要な機構となった。単一化は副目標(質問)と対応する定義節の頭部のパターンが完全に一致するか、調べることで、節の選択^[3]を可能にする。基本的な言語仕様の章で詳述するが、Prolog の実行順序等の制御は単一化のからくりを利用してプログラミングされる。

簡単なからくりでかつ極めて強力な単一化であるが実行コストも大きい、すなわち実行速度が遅くなる原因となる。さらに、パターンとして認識することと引き換えに、引数での関数評価は不可能になった。独立して節の本体で式評価を記述しなくてはならないため、数値計算ではやや冗長になる。これらの点は、単一化の強力さとのトレードオフの関係になっている。

動的型付け

型付けは動的型付けに分類できるが、言語仕様の中に型概念は登場しない。上記の単一化、バックトラッキング、と論理変数の束縛においては独特のものがあり、その実行は型推論の実行過程に酷似している。既に Prolog はその引数の引渡し時に単一化という厳密なパターンマッチングを施すことに多大なコストを掛けた。単一化だけでプログラムをコントロールできる言語が Prolog であるといっても過言ではない。この単一化のみによる簡素で強力なプログラムコントロールの足を引っ張ることに成り兼ねない、型付けの強化は、Prolog 言語とその支持者によって受け入れられることはないだろう。

非オブジェクト指向言語

Prolog は言語による思考をモデル化して主語・述語といった意味での文中の述語を特に重視して記述する系である。この一点からも、対象物を中心に記述していくオプジェクト指向とは距離が大きい。述語論理以前にオブジェクトありきとする立場を一般には取らない。

いくつかの処理系では、オブジェクト指向言語としての拡張が行なわれているが、オブジェクトを中心に設計されることは、論理プログラミングを重視して記述される限りほとんどない。分類するならば、非オブジェクト指向言語に分類される。

モジュラープログラミング

Prolog はオブジェクト指向とは疎遠であるが、一方、述部を重視する系であるという点から見ても、モジュラープログラミングとは近い関係にある。Prolog の述語をモジュールとして捉えた場合、多くは再帰的で宣言的であり、情報強度は極めて強く、情報結合度は極めて弱い。引数にはリスト以外の構造体(複合項)が来ることはほとんどなく明解であり、記述単位は数行と極めて短くかつ記述は簡潔である。モジュラープログラミングを突き詰めたものが Prolog だといってもよいように見える。しかし、Prolog をモジュラープログラミングとして評価した場合、疑問符の付くであろう部分もないわけではない。それはPrologの引数の入力・出力の関係が多く場合双方向であり、意味的にも多義性を持つという点である。モジュラープログラミングは「〜を〜する」というような単一機能にまとめることが推奨されたが、この原則に反する。さらにPrologは複数の解を示すことがありうる。この性質を非決定性(後述)というが、実はこのことは定義された述語全体がコルーチンでありうることを意味する。単一の入口点による制御を良しとするモジュラープログラミングの原則にここでも反する。

オンメモリデータベース

後に述べるが Prolog の述語はその構造が頭部と本体と分かれていて、本体はルールを意味するため、全体として、ルールを持ったデータベース、演繹データベースとして捉えることができる。これはPrologプログラム全体がデータベースであるということだから、データベースの表現としては最強のクラスに属する。一方、事実を表す本体のない（強制的に真）頭部のみの定義節による述語はリレーショナルデータベースとその集合論的な性質で一致する。収集した情報を一つの述語に対して多数の頭部のみを持った節の集まりとして定義することにより、オンメモリリレーショナルデータベースを構築することが可能である。しかし、Prologをデータベース管理システムとして捉えた場合、 assert、retract、setof、bagof、findall という組込述語を持つこと以外には、管理機構としての特別の組込述語が用意されている訳ではなく、ディクショナリ管理などのための述語定義をユーザが追加する必要がある。

非決定性と双方向性

関数型言語等、他のプログラミング言語と比較しての Prolog の特長は、上記、一階述語論理に基づくこと、単一化、データベース言語的性格の他に、非決定性と双方向性が挙げられる。

非決定性は、解が唯一とは限らない場合、処理系側から見てひとつの解に決定できない場合、外部からの選択の余地を与える。そういうことが当然可能なこととして述語は定義されていく。インタプリタトップではなく、導出を繰り返すプログラム内部にあっては、処理系とした所を述語と置き換えて考えると、非決定性の述語の解を決定するのは、前方または後方に連接する質問(副目標という)である。ここから引数経由に与えられる情報によって、選択する節が最終的に決定される。ここでも非決定性の述語から見ての解の決定権は外部にあるということになる。

非決定性は導出の過程、取り分けバックトラックアルゴリズムと一体化しており、Prolog プログラムの制御の根幹のひとつである。ただ、非決定性述語実行時に見られる論理変数の束縛→解放→再束縛という遷移、すなわち一度束縛されたものが別のものに再度束縛されるということを好ましくないとする見方もある。

双方向性は、述語が実行された場合の返り値は真または偽だけであり、その代わりとして引数内の変数で値の授受を終始するのだが、このとき、入力として使われた変数が出力に、出力として使われていた変数が入力として使うことのできる述語となることがある。この性質を双方向性という。多くの場合、双方向性を持つ述語はそれ自体多義性を持つ。例えば append という3引数の述語は第一引数と第二引数に具体的なリストが来て呼ばれた時は、リストを結合する意味でよいが、第三引数がリストで第一引数と第二引数が変数の状態で呼ばれた場合その意味は、リストを分解する、がふさわしい。既に存在するリストを、それが結合されて存在したものと考え、それではどのように結合されていったか、あるいは、どのような組み合わせで結合されていったのかを、示していると解釈できる。

このように、双方向性は Prolog の述語自らがリバースエンジニアリング的開示能力を示していると捉えることができる。この性質は、プログラム作成時はもちろん、テスト、デバッグなどの検証の各段階でプログラムコードに対する見通しを向上させる。

Prolog プログラミングの難しさ

ブログラマは引数の単一化、再帰/失敗駆動等のプログラムパターンの選択、非決定性、双方向性といった特長をできる限り生かすことなどに配慮しながら、述語の骨格を決めプログラミングを進める。しかし、これらの特長、性質は複合した場合には相当に複雑であり、制御上相反する部分も多々ある。Prolog では、述語論理を逸脱して計算量/資源量/制御の調整に当たる述語「!」（カット）を導入してこの問題に対処しているが、Prolog プログラミングの難しさはこの調整部分に集中している。　　

歴史

誕生

Prolog の性格上、その歴史には定理の自動証明の研究が大きく関係している。1930年にジャック・エルブランは自動定理証明やPrologのベースとなる数理論理学上の基本定理であるエルブランの定理を発表した。エルブランの論文には Prolog で必須の単一化アルゴリズムもすでに含まれていた^[4]。

1950年代以降、計算機上での定理証明の研究が活発になり、ギルモアのアルゴリズム(1960)やデービス・パトナムのアルゴリズム(1958,1960) 、プラウィツによる定理証明への単一化アルゴリズムの導入(1960)などを経て、1965年のロビンソンによる導出原理や1960年代後半のラブランドによるモデル消去の証明手続きの成果からひとつの結実期を迎えた。その数年後の1971年マルセイユ大学のアラン・カルメラウアーとフィリップ・ルーセルのグループは自動定理証明システムとフランス語の自然言語解析システムとを組み合わせたコンピュータとの自然言語対話システムを作成していた。この際に自然言語解析システムも自動定理証明システムと共通の論理式という枠組みで構築できることに気が付き、論理式をそのままプログラムとして実行できる最初の Prolog を1972年に完成させた^[5]。これは数千年に及ぶ人類の叡智である論理学の成果をプログラム言語に置き換えたものと言えるが、現在の Prolog でプログラムの制御に使われるカットオペレータに相当する機能が最初から導入されるなど^[6]、現在の Prolog と同様、単なる定理証明システムではなくプログラミング言語として設計されたものだった。以下にその当時の Prolog プログラムの一部を示す。論理変数名の最初の文字が "*" で始まるなど、現在の Prolog とはシンタックスが異なる。

READ
  RULES
  +DESC(*X,*Y) -CHILD(*X,*Y);;
  +DESC(*X,*Z) -CHILD(*X,*Y) -DESC(*Y,*Z);;
  +BROTHERSISTER(*X,*Y) -CHILD(*Z,*X) -CHILD(*Z,*Y) -DIF (*X,*Y);;
  AMEN

コワルスキとDEC-10Prolog

彼らグループに理論的な助言を与えていたエジンバラ大学のロバート・コワルスキとデービッド・H・D・ウォレン^[7]は汎用機 DECsystem10 上にマルセイユ大学とはシンタックスが異なる処理系を作り上げた。これは後に DEC-10 Prolog と呼ばれることになるが、ISO 標準規格を含む今日動作する Prolog 処理系はほとんどがこの系統のシンタックスに従っている。コワルスキはその後、帝室ロンドン大学に移り、1979年に集大成ともいえ「Logic for Problem Solving」を著し、その後のこの言語と論理プログラミングの研究に決定的な影響を与えた。

コワルスキの活動と DEC-10 Prolog の存在によって、英国は Prolog 研究の中心地となった。エジンバラ大学のW・F・クロックシン^[8]とC・S・メリシュ^[9]の著わした「Programming in Prolog」は長く Prolog のバイブル本として利用された。エジンバラ大学からSRIインターナショナルに転じたディビッド・ウォレンは1983年 Prolog の仮想マシンコードである Warren's Abstract Machine（WAM）を発表した。この後の Prolog 処理系の実装は、一旦C言語などでこの仮想マシンコードを実装して、その上で Prolog のソースコードをこのマシンコードに変換するコンパイラを用意するという手順を踏むことによって、開発を簡素化し実装上の標準化を図ることが普通になった。日本の新世代コンピュータ技術開発機構の Prolog マシン PSI は1987～1988年頃に開発された PSI2 からこれを採用したし、その後開発された Prolog 処理系の多くはこの方式に従った。

1976年にSRIに留学していた古川康一はカルメラウアーらの Prolog 処理系のリストを見つけ帰国時に電子技術総合研究所に持ち帰った。当時電子技術総合研究所で推論機構研究室長をしていた淵一博はこのリストを解析して Prolog 処理系を走らせ、ルービックキューブを解くプログラムを作成するなど論理プログラミングに対する理解を深めていった。

1978年エジンバラ大学に留学中の中島秀之が「情報処理」誌に紹介記事を寄稿して、Prolog は日本でも広く知られるようになった。

新世代コンピュータ技術開発機構とProlog

1970年代終り頃、日本では通産省の電子技術総合研究所の淵一博を中心とするグループが論理プログラミングの重要性を認識して、日本のコンピュータ技術の基礎技術としてこれを取り上げることを提案する。これが最終的に1980年代の新世代コンピュータ技術開発機構の発足と活動につながった。総額約570億円の国家予算を約束されて1982年に新世代コンピュータ技術開発機構（ICOT）は活動を開始する。Prolog を含む論理型言語はこの研究の核言語と位置づけられ世界的な注目を浴びることとなる。約10年間の研究活動中に Prolog と論理プログラミングの研究は急激に深化した。実際1980年からの20年間に Prolog をメインテーマにした日本語の書籍は約50冊発刊された。ICOT の研究員は積極的に Prolog の啓蒙に努め、講習会、チュートリアル、ワークショップを年に一度ならず開催した。ICOT が主催したロジック・プログラミング・コンファレンスは1983～1985年頃をピークに若い研究者達を刺激した。研究活動前半の期間では論理型言語の実用性を証明するために、Prologマシンが設計され、三菱電機と沖電気によって製作され、ICOT の他大学等研究機関に配布された。この個人用逐次推論マシン PSI の機械語 KL0 は単一化やバックトラックなど Prolog の基本的特徴を完全に備えていた。この KL0 によって、PSI のマイクロコードを制御した。KL0 を基礎として、オペレーティングシステム SIMPOS が設計され、これを記述するために、Prolog にオブジェクト指向プログラミングを取り入れた ESP^[10]が近山隆により設計されて使われた。ESPは多重継承を特徴とする当時としては先鋭のオブジェクト指向言語であったが、後にカプセル化の不備などが指摘されて、今日あまり話題となることはない。しかし、OSを記述するという課題を通じて、論理型言語にオブジェクト指向言語的要素を加えることによって、可読性が高まりプログラム管理がしやすくなることが確認された。その反面、Prolog のみでオペレーティングシステムを完全に記述してみる絶好の機会を逸したことも確かである。

今日、このように ICOT によって持ち上げられた言語 Prolog との印象が強いが、Prolog というプログラミング言語から見ての ICOT の影響は実は限定的だった。淵ら ICOT の主研究テーマは並列論理型言語にあり、研究後半では Prolog そのものからは離れて行くことになる。PSI に使用した電子基盤を利用して並列推論マシン PIM が製作されて、Guarded Horn Clauses（GHC）に基づく並列演算処理を追加した KL1 が設計されて、知識プログラミング全般の研究に利用された。PSI と SIMPOS を使った研究も続けられはしたが、割り当てられた研究員の数は極めて少なかった。

ICOT の活動を総括して、知識プログラミング各課題において準備不足からくる未消化を指摘する向きが強いが、こと Prolog から見ての前半期の活動は、今日語られることも少ないが、極めて充実したものであったといえる。

ICOT の活動盛期の1984年京都大学の学生3名が研究課題として製作した Prolog-KABA がその性能の高さとアセンブラで記述されたことからくる高速性で世界を驚かせた。この処理系は MS-DOS 上で製品化されて Prolog の普及に大きく貢献した。Successful pop や末尾再帰の最適化など高い安定した性能で黎明期のパソコン上のビジネスソフトの基礎言語としての展開も期待されたが、16ビットの整数しか持たず、浮動小数点数も扱えない仕様であったため、この分野への展開は起こらなかった。この点はアセンブラで記述されて簡単には拡張できない点が裏目に出た。結果としてこの仕様の乏しさが、日本のビジネスソフトが知識プログラミングの水準との間に横たわる分水嶺を越えることができなかった原因の一つとなった。

1990年代とISO標準規格

1990年代に入ると制約論理プログラミングが注目され処理系が多数誕生した。これは Prolog から見ると引数の論理変数間の関係（制約）を記述可能に拡張したものである。制約論理型言語は、変数評価に遅延実行などを持ち込むことが必要となるが、連立方程式をはじめとする多くの課題で Prolog より記述が柔軟になる。Prolog の組込述語には引数が変数で渡るとエラーとなるものが多く、このため Prolog プログラマは変数が具体化されるように副目標の記述順序に気を配る必要がある。結果としてプログラミングに逐次性が生じる。制約論理プログラミングにおいては、後に変数が具体化されたときに検査されるための変数の間の制約を記述するだけで、この逐次性の拘束を解決して通過することができる。実はこの制約はPrologから見ても自然な拡張であり、むしろ Prolog の単一化が制約論理プログラミングの制約を「=」のみに限定したものだと解釈することができる。しかし、簡素で逐次的な性格を強く持つ Prolog の処理系に慣れた利用者が、制約論理プログラミングの述語中に更に変数制約の宣言を追加しなくてはならない負担を、受け入れているとは言い難い。制約論理プログラム処理系が Prolog のそれに置き換わる気配は、2013年11月現在においてもない。

ISO の標準化作業は1990年頃から作業委員会が開かれ1995年 ISO標準規格が制定された。ISO標準規格はエジンバラ仕様 DEC-10Prolog を基調に既に一家をなしていた Quintus Prolog など有力ベンダと主としてヨーロッパの学者を主体にこれに日本などの委員が参加して作成された。この規格は現在 Prolog 処理系の製作者に指針を与え、大きな逸脱を心理的に妨げる役割を果たしているが、個々の組込述語の仕様にはベンダの意向が強く反映したものもあるが、全体としては最初に述べた論理学的立場を尊重して保守的で小さな仕様となっている。そのため多くの Prolog 処理系はこの規格の述語を搭載しつつ、独自の拡張部分を修正削除することはしていない。結果として個々の処理系の互換性の乏しさは残り、それは Prolog の弱点として認識されている。

JIS規格も一旦はJIS X 3013:2001として、"標題プログラム言語Ｐｒｏｌｏｇ―第１部：基本部"が要約ＪＩＳとして発行されたが、2012年1月に周知としての目的は終了したとして廃止された。

人工知能ブームとProlog

日本において、ICOT の活動時期から1990年代前半に掛けては、いわゆる人工知能ブームの時期であり、人工知能研究への期待はこの時期再び異様に高まった。LISP マシンによる医療情報エキスパートシステムでの成果は、人工知能の研究の成果の一部は情報処理に於いても利用可能なのではないかとの夢を抱かせた。このような評価の中で Prolog は人工知能のアセンブリ言語的な位置づけを期待された。知識情報処理はこの水準の言語を基礎にその上側に築かれるべきだとの意味である。手っ取り早く利用可能な人工知能技術としてエキスパートシステムが選別され、これを支えるナレッジエンジニアの存在とそれを養成するための教育が必要とされた。Prolog はその中心に存在した。日本も例外ではないが、日本以外の国では特に、Prolog の名著は1990年代前半に刊行されている。これは、ICOT の活動とは若干のタイムラグがあるが、この時期社会的に人工知能向き言語としての Prolog に大きな期待が寄せられていたことの証しである。エキスパートシステムはビジネス分野において広範囲に応用可能な基礎技術であったが、このような低水準な分野への適用はあまり試みられず、この分野からの Prolog 言語への要請はほとんど見られないまま終った。

機械翻訳などの自然言語処理もまた人工知能の一翼を担う分野であるが、歴史的経緯から人工知能ブーム以前から、この言語に最も期待が掛けられた分野であった。しかし、左再帰問題の回避でトップダウン解析の明解さをいきなり殺がれた。さらに句構造文法への適用においては、Prolog が得意とする、句構造に分解して意味に相当するグラフを形成することの他に、極めて膨大な辞書を構造体として定義する必要が展望された。この辞書作成は Prolog とは直接関係しないタスクであることから、次第に Prolog は句構造文法によるアプローチの前線から後退してしまった。統計的言語処理のアプローチでは、単一化等に多くの計算量を費やす Prolog は大量データを扱うのに不向きとされて、利用されることはほとんどない。自然言語処理のテキストの多くが Prolog を用いて解説されているにも関わらず、期待が大きかった割に実務的には、表面に現れている成果はIBM社のワトソン程度にとどまり、自然言語処理はむしろ Prolog 評価の足を引っ張る傾向にさえある。

ICOT以後の日本における衰退

日本においては、ICOT 解散後数年を経て、論理プログラミングと Prolog は急激に下火となる。先にあげたコワルスキの成果があまりにも完成されたものでその研究成果の範囲を越えることが難しかったこと、歴史的にプログラム言語でありながら論理学からの逸脱を厳しく制限され、自由なアイデアによるプログラミング言語としての発展・展開が困難に見えたことも研究者・技術者を離れさせた。そして、人工知能ブームもまた去って行った。企業等で続けられた研究開発も発表される機会がProlog産業応用シンポジウム（INAP）などに限定され、人々の目に Prolog の成果が触れることは極端に少なくなった。ICOT の多大な研究成果がネット上に閲覧可能な状態で置かれたが、Prolog 言語の処理系はインターネット時代の技術・流れに乗れず、初心者・初学者が利用するためのネット上での情報も他の有力言語に比べて少なく、新しい利用者を惹きつけることができなかった。パソコンのオペレーティングシステムとして Microsoft Windows が一般に普及し始めると、初心者教育にウィンドウの部品の展開を題材とするのに適したオブジェクト指向言語に人気が集中し、Prolog は動作の遅い外れた言語のイメージを持たれるようになる。さらに21世紀に入ると Prolog がクラス概念を持たないため、マイクロソフト社による .NET アーキテクチュアの共通言語基盤（CLR）の対象言語から外され、この傾向に拍車をかけた。ついには枯れた言語というニュアンスを含んでではあるが、「化石言語」と揶揄されるまでに至ったのである。

今日

勢いは失ったものの、Prolog は各教育機関で主として論理学の教材として利用され続け、今日まで数万人の人が Prolog の講座を受講している。実務的に利用される機会が少ないにも関わらず、その素養を持つ人が大量に存在するという特異な位置にあるプログラム言語となっている。

2011年夏、ブルース・A・テイト^[11]著『7つの言語 7つの世界』が出版され、その7つの言語の一つとして Prolog が紹介されたことから、多くの人々の関心を呼び起こし、この言語は突然に息を吹き返した。ダニエル・ジャクソン^[12]著『抽象によるソフトウェア設計』も翻訳されて述語論理に基礎を持つ形式記述言語 alloy が注目されるなど、Prolog に極めて親近した領域での議論がようやく活発になった。

2012年に入り、イワン・ブラトコ^[13]著「Prolog Programming for Artificial Intelligence」の第四版が11年ぶりに刊行されて、人々に Prolog は今でも活火山的な存在であることを印象付けた。また、世界的に知られる自動プログラム作成ツールシステム GeneXus が Prolog によって書かれてからそれを他の利用言語に変換されて製品化されていることや、IBM 社のワトソンの言語解析部分を現在も Prolog が担っていることなどが次々と喧伝されて、応用面でも現役言語であることが改めて認識されつつある。さらに世界的な関数型言語への急激な関心の高まりによって、関数型言語と類縁性の高い論理型言語の盟主であり、人気関数型言語 Erlang の原像でもある Prolog への関心は再び強まっている。

基本的な言語仕様

プログラムは、ホーン節、もしくは単に節と呼ばれる形式の項を並べたものである。

節は、頭部と本体部からなり、

頭部.

または

頭部 :- 本体部.

の二形式があり得る。

これは、それぞれ、頭部. の形式が「AはBである」、頭部 :- 本体部. の形式が「BならばCである」という命題の形式に対応する。節も項であり、項は関数子といくつかの引数からなる。節の関数子は ':-' であり、頭部と本体部はその引数である。頭部. の形式は実は、頭部 :- true. が省略されたものと見なされ、やはり ':-' を関数子として二引数の項である。

頭部は項が連接することはできない(ホーン節)が、本体部は項が連接する、そういう項であり得る。

頭部 :- 副目標₁,副目標₂, ... 副目標_n.

副目標₁,副目標₂, ... 副目標_n　は、これ全体を目標という。目標は副目標₁...副目標_nの連言である。

ここで 目標 = ( 副目標₁,副目標₂, ... 副目標_n ) と置けば、

頭部 :- 目標.

であり、やはりこの節の形式も、関数子 ':-' の二引数の項であることが分かる。

複数の副目標はカンマで区切られているが、このカンマは論理積を意味する。

節は、その頭部の形式、すなわち関数子とその引数の数が同一の形式を持つ述語と呼ばれる単位で管理される。

プログラムは項の集合であり、節の集合であると同時に、述語の集合でもある。

Prologはこの項、節、述語だけでその形式を表現できる点で、他のプログラム言語とは著しく異なる。これはPrologの理論的な背景が論理学にあり、この中の概念のみで構成されて、発展してきたからである。

このような節の集合をあらかじめ用意してそれを定義した上で、ある命題が真であるかどうか問うことを質問という。節の集合、つまり述語の集合をあらかじめ用意する方法については、後出の"Prologプログラミング"で述べる。

Prologの処理系は、人間の入力した質問に対して、頭部が形式的に一致する節があるか調べ、あった場合はその本体部に記述されている命題と一致する節があるか再帰的に調べる。

ここでは定義されたもの(処理系があらかじめ用意した組込述語も含めて)だけが、真になり、定義されていないものは必ず偽となる(閉世界仮説)。

具体的な例を見よう。

「ソクラテスは人間である」「人間は死ぬ」を Prolog で記述すると以下のようになる。ここで X は変数である。

人間(ソクラテス).

死ぬ(X) :- 人間(X).

システムに対して以下のように入力すると、true が返される。

?- 死ぬ(ソクラテス).

これは「ソクラテスは死ぬか」と質問したことに対して、システムが内部で推論を行なって、既知の知識から答えを出したものである。

それではここでの既知の知識とはなんであろうか。それは、

人間(ソクラテス).

死ぬ(X) :- 人間(X).

であり、内部で行っている推論とは、?- 死ぬ(ソクラテス). から死ぬ(X) :- 人間(X). により導出されて、

?- 人間(ソクラテス).
true

が、確認される過程である。

今度は以下のように入力してみる。これは、「死ぬのは誰か」と質問したことと同じになる。この場合もシステムが内部で推論を行なって、死ぬ（X）を満たすXを表示する。

?- 死ぬ(X).
X = ソクラテス

他のプログラム言語に比べると質問を基本的骨格としている点でユニークであるが、更に、Prolog は複数の計算結果があり得るという点でも極めてユニークなプログラム言語である。先のプログラム例を拡張して

人間(ソクラテス).
人間(アリストテレス).

死ぬ(X) :- 人間(X).

とした場合、死ぬ（X）を満たすXは複数（ソクラテスとアリストテレス）がありうる。

述語人間　に複数の節を設けて、その引数にソクラテス、アリストテレスと列記して行くだけで、質問に対して複数の解を処理系が列挙するようになる。

他の言語でこういう機能を実現する時に見られるような、手続き的なループや情報を管理する配列の添字管理のようなものは全く現れない。

多くのProlog 処理系ではこのような複数解が存在する時に新たな解を得る場合は

?- 死ぬ(X).
X = ソクラテス ;
X = アリストテレス

と ";"（セミコロン）記号を用いて他の解を得る。";"はこの解は真ではない、という質問者の意思表示である。

ここではインタプリタのトップからの質問、すなわち対話環境にあるから、X = アリストテレスが処理系からの質問者に対する応答、質問となっている。

質問者は「この解は真ではない」と否定することができる一方、呈示された解(ソクラテスまたはアリストテレス)を真と決定することもできる。このように処理系から見て外部からの介入によって真を得ることを非決定性という。

この非決定性がコンピュータ言語としてのProlog の際立った特徴の一つである。

もうすこし具体的なPrologプログラムの例を以下に示す。「%」から行末までは注釈である。

% member(X,Y)はXがリストYの要素として含まれているときに成功する。
% そうでないときは失敗する。

member(X, [X|_]). % Xがリストの先頭要素と同じ場合
member(X, [_|Y]) :- member(X, Y). % それ以外の場合

member(X,Y) は要素XがリストYのメンバーであるかを調べるプログラムであると同時に、「要素XがリストYのメンバーである」という関係も宣言的に表している。実行例を以下に示す。

要素XがリストYのメンバーであれば成功する。

?- member(サザエ, [波平,サザエ,マスオ]).
true.

要素XがリストYのメンバーでなければ失敗する。

?- member(サザエ, [ワカメ,マスオ,タラオ]).
false.

Xの部分を変数のままにすると、リストYのメンバーである要素が結果として返る。すなわち、ジェネレータとして働く。

?- member(X, [ワカメ,マスオ,タラオ]).
X = ワカメ ;
X = マスオ ;
X = タラオ

二つのリストの共通メンバーを求めるには単純に","で区切って並べればよい。この","はANDの意味を持つ。

?- member(X, [波平,サザエ,マスオ]), member(X, [ワカメ,マスオ,タラオ]).
X = マスオ

要素Xを指定しリストYを変数のままにすると、それらがメンバーであるリストが結果として返る。

?- member(波平, Y), member(サザエ, Y), member(マスオ, Y).
Y = [波平,サザエ,マスオ|_G001]

上の"_G001"はProlog処理系が作成した仮の変数で、リストの後半が不定であることを示す。

データタイプ

Prologが扱うデータは項（テンプレート:Lang-en-short）と呼ばれる。項は定数、変数、複合項のいずれかである。

定数はアトム、数値のいずれか。
- アトムは任意の名前を表す記号。変数と区別するため、英大文字か下線「_」で始まる場合はシングルクォートで囲む。例： atom、 プロログ、 'This is atom'
- 数値は整数や浮動小数点など。例： 1024、3.1415、0xffff
変数は英大文字か下線「_」で始まる記号で表す。通常の変数と無名変数がある。変数は任意の項と単一化(ユニフィケーション)できる。
- 通常の変数は無名変数以外の変数。例： X 、 _リスト
- 無名変数は下線「_」のみから成る変数で、その出現ごとに異なった変数とみなす。1つの節で1回しか使われず内容を意識する必要のない変数に用いる。
複合項は、「人間(ソクラテス)」のように、アトムの後にいくつかの引数をカッコで囲んで並べたもの。任意の項を引数として指定できる。
- 通常の複合項 例： person(磯野波平,54) 、 f(g(x),125)) 、 '.'(X,L)
- リスト 特別な複合項についての記述を参照。例： [namihei,sazae,masuo] 、 [member, X, [1,2,3]]
- 前置、中置、または後置記法された複合項 特別な複合項についての記述を参照。例： X+Y*3 、 死ぬ(X):-人間(X)

複合項でのアトム部分を関数子（テンプレート:Lang-en-short）、引数の数をアリティ（テンプレート:Lang-en-short）と呼ぶ。アトムはアリティが0個の複合項とみなすこともできる。アリティが異なれば同じ関数子でも別のものとして扱われる。

前置・中置・後置記法された複合項は、複合項の関数子を前置・中置・後置記法の演算子として定義したものだが、これは表記法の問題でしかない。Prologではユーザが任意の演算子を定義できる。いくつかの演算子が事前に定義されており、例えば、算術式での"+","-","*","/"などが代表である。 X+Y*3 は実は複合項 '+'(X,'*'(Y,3)) として処理系に解釈され、そのような構造体を表現するものとして実装される。また、 死ぬ(X):-人間(X) は ':-'(死ぬ(X),人間(X)) に等しい。このことから、Prologのプログラムは複数の項、すなわち述語 :- の集合、として記述されていると考えることができるため、プログラムをデータとしてProlog自身で処理することは比較的容易にできる。

ユーザが演算子を定義するには、組込述語op/3を使う。下記のようにプログラム中でop/3の実行して宣言を要求することもできるし、インタプリタのトップから ?- op(600,xfx,は). のように実行して直接宣言することもできる。opの第一引数は項の結合強度を、第二引数はオペレータの型を表す。演算子は第三引数で指定する。

死ぬ(X) :- 人間(X).を

:- op(600,xfx,は).
:- op(600,xfx,が).

ソクラテス は 人間.

X が Y :- X は Y.

X は 死ぬ :- X が 人間.

と定義すると、述語はは/2,が/2 に変わってしまって、全く別の定義だと言えるが、我々には意味的に同様のものと理解できる。これは中置記法の例であるが、以下のように、前置記法の"必ず"、後置記法の"ならば" を加えて意味的に補強することも可能だろう。( _ :- _ の中にその義を含むから、本来その必要はないが)

:- op(600,xfx,は).
:- op(600,xfx,が).
:- op(500,fx,必ず).
:- op(700,xf,ならば).

X は 必ず 死ぬ :- X が 人間 ならば.

Prologは動的型付き言語であり、型を宣言することはしない。論理変数は関数または述語の引数の中にしか現れず、この変数の型を指定する(例えば integer:X のような)記述はできない。

質問がなされ述語が呼び出された時に処理系は単一化のルールによって論理変数を可能であれば束縛するが、その際、型を検査することはしない。その引数が例えば、整数であるか、あるいは浮動小数点数に束縛されているかは、組込述語 integer/1 float/1 でそれを随時質問することによって検査することができるのみである。

複合項の中で特別な扱いを受けているものとしてリストがあり、LISP以来の記号処理プログラミングの伝統に則りPrologでも極めて多用される。実際のところ、Prologのデータ構造は単位節定義とリスト以外にはないと言っても言い過ぎではない。

リスト'はいくつかの項を順に並べたもので、その先頭要素を取り出せば、残りはまたリストであるというように再帰的である。例えば [a,b,5] のように、要素となる項を「,」で区切り「[」と「]」で囲った形で表現する。要素のないリストは [] と表記し、空リスト、あるいは nil と呼ぶ。リストは読みやすいように特別な表記法を与えられた複合項であるが、実は一般の複合項と同様の構造で実現されている。リストは関数子名が'.' と決められていて、以下の例のように実現されたアリティが2の複合項である。例： [a,b] は複合項 '.'(a, '.'(b, [])) と等価である。

?- [a,b] = '.'(a, '.'(b, [])).
true.

Prologのリストの表記として、要素を"|"で区切る方法がある。この記法があるためにPrologのリスト処理は視覚的で読みやすい。先頭からいくつかの要素の後に"|"が来て、その後にはリストか[]が来る。例： [a,b,c,5,6] は、先頭の要素 a,bと残りの要素 [c,5,6] をつなげた [a,b|[c,5,6]] と等価。ただし、[[a,b]|[c,5,6]]ではない。Prologの複雑なリスト処理をそれでも宣言的と見なすことができるのは、専らこの記法あってのことである。

?- [a,b,c,5,6] = [a,b|[c,5,6]].
true.

?- [a,b,c,5,6] = [[a,b]|[c,5,6]].
false.

この記法はPrologのプログラムではリストを先頭要素と残りリストに分解する場合に多用される。[1,2,3]=[H|R]の場合、Hは単一の項(複合項であることも含めて)を表すパターンだから、H=1,R=[2,3] に分解される。下方に示されるプログラム例のリスト要素の加算,append,組合せ,クイックソートなどに多数の事例がある。

member(H,[H|T]).
member(H,[_|T]) :- member(H,T).

append([],L,L).
append([H|X],L2,[H|Z]) :- append(T,L2,Z).

?-  member(H,[1,2,3]).
H = 1;
H = 2;
H = 3 .

Prologを代表する述語 member/2 の[H|T]と[_|T] と append/3の[H|X]と[H|Z] の所にこの記法が使われている。

?- member(H,[1,2,3]). にあっては、第一番目の定義節から

[1,2,3] が [1|[2,3]] に分解できて H = 1, T = [2,3] となるから、最初の解である

H = 1

が表示されるのである。

形式記述言語の多くがそうであるように、Prologはその制御の大半が再帰処理によっている。リストは再帰的な構造データの中でも最も簡素で扱いやすいものであり、制御構造とデータ構造の一致という点からもリストが多用される十分な理由がある。複合項(リストも実はそれに属するが)も再帰的構造データではあるが、生成や置換などの際の扱いが複雑になるため、グラフやオートマトンなどの定義/表示以外にはあまり使われない。

Prologではリストの内包表記はできない。setof や findall の表現が意味的にそれに近いが、ここでの表記をリストを表す項として、遅延評価して持ち回ることはできない。

Prologには集合を表す特別な表現がなく、リストでこれを代用するのが普通である。この問題については、Prologプログラミングの章で詳述する。

Prologプログラミング

質問

Prologの実行は述語を定義された処理系に対してユーザが質問することによってなされる。質問とは、

?- 親子(ふね,タラオ).

のようなものである。ここでの質問は「ふねはタラオの親か」という意味だ。「ふねとタラオは親子関係である」という読み方もある。

このような質問に処理系が答えることができるためにはその知識が必要である。Prologではこの知識を述語という形式で与える。そのことを述語を定義するという。

定義された述語には一般に処理系によって最低限必要なものとしてユーザに対してあらかじめ用意された組込述語(ユーザは定義しなくてもよい)と、ユーザが自ら定義したユーザ定義述語の二種類がある。ユーザは自ら定義した述語群をファイルに保存して、そのファイルを組込述語である consult/1 述語によって処理系に読み込ませる。

サザエさんの家系図に関する述語群が

親子(波平,サザエ).
親子(ふね,サザエ).
親子(波平,カツオ).
親子(ふね,カツオ).
親子(波平,ワカメ).
親子(ふね,ワカメ).
親子(マスオ,タラオ).
親子(サザエ,タラオ).
 
夫婦(波平,ふね).
夫婦(マスオ,サザエ).

member(X,[X|_]).
member(X,[_|R]) :-
    member(X,R).

上記のように、エディタなどで書かれて、ファイル'sazaesan.pl'に存在するとして、

?- consult('sazaesan.pl').
true.

を実行することによって、サザエさんの家系図に関する述語群がユーザから参照できるようになる。

?-

はプロンプトと呼ばれ、質問を受け付ける準備ができていることを示す。プログラムを実行するのには、一般にProlog処理系の起動後、最初のプロンプトが表示されてからユーザ自身で質問(目標)という形でプログラムを実行する。

実務的なプログラムではこの質問によって述語定義の融合、頭部の単一化、本体部の導出の長い連鎖となり、最終的にその質問が真か偽の結果を残して終了する。

これが普通の使い方だが、処理系の起動時にコマンド引数などで最初に実行する質問を引き渡して、起動後停止することなく、質問が実行される場合もある。

ここで listing という質問を与えてみる。この組込述語は現在実行可能な状態にある述語すべてのソースコードを表示する。

?- listing.

親子(波平,サザエ).
親子(ふね,サザエ).
親子(波平,カツオ).
親子(ふね,カツオ).
親子(波平,ワカメ).
親子(ふね,ワカメ).
親子(マスオ,タラオ).
親子(サザエ,タラオ).
 
夫婦(波平,ふね).
夫婦(マスオ,サザエ).

member(X,[X|_]).
member(X,[_|R]) :-
    member(X,R).

このように定義済みであることが分かった。これが先の ?- consult('sazaesan.pl'). の効果である。

最初の親子(波平,サザエ). から夫婦(マスオ,サザエ). までが事実であり、形式的には本体がなく、単位節と呼ばれる。その下の member は二番目の節に再帰的に本体があり、これはルールと呼ばれる。

ルール memberを使った質問をしてみる。

?- member(サザエ, [波平,サザエ,マスオ]).
true.

となる。サザエは集合{波平サザエマスオ} の要素であるかという質問に真と答えている。

さらに簡単な質問をしてみる。単に事実を問うものだ。

?- 親子(波平,サザエ).
true.

?- 親子(ふね,X).
X = サザエ;
X = カツオ;
X = ワカメ .

?-

この質問で第二引数に X 乃ち論理変数が使われた。処理系はこのXに適切な値が入ることで、この質問を真となって終わらせようとする。

X にカツオが入った時、

?- 親子(ふね,カツオ).
true.

で真となるし、ワカメが入った時、

?- 親子(ふね,ワカメ).
true.

で真となる。

この二つの質問を論理変数 X を順に束縛することで満たしているのが上の ?- 親子(ふね,X). での実行結果である。

質問の詳しい説明は後のプログラム例「家系図」以下にある。

プログラムの起動と質問の自動実行

次に質問することなしに、プログラムを実行する方法を示す。

consultされるファイルの途中に特別な述語 ':-' を指定して、自動で質問が実行できるようになっている処理系が多い。ファイル'sazaesan.pl'の第一行目に

:- write('%%% サザエさん家系図の読み込み %%%\n').

親子(波平,サザエ).
親子(ふね,サザエ).
親子(波平,カツオ).
親子(ふね,カツオ).
親子(波平,ワカメ).
親子(ふね,ワカメ).
親子(マスオ,タラオ).
親子(サザエ,タラオ).
 
夫婦(波平,ふね).
夫婦(マスオ,サザエ).

member(X,[X|_]).
member(X,[_|R]) :-
    member(X,R).

が書かれているとすれば、

?- consult('sazaesan.pl').

を実行した直後に

%%% サザエさん家系図の読み込み %%%

と表示される。'sazaesa.pl'の第一行が読み込まれ、処理系が :- から始まる特殊な節を見つけると、

?- write('%%% サザエさん家系図の読み込み %%%\n').

という質問をユーザからの入力なしに実行する。

この機能を利用して、起動時に -f オプションなどで初期読み込み述語ファイル名が指定できる作りになっている処理系では、

# prolog -f sazaesan.pl

この ':-' 述語をファイル内の適宜な場所に記述することによって、質問の自動起動が可能となる。

しかしながら質問で変数束縛の状態表示を期待している場合は、一旦停止するわけではないから、質問する場合のようにはうまくいかない。";"や改行待ちとなる非決定性の制御にも移行しない。このような変数束縛の表示はwriteのような出力述語を続けて記述してユーザが表示させる必要があるだろう。

自動実行を理解しやすくするために、'sazaesa.pl'に少し :- 節を追加してみる。

:- write('%%% サザエさん家系図の読み込み %%%\n').

親子(波平,サザエ).
親子(ふね,サザエ).
親子(波平,カツオ).
親子(ふね,カツオ).
親子(波平,ワカメ).
親子(ふね,ワカメ).
親子(マスオ,タラオ).
親子(サザエ,タラオ).
 
夫婦(波平,ふね).
夫婦(マスオ,サザエ).

member(X,[X|_]).
member(X,[_|R]) :-
    member(X,R).

:- write('%%% 波平の子供は %%%\n').
:- member(波平,X),writef('%t\n',[X]),fail;true.
:- wrte('%%% 終了します %%%\n').
:- halt.

組込述語 writef/2 や fail;true 制御についてここでは詳しくは述べないが、

最後に処理系を終了させる組込述語 halt. を実行させることにより、

# prolog -f temp1.pro
% library(swi_hooks) compiled into pce_swi_hooks 0.00 sec, 2,224 bytes
%%% サザエさん家系図の読み込み %%%
%%% 波平の子供は %%%
サザエ
カツオ
ワカメ
%%% 終了します %%%
#

のような、バッチ処理プログラムとして実行することができる。

組込述語 consult/1 の事例を示したが、Prologの処理系は共通の組込述語群とその処理系独自の組込述語群を持っており、後者が統一されない状態であることは歴史の中で触れた。ユーザは各処理系のマニュアルを注意深く読む必要がある。

述語

Prologでプログラムを記述する単位は述語（テンプレート:Lang-en-short）で、他の言語での関数やサブルーチンに相当する。つまり、Prologプログラムは述語の集まりで、述語はあるまとまった機能を表現している。述語は1つ以上の節（テンプレート:Lang-en-short）と呼ばれる項からできている。節は以下の形をしている。

頭部 :- 副目標₁, ..., 副目標_n.

あるいは、

頭部.

1つの述語に属する節は、同じ述語名(関数子名)と引数の数(アリティ)を持つ頭部からできている。述語名とアリティが異なれば別の述語とみなすため、述語を指定するときは"述語名/アリティ"と表記されることもある (例： member/2) 。 1つの述語は成功、あるいは失敗のいずれかの結果を返す。副目標₁～副目標_nの間の "," はANDを意味する演算子であり、1つの節が成功するのは本体部がすべて成功した場合である。本体部の実行は左から右に行われる。頭部のみの節は 頭部 :- true. と同じ意味である。

1つの述語が複数の節からなる場合、上から順に実行され、どれかが成功したら述語自体は成功する。つまり同じ述語内の節の関係はORの関係となる。節同士はOR関係であり、それぞれ情報の共有という観点からは完全に独立している。一つの節の中の副目標から別の節中の情報にアクセスするためには、新たにこの述語を目標(質問)として呼び出す必要があり、この場合、制御や変数束縛等は完全に初期状態での実行となる。

一度trueになった節であったとしても、バックトラックして、それより下の節に制御が移った場合は、制御の移った節からバックトラックした(すなわち偽となった)節での変数束縛を利用することはできない。

宣言的意味と手続き的意味

Prologの基本的なアイデアは、ホーン節をプログラムと見なして実行する、ということであるため、純粋なPrologのプログラムは手続き的にもホーン節に従って宣言的にも解釈ができる。1つの節の解釈は以下のようになる。

"副目標₁"かつ ...、かつ"副目標_n"が真であれば、"頭部"は真である (宣言的意味)

"頭部"であることを示すには、"副目標₁"かつ...、かつ"副目標_n"を示す (手続き的意味)

手続き的に見ると、"副目標₁"～"副目標_n"がすべて成功する場合、節は本体部を順番に実行する関数やサブルーチンのように見なせ、再帰呼び出し可能な手続き型/関数型言語と動きはさほど違わない。他の言語との大きな違いは、本体部のいずれかが失敗した場合、最後に選択した節にバックトラックし次の節から再度実行を続けることである。

Prologの動作をプログラムが指定した条件での解の探索として見ると、深さ優先の解探索ととらえることができる。

論理変数

C言語など通常のプログラミング言語の変数は値の格納場所であって、計算が進むに従って内容が変化する。Prolog などの論理型言語での変数は数学的な変数に近いもので、何らかの値につけた名前である。値は決まっているか決まっていないか(代入されているか代入されていないか)のいずれかで、一度決まってしまえば値が他の値で置き換わることはない。値が変わるのはバックトラックにより代入が解かれた後に再度値が決まった(代入された)場合のみである。この変数は他のプログラム言語のそれのようにプログラム中に宣言することはできず、述語或いは述語呼び出しの引数の位置にのみ現れる。

通常のプログラミング言語の変数と区別するために論理変数と呼ばれることもある。論理変数が述語または質問の引数の位置にのみ現れるという意味を理解しやすくするために以下の例を示す。

Y=Y,Y=Z,Z=3.のX,Y,Zは一見プログラムの中に宣言しているように見えるが、全て組込述語 =/2 の引数である。Prologにおいて = とは単一化を施すという意味である。

変数の値の変化の例：

?- X=Y, Y=Z, Z=3.
X = 3,
Y = 3,
Z = 3
true.

?- W=5, W=3.
false.

論理変数は、格納場所ではなく、質問がなされる度に定義節を写して生成される一時的な論理域に存在するもので、プログラムの他の箇所からその値が参照されることはあり得ない。

member(X,[X|_]).
member(X,[_|R]) :-
        member(X,R).

第一節にXが二箇所、第二節にはXとRが二箇所現れている。それぞれの変数が最終的に同一のものに代入されることの宣言である。

また上記の定義では第一節と第二節にXという論理変数が現れているが、この二つの論理変数名が同一であることには意味がない。第一節のXに値が代入されて解が得られた後、バックトラックされて第二節に移行したから値が解放されて、Xは代入されていないのではなくて、第二節のXは第一節のXとは元々無関係だから、代入されていないことになる。

論理変数の名前が同一であることが意味を持つのは、質問されて、述語のひとつの定義節と融合された時、その融合された定義節側の頭部、本体の中に、質問としての副目標の引数とは無関係に、同名の論理変数があるかないかだけである。融合の際の頭部の単一化でさえ、論理変数同士の単一化であっても、変数名が同じあるか否かは問われない。この点については、次の節の単一化を参照。

ここで起こっている質問としての副目標(または目標)と定義節との融合は、述語定義のコードからは離れて、対応する節の姿が写されて実行されるのであって、その実行と述語定義のコードは直接的な関係を持たない。

したがって、この質問、導出過程で論理変数が束縛されても、述語定義の他の定義節の論理変数に影響を及ぼしようがないのである。

単一化

Prolog の動作の基本は単一化と後に述べるバックトラックである。

単一化(ユニフィケーション)は、述語呼び出し時に使用される、呼び出し側、呼び出される側双方向の強力なパターンマッチングだが、そのルールは簡単である。

すなわち、二つの項の単一化において、

2項がそれぞれ変数の場合は、以後この二つの変数は同一のものと看做される。同時に単一化は成功する。
2項の一方が変数であり、他方が変数以外の項である場合は、変数はこの変数以外の項と同一のものとなる。単一化は成功する。
2項がそれぞれアトムの場合は、二つのアトムが完全に一致した場合に単一化は成功する。
2項がそれぞれ複合項の場合は、二つの複合項の関数名とそれぞれの引数の形式が一致した上で、全ての引数要素に対して、再帰的に単一化が成功する場合のみ、単一化は成功する。

以上挙げた以外の場合は、単一化は全て失敗する。したがって、アトムと複合項の単一化は常に失敗する。述語呼び出し時の候補節では、一つでも頭部にある引数の単一化に失敗すると、その候補節は選択されない。

1 と 2 は意味的に統合可能であり、単一化ルールを三つとすることもある。Wikipediaのユニフィケーションの説明ではそうなっている。しかし、変数の単一化は値が代入されないという意味で特殊であり、Prologでは同一性のみ主張できる変数の制約そのものであり、Prologの最も独自性の強い部分であることから、ここでは独立したルールとして扱う。

単一化によって論理変数がある値に決まることを、代入という。一般のプログラム言語の代入と表現は同じであるが、Prologの代入はある値をその論理変数を通じて覗くことができる。あるいは、この値が参照(利用)可能な状態になるといったニュアンスに近い。なぜなら、この代入がバックトラックによって「解かれる」と論理変数は再び何も参照できなくなる。

単一化は処理系が述語を質問として呼び出す(目標が実行される)たびに、暗にPrologシステム内でに実行されつづけているのだが、利用者が明示的に二項の単一化を指定することもできる。それが先の論理変数の事例に現れた = である。述語 = は左右に二つの引数を持ち、この二つの項の単一化を試みる述語である。

ここで、明示的な二項の単一化(=/2)を組み合わせて単一化の説明を試みよう。

?- X = Y,    % X と Y が同値と制約された。
   Y = 3.    % Y から 3 が参照可能になった。同値制約されている X もまた、3 が参照可能になった。

X = 3,
Y = 3.
?-

単一化は極めて強力なパターンマッチングではあるが、実行コストも多大である。Prolog処理系の実行速度が他のプログラム言語のそれに比べて遅いことの主要な原因は単一化にある。

通常のプログラミング言語との比較で考えると、Prologの単一化は以下の機能を含んでいる。

変数への値のアサイン
変数の同値制約(変数同士の単一化)
パラメータの受け渡し
リストの作成/リストの分解/リスト各要素の読み出し・設定
複合項(通常言語での構造体やレコード)の値の読み出し/値の設定
条件分岐(通常言語のif文やswitch文)

バックトラック

バックトラックは他のプログラム言語と比較してPrologを特徴づける部分である。バックトラックとは後戻りくらいの意味だが、現在まで日本語として適切な訳を見つけられず、このバックラックがもっぱら使用されている。プログラムのコードとして明示的に指示がないにも関わらず、暗に実行コードが既に実行を済ませた部分に後戻りして実行を始める、そういう制御のことをバックトラックと呼んでいる。

質問が

 ?- P1,P2,P3,P4,P5.

とされたとする。

これから、p3(副目標という)が実行されると考えよう。P1,P2は成功裡に終了している。(ここでは副目標を抽象化して P_n の形式で表すこととする) このP3が成功(真となる)すると実行はP4が呼び出され、その定義の第一節に移る。ところがP3が失敗(偽となる)すると、P2,P1の順に、まだ実行されていない、候補節が残っているものを探し、それがあれば、そこから実行される。この後戻りして、実行する制御のことをバックトラックという。

P2に候補節がなく、p1にまだ候補節があってここから実行される時には、P3を含むP2以降に生じた変数の代入は完全に解消されている。 P1にももはや実行されていない候補節がない場合、最初の質問 ?- P1,P2,P3,P4,P5. が偽となる。

ここで候補節が残っている、または残っていないと書いたが、既に概要のところで述べられた非決定性の述語だけが、この候補節が残っている状態に成り得る。副目標の述語定義が決定性である場合は当然候補節は残っていない訳だから、?- P1,P2,P3, ... に於いて、P2が決定性の述語だったとすれば、P3がバックトラックすれば次はP2をスキップしてP1の残り候補節を探すことになる。

述語Q の定義が以下の場合に ?- Q. が実行されて、上記のようにP3が失敗したとする。

Q :- P1,P2,P3,P4,P5.
Q :- P6,P7.

P3が失敗して、もはやP2,P1にまだ実行されていない候補節がない場合、次の実行は第二節のP6に移る。つまり、Qの第一節は失敗して、第二節(まだ実行されていない)に移る。のように、Prologの実行制御を把握するためには、Pnの真偽だけではなく、Pn-1,Pn-2,...や、そのPnを呼び出しているQの実行状況まで視野に入れる必要がある。

たとえば、以下の述語に対して、

member(X, [X|_]). % Xがリストの先頭要素と同じ場合
member(X, [_|Y]) :- member(X, Y). % それ以外の場合

以下の member(Z, [ワカメ,マスオ]) というゴールを指定すると結果は次のようになる (";"を1回入力しバックトラックを行わせた例) 。

?- member(Z, [ワカメ,マスオ]).
Z = ワカメ ;
Z = マスオ

複数の解がありうる述語member/2に於いて、処理系は質問者に最初の解候補 Z = ワカメを示したが、

質問者は";"を入力することによってこれを否定した(非決定性)。

続いて処理系が Z = マスオという解候補を示し、

質問者はそれを受け入れて、改行した。これがこの実行の解釈である。

具体的に、member/2で解候補が選択される過程を追ってみると、

まず最初の節の頭部

member(X, [X|_])

で単一化が成功し、 Z=ワカメ で member/2 自体も成功する。

この状態でバックトラックを行わせると、次の節である2番目の節の頭部

member(X, [_|Y]) :- ...

で単一化が成功し、その本体部( ... の部分)を

:- member(Z, [マスオ]).

として実行することになる。

これは、最初の節の頭部

member(X, [X|_])

で単一化が成功し、 Z=マスオ で member/2 は成功する。質問者は"."を入力することによって、これが解であることを受け入れた。

非決定性の述語の解の決定権をここでは質問者が持っている。しかし、このように質問者が介在することはPrologプログラミングの中では寧ろ特殊な場合であって、多くの場合、非決定性の述語の解を最終的に決定するのは後続する副目標である。

タラオの親は(L,A) :- member(A,L),親子(A,タラオ).

?- タラオの親は([ワカメ,マスオ],X).
X = マスオ.

これは、タラオの親はワカメかマスオかという質問になっている。解はもちろんマスオだが、これを決定したのは、質問者ではなく親子(A,タラオ) という副目標であり、親子(マスオ,タラオ). という定義から導かれる論理が member(A,[ワカメ,マスオ]) の解をマスオに導いた。このように member/2 からの視点で述べると、解を決定したのは質問者であったり、後続の副目標であったりした。すなわち member/2 にとっての外部である。述語自体は解を決定できないから、外部の導きによって最終的な解を選択するのだと考えればよい。非決定性述語の非決定性とはそんな意味である。

バックトラックは通常のプログラム言語には存在しないProlog独特の機能だが、強いて他のプログラム言語の中から類似したプログラミング要素を探すと、

ループ(通常言語のfor,while等)
探索機能

ループの簡単な例を以下に示す。この例ではリストの先頭から0以上100以下の数値が見つかるまで繰り返す。

?- member(X, [3000, 1254, -2, 3598, 88, 9618]), X>=0, X=<100.
X = 88

手続き型言語では探索機能を実装することは大きなタスクとなるが、Prologは非決定性述語を中心にプログラムを書くものであり、すなわちプログラミングとはバックトラックしながら探索することである。

数式

X+Y*3 などの数式は単なる項にすぎず、そのままでは評価されない。数式を評価するには"is"などの述語を使う。以下にいくつかの述語の例を示す。

X is Y :評価と単一化をおこなう
X = Y :単一化をおこなう
X=:=Y :評価と比較をおこなう
X==Y :比較をおこなう

?- 3+5.
NO

?- X is 3+5.
X = 8
YES

?- X = 3+5.
X = 3+5
YES

?- 3+5 =:= 2+6.
YES

?- 3+5==2+6.
NO

?- 3+5==3+5.
YES

関数型言語とは異なり、導出時に引数の中で数式を渡しても、評価されずに述語が呼び出される。

f1(0).
f1(M) :-
        M_2 is M - 1,
        f1(M_2).

f2(0).
f2(M) :-
        f2(M - 1).

?- f1(10000000).

?- f2(10000000).

ERROR: Out of global stack

f2はエラーになってしまう。再帰する度に引数が 1000000,1000000-1,(1000000-1)-1, ((1000000-1)-1)-1, ... , となっていって、やがてスタックがオーバーフローしてしまう。

カットと否定

Prologは一階述語論理をベースにしているが、実用的なプログラミングのため、述語論理の範囲外の機能も用意されている。カットや否定の組み込みはその例である。

Prologのバックトラックは強力な機能だが、実際のプログラムでは不要なバックトラックを制限したい場合もある。"!" (カット) はバックトラックを制限するための述語である。カットが最初に実行された時には無条件で成功するが、バックトラックでカットに制御が戻ってきたとき、カットを含む述語は無条件に失敗する。つまり、1つの述語内でカット以前に制御が戻ることはない。たとえば、通常のプログラミング言語での if p then q else r の動きは、カットを使って以下のように書ける。

x :- p, !, q.
x :- r.

一度、pが成功して、qに進んだら、qの真偽に関わらず、後にrが実行される可能性はなくなる。

プログラマにとって、カットが重宝なのは、条件p の否定を省略できる点にもある。

x :- p,q.
x :- \+(p),r.

pに副作用がない場合、p,!,q とした場合と同じ意味になる。論理式として正統な記述で推奨されるものではあるが、以下のように、

x :- p1,p2,q1.
x :- \+((p1,p2)),p3,q2.
x :- \+((p1,p2)),\+(p3),q3.

次々と、条件を否定して行かなくてはならないのでは、プログラマにとって負担が大きくなる。

カットを使った場合と比較する。

x :- p1,p2,!,q1.
x :- p3,!,q2.
x :- q3.

このように正確な条件を記述することが大きな負担となる場合、その負担を解消するためにカットが使用されることが実は多い。

これも同様の例である。文字 a を繰り返し表示したい。

f(0).
f(N) :-
    write(a),
    N_1 is N - 1,
    f(N_1).

ここで、

?- f(30).
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaa

となるが、

?- f(30),fail.
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaa

のようにfにバックトラックして来ると、動作は怪しげなことになる。少なくとも多倍長整数をサポートする処理系では Nが -1,-2,-3・・・・・と無限に小さくなっていって反応しなくなる。このような現象を避けるために、普通第一節に

f(0) :- !.
f(N) :-
    write(a),
    N_1 is N - 1,
    f(N_1).

上記のようにカットを入れる。

ただし、この場合でも、カットなしで済ませる方法はある。

f(0).
f(N) :-
    N > 0,
    write(a),
    N_1 is N - 1,
    f(N_1).

でよい。

通常のProlog処理系では、バックトラックで戻ってくる場合に備えて、それまでに実行した各ゴールの情報や値を設定した変数をメモリ上に記憶している。カットを実行するとそれらのうち不要な情報を開放することができるため、カットは使用メモリの削減にもつながる。

カットは非決定性の述語と定義されたものを決定性に転じるためにも多用される。実例を見よう。

append([],L,L).
append([U|X],Y,[U|Z]) :- append(X,Y,Z).

appendの定義であるが、第一引数かつ第二引数に変数が来ると非決定性に働く。

?- append(X,Y,[1,2]).
X = [], Y = [1,2];
X = [1], Y = [2];
X = [1,2], Y = [];
false.

である。appendの第一節の本体にカットを加えると、非決定性の性質が事実上消える。

append([],L,L) :- !.
append([U|X],Y,[U|Z]) :- append(X,Y,Z).

?- append(X,Y,[1,2]).
X = [], Y = [1,2];
false.

元々のappendの定義を壊さず、

決定性append(X,Y,Z) :- append(X,Y,Z),!.

でもよい。appendを決定性に使用したい場合は、以後appendの代わりに専ら決定性appned を使えばよい。

次に、appendの第二節の末尾にカットが来る場合を考える。

append([],L,L).
append([U|X],Y,[U|Z]) :- append(X,Y,Z),!.

このカットも非決定性を決定性に転じる場合に使われるがそう簡単な話ではない。最初にこれでは決定性述語とはならない。

?- append(X,Y,[1,2]).
X = [], Y = [1,2];
X = [1], Y = [2];
false.

最初の解 X = [], Y = [1,2]; は第一節でいきなり真になってしまう。したがって、これはまだカットとは関係がない。第二解は、通常通り第三引数の先頭要素が第一引数に移動して、それで第一引数が[1|X],第二引数tがY,第三引数が[2]となって、移動した後のappendが実行され、

?- append(X,Y,[2]).
X = [], Y = [2]

先ほどの[1|X]のXの部分に[]が来るため、X = [1], Y = [2] が取得できる。

これで一旦成功することになる。成功すると、そのとたんにカットが働く。そのカットの働きで、もう第二節の本体の副目標から次の選択肢を得る指示は与えられない。?- append(X,Y,[2]). にはもう一解存在するのだが、

?- append(X,Y,[2]).
X = [], Y = [2]  % ここまでは使用された。
X = [2], Y = []  % この解を返す指示は来ない。

その解はカットの働きで、この append(X,Y,[2]) で呼び出している副目標が偽となるため、返される機会は来ない。

末尾にカットが在る場合をまとめると、

このカットに到達するのは、ひとつでも解が得られたときであるが、解が得られこのカットに至った場合、カット以前にある副目標によって、次の選択肢として予定されている節選択の可能性は一切なくなる。上記の表現で言い換えれば、次の解を返す指示を出せなくなる。

そして、末尾にカットのある節の後にこの述語の選択節がある場合ももちろんその節が選択されることはない。

説明の順序が前後したが、実行結果の否定のためには述語"\+"が用意されている。 \+(P) はゴールPが成功したときに失敗し、失敗したとき成功する。この述語は本当の否定 "Pは偽である" ではなく "Pは証明できない" という失敗による否定で、ある種の非単調論理による推論を行う。これは以下のように定義した述語と同じ動きをする。ここで fail は必ず失敗する組込述語である。

\+(P) :- P, !, fail.
\+(_).

この否定は、カットなしには定義する方法がない。

論理プログラミングにおいては、「計算は、書き換えの系列として記述される」。ところがPrologにあっては、この書き換え(導出)という表現が好ましくなく場面が現出する。それはカットが導出されるような場面だ。

p :- q1,q2,q3,q4.

q2 :- q5,!.
q2.

のような副目標 p を

?- p.

を q2 の第一節を導出して、

?- q1,q5,!,q3,q4.   % 誤り

と展開して良いであろうか。これは誤りである。実際にはこのカットは働かない。カットは本体の連接の範囲の中のみで有効である。

この問題を別の観点から述べると、カットの重要な性質としてそのカットを別の副目標として置換(述語の再定義)することはできないということになる。さらに実例を示そう。

p(X) :- true,!,X = 1.
p(X) :- X = 2.

のカットをcutに置き換えたとしたら、カットの働きを失う。

p(X) :- true,cut,X = 1.
p(X) :- X = 2.

cut :- !.

最も単純な置換例が上記であるが、これでは、バックトラック後に第二節の実行を妨げられない。

?- p(X).
X = 1;
X = 2.

ここで分ることは、カットは ! が書かれた「節の実行制御」としてのみ有効ということである。

カットを検証する時、取るべきプログラマの視点について最後に記す。

プログラマは定義された述語の各節の本体にのみ焦点を合わせる。そして、その部分に現れるカットによってバックトラックしなくなる本体のカットより前の部分と利用されることがなくなる後続する定義節の存在は視野に入れる必要があるが、導出される謂わば子タスクとしての副目標内に現れるカットは考慮の対象から完全に外す必要がある。

カットが論理プログラミングをどんなに逸脱していても、その利用が不可避である以上、このカットの有効範囲の認識はPrologの基本中の基本である。

高階述語とメタインタプリタ

Prologの述語はPrologの基本データタイプである項で表現でき、述語自身の引数として別の述語を与える高階述語を作成できる。

たとえば、引数で述語を与えそれを単純に実行させたい場合、ゴールとして変数をそのまま書けばいい。

eval(P) :- P.

任意の述語を実行時に作成して実行することができるため、リストのすべての要素に特定の述語を適用し結果のリストを返す maplist/2 や、リストの要素を与えられた述語の結果で選択する sublist/3 などの高階述語を容易に作成できる。同様の高階述語には findall/3 、 setof/3 、 bagof/3 などがある。

また、純粋なPrologのメタインタプリタは以下のように書ける。 clause(P, Q) は頭部が P にユニフィケーション可能な節の本体部 Q を取得する述語である。

execute(true) :- !. % trueならば成功
execute((P,Q)) :- !, execute(P), execute(Q). % P1,... ,Pnの各要素を左から順に試みる
execute(P) :- clause(P, Q), execute(Q). % ゴールPの定義を取得し、本体Qを試みる

純粋なPrologのメタインタプリタには組込述語がないとされるため、上記の通りであるが、実際のProlog処理系には組込述語が存在するため、上記定義では、第三節のclause(P, Q),の部分でPが組込述語の頭部になった時、この副目標が偽となっとしまうことがある。

このclause(P, Q),を実行する前に、ユーザ定義述語か、組込述語かを検査し、別の節に分離する必要がある。組込述語についてはclause(P, Q),することなしに、単にP,すればよい。

データとプログラムの形式が同じであることや、任意の演算子がユーザ定義可能なこと、Prolog自身が強力な構文解析機能を持つことなどもあり、このようなメタインタプリタをもとにPrologの一部機能を拡張した別言語のインタプリタを作成することは、比較的容易である。

関数型言語で高階関数を代表するmap()はPrologでも高階述語を使って定義可能である。しかし、関数型では出力は返り値だけであったが、Prologでは引数のどれかである。入力も複数あり得る。

しかもどの引数が入力であるか、あるいは出力であるかを示すモード宣言は、ほとんどの処理系で採用されていない^{[註 1]}。したがって、Prologでmap述語を構成するためには、対象となるリストの項はどの引数に当たるのかを陽に示さなくてはならない。

以下に、map述語を二つ示す。map/4とmap/5である。

map(_副目標,_要素,_対象リスト,_収集された副目標リスト) :-
        findall(_収集解,(
                    member(_要素,_対象リスト),
                    _副目標),
                _収集された副目標リスト).


map(_副目標,_要素,_対象リスト,_収集項,_収集項のリスト) :-
        findall(_収集項,(
                    member(_要素,_対象リスト),
                    _副目標),
                _収集項のリスト).

どちらも、対象リストの要素が反映して副目標の実行が変化して、それをリストに収集している。map/4は収集されるのが実行された_副目標自体であるのに対して、map/5では実行された _副目標自体ではなく、実行した時々に構成された _収集項がリストに積み上がる。

以下にこのmap述語使用例を示す。

?- map(sub_atom(_文字列,S,Len,_,S), [_文字列,S,Len], [[abcde,0,2],[efgh,2,1],[qazxyz,1,2]], L).

L = [sub_atom(abcde,0,2,3,ab),sub_atom(efgh,2,1,1,g),sub_atom(qazxyz,1,2,3,az)]


?- map(sub_atom(_文字列,S,Len,_,S), [_文字列,S,Len], [[abcde,0,2],[efgh,2,1],[qazxyz,1,2]], S, L).

L = [ab,g,az]

となる。

上記事例で map は、_副目標の引数 _文字列,S,Len,Y が map述語の中で巧みに結びつけられているが、やはり難解である。これではfindall/3を直接使って、

?- findall(Y,(member([_文字列,S,Len],[[abcde,0,2],[efgh,2,1],[qazxyz,1,2]]),sub_atom(_文字列,S,Len,_,Y)),L).

L = [ab,g,az]

と記述してしまっても差がない。member/2が副目標として追加されただけの差である。一般に Prolog に於いて高階述語を使ったmap述語はあまり使用されないが、Prologにはこのように強力なメタ述語 findall や setof が既に存在している。しかも、関数型言語のように引数が事前評価されることはなく、引数に関数を置いて渡すこともできないため、map述語の効用は関数型言語のようには大きくない。

リレーショナルデータベース

Prologはルールを持つデータベースであり、演繹データベースであるといえる。このルールの部分を全てtrueのみに限定した単位節のみからなる述語をデータベースと呼び、リレーショナルデータベースに模して解釈されることが多い。このPrologのデータベースとリレーションナルデータベースは集合論的に類似しているが、異なる部分もあり、この部分がSQLなどデータベース照会言語との変換などで問題となる。

ここでは主としてふたつのデータベースの相違点に焦点を当てて、プログラミング手法を考えてみる。

リレーショナルデータベースはテーブルの集まりであり、

テーブルとは属性(最終的に列となる)の定義域集合の全ての可能な値の組み合わせ(直積)の部分集合である。

属性が、四季と果物の二つ集合 {春,夏,秋,冬} {みかん,りんご,もも,いちご} の直積は

{(春,みかん),(春,りんご),(春,もも),(春,いちご),(夏,みかん),(夏,りんご),(夏,もも),(夏,いちご),(秋,みかん),(秋,りんご),(秋,もも),(秋,いちご),(冬,みかん),(冬,りんご),(冬,もも),(冬,いちご)} であるが、

この部分集合であるテーブル「季節の果物」は季節の果物 :: {(春,いちご),(夏,もも),(秋,りんご),(冬,みかん)} であるとする。

この直積の組み合わせの中で、真となる関係、あるいはその更に一部がテーブルだと考えればよいだろう。

これがリレーショナルデータベースのテーブルの実体である。一方このテーブルをProlog単位節で表すと

季節の果物(春,いちご).
季節の果物(夏,もも).
季節の果物(秋,りんご).
季節の果物(冬,みかん).

となる。Prologデータベースの第一節は「春といちごは季節の果物関係にある」というものであり、述語名として季節、果物が暗示されてはいるものの、実は第一引数が季節であり、第二引数が果物であるという情報はどこにもない。「季節」や「果物」といった属性(列)から出発したリレーショナルデータベースとは明らかに異なる。

この相違に起因する問題がSQL問い合わせをProlog述語に変換する際に生じる。

以下のような、SQLに問い合わせを考える。

select 季節 from 季節の果物 where 果物 = 'もも'

これに相当するPrologの質問は

?- 季節の果物(X,もも).

X = 夏

であるが、問題点がふたつある。

第一引数が果物なのか、第二引数が果物なのか定かでない。季節についても同様である。
実はSQLの質問からだけでは季節の果物テーブルの属性がここに現れた「季節」と「果物」だけであるかどうか定かでない。

例えば、「産地」などの属性も実はあるのかも知れない。つまり、何引数の述語を用意すれば良いのかさえわからない。

つまりこのふたつのデータベースを比較すると、Prolog述語側に属性の情報が欠落しているということになる。一方、リレーショナルデータベースのテーブルは属性からスタートしていてこの情報は根幹にあり、したがってSQLがこれを利用することは容易であるし、自然なことである。

したがって、Prolog述語としてSQLと対等の情報を用意し、相互に変換を試みるとすれば、

テーブル定義(季節の果物,1,季節).
テーブル定義(季節の果物,2,果物).

のような、補助情報を定義する必要がある。

ここでは、テーブル定義/3を用いたが、Prologの規格によって指定された述語名/アリティのようなものは存在しないから、自由に定義してよい。

このような定義を前提にすれば、

属性名での照会(_テーブル名,_選択する属性名,_値) :-
        テーブルの引数をリストとして得る(_テーブル名,_引数のリスト),
        属性名と値を結びつける(_テーブル名,_選択する属性名,_値,_引数のリスト),
        テーブルを照会する(_テーブル名,_引数のリスト).

テーブルの引数をリストとして得る(_テーブル名,_引数のリスト) :-
        count(テーブル定義(_テーブル名,_,_),_アリティ),
        length(_引数のリスト,_アリティ).

属性名と値を結びつける(_テーブル名,_選択する属性名,_値,_引数のリスト) :-
        テーブル定義(_テーブル名,_何番目の引数,_選択する属性名),
        nth1(_何番目の引数,_引数のリスト,_値).

テーブルを照会する(_テーブル名,_引数のリスト) :-
        _テーブル =.. [_テーブル名|_引数のリスト],
        call(_テーブル).

count(P,Count) :-
        findall(1,P,L),
        length(L,Count).

length/2を使って変数だけからなる _引数のリストを生成して、それと質問の引数である _値をnth1/3を使って単一化している。変数と変数の間に = の制約を築いておく。属性名と値を結びつける/4 がそれだ。

=.. は二引数の組込述語であるが、この述語は関数名を第一項に第二項以後を引数を順序に持つリストを複合項に変換するメタ述語と呼ばれる範疇の述語である。

?- P =.. [季節の果物,冬,みかん].

P = 季節の果物(冬,みかん).

となる。

これで属性名(列名)を与えての照会が、

?- 属性名での照会(四季の果物,果物,X).

X = いちご;
X = もも;
X = りんご;
X = みかん

可能となった。

次に、鍵名とその値を与えての参照は、

鍵による照会(_テーブル名,_鍵名,_鍵の値,_選択する属性名,_値) :-
        テーブルの引数をリストとして得る(_テーブル名,_引数のリスト),
        '鍵名と鍵値、選択する属性名と値を結びつける'(_テーブル名,_鍵名,_鍵の値,_選択する属性名,_値,_引数のリスト),
         テーブルを照会する(_テーブル名,_引数のリスト).

テーブルの引数をリストとして得る(_テーブル名,_引数のリスト) :-
        count(テーブル定義(_テーブル名,_,_),_アリティ),
        length(_引数のリスト,_アリティ).

'鍵名と鍵値、選択する属性名と値を結びつける'(_テーブル名,_鍵名,_鍵の値,_選択する属性名,_値,_引数のリスト) :-
        属性名と値を結びつける(_テーブル名,_鍵名,_鍵の値,_引数のリスト),
        属性名と値を結びつける(_テーブル名,_選択する属性名,_値,_引数のリスト).

属性名と値を結びつける(_テーブル名,_選択する属性名,_値,_引数のリスト) :-
        テーブル定義(_テーブル名,_何番目の引数,_選択する属性名),
        nth1(_何番目の引数,_引数のリスト,_値).

テーブルを照会する(_テーブル名,_引数のリスト) :-
        _テーブル =.. [_テーブル名|_引数のリスト],
        call(_テーブル).

count(P,Count) :-
        findall(1,P,L),
        length(L,Count).

このようにテーブル情報/3のような補助的情報を与えることを前提に、SQLに対応する述語を定義していくことによって、Prolog述語はオンメモリデータベースシステムとしての機能性を得ていくことになる。

実行例

?- 鍵による照会(季節の果物,果物,もも,季節,_値).

_値 = 夏

ここでは説明を簡素化するために、選択する属性値を一つに限定したが、一般には鍵、選択項それぞれをリストとして、複数の鍵の指定と、複数の選択項の値が得られるように設計されるべきであろう。

リレーショナルデータベースとProlog述語の関係をProlog述語をリレーショナルデータベースと見なすことでProlog処理系内にこれを築くことについて述べた。これとは別に、

Prologの節の中で文字列としてのSQLを生成し、これを外部インターフェイスを経由して、RDBMSに送り解集合を用意させて、これを順にフェッチしていくということは、多くの処理系でライブラリを用意して実現している。

さらにオペレータ定義を駆使して、

select * into _解 from _関係表名 where _属性名 = _値 :- ・・・

のような定義をして、

?- select * into X from 季節の果物 where 果物 = もも.
X = [[夏,もも]]

のようなSQLに模した表現でPrologにデータを取得することも部分的には実現できる。しかし以下のような表現はどのようにオペレータ定義を工夫してもできない。

select 季節,果物 into X from 季節の果物 where 果物 = もも.

ここでは詳細には述べないが季節,果物の表現をPrologでは取れない。季節と果物の間のカンマを境に、それ以前と以後が副目標として分離されてしまう。

select (季節,果物) into X from 季節の果物 where 果物 = もも.

これならProlog述語として定義可能になるが、今度はこの括弧が SQL の構文違反になってしまう。

集合

Prologでは特別な集合表現は用意されていない。

例えば、{_,_, ... ,_} が集合を表すというような規則はなく、リストが代用されることが普通である。

リストが集合に利用されると、不都合な点が二つ存在する。

リストは要素の重複が許されるが、集合は重複が存在しない。
リストは要素の順序に意味があり、それを前提で使用されている。一方、集合の要素には出現順位のような概念はない。

リストでは当たり前に存在する [1,1,4] は集合では [1,4] であり、しかも [4,1] でも集合として等しい。型付けのないPrologではこのように利用者が集合としてリストを見なすことが集合プログラミングの前提になる。四季を表す集合を例に取ると、集合が[春,夏,秋,冬]の順序で渡されるとは限らないことを常に意識している必要がある。

Prologの組込述語として is_set/1, subset/2, subtrct/3, intersection/3, union/3, さらにメタ述語として setof/3 などが用意されていて、プログラマはできる限りこの組込述語のみで集合演算を行うように心がけることによってリストと集合の意味の齟齬に起因する誤謬を回避することができる。

Prologには同一の集合を定義する述語が用意されていないため、組込述語subset/3を使って集合として等しい/2 を定義してみよう。

集合として等しい(_集合_1,_集合_2) :-
        subset(_集合_1,_集合_2),
        subset(_集合_2,_集合_1).

これで、

?- 集合として等しい([春,夏,秋,冬],[秋,冬,夏,春]).
true.

?- 集合として等しい([春,夏,秋,冬],[秋,冬,夏]).
false.

となる。ただし、論理変数を複数導入した例では、解が

?- 集合として等しい([1,2,3],[X,3,Y]).
X = 1,
Y = 2.

?-

のみで、順序に関わりなく充足しているというべきで、X = 2,Y = 1 という解は得られない。この点、注意を要する。

この集合として同一を中置演算子として定義してみる。

:- op(700,xfx,===).

(L1 === L2) :- 集合として等しい(L1,L2).

これで

?- [2,1,3] === [1,2,3].
true.

となる。演算子の導入は後々までプログラミングに影響を与えるものだから、極めて慎重に行う必要はあるが。

構文解析

Prologは構文解析を行うのに向いたプログラミング言語である。元々、Prologは論理を利用した自然言語処理のために開発された^[14]。実際、文脈自由文法のトップダウン構文解析の動きはProlog自身の動きと同じである。

限定節文法

Prologには限定節文法（テンプレート:Lang-en-short）と呼ばれる特別な表記法が用意されている。文脈自由文法を拡張したもので、文法を記述する場合は :-/2 ではなく -->/2 を用いる。

 head --> body.

文法での非終端記号はPrologの項で、終端記号は非終端記号と区別するためリスト内の項で表現する。付加的な条件や動作を指定したい場合、文法の最後に任意のProlog述語を { } で囲んで記述する。限定節文法の例を以下に示す。この例では数式を解析し計算を行う。

expression(E) --> term(X), [+], expression(Y), {E is X + Y}.
expression(E) --> term(X), [-], expression(Y), {E is X - Y}.
expression(E) --> term(E).

term(T) --> num(X), [*], term(Y), {T is X * Y}.
term(T) --> num(X), [/], term(Y), {T is X / Y}.
term(T) --> num(T).

num(N) --> [+], num(N).
num(N) --> [-], num(X), {N is -X}.
num(N) --> [N], {number(N), between(0, 9, N)}.

これはバッカス・ナウア記法で書かれた以下の文法規則に計算の動作を付加したものと同じ意味を持つ。

<expression> ::= <term> "+" <expression> | <term> "-" <expression> | <term>
<term> ::= <num> "*" <term> | <num> "/" <term> | <num>
<num> ::= "+" <num> | "-" <num> | 0..9

実行結果は以下のようになる。

?- expression(Z,[-, 2, +, 9, *, 2, +, 3, *, 5],[]).
Z = 31

このように直接計算を行うのではなく抽象構文木を作成するような文法規則を作成することもできる。構文木はPrologの項として素直に表現できるため、その後の機械語へのコンパイルや最適化などを行うことも可能である。

実際には、限定節文法の文法規則はProlog節を見やすくするためのシンタックスシュガーで、他のプログラミング言語でのマクロ展開のように、文法規則読み込み時にPrologの述語に変換される。変換規則は expand_term/2 で定義されている。たとえば、 p(X,Y) --> q(X), r(X,Y), s(Y). の文法規則は p(X,Y,S0,S) :- q(X,S0,S1), r(X,Y,S1,S2), r(Y,S2,S). の節に変換され、付加された変数間で解析の情報が受け渡される。

プログラム例

Prologのプログラム例を以下に示す。

Hello world

"Hello World"は1970年代から「コンピュータはプログラム言語を使って、こんなにも簡単に動くものですよ」ということを感じさせる課題として好んで使われ、今日では教則本の冒頭にこれを置くことが半ば様式化してしまった。しかしPrologの述語は基本的に真偽値を問うものであって、入出力は副作用として疎ましい存在であり、冒頭にHello World述語を持ってくることには反対意見が強い。

そういう事情を理解した上で、ここでは、この課題をPrologプログラミングの導入として利用してみよう。

Prologは質問すると、処理系が答えを返す系である。"Hello World!"という表示は処理系が行うのだから、その前に質問がなくてはならない。質問を "hi" とする。

hi :-
        write('Hello World!\n').

writeは引数が一個の組込述語である。引数の内容を表示する。world!の後の"\n"は改行することを意味する。

実行例で見てみよう。Prologインタプリタは一般にプロンプトとして "?- "　が表示された後に、ユーザーが質問を入れる。

?- hi.
Hello World!

述語名が hi であっても hi(a) :- や hi(1,2,3) :- の定義もあるかもしれない。Prologではこれらを区別するために、それぞれ hi/0 hi/1 hi/3 のようにスラッシュの後に引数の数を書いて区別する。ここでは hi/0 である。

質問 hi に対して、定義済みの hi が呼び出されて、その中でさらに write('Hello World!\n') が呼び出された。

ここでは "Hello World!\n" は組込述語 write/1 の中に直接記述されたが、一般にはこのような原初的な情報はデータベース述語によって管理され、そこから引き出されて使われる。

hi :-
        answer(hi,S),
        write(S).

answer(hi,'Hello World!\n').

S は先頭が英大文字だから論理変数である。answer/2はプログラマが定義したデータベース述語である。

副目標answer(hi,S)は述語定義 answer/2 と単一化されて、第一引数はatom同士でしかもhiで完全一致、第二引数はSと'Hello Wolrld!\n'が単一化されて、これは単一化のルールにより無条件に論理変数Sは'Hello World!\n'となる。そのS、乃ち'Hello World!\n'をwrite/1する。

さらにこのプログラムに bye を追加してみよう。

hi :-
        answer(hi,S),
        write(S).

bye :-
        answer(bye,S),
        write(S),
        halt.

answer(hi,'Hello World!\n').
answer(bye,'See you again!\n').

述語 bye/0 の本体 (:- の右側) の最後にある halt は0引数の組込述語で処理系を終了させる。

実行例

?- hi.
Hello World!

?- bye.
See you again!

#

Hello World からの導入はこんなところだろう。

家系図

よく知られる「サザエさん」の家系図(部分)をPrologで表現する。

親子(波平,サザエ).
親子(ふね,サザエ).
親子(波平,カツオ).
親子(ふね,カツオ).
親子(波平,ワカメ).
親子(ふね,ワカメ).
親子(マスオ,タラオ).
親子(サザエ,タラオ).

夫婦(波平,ふね).
夫婦(マスオ,サザエ).

このように、本体がない、あるいは本体のtrueが省略された定義を、単位節と呼ぶ。親子、夫婦の両述語はともに第一引数または第二引数をキーとしてデータを参照することができる一種のデータベースと考えることができる。

このような単位節データベースは全ての知識の基礎であって、必ずしもすぐにプログラムとして利用されなくても価値がある。ノートに書き付けるように身の回りの知識を定義していけばよい。

備忘録としての単位節データベースへ実際に問いかける例を示そう。「サザエの親は誰か」という質問をする。

?-  親子(_親,サザエ).
_親 = 波平

ここで一旦処理系は停止する。この解に満足な時はただ改行する。

?- 親子(_親,サザエ).
_親 = 波平 ;
_親 = ふね.

?-

1) 波平に満足できない。 2) 波平以外の解がほしい。そんな場合には停止中のカーソルにセミコロン(;)を入力すると、次の解を示してくる。_親 = ふねだ。他にも親はいないものかとさらにセミコロンを入力すると、もうこれ以上解はないと、この処理系では入力したセミコロンをピリオドに置き換えて表示して質問は終わりとなる。

孫の定義

前題の家系図が既に定義済みという前提で、祖父-孫関係を定義してみよう。

'祖父-孫'(波平,タラオ).

祖父・孫の関係になれるのは波平とタラオだけである。'祖父-孫'という述語名はハイフンのような記号を含むアトムとなるため、シングルクォートで囲む必要がある例として示した。述語名はこれに限らず、祖父孫でも祖父と孫でも祖父孫関係あるいは単に祖父でも、特にこうしなくてはいけないというルールはない。処理系への知識の与え方は基本的に自由である。

今度は、「孫」を定義する。上記の定義に倣うなら '祖父母-孫' 関係ということになるが、ここでは単に「孫」とする。

孫(波平,タラオ).
孫(ふね,タラオ).

実行例を示そう。

?- 孫(X,タラオ).
X = 波平 ;
X = ふね.

?-

一般に質問する時は、入力の負担を減らすために、最少の文字数となる XとかA,Bなど英大文字一文字を論理変数に置くことが多い。 Xを使うことが多いのは、方程式の解となる変数をXとする習慣を引き継いだものと考えられる。もちろん家系図の時のように ?- 孫(_祖父母,タラオ). と質問しても構わないし、常にそういう習慣があるならそれが望ましい。

孫を具体的な人と人の関係として定義して見たが、以下のような定義も可能である。このような定義をルールという。

孫(_祖父または祖母,_孫) :-
        親子(_祖父または祖母,A),
        親子(A,_孫).

Aは孫から見ると親であるが、祖父または祖母から見ると親ではないので、_親とはせずに、英大文字の A で抽象化した。二つの親子/2の副目標に共通してAが存在することが重要である。孫の親と祖父または祖母の子が同一人物のAであることを示している。だから

% これでは具合が悪い!

孫(_祖父または祖母,_孫) :-
        親子(_祖父または祖母,_祖父または祖母の子),
        親子(_孫の親,_孫).

_祖父または祖母の子と _孫の親とは単一化できていないため、変数名から同一が類推できるとしても、処理系は A の時のように同一のものと扱わない。

なお、行の先頭に % がある一行目は「註釈行」でありプログラム実行の対象とはならない。述語形式以外の自由な文を書くこともできる。

家系図の中で、このような二つの親子関係が連接して、孫関係を充たすのは、

?- 孫(X,Y).
X = 波平,
Y = タラオ;
X = ふね,
Y = タラオ .

?-

である。

リスト要素の加算

与えられたリスト要素を加算する。再帰的な定義である。

リスト要素の加算([],0).
リスト要素の加算([N|R],S) :-
        リスト要素の加算(R,S1),
        S is S1 + N.

1要素少ないRの加算計がS1ならばSはS1にNを加えたものだ、という宣言である。

実行例: このように定義しておけば、以下の質問は

?- リスト要素の加算([1,2,3,4,5,6,7,8,9,10],X).
X = 55

となる。

加算は以下のように、二つの述語に分離して、引数をひとつ増やした述語を作ると累算部分がはっきりしてわかりやすい。加算を担うのは後の方、引数が3個ある方の述語だ。述語名は引数の数が違うから同じリスト要素の加算で構わない。リストから数を取り出すと、この第二引数に加算していく。

% 1
リスト要素の加算(L,S) :-
        リスト要素の加算(L,0,S).

% 2
リスト要素の加算([],S,S).
リスト要素の加算([N|R],S1,S) :-
        S2 is S1 + N,
        リスト要素の加算(R,S2,S).

リスト要素の加算/3 の第一節の %1 の下の

リスト要素の加算([],S,S).

というところがProlog独特のテクニックである。

第一引数のリストが空になったとき、第二引数に累計が存在するのだが、

最初の %1 述語リスト要素の加算/2の副目標

        リスト要素の加算(L,0,S).

の第二引数では初期値0と値を決めて引数に渡しているため、この第二引数から値を受け取ることは不可能である。

そこで、第三引数として一つ余分な引数を設けて、そちらを変数にして置けば、最終的にその引数が単一化されることによって値を受け取ることができるという訳だ。その第二引数と第三引数の単一化を行っているのが、%2 のリスト要素の加算/3の第一節の

リスト要素の加算([],S,S).

である。

この述語の第二節第三引数がともにSで同一であることも重要である。

リスト要素の加算([N|R],S1,S) :-
        S2 is S1 + N,
        リスト要素の加算(R,S2,S).

この部分が束縛されないまま、単に同一の変数であることが示されている。

質問の第一引数が[]になれば、この述語の第二節が融合されて、質問側に用意されている第二引数の加算計がこれに単一化される。

リスト要素の加算([],S,S).

これまで第三引数は全て同一ということになっているため、この第三引数経由で加算値が質問の第二引数に返される。

単位節要素の加算(集約問題)

単位節(本体のない事実上のデータベース定義)要素の加算。実例として次の単位節データベースを考える。

年齢(山田,35).
年齢(大島,20).
年齢(清川,28).

ここでは年齢の合計を計算する。簡単なデータベースの参照は、

?- 年齢(A,B).
A = 山田,
B = 35;
A = 大島,
B = 20;
A = 清川,
B = 28 .

?-

Prologの述語の中のそれぞれの節に現れる要素は他の節から完全に独立である。すなわち一つの節の中の値は別の節からは参照できない。山田を得たとき、大島を得たとき、清川を得たときはそれぞれ独立している。以前の変数の束縛は解かれてしまっている。

大島の20を得たときには、山田の35の情報は失ってしまっているということになる。

これでは加算のような集約問題を解決できない。

このことを可能にするために、メタ述語 findall/3 が存在する。 findall/3 はSQLのselect文に似た述語であり、述語を実行した際に任意の値をリストに集めることができる。

年齢(山田,35).
年齢(大島,20).
年齢(清川,28).

年齢合計(X) :-
        findall(N,年齢(_,N),L),
        リスト要素の加算(L,X).

本来、情報の連関のない述語年齢/2 のそれぞれの節を、連関を持つデータ構造であるリストに取り込むことによって、集約を可能とする。

実行例:

?- 年齢合計(X).
X = 83

理解を深めるために、findall以下を直接質問として呼び出してみよう。

?- findall(N,年齢(_,N),L),
   リスト要素の加算(L,X).

L = [35,20,28],
X = 83

となる。findallは強力な述語であるが、対象となる定義節数が極めて多い場合、例えば、1000万節を越えるような場合、スタックオーバーフロー等のエラーが発生する危険が生じる。内部メモリにリストとして情報の連鎖を生成するのだから、やむを得ないことではあるが、注意が必要である。

相加平均

算術平均ともいい、一般に平均値といった場合これを指す。標本はリストとして保持しているとする。基本的には加算と同じだが、同時にリストの標本数も数える。第二、第三引数にそれぞれ初期値 0 を置き、これに標本数と値を加算していく。

相加平均(_標本リスト,_相加平均) :-
        相加平均(_標本リスト,0,0,_相加平均).

相加平均([],_標本数,_累計,_相加平均) :-
        _標本数 > 0,
        _相加平均 is _累計 / _標本数.
相加平均([_値|R],_標本数累計_1,_累計_1,_相加平均) :-
        _標本数累計_2 is _標本数累計_1 + 1,
        _累計_2 is _累計_1 + _値,
        相加平均(R,_標本数累計_2,_累計_2,_相加平均).

この述語では要素数や累計を求められていないため、これを入手するための変数は用意されていない。その代わりにリストが空の時に相加平均が計算されて単一化される。これが平均値の述語定義だが、多くの場合ここまでプログラマが定義する必要はない。下記のように、組込述語を含めて、定義済みの述語を組み合わせて相加平均は定義される。上記の要素数のカウント部分は独立して length という組込述語となっている。したがって、相加平均の定義は

相加平均(_標本リスト,_相加平均) :-
        length(_標本リスト,_標本数),
        リスト要素の加算(_標本リスト,_合計),
        _相加平均 is _合計 / _標本数.

で構わない。

最大値、カットの用法

リストの最大値を求める。併せて、カットの典型的な用法について説明する。最初に初期値を設定して、それと再帰的に比較する。初期値はリストの中の要素であれば、何でも構わないのだが、ここでは第一要素を使う。

最大値(_標本リスト,_最大値) :-
        _標本リスト = [_第一要素|R],
        最大値(R,_第一要素,_最大値).
 
最大値([],_最大値,_最大値).
最大値([_要素|R],_最大値_1,_最大値) :-
        _要素 > _最大値_1,!,           % ! の位置に注意。
        最大値(R,_要素,_最大値).
最大値([_要素|R],_最大値_1,_最大値) :-
        最大値(R,_最大値_1,_最大値).

_要素がこれまでの最大値を超えない時は最後の節が選択される。超えた場合は第二節の「_要素 > _最大値_1,!」のカットが働き最後の節が選択されることはなくなる。引数が3の最大値の第二節に「!」がある。これがないと、

最大値(_標本リスト,_最大値) :-
        _標本リスト = [_第一要素|R],
        最大値(R,_第一要素,_最大値).
 
最大値([],_最大値,_最大値).
最大値([_要素|R],_最大値_1,_最大値) :-
        _要素 > _最大値_1,
        最大値(R,_要素,_最大値).
最大値([_要素|R],_最大値_1,_最大値) :-
        最大値(R,_最大値_1,_最大値).
 
?- 最大値([2,4,6,8,3],X).
X = 8;
X = 6;
X = 8;
X = 4;
X = 8;
X = 6;
X = 8;
X = 3;
X = 2;
false.
?-

というようなことが起こりうる。バックトラックして来たときにそれまでで最大としたものを、「;」の入力で「それではない」と否定されて、撤回してしまう。せっかく見つけ出したそれまでの最大値であるべきものがこれまでの最大値として使われないためである。「!」を入れることが有効な場所を、最初の定義も含めて示す。

%%% 案1 %%%
最大値(_標本リスト,_最大値) :-
        _標本リスト = [_第一要素|R],
        最大値(R,_第一要素,_最大値).
 
最大値([],_最大値,_最大値).
最大値([_要素|R],_最大値_1,_最大値) :-
        _要素 > _最大値_1,!,             % ! の位置に注意。
        最大値(R,_要素,_最大値).
最大値([_要素|R],_最大値_1,_最大値) :-
        最大値(R,_最大値_1,_最大値).

%%% 案2 %%%
最大値(_標本リスト,_最大値) :-
        _標本リスト = [_第一要素|R],
        最大値(R,_第一要素,_最大値).
 
最大値([],_最大値,_最大値).
最大値([_要素|R],_最大値_1,_最大値) :-
        _要素 > _最大値_1,
        最大値(R,_要素,_最大値),!.       % この節の末尾に ! がくる。
最大値([_要素|R],_最大値_1,_最大値) :-
        最大値(R,_最大値_1,_最大値).

%%% 案3 %%%
最大値(_標本リスト,_最大値) :-
        _標本リスト = [_第一要素|R],
        最大値(R,_第一要素,_最大値),!.   % ここに ! を打つ。非決定性述語 最大値/3 を事実上決定性述語とすることができる。
 
最大値([],_最大値,_最大値).
最大値([_要素|R],_最大値_1,_最大値) :-
        _要素 > _最大値_1,
        最大値(R,_要素,_最大値).
最大値([_要素|R],_最大値_1,_最大値) :-
        最大値(R,_最大値_1,_最大値).

などが考えられる。ただし、案3は　最初の 最大値 で質問した場合は ! が有効になるが、最大値 の方で質問した場合は、「!」はないので、有効にならない。最大値/2の方で質問するように注意する必要がある。

最大値([],_最大値,_最大値).

の本体に必ずしも「!」が存在しない理由は、第一引数が [] で呼ばれた場合、さらに他の節が選択されることはこの定義の場合はあり得ないからだ。最初の最大値の定義の、

最大値(_標本リスト,_最大値) :-
        _標本リスト = [_第一要素|R],
        最大値(R,_第一要素,_最大値).
 
最大値([],_最大値,_最大値).
最大値([_要素|R],_最大値_1,_最大値) :-
        _要素 > _最大値_1,         % 今度は ! がない。
        最大値(R,_要素,_最大値).
最大値([_要素|R],_最大値_1,_最大値) :-
        _要素 =< _最大値_1,
        最大値(R,_最大値_1,_最大値).

最後の節の本体に「_要素 =< _最大値」を加えれば「!」を排除することができる。

最後に、最も宣言的な最大値の定義を示す。

最大値(_標本リスト,_最大値) :-
        select(_最大値,_標本リスト,_最大値を除くリスト),
        forall(member(_要素,_最大値を除くリスト),_要素 =< _最大値).

select/3とforall/2は共に組込述語となっている。select/3は第二引数のリストの先頭から要素を非決定性に取り出し、第一引数に単一化すると共に第三引数にその要素を除いたリストを単一化する。

forall/2は第一引数の評価を真とするものに全てに対して、第二引数の評価は真となる、というものである。

行列

行列も集合同様、Prologでは特別な記法は用意されてはいない。そのため一般に行列を、リストを要素として持つリストとして表現することが多い。

例えば 3 × 3　の単位行列

| 1  0  1 |
| 0  1  0 |
| 0  0  1 |

は [[1,0,0],[0,1,0],[0,0,1]] のように表す。全体が3要素のリスト、そのそれぞれの要素がまた3要素のリストである。

ここでは、findall/3を二重に使った行列の転置の定義を示す。

行列の転置([_最初の行|_残りの行],_転置行列) :-
        length(_最初の行,_列数),
        findall(_転置された行,(
                    between(1,_列数,_nth1),
                    findall(_値,(
                                member(_行,[_最初の行|_残りの行]),
                                nth1(_nth1,_行,_値)),
                            _転置された行)),
                _転置行列).

この定義の難しさは、列数を得るための表現にある。ここでは行列の転置述語の第一引数を細工してこれを得たが、代償として、対象行列を[_最初の行|_残りの行]と表現したため、この引数が何を意味するのかわかりにくいコードとなった。

行列が[[1,2,3],[4,5,6],[7,8,9],[10,11,12]]として与えられた時の行列の転置は

実行例

?- 行列の転置([[1,2,3],[4,5,6],[7,8,9],[10,11,12]],_転置行列).
_転置行列 = [[1,4,7,10],[2,5,8,11],[3,6,9,12]]

となる。

行列の転置の再帰的な定義は

行列の転置(L,[L1|R2]) :-
        行列の転置(L,L2,L1),
        行列の転置(L2,R2).

行列の転置([],[],[]) :- !.
行列の転置([[A|R1]|R2],[R1|R3],[A|R4]) :-
        行列の転置(R2,R3,R4).

findall/3の定義に比べると、定義自体は簡素なのだが、可読性はかなり悪い。

行列の掛算

行列の掛算は普通第二引数の行列を一旦、行列の転置/2 で転置し、掛け合わせる3つの述語行列の掛算_1/3 行列の掛算_2/3 行列の掛算_3/3 によって積を得る。述語名の末尾に _1 _2 _3 を付加して別の述語とするのは、引数が同じで同一の述語名が使えない時の方便である。一般に、述語の意味する言葉を述語名とすることが望ましいが、行列述語などを含めて数学的なアルゴリズムでは、部分的な計算を言葉で表現することが困難な場合も多い。それでこのような述語の命名がしばしば見られる。

行列の掛算(_行列_1,_行列_2,_行列の積) :-
        行列の転置(_行列_2,_転置された行列),
        行列の掛算_1(_行列_1,_転置された行列,_行列の積).

行列の掛算_1([],_,[]) :- !.
行列の掛算_1([L_1|R1],LL_2,[S1|R3]) :-
        行列の掛算_2(L_1,LL_2,S1),
        行列の掛算_1(R1,LL_2,R3).

行列の掛算_2(_,[],[]) :- !.
行列の掛算_2(L_1,[L_2|R2],[S|R3]) :-
        行列の掛算_3(L_1,L_2,S),
        行列の掛算_2(A,R2,R3).

行列の掛算_3([],[],0) :- !.
行列の掛算_3([A|R1],[B|R2],S) :-
        S1 is A * B,
        行列の掛算_3(R1,R2,S2),
        S is S1 + S2.

実行例

?- 行列の掛算([[3,4,8],[2,6,5]],[[7,8],[2,6],[5,4]],X).

X = [[69,80],[51,72]].

正方行列の対角要素

正方行列の右下がり対角要素リストと左下がり対角要素リストを得る。正方行列の対角要素とは、

<math> \begin{pmatrix}

 1 & 2 & 3 \\
 4 & 5 & 6 \\
 7 & 8 & 9

\end{pmatrix} </math>

1、5、9 が右下がり対角要素であり、3、5、7 が左下がり対角要素であるとする。これを nth1 と length と append の組み合わせで定義する。

右下がり対角要素リスト(_正方行列,_右下がり対角要素リスト) :-
        findall(V,(
                    nth1(_nth1,_正方行列,L),
                    nth1(_nth1,L,V)),
                _右下がり対角要素リスト).

左下がり対角要素リスト(_正方行列,_左下がり対角要素リスト) :-
        findall(V,(
                    nth1(_nth1,_正方行列,L),
                    length([_|R],_nth1),
                    append(_,[V|R],L)),
                _左下がり対角要素リスト),!.

組込述語 nth1 は非決定性の述語で第一引数が論理変数の場合は、1、2、3、…、n とバックトラックされる度に順に値を生成する。nth1 の 1 は1からこのカウントを開始するの意味である。

上記二つの定義では、要素位置を示す論理変数 _nth1 が現れるが、この論理変数に対して何ら演算を施してはいない。このように要素位置等の数値による管理からプログラマが解放される機会が多いことも Prolog の大きな特長である。

実行例を示す。

?- 右下がり対角要素リスト([[1,2,3,4],[5,6,7,8],[9,10,11,12],[13,14,15,16]],L).

L = [1,6,11,16]

?- 左下がり対角要素リスト([[1,2],[3,4]],L).

L = [2,3]

部分集合

Prolog が集合をどのように扱うかについては、既に Prolog プログラミングの章で述べた。

ある集合が別の集合の部分集合であるか確かめる述語 部分集合 を定義する。

この述語は組込述語 subset として定義済みであり、その定義は

subset(_subsets,_sets) :-
        forall(member(_element,_subsets),member(_element,_sets)).

であると考えられる。_subsets のメンバーは必ず _sets のメンバーであると宣言している。

組込述語 forall は第一引数の副目標が真になる場合は、第二引数の副目標も必ず真になると宣言するメタ述語である。

ここではこれとは別に 部分集合 として再帰を使って定義する。

部分集合([],_).
部分集合([_要素|R],_集合) :-
        member(_要素,_集合),
        部分集合(R,_集合).

実行例を示す。

?- 部分集合([2,4],[4,1,2,6]).
true.

?- 部分集合([3,4],[4,1,2,6]).
false.

となる。

階乗

階乗は整数の性質に含まれる数の連関を使うだけで計算できる数少ない例の一つである。Nの階乗を 階乗 として定義する。

階乗(0,1) :- !.
階乗(N,_階乗) :-
        N_1 is N - 1,
        階乗(N_1,_階乗_1),
        _階乗 is _階乗_1 * N.

計算対象となる要素が、ここでのように常に1少ないというような場合は、特別な例なのであって、そのような固定した性質がない集合の計算では計算対象をリストに取ることが多い。既にそのような例としては加算の リスト要素の加算 があった。

階乗保存計算

10000以下の素数のリストをウィルソンの定理による素数判定を使って得る。この計算では階乗計算が繰り返し使われるのだが、述語に定義節を動的に書き加えることによって、階乗の呼び出し回数を大幅に少なくできる。ただし、述語論理を完全に逸脱したプログラムである。

:- dynamic(階乗保存計算/2).

'ウィルソンの定理を使って素数を判定する関数is_primeを実装し、100000以下の素数以外をリストに得る'(_10000以下の素数リスト) :-
        findall(_p,(
                    between(1,10000,_p),
                    is_prime(_p)),
                _10000以下の素数リスト).

is_prime(_p) :-
        'ウィルソンの定理とは pが素数 <=> (p-1)!+1 (mod p) == 0'(_p).

'ウィルソンの定理とは pが素数 <=> (p-1)!+1 (mod p) == 0'(_p) :-
        _p > 0,
        Y is _p - 1,
        階乗保存計算(Y,Z),
        0 is (Z + 1) mod _p,!.

階乗保存計算(0,1) :- !.
階乗保存計算(1,1) :- !.
階乗保存計算(N,X) :-
        N2 is N - 1,
        階乗保存計算(N2,Y),
        X is N * Y,
        asserta((階乗保存計算(N,X) :- !)).

asserta は述語の先頭に定義節を加える組込述語。既に計算した階乗は答えを階乗保存計算の先頭に付け加えることで、以後階乗計算に入るまえに、その解を得ることができるようになる。

述語 階乗保存計算 の定義は階乗保存計算(7). を実行前と後では以下のように変化する。

?- listing(階乗保存定義/2).

階乗保存計算(0, 1) :- !.
階乗保存計算(1, 1) :- !.
階乗保存計算(A, C) :-
        B is A + -1,
        階乗保存計算(B, D),
        C is A * D,
        asserta((階乗保存計算(A, C):-!)).

true.

?- 階乗保存計算(7,X).

X = 5040

?- listing(階乗保存計算/2).

階乗保存計算(7, 5040) :- !.
階乗保存計算(6, 720) :- !.
階乗保存計算(5, 120) :- !.
階乗保存計算(4, 24) :- !.
階乗保存計算(3, 6) :- !.
階乗保存計算(2, 2) :- !.
階乗保存計算(0, 1) :- !.
階乗保存計算(1, 1) :- !.
階乗保存計算(A, C) :-
        B is A + -1,
        階乗保存計算(B, D),
        C is A * D,
        asserta((階乗保存計算(A, C):-!)).

true.

listing は現在の述語定義を示す、処理系のサービス述語である。

組込述語 asserta や assertz を使えば、プログラムによるプログラムの生成が可能になる。それだけではなく、プログラムの実行中に追加プログラムコードを生成して、それを即実行することもできる。

リストの全ての要素が同じ

リスト要素が全て同じ。検査述語であると同時に、リストに変数を含む場合はそれを第二引数と単一化して全て同じ要素になるように企てる働きをする。

全ての要素が同じ([],_).
全ての要素が同じ([A|R],A) :-
        全ての要素が同じ(R,A).

実行例

?- 全ての要素が同じ([2,2,2],2).
true.<sub></sub>

?- 全ての要素が同じ([2,2,3],2).
false.

?- 全ての要素が同じ([2,2,2],X).

X = 2

?- 全ての要素が同じ([X,Y,Z],0).

X = 0,
Y = 0,
Z = 0,

N個の空白からなるアトムを生成する

N個の空白からなるアトムを生成する。ここでは組込述語 length によって要素数N個の変数のリストを生成し、その要素全てを空白文字とした上で、文字のリストからアトムを生成するために、組込述語 atom_chars を使っている。

'N個の空白からなるアトムを生成する'(N,_アトム) :-
        length(L,N),
        全ての要素が同じ(L,' '),
        atom_chars(_アトム,L).

実例を示す。

?- 'N個の空白からならアトムを生成する'(8,Atom).

Atom = '        '


上に示した定義は、全ての要素が同じ/2が既に用意されていることを前提に、空白からなるアトムを作ったが、
<source lang="prolog">
'N個の空白からなるアトムを生成する'(N,_アトム) :-
        findall(' ',between(1,N,_),L),
        atom_chars(_アトム,L).

でよく、この定義の空白と指定された部分を抽象して、同一文字からなるアトムの定義は

'N個の同一文字からなるアトムを生成する'(N,_文字,_アトム) :-
        findall(_文字,between(1,N,_),L),
        atom_chars(_アトム,L).

でよい。

ヘッドゼロサプライ

事務計算などでは、123という整数を8桁の数値表現で、しかも頭部を空白ではなく0で埋めることを要求されることがある。

これを上記 全ての要素が同じ を使って定義する。最初に枠を取り、頭部の桁不足の部分は 全ての要素が同じ を使って 0 を埋めている。

ヘッドゼロサプライ(_桁数,_数値,_ヘッドゼロサプライ数値表現) :-
        length(_桁数枠のリスト,_桁数),
        number_chars(_数値,_数字のリスト),
        append(_頭部の枠リスト,_数字のリスト,_桁数枠のリスト),
        全ての要素が同じ(_頭部の枠リスト,'0'),
        atom_chars(_ヘッドゼロサプライ数値表現,_桁数枠のリスト).

number_chars、atom_chars ともに組込述語で、それぞれ、数値を分解して数字リストに、アトムを分解して文字リストとする。

頭部の枠リストの桁（要素数）は述語 append が決定する。

実行例

?- ヘッドゼロサプライ(8,123,X).
X = '000000123'

?-

ヘッドゼロサプレスの定義は、

ヘッドゼロサプレス(_桁数,_数値,_ヘッドゼロサプレス数値表現) :-
        length(_桁数枠のリスト,_桁数),
        number_chars(_数値,_数字のリスト),
        append(_頭部の枠リスト,_数字のリスト,_桁数枠のリスト),
        全ての要素が同じ(_頭部の枠リスト,' '),
        atom_chars(_ヘッドゼロサプレス数値表現,_桁数枠のリスト).

変数名を変更したが実質的には 全ての要素が同じ の第二引数を変更するだけの違いである。

ユークリッドの互除法によって最大公約数を求める

ユークリッドの互除法によって最大公約数を求める。

数値演算の場合、他の言語とそれほど変わらない。Prologの特徴を求めるならば出力用の引数が必要とされることだろう。

最大公約数(N,_最大公約数,_最大公約数) :-
        0 is N mod _最大公約数.
最大公約数(N,M,_最大公約数) :-
        M_2 is N mod M,
        最大公約数(M,M_2,_最大公約数).

実行例

?- 最大公約数(49,28,X).
X = 7

?-

エラトステネスの篩

n以下の全ての素数をリストに集める。エラトステネスの篩を述語として定義し、これを呼び出す。

最初の述語 n以下の素数 の冒頭で、2から始まりnまで連続する整数のリストを組込述語 findall と between を使って生成する。代表的な生成パターンである。

このリストを対象に小さい順に素数を探し、その素数の倍数をリストから削除して再帰的にエラトステネスの篩は実行される。

n以下の素数(_n以下,_n以下の全ての素数) :-
        findall(_数,between(2,_n以下,_数),_2以上_n以下の数リスト),
        エラトステネスの篩(_2以上_n以下の数リスト,_n以下の全ての素数).

エラトステネスの篩([],[]) :- !.
エラトステネスの篩([A|R1],[A|R2]) :-
        エラトステネスの篩(A,R1,L),
        エラトステネスの篩(L,R2).

エラトステネスの篩(_,[],[]) :-!.
エラトステネスの篩(N,[A|R1],R2) :-
        0 is A mod N,
        エラトステネスの篩(N,R1,R2),!.

エラトステネスの篩 の定義の中で findall　を使うと エラトステネス/3 は実は不要である。

エラトステネスの篩([],[]).
エラトステネスの篩([M|R1],[M|R2]) :-
        findall(N,(
                    member(N,R1),
                    \+(0 is N mod M)),
                L),
        エラトステネスの篩(L,R2).

どちらの定義が読みやすいかについては、常に問題となる。

この findall を エラトステネスの篩 の中に持つ

エラトステネスの篩([],[]) :- !.
エラトステネスの篩([M|R1],[M|R2]) :-
        エラトステネスの篩(M,R1,L),
        エラトステネスの篩(L,R2).

エラトステネスの篩(M,R1,L) :-
        findall(N,(
                    member(N,R1),
                    \+(0 is N mod M)),
                L).

が最も宣言的なエラトステネスの篩の定義かも知れない。

エラトステネスの篩 の方は、findall で生成される新たなリストが第一引数に置き換えられて再び駆動される。このような新しい対象を生成しつつ、ダイナミックに繰り返すパターンは、再帰的な定義以外に方法がない。

実行例

?- n以下の素数(32,L).
L = [2,3,5,7,11,13,17,19,23,29,31]

?- エラトステネスの篩([2,3,4,5,6,7,8,9,10,11,12,13,14],L).
L = [2,3,5,7,11,13]

?-

文字列の検索

文字列という場合、一般にアトムを指すが、String（文字コードのリスト）を指す場合もあり、少々曖昧である。ここではアトムを指すとする。

文字列の検索(_文字列,_検索語,_検索語の前方文字列,_検索語,_検索語の後方文字列) :-
        sub_atom(_文字列,_開始点,_文字列長,_残り文字列長,_検索語),
        sub_atom(_文字列,0,_開始点,_,_検索語の前方文字列),
        sub_atom(_文字列,_,_残り文字列長,0,_検索語の後方文字列).

sub_atom という極めてスーパーな非決定性の組込述語がこの機能の全てを司る。開始点は0オリジンであることに注意が必要。

sub_atom の仕様は (1) 第一引数にアトムがくる、(2) 第二引数には検索語の開始点がくる、(3) 第三引数には検索語の文字数、(4) 第四引数には検索が成功した時の残り文字列長、(5) 第五引数に検索語がくる。

実行例

?- 文字列の検索(abd126fgabyz,ab,X,Y,Z).

X = '',
Y = ab,
Z = d126fgabyz;
X = abd126fg,
Y = ab,
Z = yz;

False

上記検索パターン通じて、目標に _検索語がふたつ冗長に現れ、単一化を二重に行っている部分もあるが、将来、検索語に何らかの記号パターン(正規表現のような)が利用される可能性を考えて、ここではあえて検索語と検索結果の検索語が同じになることを承知の上で、一引数余分に確保している。

文字列の置換

ISO規格を含めて、ほとんどの処理系では正規表現がサポートされていない。Prologは文字列操作を得意とする言語だが、それでも複雑な置換パターンでは長い定義となることが多い。

最初に、置換対象が一つの単純な置換を考えよう。

文字列の置換(_対象文字列,_置換される副文字列,_置換する副文字列,_置換された文字列) :-
        sub_atom(_対象文字列,_開始点,_長さ,_残り長さ,_置換される副文字列),
        sub_atom(_対象文字列,0,_開始点,_,_前文字列),
        sub_atom(_対象文字列,_,_残り長さ,0,_後文字列),
        atomic_list_concat([_前文字列,_置換する副文字列,_後文字列],_置換された文字列).

atomic_list_concat はリスト要素を結合して新しいアトムを生成する。

実行例を示す。

?- 文字列の置換(いろはにほへと,はに,はは,_置換された文字列).

_置換された文字列 = いろははほへと

これはうまく行くが、複数置換対象が存在する場合を見てみよう。

?- 文字列の置換(生垣作るその生垣を,生垣,八重垣,_置換された文字列).

_置換された文字列 = 八重垣作るその生垣を;
_置換された文字列 = 生垣作るその八重垣を;

false.

置換対象が複数あっても、一ヶ所だけ置換するという場合もある。その場合には選択的に置換できるこの定義で良い。

しかしこの例もそうだが、対象となる副文字列全てを置換したいことも多い。結論を言ってしまえば、このようなバックトラックを使ったパターン(失敗駆動)では全置換は定義できない。

文字列の全置換(_対象文字列,_置換される副文字列,_置換する副文字列,_置換された文字列) :-
        置換対象の選択(_対象文字列,_置換される副文字列,_前文字列,_後文字列),
        文字列の全置換(_後文字列,_置換される副文字列,_置換する副文字列,_置換された後文字列),
        atomic_list_concat([_前文字列,_置換する副文字列,_置換された後文字列],_置換された文字列),!.
文字列の全置換(_文字列,_,_,_文字列).

置換対象の選択(_対象文字列,_置換される副文字列,_前文字列,_後文字列) :-
        sub_atom(_対象文字列,_開始点,_長さ,_残り長さ,_置換される副文字列),
        sub_atom(_対象文字列,0,_開始点,_,_前文字列),
        sub_atom(_対象文字列,_,_残り長さ,0,_後文字列).

一般に置換では、置換対象文字列が存在しなかった時、その副目標(質問)を偽としないで、元の文字列をそのまま残す。文字列の全置換 の第二節文字列の全置換(_文字列,_,_,_文字列). はそのために必要である。

ちょっとわかりにくいが、文字列の全置換 は再帰的な述語である。置換対象までとその後文字列に分割して、後文字列を再帰的に置換したものと、それまでの文字列を置換しながら結合する。

実行例

?- 文字列の全置換(生垣作るその生垣を,生垣,八重垣,_置換された文字列).

_置換された文字列 = 八重垣作るその八重垣を

これで二ヶ所の生垣を八重垣に置換できた。

リストの結合

リストの結合とは引数として与えられた二つのリストを最初のリストの最終要素の次から第二リストの最初の要素から順に付け加えて行って、一つのリストに纏めることを言う。この述語はほとんどの処理系で組込述語 append として特に利用者が定義しなくても済むが、述語定義技法としての観点からも Prolog を代表する述語であるため、ここでは append 述語が Prolog でどのように定義されるかを紹介する。

リストの結合(L1,L2,L) :- append(L1,L2,L).

appendは2つのリストを結合する

append([],L,L).
append([E|L1],L2,[E|L]) :- append(L1,L2,L).

実行例

?- append([a,b],[1,2,3],L).
L = [a,b,1,2,3]

appendの意味は結合に留まらない。第一引数、第二引数に変数が来るとリストを分解する。 実は非決定性の述語としての代表でもある。

?- append(X,[2,3],[1,2,3]).
X = [1]

?- append(X,Y,[1,2,3]).
X = [],
Y = [1,2,3];
X = [1],
Y = [2,3];
X = [1,2],
Y = [3];
X = [1,2,3],
Y = [];
false

となる。さらに以下のように使用するとappendは実はmemberのスーパーセットであることがわかる。

?- append(L1,[X|L2],[ワカメ,マスオ,タラオ]).
L1 = [],
X  = ワカメ,
L2 = [マスオ,タラオ];
L1 = [ワカメ],
X  = マスオ,
L2 = [タラオ];
L1 = [ワカメ,マスオ],
X  = タラオ,
L2 = [];
false

ここで注目するべきことは、このような使い方の append に於いては、切り出したい情報とその情報のリスト前部、リスト後部の情報を同時に取得できることである。例えば切り出した情報（上の定義例では X）の前部や後部にXが含まれていないか検査などが可能になる。これは member においては不可能なことである。

append は多義的な述語であり、同時に Prolog を代表する述語でもあるため、機能に見合った述語名をリストの結合、リストの分解という具合に与えるか、それとも、通りのよい append 一本で貫くか迷うことが多い。ここではこの述語定義を理解、記憶してもらうためにもっぱら append で通したが、それぞれ別の述語名を与えて利用するのが本来の Prolog の姿であろう。

リストの結合(L1,L2,L) :- append(L1,L2,L).

リストの分解(L1,L2,L) :- append(L1,L2,L).

四引数以上のリストの結合

引数が3のappendを示したが、4引数以上のものも便利である。

?- append(L1,[X,Y],L3,[a,b,c,d]).
L1 = [],
X = a,
Y = b,
L3 = [c,d];
L1 = [a],
X = b,
Y = c,
L3 = [d];
L1 = [a,b],
X = c,
Y = d,
L3 = [];
false.

このように、中間のリストの前のリスト、後のリストという分解が簡単にできる。この append/4 の定義は append/3 の定義を利用して

append([],L2,L3,L4) :-
        append(L2,L3,L4).
append([E|L1],L2,L3,[E|L4]) :-
        append(L1,L2,L3,L4).

である。

さらに append/4 ができれば、 append/5 は

append([],L2,L3,L4,L5) :-
        append(L2,L3,L4,L5).
append([E|L1],L2,L3,L4,[E|L5]) :-
        append(L1,L2,L3,L4,L5).

となっていく。一引数少ない append の定義ができていれば、このように簡単に追加できる。

文字リストに変換して文字列を検索

先に文字列の検索を組込述語 sub_atom を使うことで例題とした。ここでは一旦、アトムとしての文字列を文字を要素とするリストに変換して検索する例を示す。この場合、検索語も文字のリストに変換する。

文字列の検索(_文字列,_検索語,_検索語の前方文字列,_検索語,_検索語の後方文字列) :-
        文字列と検索語を文字リストに変換(_文字列,_検索語,_文字リスト,_検索文字リスト),
        文字リストの検索(_文字リスト,_検索文字リスト,_検索語の前方文字リスト,_検索文字リスト,_検索語の後方文字リスト),
        '検索語の前方文字リスト、検索文字リスト、検索語後方の文字リストを文字リストから文字列に変換'(_検索語の前方文字リスト,_検索文字リスト,_検索語の後方文字リスト,_検索語の前方文字列,_検索語,_検索語の後方文字列).

文字列と検索語を文字リストに変換(_文字列,_検索語,_文字リスト,_検索文字リスト) :-
        atom_chars(_文字列,_文字リスト),
        atom_chars(_検索語,_検索文字リスト).

文字リストの検索(_文字リスト,_検索文字リスト,_検索語の前方文字リスト,_検索文字リスト,_検索語の後方文字リスト) :-
        append(_検索語の前方文字リスト,L2,_文字リスト),
        append(_検索文字リスト,_検索語の後方文字リスト,L2),

'検索語の前方文字リスト、検索文字リスト、検索語後方の文字リストを文字リストから文字列に変換'(_検索語の前方文字リスト,_検索文字リスト,検索語の後方文字リスト,_検索語の前方文字列,_検索語,_検索語の後方文字列) :-
        atom_chars(_検索語の前方文字列,_検索語の前方文字リスト),
        atom_chars(_検索語,_検索文字リスト),
        atom_chars(_検索語の後方文字列,_検索語の後方文字リスト).

「検索語の前方文字リスト、検索文字リスト、検索語の後方文字リストを文字リストから文字列に変換」がシングルクォートで囲まれて定義されているのは、途中に「、」が含まれているからである。規格で定められてはいないが、全角の記号は将来全角文字のみで処理系が利用される可能性から、記号扱いにしている処理系が多い。述語文字リストの検索/5 では、上記のリストの結合 append が、リストの結合というより分解として二つ連続して利用されている。

文字列を検索パターンを用いて検索

すでに文字列の検索を sub_atom を用いた例を示したが、一般に文字列の検索は atom_chars を用いて一旦文字のリストに変換してから検索するほうが定義が柔軟になる。

:- dynamic(パターン照合/2).

文字リストに変換しての検索(_文字列,_検索パターンリスト,_前文字列,_適合文字列,_後文字列) :-
        atom_chars(_文字列,_文字リスト),
        リストによる検索(_前文字列リスト,_適合文字リスト,_後文字リスト,_文字リスト),
        パターン照合(_検索パターンリスト,_適合文字リスト),
        atom_chars(_前文字列,_前文字リスト),
        atom_chars(_適合文字列,_適合文字リスト),
        atom_chars(_後文字列,_後文字リスト).

リストによる検索([],L2,L3,L4) :-
        append(L2,L3,L4).
リストによる検索([A|R1],L2,L3,[A|R4]) :-
        リストによる検索(R1,L2,L3,R4).

この述語の利用者は、検索する前に述語パターン照合/2 を定義する。リストによる検索/4 は append/4 として知られる述語。

append/3 を member/2 として使う

?- append(L1,[A|L2],[1,2,3,4]).

に極めて近いが、Aは単項としか単一化できないのに対して、リストによる検索/4 のL2は複数項のパターンを切り取ることができる点が違う。

実例を示す。"八重"から始まり"に"で終わる文字列を検索する。

?- assertz((パターン照合(L,L) :-
        L = [八,重|R],append(L1,[に],R))).

?- 文字リストに変換しての検索(八雲立つ出雲八重垣妻籠みに八重垣作るその八重垣を,L,_前文字列,_適合文字列,_後文字列).

_前文字列 = 八雲立つ出雲,
L = [八,重,垣,妻,籠,み,に],
_適合文字列 = 八重垣妻籠みに,
_後文字列 = 八重垣作るその八重垣を;

false.

ここでは検索パターンリストに変数を置いている。最初に[八,重]が来て文字がわからないリストが来て、そして最後に[に]が来る。Prolog では、このようにパターンを一つのリストで表現することはできない。それでここは変数にして、パターン照合 述語に解決を委ねている。

リスト要素の隣／リスト要素の両隣

append を利用してリスト要素の隣を定義してみよう。極めて宣言的な定義となる。

リスト要素の隣(_リスト,_要素,_隣の要素) :-
        append(_,[_隣の要素,_要素|_],_リスト).
リスト要素の隣(_リスト,_要素,_隣の要素) :-
        append(_,[_要素,_隣の要素|_],_リスト).

さらに、リスト要素の両隣は

リスト要素の両隣(_リスト,_要素,_隣の要素_1,_隣の要素_2) :-
        append(_,[_隣の要素_1,_要素,_隣の要素_2|_],_リスト).
リスト要素の両隣(_リスト,_要素,_隣の要素_1,_隣の要素_2) :-
        append(_,[_隣の要素_2,_要素,_隣の要素_1|_],_リスト).

実行例

?- リスト要素の隣([a,b,c],X,Y).
X = a,
Y = b;
X = b,
Y = a;
X = b,
Y = c;
X = c,
Y = b

?- リスト要素の隣([a,b,c,d,e,f,g],b,f).
false.

?- リスト要素の隣([a,b,c,d,e,f,g],e,d).
true.

?- リスト要素の両隣([a,b,c,d,e,f,g],e,Y,Z).
Y = d,
Z = f;
Y = f,
Z = d

二つの隣要素が第三引数と第四引数に出現順に入るのだと決めておけば定義は

リスト要素の両隣(_リスト,_要素,_左隣の要素,_右隣の要素) :-
        append(_,[_左隣の要素,_要素,_右隣の要素|_],_リスト).

となる。これが自然な定義であろう。

しかし、「リスト要素の両隣」がこの述語の仕様であったとすると、左右の順序や出現順はどこにも示唆されていないと考えることがむしろ素直であり、上記の左右順あるいは右左順の二節とする定義も成立するのである。

リスト要素の反転

リストの要素の反転は reverse が組込述語になっているが、ここでは、これを定義してみる。

リスト要素の反転([],[]).
リスト要素の反転([A|R1],L) :-
        リスト要素の反転(R1,L2),
        append(L2,[A],L).

append を使った明解な宣言性の強い定義であるが、実行速度が遅いことからこの定義はあまり使わることがない。

普通、リストの反転の定義には、以下のように二つの述語に分解して定義する。ただしこの定義は完全ではない。正しい定義は最後に示す。

リスト要素の反転(L1,L2) :-
        リスト要素の反転(L1,[],L2).

リスト要素の反転([],L,L).
リスト要素の反転([A|R1],L1,L) :-
        リスト要素の反転(R1,[A|L1],L).

リスト要素の反転 の方の第二節 A に着目して欲しい。第二引数で受け取ったリストの前に追加しているが、最初が [] だから、先頭から順に末尾から付加されていくことになる。第一節の主張は、第一引数が [] になった時には、第二引数に反転したリストが積み上がっているはず、ということである。

実行例

?- リスト要素の反転([a,b,c],L).

L = [c,b,a]

さらに、

?- リスト要素の反転(L,[a,b,c]).

L = [c,b,a]

述語の双方向性も確かめられたと思いがちだが、そうはいかない。

?- リスト要素の反転(L,[a,b,c]).

L = [c,b,a];

%%%  解を示さなくなり、やがて、多くの処理系で内部メモリが足りなくなりエラーとなる(スタックオーバーフロー) %%%

エラー状態が生成されていく過程は興味深いのだが、複雑で難解になり過ぎるため、どのような経過で内部メモリがなくなっていくかはここでは示さない。このような基礎的な述語定義の中に重大なエラーが潜む余地があることは Prologの弱点と考えるべきである。

以下はこのエラーに対する対策の一例である。

リスト要素の反転(L1,L2) :-
        リスト要素の反転(L1,[],L2).

リスト要素の反転([],L,L) :- !.
リスト要素の反転([A|R1],L1,L) :-
        リスト要素の反転(R1,[A|L1],L).

リスト要素の反転/3 の方の第一節にカットを入れる。これで上記エラーは回避できる。

最初に示した append を利用した定義ではこのようなことは起こらない。それで、あまり使われることがないとしながらも、こちらの定義を最初に載せた。

文字列の反転

"文字列" という文字列を反転して "列字文" という文字列を生成する文字列の反転/2 を定義する。組込述語 atom_chars と上記定義した リストの反転 を組み合わせる。

文字列の反転(_文字列,_反転した文字列) :-
        atom_chars(_文字列,_文字のリスト),
        リストの反転(_文字のリスト,_反転した文字のリスト),
        atom_chars(_反転した文字列,_反転した文字のリスト),

ここでは一旦文字のリストに変換している。それによってリストの反転/2が利用できた。

ただし、元の文字列の形式に atom_chars をもう一度使って戻さなくてはならない。

atom_chars でリストに変換せずに、文字列の反転/2を定義できるが、以下のような難しい定義となる。

文字列の反転(_文字列,_反転した文字列) :-
        文字列の反転(0,_文字列,_反転した文字列).

文字列の反転(N文字目,_文字列,_文字) :-
        sub_atom(_文字列,N文字目,1,0,_文字).
文字列の反転(N文字目,_文字列,_副文字列) :-
        sub_atom(_文字列,N文字目,1,_,_反転した文字列),
        N_1文字目 is N文字目 - 1,
        文字列の反転(N_1文字目,_文字列,_反転した文字列_1),
        atom_concat(_反転した文字列_1,_文字,_反転した文字列).

組込述語 atom_concat が使われた。アトムとアトムを結合して別の長いアトムを生成する述語である。

文字列の反転の例を示す。

?- 文字列の反転(文字列,X).
X = 列字文

?-

回文

回文とは先頭から読んでも、末尾から反対に文字をたどって読んでも、同じ文になるある程度意味の通る文のことである。ここでの定義は回文を生成するのではなく、回文であるかどうかの検査である。ここでは「なかきよのとおのねふりのなふめさめふなのりふねのおとのよきかな」（長き夜の遠の睡りの皆目醒め波乗り船の音の良きかな）のように、文字の並びを対象とする。

回文(_回文) :-
        atom_chars(_回文,Chars),
        リストの反転(Chars,Chars).

一旦組込述語 atom_chars で文字のリストに変換する。ここまではいわば定石のようなものだが、回文の場合はここから、そのリストを反転し、引数が共通であることを示して、反転前と反転後が同じなのが回文であると宣言している。実例はもちろん

?- 回文(なかきよのとおのねふりのなふめさめふなのりふねのおとのよきかな).
true.

?-

である。

`above`、到達可能性

above(X,Y) :-
        on(X,Y).
above(X,Y) :-
        on(X,Z),
        above(Z,Y).

ここで on の定義は具体的に定義する。例えば、

on(波平,サザエ).
on(サザエ,カツオ).

実行例

?- above(波平,X).
X = サザエ;
X = カツオ;
False
?= above(波平,カツオ).
True

一つ以上離れた関係を above の第二節でので定義で、引数の変数を on を経ながら X - Z - Y と連鎖することによって表現している。

経路が以下のような定義の時、ある駅から別の駅に到達できるかを示す 到達可能性 の定義は。

経路(渋谷,神泉).
経路(神泉,駒場東大前).
経路(駒場東大前,池の上).
経路(池の上,下北沢).

到達可能性(_駅_1,_駅_2) :-
        経路(_駅_1,_駅_2).
到達可能性(_駅_1,_駅_2) :-
        経路(_駅_1,_駅_3),
        到達可能性(_駅_3,_駅_2).

実行例

?- 到達(神泉,下北沢).
true.

検索は、(神泉,駒場東大前) → (駒場東大前,池の上) → (池の上,下北沢) と進み、第一節の本体で :- 経路(池の上,下北沢). が真となることにより、到達可能性は真となる。この定義を見比べると、経路/到達可能性とon/aboveの関係が同じアルゴリズムであることがわかる。

失敗駆動

単位節要素の加算の例に示された"年齢"のような単位節（本体定義なのない節）を定義順に表示するには普通失敗駆動を利用する。年齢の定義次の通りだとする。

年齢(山田,35).
年齢(大島,20).
年齢(清川,28).

ここでは定義順に氏名,年齢を全て表示する方法を示す。

年齢表示 :-
      年齢(_氏名,_年齢),
      writef('%t,%t\n',[_氏名,_年齢]),
      fail.

表示は組込述語 writef を使っている。無条件に偽になる組込述語があるため、バックトラックが起こり順に述語 年齢 の各節が呼び出されて表示される。これが失敗駆動だ。最終的には年齢/2の呼び出しは偽となるため、質問は False で終わる。

実行例

?- 年齢表示.
山田,35
大島,20
清川,28
false.

?-

一般に必ず偽となって終わる定義は、これを再利用する際に不都合が生じる場合が多い。真として終了するためには、

年齢表示 :-
      年齢(_氏名,_年齢),
      writef('%t,%t\n',[_氏名,_年齢]),
      fail.
年齢表示.

と書き加えるのみである。

失敗駆動を用いることなく、再帰を使って上記の年齢を表示することは案外と難しい。

年齢表示 :-
      findall([_氏名,_年齢],年齢(_氏名,_年齢),L),
      再帰による年齢表示(L).

再帰による年齢表示([]).
再帰による年齢表示([[_氏名,_年齢]|R]) :-
      writef('%t\n',[_氏名,_年齢]),
      再帰による年齢表示(R).

完全に独立した存在である定義節から、情報の連関を付与されたものとしてのリストを得るために、findall　をここでも使用した。実はこの findall の中に失敗駆動が含まれている。つまり、ここでは findall を使うことによって失敗駆動を隠蔽していることになる。

`repeat`

repeat の定義は以下の通り単純である。

repeat.
repeat :- repeat.

repeat 自体は究極の再帰プログラミングである。問題はこれをどのように使用するかで、

?- repeat,read(X),write(X),nl,X=end_of_file.
|: abc.
abc
|: 123.
123
|: end_of_file.
end_of_file

X = end_of_file

repeat は再帰述語ではあるが、失敗駆動の起点としてのみ利用される。

repeatに制御が返ってくるのは、後続する副目標が完全に失敗したときである。repeatまで制御は戻り、再び後続する副目標が実行される。まったく最初と同じ状態に戻って実行される。ということは、本来述語定義や定義された節の引数は実行中に書き換えないことが基本なので、後続の副目標を何度繰り返しても同じ結果となり、停止しないはずである。したがってrepeatを含む節がプログラマの期待通り停止するためには、その後続の副目標の実行に副作用があることが前提となる。この副作用による変化を読み取ってrepeatの節を停止するように工夫する。上記の場合、

X = end_of_file.

がそれである。

次に、四季 という検索述語を repeat の前に置いてみる。

四季(春).
四季(夏).
四季(秋).
四季(冬).

?- 四季(_季節),repeat,read(X),write(X),nl,X=end_of_file.
|: abc.
abc
|: 123.
123
|: end_of_file.
end_of_file

_季節 = 春,
X = end_of_file,

季節 の選択が春から先に進んでいない。副目標 四季 には repeat があるためバックトラックしてこないことになる。

行入力

前節ですでに用いたが、Prolog には入力述語として古くから、1引数と2引数の read が存在した。この入力述語の魅力はアトム、数値、リストを含む複合項など、どんな項でも入力可能である点にある。

?- read(X).
|: 33.

X = 33.

?- read(X).
|: a(b,c).

X = a(b,c)

?-

のように使う。注意するべきことは、プロンプト |: の後の入力には正しく項が来なくてはならず、しかも、入力はピリオドで終了する必要がある。

ごく一般的なカンマ区切りの「abc,def」の入力はシングルクォートで囲み「'abc,def'.」でなくてはならないことになる。これでは実務的には不自由なので、文字列が改行されて終了するまでを、アトムとして受け取る 行入力 を定義してみる。

行入力(X) :-
        get_char(C),
        行入力_1(C,Chars),
        atom_chars(X,Chars) .

行入力_1('\n',[]) :- !.
行入力_1(end_of_file,[]) :- !.
行入力_1(C,[C|R]) :-
        get_char(C2),
        行入力_1(C2,R).

これで改行によって、それまで入力された文字が一旦リストに収められ、それを atom_chars で変換して、アトムとして受け取ることができるようになった。ただし、入力はアトムだけに限られる。この点は read が項であったのとは異なる。

行入力_1 の第二節に現れる end_of_file であるが、これは改行ではなくファイルの終端を意味する情報が入力されたことを意味する。この独特なアトムを Prolog では伝統的に用いている。

実行例

?- 行入力(X).
abc,def

X = 'abc,def'

今度は |: のプロンプトが表示されない。このプロンプトの表示は項入力述語 read のいわばサービスであって、同じく組込述語であるが、get_char では表示されない。

入力検査

整数入力 は repeat によく似ているが、第一節の末尾にカットがあるため、失敗駆動の起点としての繰り返しにはならない。整数入力検査に失敗した場合のみ、整数入力を繰り返す。

整数入力(_整数) :-
        行入力(_行入力),
        整数入力検査(_行入力,_整数),!.
整数入力(_整数) :-
        整数入力(_整数).

整数入力検査(_行入力,_整数) :-
        atom_to_term(_行入力,_整数,_),
        integer(_整数),!.
整数入力検査(_行入力,_) :-
        writef('入力された文字列%tは整数ではありません。再入力をお願いします。\n',[_行入力]),
        fail.

atom_to_term は組込述語であり、アトム（文字列）を受け取りこれを解析して、Prolog の項に変換している。整数でない情報を受け取った時にその情報を表示させるためには、get_line と同じ本体の中で、処理することが必要である。

整数入力 の第二節で表示することは、この節が引数から get_char で得た情報を受け取っていない以上不可能である。入力エラーを表示させる際に、入力された文字列も共に表示したいのであるが、第一節の本体内の副目標でない限り、引数からこの情報を受け取ることはできない。

実行例

?- 整数入力(X).
33
X = 33

?- 整数入力(X).
abc
入力されたabcは整数ではありません。再入力をお願いします。
8
X = 8

?-

整数入力 述語は repeat を使っても書くことができる。

整数入力(_整数) :-
        repeat,
        行入力(_行入力),
        整数入力検査(_行入力,_整数),!.

repeat とほとんど同型の再帰述語の整数入力の代わりに repeat 自体を挿入することによって上記のように失敗駆動的な整数入力述語が定義できることは実に興味深い。

整数入力(_整数) :-
        行入力(_行入力),
        整数入力検査(_行入力,_整数),!.
整数入力(_整数) :-
        整数入力(_整数).

repeat.
repeat :-
        repeat.

member(H,[H|T]).
member(H,[_|T]) :-
        member(H,T).

append([],L,L).
append([U|X],Y,[U|Z]) :-
        append(X,Y,Z).

整数入力の主述語と Prolog を代表する述語 repeat、member、append を比較した見た。極めて類似したパターンの述語であることが分かる。

キュー操作

Prolog ではキュー操作を差分リスト(重リストともいう)を使って表現している。差分リストとは二つのペアとなったリストを設定し、第二リストの全てが、第一リストの末尾に来るようにしたものである。第一リストのなかで第二リストと重ならない部分が、示したい情報・生きた情報である。例を示す。

第一リスト 第二リスト 示したい情報
[1,2,3,4]  [3,4]      [1,2]
[x,y,z]    [y,z]      [x]
[1,2,3|X]  [3|X]      [1,2]
[1,2,3|X]  [2,3|X]    [1]
[1,2,3|X]  X          [1,2,3]

キュー操作では、もっぱらこの最後の表現を使う（[1,2,3|X] X → [1,2,3]）。ここでは、直感的理解を深めるためオペレータ「-」を使って（すなわち複合項として）キューを表現してみる。

makeEmptyQueue(X-X).
emptyQueue(X-Y) :- X == Y.
dequeue(_要素,[_要素|X]-Y,X-Y).
enqueue(_要素,X-[_要素|Y],X-Y).

[1,2,3|X] のような構造を不完全データ構造と呼ぶ。[1,2,3,4] のように完結していないという意味で。しかし、すでに多くのプログラム例を見てきたが、append に代表されるように、Prolog の引数部分はこの不完全データ構造で満ちている。構造の不完全な部分、すなわち変数部分に新たに情報構造を単一化することによって、そしてその末尾に再び不完全データ構造が来るようにすることで構造を成長させる。不完全データ構造の多用は Prolog プログラムの最も顕著な特徴である。キューの操作は、以下のようにキューを以前、以後と対にして（ここでは A,B B,C）持ち回ることで利用する。

?- makeEmptyQueue(A), ・・・ ,enqueue(2,A,B), ・・・ ,dequeue(E,B,C), ・・・

上記の例では、現在のキューは、最後の C と単一化された構造であるといえる。キュー C は現在は空である。E には 2 が取り出せた。ところで、上記のキュー定義では、オペレータ「-」を利用して直感的に差分を強調することによって宣言性を高めた。しかし、Prolog では、引数には極力、リストを排することはできないにしても、構造体を持たず、アトムのみで構成するほうがプログラムの見通しがよくなる。ここで、キュー操作を日本語に書き直しながら、定義を書き直す。

空のキューを生成する(X,X).

キューは空である(X,Y) :- X == Y.

キューから要素を取り出す(_要素,[_要素|X],Y,X,Y).

キューに要素を追加する(_要素,X,[_要素|Y],X,Y).

X と Y がペアであることが不明瞭になってしまったが、これで自然な定義である。

スタック操作

キュー操作が出てきたところでスタック操作について述べる。スタックの定義はさらに簡単である。

スタックを生成する([]).

スタックに要素を追加する(_pushされる要素,_push前のスタック,[_pushされる要素|_push前のスタック]).

スタックから要素を取り出す([_popされる要素|_pop後のスタック],_popされる要素,_pop後のスタック).

利用法は、

?- スタックを生成する(A), ・・ ,スタックに要素を追加する(2,A,B), ・・ ,スタックに要素を追加する(3,B,C), ・・ ,スタックから要素を取り出す(C,E,D), ・・・

上記の例では現在のスタックは、D であり、内容は [3] である。2 は一度プッシュされたがその後ポップされてしまった。

組合せ

リストによって与えられた集合要素のN個の組合せ。非決定性の述語である。

組合せ(X,1,[A]) :-
        member(A,X).
組合せ([A|Y],N,[A|X]) :-
        N > 1,
        N_1 is N - 1,
        組合せ(Y,N_1,X).
組合せ([_|Y],N,A) :-
        N > 1,
        組合せ(Y,N,A).

実行例

?- 組合せ([a,b,c,d],3,X).

X = [a,b,c];
X = [a,b,d];
X = [a,c,d];
X = [b,c,d];
false

全ての組合せを蒐集するには、findall を用いればよい。述語を非決定性に定義することを基本として、必要な場合に findall によって全解をリストに取得する。これは Prolog の代表的なプログラムスタイルである。

全ての組合せ(L,N,LL) :-
        findall(X,組合せ(L,N,X),LL).

実行例

?- 全ての組合せ([a,b,c,d],3,LL).

LL = [[a,b,c],[a,b,d],[a,c,d],[b,c,d]]

組合せの総数

異なるn個のものから異なるr個のものを選ぶ、組合せの総数は公式から、

nCr(N,R,X) :-
        U is N - R + 1,
        階乗(U,N,K1),
        階乗(R,K2),
        X is K1 // K2 .

と Prolog では定義される。階乗の定義はこのプログラム例の中で既出である。

findall を使い、組合せ が解を生成するごとに1をリストに格納することによっても、組合せの総数を求めることができる。

nCr(N,R,X) :-
        findall(1,組合せ(N,R,_),L),
        length(L,X).

ここでは、格納する値を1としたが、実はこれはアトム、数値、変数、何が来てもよい。

実行例

?- nCr(4,3,X).

X = 4

項複写

項を複写する。ただ、単なる複写ではない、大事な点がある。変数はそのまま複写することはしない。新たに別の変数を作り出して、それを複写元の変数があった構造上の同じ位置に置く。この述語は高階述語を使用し、かつそれが再帰の中で引数として引き継がれて行く場合に使用される。引数として受け取った高階の述語呼び出し項と基本的に同じ構造だが、変数だけは単一化されることのない項を作り出し、それを引数として渡す時の基礎とする。引数を受け取った時点と引き渡す時点の間で変数が単一化された場合、意図した同型の引き渡し述語とならず、再帰が失敗してしまうことを避けるために使用されることが多い。項複写のプログラムを示す前に、この高階述語の使用例を示してしまう。第一引数 P に述語が渡されることとする。

foo(P,X) :-
        項複写(P,Q),
        call(P),
        ・・・
        foo(Q,X).

P が単一化されてしまうと、次の再帰呼び出しでは、受け取った P とは単一化された、つまり、異なったデータを渡してしまうこととなる。Pの引数に変数があった場合そのことが起こる。引き続き変数で渡したいQであるが、これを単一化され具体化された値で渡してしまうことになる。往々にしてこの場合呼び出した再帰の副目標はプログラマの意図に反して偽となる。これを避けるために、この述語の入り口で P を複写して Q を作ってしまってそれを渡すようにする。

さて、本題に戻って項複写の定義は

項複写(P,P1) :-
        compound(P),
        同一構造を生成(P,P1,A),
        項引数複写(1,A,P,P1),!.
項複写(P,P1) :-
        var(P),!.
項複写(P,P).

同一構造を生成(P,P1,A) :-
        functor(P,F,A),
        functor(P1,F,A).

項引数複写(M,N,P,P1) :-
        M > N,!.
項引数複写(M,N,P,P1) :-
        '1引数を再帰的に項複写'(M,P,P1),
        M1 is M + 1,
        項引数複写(M1,N,P,P1).

'1引数を再帰的に項複写'(M,P,P1) :-
        arg(M,P,T),
        arg(M,P1,T1),
        項複写(T,T1).

第一引数に複写前の項、第二引数に複写後の項がくる。項複写/2の第二節 P,P1 と変数が異なっている点が重要である。functor、arg は組込述語。functor は項を関数とアリティに分解する。arg は項の引数に値を与える。compound も組込述語で引数が複合項であるかどうか検査する。述語 1引数を再帰的に項複写 は第一文字が数字であるためシングルクォートで囲われている。

実行例

?- 項複写(a(b,U,c(V,W),d),X).

U = _1,
V = _2,
W = _3,
X = a(b,_4,c(_5,_6),d)

項複写された変数は元の変数とは別のものなので、逆にこの変数を単一化する必要がある場合は、どこに変数があるか、あるいは何に単一化すればよいかわからないという事態が生じる。その可能性に対処するためには項複写を少し拡張する。ここで、項複写<code> の引数の数を増やし、第三引数に複写元の項の変数、第四引数に複写先の項の変数をそれぞれ順序正しくリストに取れるようにする。


項複写(P,P1,VL1,VL2) :-
        compound(P),
        同一構造を生成(P,P1,A),
        項複写(1,A,P,P1,VL1,VL2),!.
項複写(P,P1,[P],[P1]) :-
        var(P),!.
項複写(P,P,[],[]).

同一構造を生成(P,P1,A) :-
        functor(P,F,A),
        functor(P1,F,A).

項引数複写(M,N,P,P1,[],[]) :-
        M > N,!.
項引数複写(M,N,P,P1,VL1,VL2) :-
        ひとつの引数を再帰的に項複写(M,P,P1,V3,V4),
        M1 is M + 1,
        項引数複写(M1,N,P,P1,VL5,VL6),
        append(VL3,VL5,VL1),
        append(VL4,VL6,VL2),!.

ひとつの引数を再帰的に項複写(M,P,P1,V3,V4) :-
        arg(M,P,T),
        arg(M,P1,T1),
        項複写(T,T1,V3,V4).
これで以下の実行例に見られるように、引数の対応を取ることができる。
実行例

?- 項複写(a(b,U,c(V,W),d),X,L1,L2),V = 8.

U = _1,
V = 8,
W = _3,
X = a(b,_4,c(_5,8),d),
L1 = [U,8,W],
L2 = [_4,8,_6]
挿入ソート
プログラム例全体を通して、可能な限り述語名を日本語にしてきた。ここでもソートには整列という語があるが、一般にソートが使われる機会が圧倒的に多い。それでここは挿入ソートとした。与えられたリストを昇順にソートする挿入ソートのプログラムを示す。

挿入ソート(L1,L2) :-
        挿入ソート(L1,[],L2).

挿入ソート([],L,L).
挿入ソート([A|R],L1,L) :-
        挿入(A,L1,L2),
        挿入ソート(R,L2,L).

挿入(A,[],[A]).
挿入(A,[B|R],[A,B|R]) :-
        A @=< B,!.
挿入(A,[B|R1],[B|R2]) :-
        A @> B,
        挿入(A,R1,R2).

空のリストから始めて一要素ずつ取り出し、整列した状態で成長するリストの適切な位置に挿入するという述語である。降順の挿入ソートの場合は <code>挿入 を

挿入(A,[],[A]).
挿入(A,[B|R],[A,B|R]) :-
        A @>= B,!.
挿入(A,[B|R1],[B|R2]) :-
        A @< B,
        挿入(A,R1,R2).

のように比較演算子を反転させればよい。ただ、これでは 挿入 が二通りできてしまうため、

昇順挿入(A,[],[A]).
昇順挿入(A,[B|R],[A,B|R]) :-
        A @=< B,!.
昇順挿入(A,[B|R1],[B|R2]) :-
        A @> B,
        昇順挿入(A,R1,R2).

降順挿入(A,[],[A]).
降順挿入(A,[B|R],[A,B|R]) :-
        A @>= B,!.
降順挿入(A,[B|R1],[B|R2]) :-
        A @< B,
        降順挿入(A,R1,R2).

のように明確に述語名を分けて定義するべきである。当然これら述語を副目標として呼び出す定義の述語名も 昇順ソート、降順ソート でなくてはならない。

クイックソート

与えられたリストを昇順にソートするクイックソートのプログラム例を示す。

quicksort([],[]).
quicksort([X|Xs], Ys) :-
        partition(Xs, X, Smaller, Bigger),
        quicksort(Smaller, L1),
        quicksort(Bigger, L2),
        append(L1, [X|L2], Ys).


partition([], _, [], []).
partition([X|Xs], Pivot, [X|Smalls], Bigs) :-
        X @< Pivot,
        partition(Xs, Pivot, Smalls, Bigs).
partition([X|Xs], Pivot, Smalls, [X|Bigs]) :-
        X @>= Pivot,
        partition(Xs, Pivot, Smalls, Bigs).

末尾再帰版（partitionは上に同じ）

quicksort(Xs, Ys) :-
        quicksort(Xs, [], Ys).

quicksort([], Ys, Ys).
quicksort([X|Xs], Ys_1, Ys) :-
        partition(Xs, X, Smaller, Bigger),
        quicksort(Smaller, [X|Ys_2], Ys),
        quicksort(Bigger, Ys_1, Ys_2).

限定節文法によって記述されたもの（partitionは上に同じ）

quicksort(Xs,Ys) :-
        quicksort(Xs,Ys,[]).

quicksort([])     --> [].
quicksort([X|Xs]) -->
       { partition(Xs, X, Smaller, Bigger) },
        quicksort(Smaller), [X], quicksort(Bigger).

Pivotとは軸要素のことである。

実行例。

?- quicksort([3,2,1,6],L).

L = [1,2,3,6]

?= quicksort([a,b,1,2],L).

L = [1,2,a,b]

?- quicksort([聖,徳,太子],L).

L = [太子,徳,聖]

?- quicksort([2,3,3,1,1,4],L).

L = [1,1,2,3,3,4]

実行例の最後に示すように、ここでの定義では Xs を集合と見なしていない。そのため重複する2番目以降の要素を削除することはしていない。

集合解 L = [1,2,3,4] を期待する場合は、partition の定義を

partition([], _, [], []).
partition([X|Xs], Pivot, [X|Smalls], Bigs) :-
        X @< Pivot,
        partition(Xs, Pivot, Smalls, Bigs).
partition([X|Xs], Pivot, Smalls, [X|Bigs]) :-
        X @> Pivot,
        partition(Xs, Pivot, Smalls, Bigs).
partititon([_|Xs], Pivot, Smalls, Bigs) :-
        X = Pivot,
        partition(Xs, Pivot, Smalls, Bigs).

と文字変更する。すなわち、6行目の「X @>= Pivot」を「X @> Pivot」に変更する。なぜならば、すでに同一の値は Pivot 自身として存在するからである。さらにそれだけだと同一要素が出現すると partition は失敗してしまうから、同一要素は無視することの宣言である第四節を加える。組込述語 sort は、この集合解が返ってくる仕様に決められている。

最後に昇順または降順を区別する問題は挿入ソートの部分で述べた方針で、このクイックソートも書き直す必要がある。

ハノイの塔

ハノイの塔は最も Prolog 向きの課題のひとつとして知られる。ここでは、N枚の円盤を三本の柱のうち、一番左の柱から右の柱に移すケースを示す。円盤は下から上に向かうほど小さくなるように積まれ、常にその状態が維持されなくてはならない。

:- op(500,xfx,から).
:- op(400,xf,へ).

ハノイの塔(N,_移動履歴) :-
        length(Ln,N),
        ハノイの塔(Ln,左柱,中柱,右柱,_移動履歴).

ハノイの塔([_],_左,_中,_右,[_左 から _右 へ]).
ハノイの塔([_|Ln],_左,_中,_右,_移動履歴) :-
        ハノイの塔(Ln,_左,_右,_中,_移動履歴_1),
        ハノイの塔(Ln,_中,_左,_右,_移動履歴_2),
        append(_移動履歴_1,[_左 から _右 へ|_移動履歴_2],_移動履歴).

冒頭、から を中置演算子、へ を後置演算子として定義している。それを使って _移動前の位置<code> から <code>_移動後の位置 という項を表現して、それを履歴として残している。

このプログラムは Prolog が宣言的であることを顕著に示す好例である。この述語で述べられていることは、三回が一組となって同じパターンが繰り返されるということ。さらに最も下の一枚が順に、この課題では右柱に積まれるのだが、新しい最下層の円盤が右柱の最上位に積まれた時には、それより上の塔は中柱、左柱と交互に完全に積み上がっている。それを、ハノイの塔述語の本体の二番目の副目標で、どちらの柱を起点として以後の移動を開始するかを、引数の位置を入れ替えることだけによって、表現している。このように全体の骨格と僅かな引数の置き換えだけによって、手続的動作の全てを暗示している。このような表現力に対して「宣言的」と言うのである。

実行例

?- ハノイの塔(4,L),
   member(A,L),
   writef('%t\n',[A]),
   fail;
   true.
左柱 から 中柱 へ
左柱 から 右柱 へ
中柱 から 右柱 へ
左柱 から 中柱 へ
右柱 から 左柱 へ
右柱 から 中柱 へ
左柱 から 中柱 へ
左柱 から 右柱 へ
中柱 から 右柱 へ
中柱 から 左柱 へ
右柱 から 左柱 へ
中柱 から 右柱 へ
左柱 から 中柱 へ
左柱 から 右柱 へ
中柱 から 右柱 へ
true.

?-

nクイーン

nクイーン問題も Prolog 向き問題の代表のひとつである。チェス盤が8×8であることから、8クイーンとして課題になることが多いが、ここでは盤面の大きさを一般化したnクイーンである。チェスのクイーンは縦横斜め、盤面の自分の位置から盤面の端までが全て利き筋となる駒である。この駒を各行に適宜ひとつずつ配置して、全てのクイーンの利き筋に他のクイーンがいないように、全ての列にクイーン配置せよという問題である。一つの解は列番号のリストで得られる。nクイーンの Prolog 定義は随分と工夫され、多くの作品がある。ここでは最も一般的な戦略の解法を示す。駒の利き筋という概念を示すために、可能な限り説明的な Prolog をコードを試みている。途中に現れる Qs という論理変数に、一つずつ解候補のクイーン位置が成長していく。

nクイーン(_nクイーン,_一解) :-
        '1からnまでの数リストを得る(縦横の利き筋はこれを行ごとに一つずつ選択することで回避される)'(_nクイーン,_数リスト),
        行ごとに順に駒を置き利き筋を調べて一解を得る(_数リスト,[],_一解).

行ごとに順に駒を置き利き筋を調べて一解を得る([],_一解,_一解).
行ごとに順に駒を置き利き筋を調べて一解を得る(_位置リスト,Qs,_一解) :-
        '駒の位置と残り駒の位置リストを得る(この選択自体が縦横の利き筋検査になっている)'(_駒の位置,
                                                                                               _位置リスト,_残り駒の位置リスト),
        斜めの利き筋に駒はない(_駒の位置,1,Qs),
        行ごとに順に駒を置き利き筋を調べて一解を得る(_残り駒の位置リスト,[_駒の位置|Qs],_一解).

'駒の位置と残り駒の位置リストを得る(この選択自体が縦横の利き筋検査になっている)'(_駒の位置,
                                                                          [_駒の位置|_残り駒の位置リスト],_残り駒の位置リスト).
'駒の位置と残り駒の位置リストを得る(この選択自体が縦横の利き筋検査になっている)'(X,[H|T],[H|T1]) :-
        '駒の位置と残り駒の位置リストを得る(この選択自体が縦横の利き筋検査になっている)'(X,T,T1).

斜めの利き筋に駒はない(_,_,[]).
斜めの利き筋に駒はない(Q,_隔たり,[Q1|Qs]) :-
        Q + _隔たり =\= Q1,
        Q - _隔たり =\= Q1,
        _隔たり_2 is _隔たり + 1,
        斜めの利き筋に駒はない(Q,_隔たり_2,Qs).

'1からnまでの数リストを得る(縦横の利き筋はこれを行ごとに一つずつ選択することで回避される)'(_nクイーン,_数リスト) :-
        findall(M,between(1,_nクイーン,M),_数リスト).

これは非決定的な述語である。

上記の定義では、表示幅の制限から引数の途中で改行している部分があるが、引数の区切りである「,」の前後であるならば、これは構わない。6クイーンの場合の実行例を示す。

?- nクイーン(6,L).
L = [5, 3, 1, 6, 4, 2] ;
L = [4, 1, 5, 2, 6, 3] ;
L = [3, 6, 2, 5, 1, 4] ;
L = [2, 4, 6, 1, 3, 5] ;
false.

?-

ここでは4つの解が得られたが、8クイーンだと92解になる。

有限オートマトン

言語 (ab)* を受理する決定性有限オートマトンと非決定性有限オートマトンのシミュレート。

%                               a             
%                  -------------------------->
%         状態_0                                 状態_1
%                  <--------------------------
%                               b
%
%          言語(ab)*を受理する決定性有限オートマトンの遷移
%

'言語(ab)*を受理する決定性有限オートマトン'(_記号ならび) :-
        '言語(ab)*初期状態'(_状態),
        '言語(ab)*を受理する決定性有限オートマトン'(_状態,_記号ならび).

'言語(ab)*を受理する決定性有限オートマトン'(_状態,[_記号|R]) :-
        '言語(ab)*'(_状態,_記号,_状態_1),
        '言語(ab)*を受理する決定性有限オートマトン'(_状態_1,R).
'言語(ab)*を受理する決定性有限オートマトン'(_状態,[]) :-
        '言語(ab)*終了状態'(_状態).

'言語(ab)*初期状態'(状態_0).

'言語(ab)*終了状態'(状態_0).

'言語(ab)*'(状態_0,a,状態_1).
'言語(ab)*'(状態_1,b,状態_0).


%
%                               a             
%                  -------------------------->
%       状態集合_0 {0}                         状態集合_1 {1}
%                  <--------------------------
%                               b
%
%          言語(ab)*を受理する非決定性有限オートマトンの遷移
%

'言語(ab)*を受理する非決定性有限オートマトン'(_記号ならび) :-
        '言語(ab)*初期状態'(_状態),
        '言語(ab)*を受理する非決定性有限オートマトン'(_状態,_記号ならび).

'言語(ab)*を受理する非決定性有限オートマトン'(_状態,[_記号|R]) :-
        '言語(ab)*'(_状態集合,_記号,_状態集合_1),
        状態集合(_状態集合,_状態),
        状態集合(_状態集合_1,_状態_1),
        '言語(ab)*を受理する決定性有限オートマトン'(_状態_1,R).
'言語(ab)*を受理する非決定性有限オートマトン'(_状態,[]) :-
        '言語(ab)*終了状態'(_状態).

'言語(ab)*初期状態'(0).

'言語(ab)*終了状態'(0).

'言語(ab)*'(状態集合_0,a,状態集合_1).
'言語(ab)*'(状態集合_1,b,状態集合_0). 

状態集合(状態集合_0,0).
状態集合(状態集合_1,1).

記号ならびが [a,b,a,b,a,b] のように a,b が対になって最後まで並んでいる場合だけ真となる。正規表現を正しく理解してプログラムテスト等に挑むためには、このようなコードの理解も必要である。

非決定性有限オートマトンを状態集合で記述したが、これを'言語(ab)*' に展開してしまうことも可能である。

例えば状態集合_1 が {1,2} である場合には、

'言語(ab)*'(0,a,1).
'言語(ab)*'(0,a,2).
'言語(ab)*'(1,b,0).
'言語(ab)*'(2,b,0).

と展開できる。複数行になるだけで、決定性有限オートマトンと形式的なの違いはなくなってしまう。決定性有限オートマトンは、このような複数の状態を書かないという約束事によって成立している。

上記、有限オートマトンと同等の Prolog 述語としての定義は、

'(ab)*'([]).
'(ab)*'([a,b|R]) :-
        '(ab)*'(R).

とこれも相当に短いコードとなる。

チューリングマシン

Prolog のチューリング完全性は、チューリングマシンをシミュレートすることで示すことができる。

turing(Tape0, Tape) :-
        perform(q0, [], Ls, Tape0, Rs),
        reverse(Ls, Ls1),
        append(Ls1, Rs, Tape).

perform(qf, Ls, Ls, Rs, Rs) :- !.
perform(Q0, Ls0, Ls, Rs0, Rs) :-
        symbol(Rs0, Sym, RsRest),
        once(rule(Q0, Sym, Q1, NewSym, Action)),
        action(Action, Ls0, Ls1, [NewSym|RsRest], Rs1),
        perform(Q1, Ls1, Ls, Rs1, Rs).

symbol([], b, []).
symbol([Sym|Rs], Sym, Rs).

action(left, Ls0, Ls, Rs0, Rs) :-
        left(Ls0, Ls, Rs0, Rs).
action(stay, Ls, Ls, Rs, Rs).
action(right, Ls0, [Sym|Ls0], [Sym|Rs], Rs).

left([], [], Rs0, [b|Rs0]).
left([L|Ls], Ls, Rs, [L|Rs]).

以下のルールは簡単なチューリングマシンの例である。状態遷移と動作を Prolog の節として表現している。

rule(q0, 1, q0, 1, right).
rule(q0, b, qf, 1, stay).

このチューリングマシンは単進符号化（1の並びで符号化）した数値に1を加える。つまり、任意個の1のセル上をループし、最後に1を追加する。

?- turing([1,1,1], Ts).
Ts = [1, 1, 1, 1] ;

この例から、状態間の関係を Prolog で表現することで、任意の計算が状態遷移のシーケンスとして宣言的に表現できることが分かる。

動的計画法

以下のPrologプログラムは動的計画法を使って2つのリストの最長共通部分列問題^[15]を多項式時間で求める。Prolog節によるデータベースを部分計算の結果のメモ化に用いている。

:- dynamic(stored/1).

memo(Goal) :-
       ( stored(Goal) -> true ; Goal, assertz(stored(Goal)) ).

lcs([], _, []) :- !.
lcs(_, [], []) :- !.
lcs([X|Xs], [X|Ys], [X|Ls]) :-
        !,
        memo(lcs(Xs, Ys, Ls)).
lcs([X|Xs], [Y|Ys], Ls) :-
        memo(lcs([X|Xs], Ys, Ls1)),
        memo(lcs(Xs, [Y|Ys], Ls2)),
        length(Ls1, L1), length(Ls2, L2),
        ( L1 >= L2 -> Ls = Ls1 ; Ls = Ls2 ).

実行例:

?- lcs([x,m,j,y,a,u,z], [m,z,j,a,w,x,u], Ls).
Ls = [m, j, a, u]

処理系

多くの処理系は Prolog の基本機能以外に、制約プログラミングや並行プログラミングのための拡張機能や Constraint Handling Rules などの各種言語をライブラリとして含んでいる。

処理系	オープンソース	有償・無償の別	準拠規格	備考
Amzi!Prolog	テンプレート:N/A	有償	ISO規格
AZ-Prolog	テンプレート:N/A	個人は無償	DEC-10 Prolog
B-Prolog	テンプレート:N/A	学術は無償	テンプレート:N/A
Ciao Prolog	○	テンプレート:N/A	ISO規格
GNU Prolog	○	テンプレート:N/A	ISO規格
Jekejeke Prolog	テンプレート:N/A	テンプレート:N/A	ISO規格
K-Prolog	テンプレート:N/A	有償	ISO規格	日本語対応
MINERVA	テンプレート:N/A	有償	ISO規格	業務用、Java ベース
Open Prolog	テンプレート:N/A	無償	ISO規格	Mac OS 用
Prolog Cafe	○	テンプレート:N/A	テンプレート:N/A	Prolog プログラムを Java プログラムに変換
Prolog.NET	○	テンプレート:N/A	テンプレート:N/A	.NET で Prolog を使用できる
P#	テンプレート:N/A	テンプレート:N/A	テンプレート:N/A	PrologプログラムをC# プログラムに変換
Qu-Prolog	テンプレート:N/A	テンプレート:N/A	テンプレート:N/A	マルチスレッド処理系
Rebol Prolog	テンプレート:N/A	テンプレート:N/A	テンプレート:N/A
SICStus Prolog	テンプレート:N/A	有償	ISO規格	多くのオペレーティングシステムに対応。Java や .NET でのウェブアプリケーション開発可能。
Prolog for Squeak	テンプレート:N/A	テンプレート:N/A	テンプレート:N/A	Squeak に統合された Prolog 環境
Strawberry Prolog	○	テンプレート:N/A	テンプレート:N/A
SWI-Prolog	○	テンプレート:N/A	ISO規格	多くのオペレーティングシステムに対応
TuProlog	テンプレート:N/A	テンプレート:N/A	テンプレート:N/A
Visual Prolog	テンプレート:N/A	個人は無償	テンプレート:N/A
XSB	○	テンプレート:N/A	テンプレート:N/A
YAP Prolog	○	テンプレート:N/A	ISO規格	Prolog コンパイラ。

国際会議

INAP — International Conference on Declarative Programming and Knowledge Management

脚注

元の位置に戻る ↑ ただし、コメントでそれらを代用することがよくあり、大体通用する表記法がある。引数の前に+を置けば入力、-を置けば出力、?ならばどちらにもなり得る。

参考文献

テンプレート:Refbegin

William F. Clocksin, Christopher S. Mellish: Programming in Prolog: Using the ISO Standard. Springer, 5th ed., 2003, ISBN 978-3540006787.
Leon Sterling, Ehud Shapiro: The Art of Prolog: Advanced Programming Techniques, 1994, ISBN 0-262-19338-8.
D.L. Bowen, L. Byrd, F.C.N. Pereira,L.M. Pereira and David H.D. Warren: DECsystem-10 PROLOG USER'S MANUAL, University of Edinburgh,1982.
ISO/IEC 13211: Information technology — Programming languages — Prolog. International Organization for Standardization, Geneva.
Robert Kowalski. The Early Years of Logic Programming, CACM January 1988.
Alain Colmerauer, Philippe Roussel. The birth of Prolog, in The second ACM SIGPLAN conference on History of programming languages, p. 37-52, 1992.
David H D Warren, Luis M. Pereira and Fernando Pereira, Prolog - the language and its implementation compared with Lisp. ACM SIGART Bulletin archive, Issue 64. Proceedings of the 1977 symposium on Artificial intelligence and programming languages, pp 109 - 115.
Buss, Samuel R., "On Herbrand's Theorem", in Maurice, Daniel; Leivant, Raphaël, Logic and Computational Complexity, Lecture Notes in Computer Science, Springer-Verlag, pp. 195–209. 1995.

テンプレート:Refend

脚注

テンプレート:Reflist

Prolog

目次

概要

述語論理と論理プログラミング

非述語論理的な立場

記号処理用言語・人工知能言語

宣言型言語

単一化

動的型付け

非オブジェクト指向言語

モジュラープログラミング

オンメモリデータベース

非決定性と双方向性

Prolog プログラミングの難しさ

歴史

誕生

コワルスキとDEC-10Prolog

新世代コンピュータ技術開発機構とProlog

1990年代とISO標準規格

人工知能ブームとProlog

ICOT以後の日本における衰退

今日

基本的な言語仕様

データタイプ

リスト

Prologプログラミング

質問

プログラムの起動と質問の自動実行

述語

宣言的意味と手続き的意味

論理変数

単一化

バックトラック

数式

カットと否定

高階述語とメタインタプリタ

リレーショナルデータベース

集合

構文解析

限定節文法

プログラム例

Hello world

家系図

孫の定義

リスト要素の加算

単位節要素の加算(集約問題)

相加平均

最大値、カットの用法

行列

行列の掛算

正方行列の対角要素

部分集合

階乗

階乗保存計算

リストの全ての要素が同じ

N個の空白からなるアトムを生成する

ヘッドゼロサプライ

ユークリッドの互除法によって最大公約数を求める

エラトステネスの篩

文字列の検索

文字列の置換

リストの結合

四引数以上のリストの結合

文字リストに変換して文字列を検索

文字列を検索パターンを用いて検索

リスト要素の隣／リスト要素の両隣

リスト要素の反転

文字列の反転

回文

above、到達可能性

失敗駆動

repeat

行入力

入力検査

キュー操作

スタック操作

組合せ

組合せの総数

項複写

挿入ソート

`above`、到達可能性

`repeat`