Prolog
| Prolog | |
|---|---|
| パラダイム | 論理プログラミング |
| 登場時期 | 1972年 |
| 設計者 | Alain Colmerauer 他 |
| 型付け | 動的型付け |
| 主な処理系 | AZ-Prolog, BProlog, Ciao Prolog, ECLiPSe, GNU Prolog, IF/Prolog, K-Prolog, Open Prolog, Poplog, Prolog Cafe, Prolog.NET, P#, SICStus Prolog, Strawberry Prolog, SWI-Prolog, YAP-Prolog |
| 影響を与えた言語 | Erlang, KL0,ESP,Guarded Horn Clauses, KL1,Concurrent Prolog,PARLOG, Mercury, Oz, Strand |
| プラットフォーム | クロスプラットフォーム |
Prolog（プロログ）は、非手続き型プログラミング言語の一つ。論理型言語に分類される。名称は、論理を使ったプログラミングを意味する英語「programming in logic」に由来している。
概要 [編集]
1972年ごろにフランスのアラン・カルメラウアーとフィリップ・ルーセルによって考案された[1]。
成立の事情から、Prologプログラムは論理式と見做され、その実行は述語論理によって述語が定義された環境に於ける定理証明に擬して解釈されることが多い。利用者は論理プログラミングの枠組みを、取り分け述語論理を学習することで、この枠組みに極めて忠実なこの言語の基礎的な構造のほとんどを理解できる。その言語仕様はこの枠組み以外には考案者たちも含めてそれ以上の拡張をほとんど行っていないため、他のプログラム言語とは異なり、学習しなくてはならない概念や用語もまた、述語論理に於けるものだけでこと足りる。この点はPrologプログラマにとって次々と湧き出てくるコンピュータサイエンスの新概念と無縁な位置を取れるため、極めて有利である一方、プログラミングの流行からは取り残されて孤立しがちである。
述語論理と論理プログラミング [編集]
Prologのプログラムは一階述語論理に基づいてデータ間の関係を示す命題として記述され、処理系がそれらに単一化(ユニフィケーション)と呼ばれるパターンマッチングを施しながら、与えられた命題が成立するか再帰的手続きによって探索している。
プログラムの実行は述語集合が定義された環境の元で、質問することによってなされるが、これは反駁という述語論理的な証明過程を模して、処理系が用意する導出木と呼ばれるグラフを辿って解を得る過程である。 Prolog のもととなるこの演繹手法は導出と呼ばれ、自動定理証明の研究において Prolog 開発以前よりよく知られていた。Prolog は、導出において節を頭部が一つの命題からのみなるホーン節に限定したものととらえる事が出来る。Prologが述語の形式をホーン節に限定した理由は、もし頭部に項の連言を認めるならば、導出時の計算量が爆発的に増大して、全ての解を得ることの保証が難しくなることが必至だからである。
述語論理を論理的な背景に持つことによって、Prologのプログラムはその正しさを確認することが比較的容易である。同時に、プログラマはPrologでプログラミングすることが何を意味するかを明確に理解した上で、プログラムを書いていくことができる。
非述語論理的な解釈 [編集]
上記はPrologの一つの解釈である。一方、Prologを述語論理という枠に嵌めないで捉える立場もある。導出、単一化、非決定性、双方向性、リレーショナルデータベースといったこの言語に独特の機能、記述力に着目し、そのプログラム言語としての可能性を率直に評価しようとするものだ。さらに、どの言語にも比して平坦で、平明な言語構造を持つPrologはラベル名(アトム、関数名、述語名)に適切な意味性を付与することにより、自然言語の領域にも接近したプログラミングが期待できる稀有な言語でもある。単一化という極めて単純なルールを基軸として、多分にパズル的な、あるいはゲーム的な感覚のプログラミング環境が実はそこにはあると評価する。このような立場、主張が生まれる背景には、Prologが期待されたほどには、ソフトウェア革新の担い手になり得ていない理由が、その後の数理論理学の学問的な評価を以って、プログラム言語としてのPrologの可能性を十分検証することを放棄して、定理証明といった狭い目的へ封じ込めようとする風潮を生んだことにある、という反省がある。そのことを踏まえて、Prologが述語論理から成立したことに拘らず、実在するプログラム言語として自由な視点から見直そうとするものである。
記号処理用言語・人工知能言語 [編集]
PrologはLISPの資産の多くを継承して間違いなく記号処理用の言語であるが、人工知能言語として分類されることも多い。これは、人工知能の世界では述語論理が古くから理論的な柱の一つとなっているからである。述語論理を基礎とするトップ・ダウン式の問題解決と同じく述語論理を基礎とするPrologの駆動機構の相性は当然良いため、人工知能研究に広く利用されてきた。特にエキスパートシステムで多用されるプロダクションシステムに於いては、ルールを自然に自ら動的に変更できる能力を持つことと、後ろ向き推論と呼ばれる推論がPrologの導出過程そのものであることから、その最も主要な記述言語の位置を占めてきた。
宣言型言語 [編集]
Prologは一階の述語論理に対応することから論理型言語に分類され、DSLではなく汎用言語であるが、その主張の一行一行を独立して論理式とほとんど等価な表現で行うことから、最も代表的な宣言型言語と見做されている。また、プログラムの単位である述語の記述量は極めて少なくなることが普通で、そのコードは究極のモジュラープログラミングの姿を示している。
動的型付け・非オブジェクト指向言語 [編集]
型付けは動的型付けに分類できるが、言語仕様の中に型概念は登場しない。上記の単一化、バックトラッキング、と論理変数の束縛に於いては独特のものがあり、その実行は型推論の実行過程に酷似しているなど、型付が強い弱いなどとの分類には馴染まない。
オブジェクト指向との関係は、いくつかの処理系では、オブジェクト指向言語としての拡張が行なわれているが、概して疎遠である。述語論理以前にオブジェクトありきとする立場を一般には取らない。分類するならば、非オブジェクト指向言語に分類される。
データベース [編集]
後に述べるがPrologの述語はその構造が頭部と本体と分かれていて、本体はルールを意味するため、全体として、ルールを持ったデータベース、演繹データベースとして捉えることができる。一方、本体のない(強制的にtrue)頭部のみの定義節による述語はリレーショナルデータベースとその集合論的な性質で一致する。assert,retract,setof,bagof,findallという組込述語を持つこと以外には、リレーショナルデータベースシステムとしての管理機構を持つ訳ではないが、一つの述語に多数の頭部のみの節を定義することにより、オンメモリリレーショナルデータベースを構築することが可能である。
非決定性と双方向性 [編集]
関数型言語等、他のプログラミング言語と比較しての Prolog の特長は、上記、一階述語論理に基づくこと、単一化、データベース言語的性格の他に、非決定性と双方向性が挙げられる。
非決定性は、解が唯一とは限らない場合、処理系側から見てひとつの解に決定できない場合、外部からの選択の余地を与える。そういう事が当然可能なこととして述語は定義されていく。インタプリタトップではなく、導出を繰り返すプログラム内部にあっては、処理系とした所を述語と置き換えて考えると、非決定性の述語の解を決定するのは、前方または後方に連接する質問(副目標という)である。ここから引数経由に与えられる情報によって、選択する節が最終的に決定される。ここでも非決定性の述語から見ての解の決定権は外部にあるということになる。
非決定性は導出の過程、取り分けバックトラックアルゴリズムと一体化しており、Prolog プログラムの制御の根幹のひとつである。ただ、非決定性述語実行時に見られる論理変数の 束縛->解放->再束縛という遷移、乃ち一度束縛されたものが別の物に再度束縛されるということを好ましくないとする見方もある。
双方向性は、述語が実行された場合の返り値は真または偽だけであり、その代わりとして引数内の変数で値の授受を終始するのだが、この時、入力として使われた変数が出力に、出力として使われていた変数が入力として使うことのできる述語となることがある。この性質を双方向性という。多くの場合、双方向性を持つ述語はそれ自体多義性を持つ。例えばappendという3引数の述語は第一引数と第二引数に具体的なリストが来て呼ばれた時は、リストを結合(appendはそんな意)する意味で良いが、第三引数がリストで第一引数と第二引数が変数の状態で呼ばれた場合その意味は、リストを分解する、が相応しい。既に存在するリストを、それが結合されて存在したものと考え、それでは如何に結合されていったか、あるいは、どのような組み合わせで結合されていったのかを、示していると解釈できる。
このように、双方向性はPrologの述語自らがリバースエンジニアリング的開示能力を示していると捉えることができる。この性質は、プログラム作成時はもちろん、テスト、デバッグなどの検証の各段階でプログラムコードに対する見通しを向上させる。
Prologプログラミングの難しさ [編集]
ブログラマは引数に於ける単一化、再帰/失敗駆動等のプログラムパターンの選択、非決定性、双方向性といった特長をできる限り活かすことなどに配慮しながら、述語の骨格を決めプログラミングを進める。しかし、これらの特長、性質は複合した場合には相当に複雑であり、制御上相反する部分も多々ある。Prologでは、述語論理を逸脱して計算量/資源量/制御の調整に当たる述語 ! (カット)を導入してこの問題に対処しているが、Prologプログラミングの難しさはこの調整部分に集中している。
歴史 [編集]
誕生
定理の自動証明の研究は1960年代前半のロビンソンによるレゾリューション (単一化を含む) と1960年代後半のラブランドによるモデル消去の証明手続きの成果からひとつの結実期を迎えていた。その数年後の1972年マルセイユ大のアラン・カルメラウアーとフィリップ・ルーセルのグループが FORTRAN で書かれていた自然言語解析システムを作り替えて、論理式をそのままプログラムとして実行できる系が作成できるのではないかというアイデアを得て、これを成功させた。これが Prolog である。したがって Prolog は彼らがその仕様を設計したのではなく、数千年に及ぶ人類の叡智である論理学の成果をプログラム言語に置き換えたものといえよう。完成された Prolog は主として定理の自動証明の研究に充てられた。
コワルスキとDEC-10Prolog
彼らグループに理論的な助言を与えていたエジンバラ大のロバート・コワルスキとDavid H.D.Warrenは汎用機 DECsystem10 上にマルセイユ大とは syntax が異なる処理系を作り上げた。これは後に DEC-10 Prolog と呼ばれることになるが、ISO 標準規格を含む今日動作するProlog処理系はほとんどがこの系統の syntax に従っている。コワルスキはその後、帝室ロンドン大に移り、1979年に集大成ともいえる "Logic for Problem Solving" を著し、その後のこの言語と論理プログラミングの研究に決定的な影響を与えた。
コワルスキの活動とDEC-10 Prolog の存在によって、英国はProlog研究の中心地となった。エジンバラ大のW.F.Clocksin/C.S.Mellishの著わした"Programming in Prolog"は永くPrologのバイブル本として利用された。エジンバラ大からSRIインターナショナルに転じたWarrenは1983年Prologの仮想マシンコードであるWarren's Abstract Machine (WAM)を発表した。日本のICOTのPrologマシンPSIを含む(PSI2から)後のProlog処理系の実装では、一旦C言語などでこの仮想マシンコードを設定して、その上でこのマシンコードを呼び出して動作する処理系を設計することによって、実装上の標準化を図ることが普通になった。
1978年エジンバラ大に留学中の中島秀之が「情報処理」誌に紹介記事を寄稿して、Prologは日本でも広く知られるようになった。
新世代コンピュータ技術開発機構(ICOT)とProlog
同じ頃、通産省の電子技術総合研究所の淵一博を中心とするグループが論理プログラミングの重要性を認識して、日本のコンピュータ技術の基礎技術としてこれを取り上げることを提案する。これが最終的に1980年代の新世代コンピュータ技術開発機構の発足と活動につながった。総額約570億円の国家予算を約束されて1982年新世代コンピュータ技術開発機構(通称 ICOT)は活動を開始する。Prolog を含む論理型言語はこの研究の核言語と位置づけられ世界的な注目を浴びることとなる。約10年間の研究活動中に Prolog と論理プログラミングの研究は急激に深化した。実際1980年からの20年間に Prolog をメインテーマにした日本語の書籍は約50冊発刊された。ICOT の研究員は積極的に Prolog の啓蒙に努め、講習会、チュートリアル、ワークショップを年に一度ならず開催した。ICOT が主催したロジック・プログラミング・コンファレンスは1983-5年頃をピークに若い研究者達を刺激した。研究活動前半の期間では論理型言語の実用性を証明するために、Prologマシンが設計され、三菱電機と沖電気によって製作され、ICOT の他大学等研究機関に配布された。この個人用逐次推論マシン PSI の機械語 KL0 は単一化やバックトラックなど Prolog の基本的特徴を完全に備えていた。この KL0 によって、PSI のマイクロコードを制御した。KL0 を基礎として、オペレーティングシステム SIMPOS が設計され、これを記述するために、Prolog にオブジェクト指向プログラミングを取り入れた ESP (Extended Self-contained Prolog) が近山隆により設計されて使われた。ESPは多重継承を特徴とする当時としては先鋭のオブジェクト指向言語であったが、後にカプセル化の不備などが指摘されて、今日あまり話題となることはない。しかし、OSを記述するという課題を通じて、論理型言語とオブジェクト指向言語の相性は十分に検証された。
今日、このように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のそれに置き換わる気配は現在に於いてもない。
ISO の標準化作業は1990年頃から作業委員会が開かれ1995年 ISO標準規格が制定された。ISO標準規格はエジンバラ仕様(DEC-10)Prologを基調に既に一家をなしていたQuintus Prologなど有力ベンダと主としてヨーロッパの学者を主体にこれに日本などの委員が参加して作成された。この規格は現在 Prolog 処理系の製作者に指針を与え、大きな逸脱を心理的に妨げる役割を果たしているが、個々の組込述語の仕様にはベンダの意向が強く反映したものもあるが、全体としては最初に述べた論理学的立場を尊重して保守的で小さな仕様となっている。そのため多くの Prolog 処理系はこの規格の述語を搭載しつつ、独自の拡張部分を修正削除することはしていない。結果として個々の処理系の互換性の乏しさは残り、それは Prolog の弱点として認識されている。
JIS規格も一旦は文書化まで進んだが、現在は事実上消滅してしまっている。
AIブームとProlog
ICOTの活動時期から1990年代前半に掛けては、いわゆるAIブームの時期であり、人工知能研究への期待はこの時期再び異様に高まった。LISPマシンによる医療情報エキスパートシステムでの成果は、人工知能の研究の成果の一部は情報処理に於いても利用可能なのではないかとの夢を抱かせた。このような評価の中でPrologは人工知能のアセンブリ言語的な位置づけを期待された。知識情報処理はこの水準の言語を基礎にその上側に築かれるべきだとの意味である。手っ取り早く利用可能な人工知能技術としてエキスパートシステムが選別され、これを支えるナレッジエンジニアの存在とそれを養成するための教育が必要とされた。Prologはその中心に存在した。日本も例外ではないが、海外では特に、Prolog の名著は1990年代前半に刊行されている。これは、 ICOT の活動とは若干のタイムラグがあるが、この時期社会的に 人工知能向き言語としての Prolog に大きな期待が寄せられていたことの証しである。エキスパートシステムはビジネス分野に於いて汎く応用可能な基礎技術であったが、このような低水準な分野への適用はあまり試みられず、この分野からのProlog言語への要請はほとんど見られないまま終った。
機械翻訳など自然言語処理もまたAIの一翼を担う分野であるが、歴史的経緯からAIブーム以前から、この言語に最も期待が掛けられた分野であった。しかし、左再帰問題の回避でトップダウン解析の明解さをいきなり殺がれた。さらに句構造文法への適用に於いては、Prologが得意とする、句構造に分解して意味に相当するグラフを形成することの他に、極めて膨大な辞書を構造体として定義する必要が展望された。この辞書作成はPrologとは直接関係しないタスクであることから、次第にPrologは句構造文法によるアプローチの前線から後退してしまった。 統計的言語処理のアプローチに於いては、単一化等に多くの計算量を費やすPrologは大量データを扱うのに不向きとされて、利用されることはほとんどない。 自然言語処理のテキストの多くがPrologを用いて解説されているにも関わらず、期待が大きかった割に実務的には、表面に現れている成果はIBM社のワトソン君くらいに止まり、自然言語処理は寧ろProlog評価の足を引っ張る傾向にさえある。
ICOT以後の衰退
ICOT 解散後数年を経て、論理プログラミングと Prolog は急激に下火となる。先にあげたコワルスキの成果があまりにも完成されたものでその研究成果の範囲を越えることが難しかったこと、歴史的にプログラム言語でありながら論理学からの逸脱を厳しく制限され、自由なアイデアによるプログラミング言語としての発展・展開が困難に見えたことも研究者・技術者を離れさせた。そして、AIブームもまた去って行った。企業等で続けられた研究開発も発表される機会がProlog産業応用シンポジウム(INAP)などに限定され、人々の目にPrologの成果が触れることは極端に少なくなった。ICOT の多大な研究成果がネット上に閲覧可能な状態で置かれたが、Prolog 言語の処理系はWindow/ネット時代の技術・流れに乗れず、初心者・初学者が利用するためのネット上での情報も他の有力言語に比べて少なく、新しい利用者を惹きつけることができなかった。Windows時代に入ると、初心者教育にウィンドウの部品の展開を題材とするのに適したオブジェクト指向言語に人気が集中し、Prologは動作の遅い外れた言語のイメージを持たれるようになる。さらに21世紀に入ると Prolog がクラス概念を持たないため、マイクロソフト社による.NETアーキテクチュアの共通言語基盤 (CLR) の対象言語から外されたことも、この傾向に拍車をかけた。ついには枯れた言語というニュアンスを含んでではあるが、「化石言語」と揶揄されるまでに至ったのである。
今日
勢いは失ったものの、Prolog は各教育機関で主として論理学の教材として利用され続け、今日まで数万人の人が Prolog の講座を受講している。実務的に利用される機会が少ないにも関わらず、その素養を持つ人が大量に存在するという特異な位置にあるプログラム言語となっている。
2011年夏、Bruce A. Tate 著『7つの言語 7つの世界』が出版され、その7つの言語の一つとして Prolog が紹介されたことから、多くの人々の関心を呼び起こし、この言語は突然に息を吹き返した。 Danil Jackson著『抽象によるソフトウェア設計』も翻訳されて述語論理に基礎を持つ形式記述言語alloyが注目されるなど、Prologに極めて親近した領域での議論が漸く活発になった。
2012年に入り、Ivan Bratko の大著 "Prolog Programming for Artificial Intelligence" の新版 FOURTH EDITION が11年ぶりに刊行されて、人々に Prolog は今でも活火山的な存在であることを印象付けた。また、世界的に知られる自動プログラム作成ツールシステムGeneXusが Prologによって書かれてからそれを他の利用言語に変換されて製品化されていることや、IBM 社のワトソン君の言語解析部分を現在も Prolog が担っていることなどが次々と喧伝されて、応用面でも現役言語であることが改めて認識されつつある。さらに世界的な関数型言語への急激な関心の高まりによって、関数型言語と類縁性の高い論理型言語の盟主であり、人気関数型言語 Erlang の原像でもある Prolog への関心は再び強まっている。
基本的な言語仕様 [編集]
プログラムは、ホーン節、もしくは単に節と呼ばれる形式の項を並べたものである。
節は、頭部と本体部からなり、
頭部.
または
頭部 :- 本体部.
の二形式があり得る。
これは、それぞれ、頭部. の形式が「AはBである」、頭部 :- 本体部. の形式が「BならばCである」という命題の形式に対応する。 節も項であり、項は関数子と幾つかの引数からなる。節の関数子は ':-' であり、頭部と本体部はその引数である。 頭部. の形式は実は、 頭部 :- true. が省略されたものと見做されやはり ':-' を関数子として二引数の項である。
頭部は項が連接することはできない(ホーン節)が、本体部は項が連接する、そういう項であり得る。
頭部 :- 副目標1,副目標2, ... 副目標n.
副目標1,副目標2, ... 副目標n は、これ全体を目標という。目標は副目標1...副目標nの連言である。
ここで
目標 = ( 副目標1,副目標2, ... 副目標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が扱うデータは項（英: term）と呼ばれる。項は定数、変数、複合項のいずれかである。
- 定数はアトム、数値のいずれか。
- アトムは任意の名前を表す記号。変数と区別するため、英大文字か下線「_」で始まる場合はシングルクォートで囲む。 例：
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)
- 通常の複合項 例：
複合項でのアトム部分を関数子（英: functor）、引数の数をアリティ（英: arity）と呼ぶ。アトムはアリティが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/3やfindall/3の表現が意味的にそれに近いが、ここでの表記をリストを表す項として、遅延評価して持ち回ることはできない。
Prologプログラミング [編集]
質問 [編集]
Prologの実行は述語を定義された処理系に対してユーザが質問することによってなされる。質問とは、
?- 親子(ふね,タラオ).
のようなものである。ここでの質問は「ふねはタラオの親か」という意味だ。「ふねとタラオは親子関係である」という読み方もある。
このような質問に処理系が答えることができるためにはその知識が必要である。Prologではこの知識を述語という形式で与える。そのことを述語を定義するという。
定義された述語には一般に処理系によって最低限必要なものとしてユーザに対して予め用意された組込述語(ユーザは定義しなくてもよい)と、ユーザが自ら定義したユーザ定義述語の二種類がある。ユーザは自ら定義した述語群をファイルに保存して、そのファイルを組込述語である consult/1 述語によって処理系に読み込ませる。
サザエさんの家系図に関する述語群が
親子(波平,サザエ). 親子(ふね,サザエ). 親子(波平,カツオ). 親子(ふね,カツオ). 親子(波平,ワカメ). 親子(ふね,ワカメ). 親子(マスオ,タラオ). 親子(サザエ,タラオ). 夫婦(波平,ふね). 夫婦(マスオ,サザエ). member(X,[X|_]). member(X,[_|R]) :- member(X,R).
上記のように、エディタなどで書かれて、ファイル'sazaesan.pl'に存在するとして、
?- consult('sazaesan.pl'). true.
を実行することによって、サザエさんの家系図に関する述語群がユーザから参照できるようになる。
?-
はプロンプトと呼ばれ、質問を受け付ける準備ができていることを示す。プログラムを実行するのには、一般にProlog処理系の起動後、最初のプロンプトが表示されてからユーザ自身で質問(目標)という形でプログラムを実行する。
実務的なプログラムではこの質問によって述語定義の融合、頭部の単一化、本体部の導出の長い連鎖となり、最終的にその質問が真か偽の結果を残して終了する。
これが普通の使い方だが、処理系の起動時にコマンド引数などで最初に実行する質問を引き渡して、起動後停止することなく、質問が実行される場合もある。
ここで、先に示した質問をしてみよう。
?- member(サザエ, [波平,サザエ,マスオ]). true.
となる。さらに簡単な質問をしてみる。
?- 親子(波平,サザエ). true. ?- 親子(ふね,X). 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でプログラムを記述する単位は述語（英: predicate）で、他の言語での関数やサブルーチンに相当する。つまり、Prologプログラムは述語の集まりで、述語はあるまとまった機能を表現している。述語は1つ以上の節（英: clause）と呼ばれる項からできている。節は以下の形をしている。
頭部 :- 副目標1, ..., 副目標n.
あるいは、
頭部.
1つの述語に属する節は、同じ述語名(関数子名)と引数の数(アリティ)を持つ頭部からできている。述語名とアリティが異なれば別の述語とみなすため、述語を指定するときは"述語名/アリティ"と表記されることもある (例： member/2) 。 1つの述語は成功、あるいは失敗のいずれかの結果を返す。副目標1～副目標nの間の "," はANDを意味する演算子であり、1つの節が成功するのは本体部がすべて成功した場合である。本体部の実行は左から右に行われる。頭部のみの節は 頭部 :- true. と同じ意味である。
1つの述語が複数の節からなる場合、上から順に実行され、どれかが成功したら述語自体は成功する。つまり同じ述語内の節の関係はORの関係となる。節同士はOR関係であり、それぞれ情報の共有という観点からは完全に独立している。一つの節の中の副目標から別の節中の情報にアクセスするためには、新たにこの述語を目標(質問)として呼び出す必要があり、この場合、制御や変数束縛等は完全に初期状態での実行となる。
一度trueになった節であったとしても、バックトラックして、それより下の節に制御が移った場合は、制御の移った節からバックトラックした(すなわち偽となった)節での変数束縛を利用することはできない。
宣言的意味と手続き的意味 [編集]
Prologの基本的なアイデアは、ホーン節をプログラムと見なして実行する、ということであるため、純粋なPrologのプログラムは手続き的にもホーン節に従って宣言的にも解釈ができる。1つの節の解釈は以下のようになる。
"副目標1"かつ ...、かつ"副目標n"が真であれば、"頭部"は真である (宣言的意味)
"頭部"であることを示すには、"副目標1"かつ...、かつ"副目標n"を示す (手続き的意味)
手続き的に見ると、"副目標1"～"副目標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に値が束縛されて解が得られた後、バックトラックされて第二節に移行したから、Xは束縛されていないのではなくて、第二節のXは第一節のXとは無関係だから、束縛されていないのだ。
論理変数の名前が同一であることが意味を持つのは、質問されて、述語のひとつの定義節と融合された時、その融合された定義節側の頭部、本体の中に、質問としての副目標の引数とは無関係に、同名の論理変数があるかないかだけである。融合の際の頭部の単一化でさえ、論理変数同士の単一化であっても、変数名が同じあるか否かは問われない。この点は次の節の単一化を参照されたい。
ここで起っている質問としての副目標(または目標)と定義節との融合は、述語定義のコードからは離れて、対応する節の姿が写されて実行されるのであって、その実行と述語定義のコードは直接的な関係を持たない。
従って、この質問、導出過程で論理変数が束縛されても、述語定義の他の定義節の論理変数に影響を及ぼしようがないのである。
単一化 [編集]
Prolog の動作の基本は単一化と後に述べるバックトラックである。
単一化(ユニフィケーション)は、述語呼び出し時に使用される、呼び出し側、呼び出される側双方向の強力なパターンマッチングだが、そのルールは簡単である。
すなわち、二つの項の単一化において、
1) 2項がそれぞれ変数の場合は、以後この二つの変数は同一のものと看做される。同時に単一化は成功する。
2) 2項の一方が変数であり、他方が変数以外の項である場合は、変数はこの変数以外の項と同一のものとなる。単一化は成功する。
3) 2項がそれぞれアトムの場合は、二つのアトムが完全に一致した場合に単一化は成功する。
4) 2項がそれぞれ複合項の場合は、二つの複合項の関数名とそれぞれの引数の形式が一致した上で、全ての引数要素に対して、再帰的に単一化が成功する場合のみ、単一化は成功する。
以上挙げた以外の場合は、単一化は全て失敗する。従って、アトムと複合項の単一化は常に失敗する。述語呼び出し時の候補節に於いては、一つでも頭部にある引数の単一化に失敗すると、その候補節は選択されない。
1) と 2) は意味的に統合可能であり、単一化ルールを三つとすることもある。Wikipediaのユニフィケーションの説明ではそうなっている。しかし、変数の単一化は値が束縛されないという意味で特殊であり、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は成功裡に終了している。
この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独特の機能だが、強いて他のプログラム言語の中から類似したプログラミング要素を探すと、
- ループ(通常言語のfor,while等)
- 探索機能
ループの簡単な例を以下に示す。この例ではリストの先頭から0以上100以下の数値が見つかるまで繰り返す。
?- member(X, [3000, 1254, -2, 3598, 88, 9618]), X>=0, X=<100. X = 88
数式 [編集]
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.
このように正確な条件を記述することが大きな負担となる場合、その負担を解消する為にカットが使用されることが実は多い。
通常のProlog処理系では、バックトラックで戻ってくる場合に備えて、それまでに実行した各ゴールの情報や値を設定した変数をメモリ上に記憶している。カットを実行するとそれらのうち不要な情報を開放することができるため、カットは使用メモリの削減にもつながる。
説明の順序が前後したが、実行結果の否定のためには述語"\+"が用意されている。 \+(P) はゴールPが成功したときに失敗し、失敗したとき成功する。この述語は本当の否定 "Pは偽である" ではなく "Pは証明できない" という失敗による否定で、ある種の非単調論理による推論を行う。これは以下のように定義した述語と同じ動きをする。ここで fail は必ず失敗する組込述語である。
\+(P) :- P, !, fail. \+(_).
この否定は、カットなしには定義する方法がない。
高階述語とメタインタプリタ [編集]
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/3 や setof/3 が既に存在している。しかも、関数型言語のように引数が事前評価されることはなく、引数に関数を置いて渡すこともできないため、map述語の効用は関数型言語のようには大きくない。
リレーショナルデータベース [編集]
Prologはルールを持つデータベースであり、演繹データベースであるといえる。このルールの部分を全てtrueのみに限定した単位節のみからなる述語をデータベースと呼び、リレーショナルデータベースに模して解釈されることが多い。このPrologのデータベースとリレーションナルデータベースは集合論的に類似しているが、異なる部分もありこの部分がSQLなどデータベース照会言語との変換などで問題となる。 ここでは主としてふたつのデータベースの相違点に焦点を当てて、プログラミング手法を考えてみる。
リレーショナルデータベースはテーブルの集まりであり、
テーブルとは属性(最終的に列となる)の定義域集合の全ての可能な値の組み合わせ(直積)の部分集合である。
属性が、四季と果物の二つ集合 {春,夏,秋,冬} {みかん,りんご,もも,いちご} の直積は
{(春,みかん),(春,りんご),(春,もも),(春,いちご),(夏,みかん),(夏,りんご),(夏,もも),(夏,いちご),(秋,みかん),(秋,りんご),(秋,もも),(秋,いちご),(冬,みかん),(冬,りんご),(冬,もも),(冬,いちご)} であるが、
この部分集合であるテーブル「季節の果物」は季節の果物 :: {(春,いちご),(夏,もも),(秋,りんご),(冬,みかん)} であるとする。
この直積の組み合わせの中で、真となる関係、あるいはその更に一部がテーブルだと考えればよいだろう。
これがリレーショナルデータベースのテーブルの実体である。一方このテーブルをProlog単位節で表すと
季節の果物(春,いちご). 季節の果物(夏,もも). 季節の果物(秋,りんご). 季節の果物(冬,みかん).
となる。Prologデータベースの第一節は「春といちごは季節の果物関係にある」というものであり、述語名として季節、果物が暗示されてはいるものの、実は第一引数が季節であり、第二引数が果物であるという情報はどこにもない。「季節」や「果物」といった属性(列)から出発したリレーショナルデータベースとは明らかに異なる。
この相違に起因する問題がSQL問い合わせをProlog述語に変換する際に生じる。
以下のような、SQLに問い合わせを考える。
select 季節 from 季節の果物 where 果物 = 'もも'
これに相当するPrologの質問は
?- 季節の果物(X,もも). X = 夏
であるが、問題点がふたつある。
1) 第一引数が果物なのか、第二引数が果物なのか定かでない。季節についても同様である。
2) 実は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は論理を利用した自然言語処理のために開発された[2]。実際、文脈自由文法のトップダウン構文解析の動きはProlog自身の動きと同じである。
限定節文法 [編集]
Prologには限定節文法（英: definite clause grammar）と呼ばれる特別な表記法が用意されている。文脈自由文法を拡張したもので、文法を記述する場合は :-/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個ある方の述語だ。述語名は引数の数が違うから同じ リスト要素の加算 で構わない。リストから数を取り出すと、この第二引数に加算していく。
リスト要素の加算(L,S) :- リスト要素の加算(L,0,S). リスト要素の加算([],S,S). リスト要素の加算([N|R],S1,S) :- S2 is S1 + N, リスト要素の加算(R,S2,S).
リスト要素の加算/3 の第一節の [],S,S). というところがProlog独特のテクニックである。
第一引数のリストが空になったとき、第二引数に累計が存在するのだが、最初の述語リスト要素の加算/2の副目標 リスト要素の加算(L,0,S). の第二引数では初期値0と値を決めて引数に渡しているため、この第二引数から値を受け取ることは不可能である。 そこで、第三引数として一つ余分な引数を設けて、そちらは変数にして置けば、最終的にその引数が単一化されることによって値を受け取ることができるという訳だ。その第二引数と第三引数の単一化を行っているのが、リスト要素の加算/3の第一節の [],S,S). である。
この述語の第二節第三引数がともにSで同一であることが重要である。
リスト要素の加算([N|R],S1,S) :- S2 is S1 + N, リスト要素の加算(R,S2,S).
この部分が束縛されたまま、単に同一の変数であることが示され、第一節でリストが[]になった時に加算計がこれに単一化される。 <soutce lang="Prolog"> リスト要素の加算([],S,S). </source>
単位節要素の加算(集約問題) [編集]
単位節(本体のない事実上のデータベース定義)要素の加算。 実例として次の単位節データベースを考える。
年齢(山田,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万節を越えるような場合、スタックオーバーフロー等のエラーが発生する危険が生じる。内部メモリにリストとして情報の連鎖を生成するのだから、やむを得ないことではあるが、注意が必要である。
行列 [編集]
Prologでは行列をリストを要素として持つリストとして表現することが多い。
ここでは、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]].
正方行列の対角要素 [編集]
正方行列の右下がり対角要素リストと左下がり対角要素リストを得る。 正方行列の対角要素とは、
| 1 2 3 |
| 4 5 6 |
| 7 8 9 |
1,5,9 が右下がり対角要素であり、3,5,7 が左下がり対角要素であるとする。 これをnth1/3とlength/2とappend/3の組み合わせで定義する。
右下がり対角要素リスト(_正方行列,_右下がり対角要素リスト) :- findall(V,( nth1(_nth1,_正方行列,L), nth1(_nth1,L,V)), _右下がり対角要素リスト). 左下がり対角要素リスト(_正方行列,_左下がり対角要素リスト) :- findall(V,( nth1(_nth1,_正方行列,L), length([_|R],_nth1), append(_,[V|R],L)), _左下がり対角要素リスト),!.
組込述語nth1/3は非決定性の述語で第一引数が論理変数の場合は、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]
階乗 [編集]
階乗は整数の性質に含まれる数の連関を使うだけで計算できる数少ない例の一つである。Nの階乗を 階乗/2 として定義する。
階乗(0,1) :- !. 階乗(N,_階乗) :- N_1 is N - 1, 階乗(N_1,_階乗_1), _階乗 is _階乗_1 * N.
計算対象となる要素が、ここでのように常に1少ないというような場合は、特別な例なのであって、そのような固定した性質がない集合の計算では計算対象をリストに取ることが多い。既にそのような例としては 加算の リスト要素の加算/2 があった。
階乗保存計算 [編集]
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/2は述語の先頭に定義節を加える組込述語。既に計算した階乗は答えを階乗保存計算の先頭に付け加えることで、以後階乗計算に入るまえに、その解を得ることができるようになる。
述語階乗保存計算/2の定義は階乗保存計算(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/1は現在の述語定義を示す、処理系のサービス述語である。
組込述語 asserta/1やassertz/1を使えば、プログラムによるプログラムの生成が可能になる。それだけではなく、プログラムの実行中に追加プログラムコードを生成して、それを即実行することもできる。
リストの全ての要素が同じ [編集]
リスト要素が全て同じ。検査述語であると同時に、リストに変数を含む場合はそれを第二引数と単一化して 全て同じ要素になるように企てる働きをする。
全ての要素が同じ([],_). 全ての要素が同じ([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/2 によって要素数N個の変数のリストを生成し、 その要素全てを空白文字とした上で、文字のリストからアトムを生成するために、組込述語 atom_chars/2 を使っている。
'N個の空白からなるアトムを生成する'(N,_アトム) :- length(L,N), 全ての要素が同じ(L,' '), atom_chars(_アトム,L).
実例を示す。
?- 'N個の空白からならアトムを生成する'(8,Atom). Atom = ' '
ヘッドゼロサプライ [編集]
事務計算などでは、123という整数を8桁の数値表現でしかも頭部を空白ではなく0で埋めることを要求されることがある。
これを上記 全ての要素が同じ/2 を使って定義する。最初に枠を取り、頭部の桁不足の部分は 全ての要素が同じ/2 を使って0を埋めている。
ヘッドゼロサプライ(_桁数,_数値,_ヘッドゼロサプライ数値表現) :- length(_桁数枠のリスト,_桁数), number_chars(_数値,_数字のリスト), append(_頭部の枠リスト,_数字のリスト,_桁数枠のリスト), 全ての要素が同じ(_頭部の枠リスト,'0'), atom_chars(_ヘッドゼロサプライ数値表現,_桁数枠のリスト).
number_chars/2, atom_chars/2 ともに組込述語で、それぞれ、数値を分解して数字リストに、アトムを分解して文字リストとする。
頭部の枠リストの桁(要素数)は述語 append/3 が決定する。
実行例
?- ヘッドゼロサプライ(8,123,X). X = '00000123' ?-
ユークリッドの互除法によって最大公約数を求める [編集]
ユークリッドの互除法によって最大公約数を求める。
数値演算の場合、他の言語とそれほど変わらない。Prologの特徴を求めるならば出力用の引数が必要とされることだろう。
最大公約数(N,_最大公約数,_最大公約数) :- 0 is N mod _最大公約数. 最大公約数(N,M,_最大公約数) :- M_2 is N mod M, 最大公約数(M,M_2,_最大公約数).
実行例
?- 最大公約数(49,28,X). X = 7 ?-
エラトステネスの篩 [編集]
n以下の全ての素数をリストに集める。エラトステネスの篩を述語として定義し、これを呼び出す。
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),!.
エラトステネスの篩/2 の定義の中で findall/3 を使うと エテトステネス/3 は実は不要である。
エラトステネスの篩([],[]). エラトステネスの篩([M|R1],[M|R2]) :- findall(N,( member(N,R1), \+(0 is N mod M)), L), エラトステネスの篩(L,R2).
どちらの定義が読みやすいかについては、常に問題となる。
この findall/3 を エラストステネの篩/3 の中に持つ
エラトステネスの篩([],[]) :- !. エラトステネスの篩([M|R1],[M|R2]) :- エラトステネスの篩(M,R1,L), エラトステネスの篩(L,R2). エラトステネスの篩(M,R1,L) :- findall(N,( member(N,R1), \+(0 is N mod M)), L).
が最も宣言的なエラストテネスの篩の定義かも知れない。
エラストテネスの篩/2 の方は、findall/3 で生成される新たなリストが第一引数に置き換えられて再び駆動される。このような新しい対象を生成しつつ、ダイナミックに繰り返すパターンは、再帰的な定義以外に方法がない。
実行例
?- 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/5の仕様は 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/2 はリスト要素を結合して新しいアトムを生成する。
実行例を示す。
?- 文字列の置換(いろはにほへと,はに,はは,_置換された文字列). _置換された文字列 = いろははほへと
これはうまく行くが、複数置換対象が存在する場合を見てみよう。
?- 文字列の置換(生垣作るその生垣を,生垣,八重垣,_置換された文字列). _置換された文字列 = 八重垣作るその生垣を; _置換された文字列 = 生垣作るその八重垣を; false.
置換対象が複数あっても、一ヶ所だけ置換するという場合もある。その場合には選択的に置換できるこの定義で良い。
しかしこの例もそうだが、対象となる副文字列全てを置換したいことも多い。結論を言ってしまえば、このようなバックトラックを使ったパターン(失敗駆動)では全置換は定義できない。
文字列の全置換(_対象文字列,_置換される副文字列,_置換する副文字列,_置換された文字列) :- 置換対象の選択(_対象文字列,_置換される副文字列,_前文字列,_後文字列), 文字列の全置換(_後文字列,_置換される副文字列,_置換する副文字列,_置換された後文字列), atomic_list_concat([_前文字列,_置換する副文字列,_置換された後文字列],_置換された文字列),!. 文字列の全置換(_文字列,_,_,_文字列). 置換対象の選択(_対象文字列,_置換される副文字列,_前文字列,_後文字列) :- sub_atom(_対象文字列,_開始点,_長さ,_残り長さ,_置換される副文字列), sub_atom(_対象文字列,0,_開始点,_,_前文字列), sub_atom(_対象文字列,_,_残り長さ,0,_後文字列).
一般に置換では、置換対象文字列が存在しなかった時、その副目標(質問)を偽としないで、元の文字列をそのまま残す。文字列の全置換/4の第二節 文字列の全置換(_文字列,_,_,_文字列). はそのために必要である。
ちょっと判り難いが、文字列の全置換/4 は再帰的な述語である。置換対象までとその後文字列に分割して、後文字列を再帰的に置換したものと、それまでの文字列を置換しながら結合する。
実行例
?- 文字列の全置換(生垣作るその生垣を,生垣,八重垣,_置換された文字列). _置換された文字列 = 八重垣作るその八重垣を
これで二ヶ所の生垣を八重垣に置換できた。
リストの結合 [編集]
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/2に於いては不可能なことである。
文字リストに変換して文字列を検索 [編集]
先に文字列の検索を組込述語 sub_atom/5 を使うことで例題とした。ここでは一旦、アトムとしての文字列を文字を要素とするリストに変換して検索する例を示す。この場合、検索語も文字のリストに変換する。
文字列の検索(_文字列,_検索語,_検索語の前方文字列,_検索語,_検索語の後方文字列) :- 文字列と検索語を文字リストに変換(_文字列,_検索語,_文字リスト,_検索文字リスト), 文字リストの検索(_文字リスト,_検索文字リスト,_検索語の前方文字リスト,_検索文字リスト,_検索語の後方文字リスト), '検索語の前方文字リスト、検索文字リスト、検索語後方の文字リストを文字リストから文字列に変換'(_検索語の前方文字リスト,_検索文字リスト,_検索語の後方文字リスト,_検索語の前方文字列,_検索語,_検索語の後方文字列). 文字列と検索語を文字リストに変換(_文字列,_検索語,_文字リスト,_検索文字リスト) :- atom_chars(_文字列,_文字リスト), atom_chars(_検索語,_検索文字リスト). 文字リストの検索(_文字リスト,_検索文字リスト,_検索語の前方文字リスト,_検索文字リスト,_検索語の後方文字リスト) :- append(_検索語の前方文字リスト,L2,_文字リスト), append(_検索文字リスト,_検索語の後方文字リスト,L2), '検索語の前方文字リスト、検索文字リスト、検索語後方の文字リストを文字リストから文字列に変換'(_検索語の前方文字リスト,_検索文字リスト,検索語の後方文字リスト,_検索語の前方文字列,_検索語,_検索語の後方文字列) :- atom_chars(_検索語の前方文字列,_検索語の前方文字リスト), atom_chars(_検索語,_検索文字リスト), atom_chars(_検索語の後方文字列,_検索語の後方文字リスト).
「検索語の前方文字リスト、検索文字リスト、検索語の後方文字リストを文字リストから文字列に変換」がシングルクォートで囲まれて定義されているのは、途中に「、」が含まれているからである。規格で定まっている訳ではないが、全角の記号は将来全角文字のみで処理系が利用される可能性から、記号扱いにしている処理系が多い。 述語 文字リストの検索/5 に於いて、上記のリストの結合 append/3 が、リストの結合というより分解としてが二つ連続して利用されている。
文字列を検索パターンを用いて検索 [編集]
既に文字列の検索をsub_atom/5を用いた例を示したが、一般に文字列の検索は atom_chars/2 を用いて一旦文字のリストに変換してから検索を掛ける方が定義が柔軟になる。
:- 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では、このようにパターンを一つのリストで表現することはできない。それでここは変数にして、パターン照合/2 述語に解決を委ねている。
リスト要素の隣／リスト要素の両隣 [編集]
append/3を利用してリスト要素の隣を定義してみよう。極めて宣言的な定義となる。
リスト要素の隣(_リスト,_要素,_隣の要素) :- 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
リスト要素の反転 [編集]
リストの要素の反転は reverse/2 が組込述語になっているが、ここでは、これを定義してみる。
リストの反転(L1,L2) :- リストの反転(L1,[],L2). リストの反転([],L,L). リストの反転([A|R1],L1,L) :- リストの反転(R1,[A|L1],L).
リストの反転/3 の方の第二節Aに着目して欲しい。第二引数で受け取ったリストの前に追加しているが、最初が[]だから、先頭から順に末尾から付加されていくことになる。第一節の主張は、第一引数が[]になった時には、第二引数に反転したリストが積み上がっているはず、ということである。
リストの反転はappend/3を使った定義も可能である。この定義の方がより宣言的であるが実行速度は大幅に遅い。
リストの反転([],[]). リストの反転([A|R1],L) :- リストの反転(R1,L2), append(L2,[A],L).
実行例
?- リストの反転([a,b,c],L). L = [c,b,a]
文字列の反転 [編集]
"文字列"という文字列を反転して"列字文"という文字列を生成する 文字列の反転/2 を定義する。 組込述語 atom_chars/2 と上記定義したリストの反転/2 を組み合わせる。
文字列の反転(_文字列,_反転した文字列) :- atom_chars(_文字列,_文字のリスト), リストの反転(_文字のリスト,_反転した文字のリスト), atom_chars(_反転した文字列,_反転した文字のリスト),
ここでは一旦文字のリストに変換している。それによってリストの反転/2が利用できた。
ただし、元の文字列の形式に atom_chars/2 をもう一度使って戻さなくてはならない。
atom_chars/2でリストに変換せずに、文字列の反転/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/3が使われた。アトムとアトムを結合して別の長いアトムを生成する述語である。
文字列の反転の例を示す。
?- 文字列の反転(文字列,X). X = 列字文 ?-
回文 [編集]
回文とは先頭から読んでも、末尾から反対に文字を辿って読んでも、同じ文になるある程度意味の通る文のことである。ここでの定義は回文を生成するのではなく、回文であるかどうかの検査である。
ただし、ここでは、「長き夜の 遠の睡りの 皆目醒め 波乗り船の 音の良きかな」のようなものは扱わない。「なかきよのとおのねふりのなふめさめふなのりふねのおとのよきかな」のように音の並びとしたものを対象とする。
回文(_回文) :- atom_chars(_回文,Chars), リストの反転(Chars,Chars).
一旦組込述語 atom_chars/2 で文字のリストに変換する。ここまでは謂わば定石のようなものだが、
回文の場合はここから、そのリストを反転し、引数が共通であることを示して、
反転前と反転後が同じなのが回文であると宣言している。
実例はもちろん
?- 回文(なかきよのとおのねふりのなふめさめふなのりふねのおとのよきかな). true. ?-
である。
above (或いは到達可能性) [編集]
above(X,Y) :- on(X,Y). above(X,Y) :- on(X,Z), above(Z,Y).
ここで on/2 の定義は具体的に定義する。例えば、
on(波平,サザエ). on(サザエ,カツオ).
実行例
?- above(波平,X). X = サザエ; X = カツオ; False ?= above(波平,カツオ). True
一つ以上離れた関係をabove/2の第二節でので定義で、引数の変数をonを経ながら X - Z - Y と連鎖することによって表現している。
経路が以下のような定義の時、ある駅から別の駅に到達できるかを示す 到達可能性/2 の定義は。
経路(渋谷,神泉). 経路(神泉,駒場東大前). 経路(駒場東大前,池の上). 経路(池の上,下北沢). 到達可能性(_駅_1,_駅_2) :- 経路(_駅_1,_駅_2). 到達可能性(_駅_1,_駅_2) :- 経路(_駅_1,_駅_3), 到達可能性(_駅_3,_駅_2).
実行例
?- 到達(神泉,下北沢). true.
検索は、
(神泉,駒場東大前) -> (駒場東大前,池の上) -> (池の上,下北沢) と進み、第一節の本体で :- 経路(池の上,下北沢). が真となることにより、到達可能性は真となる。
この定義を見比べると、経路/到達可能性とon/aboveの関係が同じアルゴリズムであることが判る。
失敗駆動 [編集]
単位節要素の加算の例に示された"年齢"のような単位節(本体定義なのない節)を定義順に表示するには普通失敗駆動を利用する。 年齢の定義次の通りだとする。
年齢(山田,35). 年齢(大島,20). 年齢(清川,28).
ここでは定義順に氏名,年齢を全て表示する方法を示す。
年齢表示 :- 年齢(_氏名,_年齢), writef('%t,%t\n',[_氏名,_年齢]), fail.
表示は組込述語 writef/2 を使っている。無条件に偽になる組込述語があるため、バックトラックが起こり順に述語 年齢/2 の 各節が呼び出されて表示される。これが失敗駆動だ。最終的には年齢/2の呼び出しは偽となるため、質問は False で終わる。
実行例
?- 年齢表示. 山田,35 大島,20 清川,28 false. ?-
一般に必ず偽となって終わる定義は、これを再利用する際に不都合が生じる場合が多い。真として終了する為には、
年齢表示 :- 年齢(_氏名,_年齢), writef('%t,%t\n',[_氏名,_年齢]), fail. 年齢表示.
と書き加えるのみである。
失敗駆動を用いることなく、再帰を使って上記の年齢を表示することは案外と難しい。
年齢表示 :- findall([_氏名,_年齢],年齢(_氏名,_年齢),L), 再帰による年齢表示(L). 再帰による年齢表示([]). 再帰による年齢表示([[_氏名,_年齢]|R]) :- writef('%t\n',[_氏名,_年齢]), 再帰による年齢表示(R).
完全に独立した存在である定義節から、情報の連関を付与されたものとしてのリストを得るために、findall/3をここでも使用した。実はこのfindall/3の中に失敗駆動が含まれている。つまり、ここではfindall/3を使うことによって失敗駆動を隠蔽していることになる。
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,read(X),write(X),nl,X=end_of_file. |: abc. abc |: 123. 123 |: end_of_file. end_of_file _季節 = 春, X = end_of_file,
季節の選択が春から先に進んでいないことに注目してほしい。副目標四季/1にはrepeatがあるためバックトラックしてこないのである。
行入力 [編集]
前節に既に現れてしまったが、Prologには入力述語として古くから、read/1,read/2が存在した。この入力述語の魅力はアトム、数値、リストを含む複合項など、どんな項でも入力可能である点にある。
?- read(X). |: 33. X = 33. ?- read(X). |: a(b,c). X = a(b,c) ?-
のように使う。注意するべきことは、プロンプト |: の後の入力には正しく項が来なくてはならず、しかも、入力はピリオドで終了する必要がある。
極く一般的なカンマ区切りの "abc,def" の入力はシングルクォートで囲み 'abc,def'. でなくてはならないことになる。これでは実務的には不自由過ぎるので、
文字列が改行されて終了するまでを、アトムとして受け取る 行入力/1 を定義してみよう。
行入力(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/2 で変換して、アトムとして受け取ることができるようになった。ただし、入力はアトムだけに限られる。この点はreadが項であったのとは異なる。
行入力_1の第二節に現れる end_of_file であるが、これは改行ではなくコントロール-dなどeofを意味する情報が入力されたことを意味する。この独特なアトムをPrologでは伝統的に用いている。
実行例
?- 行入力(X). abc,def X = 'abc,def'
今度は |: のプロンプトが表示されない。このプロンプトの表示は項入力述語readの謂わばサービスであって、同じく組込述語であるが、get_charでは表示されない。
入力検査 [編集]
整数入力/1はrepeatによく似ているが、第一節の末尾にカットがあるため、失敗駆動の起点としての繰り返しにはならない。 整数入力検査に失敗した場合のみ、整数入力を繰り返す。
整数入力(_整数) :- 行入力(_行入力), 整数入力検査(_行入力,_整数),!. 整数入力(_整数) :- 整数入力(_整数). 整数入力検査(_行入力,_整数) :- atom_to_term(_行入力,_整数,_), integer(_整数),!. 整数入力検査(_行入力,_) :- writef('入力された文字列%tは整数ではありません。再入力をお願いします。\n',[_行入力]), fail.
atom_to_term/3は組込述語であり、atom(文字列)を受け取りこれを解析して、Prologの項に変換している。 整数でない情報を受け取った時にその情報を表示させるためには、get_line/1と同じ本体の中で、処理することが必要である。
整数入力/1の第二節で表示することは、この節が引数からget_char/1で得た情報を受け取っていない以上不可能である。 入力エラーを表示させる際に、入力された文字列も共に表示したいのであるが、第一節の本体内の副目標でない限り、引数からこの情報を受け取ることはできない。
実行例
?- 整数入力(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/0, member/2, append/3 を比較した見た。極めて類似したパターンの述語であることが分かる。
組合せ [編集]
リストによって与えられた集合要素の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/3を用いればよい。述語を非決定性に定義することを基本として、必要な場合にfindall/3によって全解をリストに取得する。これは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/3を使い、組合せ/3 が解を生成するごとに1をリストに蒐集することによっても、組合せの総数を求めることができる。
nCr(N,R,X) :- findall(1,組合せ(N,R,_),L), length(L,X).
ここでは、蒐集する値を1としたが、実はこれはアトム、数値、変数、何が来ても可である。
実行例
?- nCr(4,3,X). X = 4
項複写 [編集]
項を複写する。
ただ、単なる複写ではない、大事な点がある。変数はそのまま複写することはしない。新たに別の変数を作り出して、 それを複写元の変数があった構造上の同じ位置に置く。 この述語は高階述語を使用し、かつ、それが再帰の中で引数として引き継がれて行く場合に使用される。 引数として受け取った高階の述語呼び出し項と基本的に同じ構造だが、変数だけは単一化されることのない項を作りだし、 それを引数として渡す時の基礎とする。
引数を受け取った時点と引き渡す時点の間で変数が単一化された場合、意図した同型の引き渡し述語とならず、再帰が失敗してしまうことを避ける為に使用されることが多い。
項複写(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/3,arg/3は組込述語。functor/3は項を関数とアリティに分解する。arg/3は項の引数に値を与える。compound/1も組込述語で引数が複合項であるかどうか検査する。'1引数を再帰的に項複写'は第一文字が数字だからシングルクォートで囲む必要がある。
実行例
?- 項複写(a(b,U,c(V,W),d),X). U = _1, V = _2, W = _3, X = a(b,_4,c(_5,_6),d)
項複写された変数は元の変数とは別のものなので、逆にこの変数を単一化する必要がある場合は、どこに変数があるか、或いは何に単一化すればよいか判らないという事態が生じる。その可能性に対処するためには項複写を少し拡張する。ここでは項複写/2を項複写/4に拡張し、第三引数に複写元の項の変数、第四引数に複写先の項の変数をそれぞれ順序正しくリストに取れるようにしよう。
項複写(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).
クイックソート [編集]
与えられたリストを昇順にソートするクイックソートのプログラム例を示す。
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/4は上に同じ)
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/4は上に同じ)
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/3の定義を
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はfailしてしまうから、同一要素は無視することの宣言である第四節を加える。組込述語 sort/2 は、この集合解が返ってくる仕様に決められている。
ハノイの塔 [編集]
ハノイの塔は最もProlog向きの課題のひとつとして知られる。ここでは、N枚の円盤を三本の柱のうち、一番左の柱から右の柱に移すケースを示す。円盤は下から上に向かうほど小さくなるように積まれ、常にその状態が維持されなくてはならない。
:- op(500,xfx,から). :- op(400,xf,へ). ハノイの塔(N,_移動履歴) :- length(Ln,N), ハノイの塔(Ln,左柱,中柱,右柱,_移動履歴). ハノイの塔([_],_左,_中,_右,[_左 から _右 へ]). ハノイの塔([_|Ln],_左,_中,_右,_移動履歴) :- ハノイの塔(Ln,_左,_右,_中,_移動履歴_1), ハノイの塔(Ln,_中,_左,_右,_移動履歴_2), append(_移動履歴_1,[_左 から _右 へ|_移動履歴_2],_移動履歴).
冒頭、「から」を中置演算子、「へ」を後億演算子として定義している。それを使って _移動前の位置 から _移動後の位置 という項を表現して、それを履歴として残している。
このプログラムはPrologが宣言的であることを顕著に示す好例である。この述語で述べられていることは、三回が一組となって同じパターンが繰り返されるということ。さらに最も下の一枚が順に、この課題では右柱に積まれるのだが、新しい最下層の円盤が右柱の最上位に積まれた時には、それより上の塔は中柱、左柱と交互に完全に積み上がっている。それを、ハノイの塔述語の本体の二番目の副目標で、どちらの柱を起点として以後の移動を開始するかを、引数の位置を入れ替えることだけによって、表現している。このように全体の骨格と僅かな引数の置き換えだけによって、手続的動作の全てを暗示している。このような表現力に対して「宣言的」と言うのである。
実行例
?- ハノイの塔(4,L), member(A,L), writef('%t\n',[A]), fail; true. 左柱 から 中柱 へ 左柱 から 右柱 へ 中柱 から 右柱 へ 左柱 から 中柱 へ 右柱 から 左柱 へ 右柱 から 中柱 へ 左柱 から 中柱 へ 左柱 から 右柱 へ 中柱 から 右柱 へ 中柱 から 左柱 へ 右柱 から 左柱 へ 中柱 から 右柱 へ 左柱 から 中柱 へ 左柱 から 右柱 へ 中柱 から 右柱 へ true. ?-
チューリングマシン [編集]
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つのリストの最長共通部分列問題[3]を多項式時間で求める。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などの各種言語をライブラリとして含んでいる。
| 処理系 | 国など | 有償? | ISO | 備考 |
|---|---|---|---|---|
| Amzi! Prolog | 英語圏 | 有償 | ISO準拠 | |
| AZ-Prolog | 日本 | 個人は無償 | DEC-10 Prolog準拠 | |
| B-Prolog | 英語圏 | 学術は無償 | ||
| Ciao Prolog | スペイン | オープンソース | ISO準拠 | |
| GNU Prolog | GNU | オープンソース | ISO準拠 | |
| Jekejeke Prolog | スイス | ISO準拠 | ||
| K-Prolog | 日本 | 有償 | ISO準拠 | 日本語対応 |
| MINERVA | 日本? | 有償 | ISO準拠 | 業務用、Javaベース |
| Open Prolog | アイルランド | 無償 | ISO準拠 | Mac OS用 |
| Prolog Cafe | 日本 | オープンソース | PrologソースをJavaソースに翻訳 | |
| Prolog.NET | 英語圏 | オープンソース | .NETでPrologを使用できる | |
| P# | イギリス | PrologソースをC#ソースにコンパイル | ||
| Qu-Prolog | オーストラリア | マルチスレッド処理系 | ||
| Rebol Prolog | ||||
| SICStus Prolog | スウェーデン | 有償 | ISO準拠 | 多くのOSに対応。Javaや.NETでのウェブアプリケーション開発可能。 |
| Prolog for Squeak | 英語圏 | Squeak に統合されたProlog環境 | ||
| Strawberry Prolog | ブルガリア | オープンソース | ||
| SWI-Prolog | 英語圏 | オープンソース | ISO準拠 | 多くのOSに対応 |
| TuProlog | イタリア | |||
| Visual Prolog | 英語圏 | 個人は無償 | ||
| XSB | 英語圏 | オープンソース | ||
| YAP Prolog | ポルトガル | オープンソース | ISO準拠 | YAP(Yet Another Prolog)。Prologコンパイラ。 |
国際会議 [編集]
- INAP International Conference on Declarative Programming and Knowledge Management
脚注 [編集]
- ^ ただし、コメントでそれらを代用することがよくあり、大体通用する表記法がある。引数の前に+を置けば入力、-を置けば出力、?ならばどちらにもなり得る。
参考文献 [編集]
- William F. Clocksin, Christopher S. Mellish: Programming in Prolog: Using the ISO Standard. Springer, 5th ed., 2003, ISBN 978-3540006787.
- Leon Sterling and 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 and 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.
- ^ Robert Kowalski, The Early Years of Logic Programming より
- ^ Alain Colmerauer and Philippe Roussel, The birth of Prolog より
- ^ 英: longest common subsequence
関連項目 [編集]
