Prolog
Prolog(プロログ)は論理プログラミング言語の一つであり、該当分野で最もよく知られている論理型言語の代表格である。主に人工知能研究や計算言語学との関連性を持つ。定理証明、エキスパートシステム、自動計画、自然言語処理とも繋がりが深い。一階述語論理と形式論理を基礎にして、事実群と規則群の表現および関係の観点に立った宣言型パラダイムに準拠しており、その関係に則った質問によって計算が開始されるという性質を持つ。
Prologは、1972年にマルセイユ大学のアラン・カルメラウアーとフィリップ・ラッセルによって開発された。フランス語の「programmation en logique」がその名の由来である。Prologの誕生にはエディンバラ大学のロバート・コワルスキが考案したホーン節が大きく寄与している。カルメラウアーによる元祖版はマルセイユPrologと呼ばれている。その後、コワルスキの門弟のデヴィッド・ワーレンが1977年に改訂開発したエディンバラProlog(DEC-10 Prolog)が標準になってPrologは広く普及した。
1972年ごろにフランスのアラン・カルメラウアーとフィリップ・ルーセルによって考案された。
成立の事情から、Prolog プログラムは論理式とみなされ、その実行は述語論理によって述語が定義された環境における定理証明に擬して解釈されることが多い。利用者は論理プログラミングの枠組みを、取り分け述語論理を学習することで、この枠組みに極めて忠実なこの言語の基礎的な構造のほとんどを理解できる。その言語仕様はこの枠組み以外には考案者たちも含めてそれ以上の拡張をほとんど行っていないため、他のプログラム言語とは異なり、学習しなくてはならない概念や用語もまた、述語論理のものだけでこと足りる。基本的に計算機科学の新しい概念や新しい手法とは無縁である。ただし、SWI-Prolog等の処理系では様々な機能拡張の試みが行われている。一階述語論理は型理論や操作的意味論の研究論文で多数用いられており、今後、再注目される可能性がある。
Prolog のプログラムは一階述語論理に基づいてデータ間の関係を示す命題として記述され、処理系がそれらに単一化(ユニフィケーション)と呼ばれるパターンマッチングを施しながら、与えられた命題が成立するか再帰的手続きによって探索している。
プログラムの実行は述語集合が定義された環境の元で、質問することによってなされるが、これは反駁という述語論理的な証明過程を模して、処理系が用意する導出木と呼ばれるグラフをたどって解を得る過程である。
Prolog のもととなるこの演繹手法は導出と呼ばれ、自動定理証明の研究において Prolog 開発以前からよく知られていた。Prolog は、導出において節を頭部が一つの命題からのみなるホーン節に限定したもので、この場合の導出をSLD導出(Selective Linear resolution for Definite clause)と呼ぶ。ホーン節に限定しているということは、つまり、Prolog は任意の述語をそのまま扱えるわけではない。Prolog が述語の形式をホーン節に限定した理由は、もし頭部に項の連言を認めるならば、導出時の計算量が爆発的に増大して、全ての解を得ることの保証が難しくなることが必至だからである。
述語論理を論理的な背景に持つことによって、Prolog のプログラムはその正しさを確認することが比較的容易である。同時に、プログラマは Prolog でプログラミングすることが何を意味するかを明確に理解した上で、プログラムを書いていくことができる。
上記は Prolog の一つの解釈である。一方、Prolog というプログラム言語を述語論理という枠にはめないで捉える立場もある。導出、単一化、非決定性、双方向性、関係データベースといったこの言語に独特の機能とその表現力、記述力に着目し、そのプログラム言語としての可能性を率直に評価しようとするものだ。
新たに Prolog を学びたいと思う人は、他のプログラム言語を全く知らなくても、ソフトウェア科学的な予備知識や概念に不通であっても、単一化という単純なルールをほとんど唯一の基軸として、パズル的な、あるいはゲーム的な感覚にだけ導かれて、プログラムを簡単に書き進むことができる。さらに、どの言語にも比して平坦で、平明な言語構造を持つ Prolog はラベル名(アトム、関数名、述語名)に適切な意味性を付与することにより、自然言語の領域にも接近したプログラミングが期待できるほとんど唯一の言語でもある。
十分述語論理的な教養を持った上で Prolog を学び、そのプログラムを書くならば、短期間で高度で安定したプログラムを書くことができる。しかし、それを前提としないでも、Prolog は冒険的で、未知の領域に満ちたプログラム言語なのである。
実はこれらの主張は、述語論理的な主張に隠れて、これまであまり強調されたことがなかった。
このような立場や主張が生まれる背景には、Prolog が期待されたほどにはソフトウェア革新の担い手になり得ていない理由が、その後の数理論理学の学問的な評価をもって、プログラム言語としての可能性を十分検証することを放棄して、定理証明といった狭い目的へ封じ込めようとする風潮を生んだことにある、という反省がある。そのことを踏まえて、Prolog が述語論理から成立したことにこだわらず、実在するプログラム言語として自由な視点からこの言語を見直そうとするものである。
Prolog は LISP の資産の多くを継承して間違いなく記号処理用の言語であるが、人工知能言語として分類されることも多い。これは、人工知能の世界では述語論理が古くから理論的な柱の一つとなっているからである。述語論理を基礎とするトップ・ダウン式の問題解決と同じく述語論理を基礎とする Prolog の駆動機構の相性は当然良いため、人工知能研究に広く利用されてきた。特にエキスパートシステムで多用されるプロダクションシステムにおいては、ルールを自然に自ら動的に変更できる能力を持つことと、後ろ向き推論と呼ばれる推論が Prolog の導出過程そのものであることから、その最も主要な記述言語の位置を占めてきた。
Prolog は一階の述語論理に対応することから論理型言語に分類される汎用言語であるが、その主張の一行一行を独立して論理式とほとんど等価な表現で行うことから、最も代表的な宣言型言語と見なされている。Prolog のプログラム単位である述語の各節の本体に現れる質問単位である副目標数は平均5個以内と極めて少ない。この副目標と各節の頭部に現れる引数の組み合わせによって得られる関係が述語の意味を構成している考えられる。これが宣言型とされるゆえんである。
単一化は1960年代の述語論理理論の発展の鍵となった概念であるが、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 で必須の単一化アルゴリズムもすでに含まれていた。
1950年代以降、計算機上での定理証明の研究が活発になり、ギルモアのアルゴリズム(1960)やデービス・パトナムのアルゴリズム(1958,1960) 、プラウィツによる定理証明への単一化アルゴリズムの導入(1960)などを経て、1965年のロビンソンによる導出原理 や1960年代後半のラブランドによるモデル消去の証明手続きの成果からひとつの結実期を迎えた。その数年後の1971年マルセイユ大学のアラン・カルメラウアーとフィリップ・ルーセルのグループは自動定理証明システムとフランス語の自然言語解析システムとを組み合わせたコンピュータとの自然言語対話システムを作成していた。この際に自然言語解析システムも自動定理証明システムと共通の論理式という枠組みで構築できることに気が付き、論理式をそのままプログラムとして実行できる最初の Prolog を1972年に完成させた。これは数千年に及ぶ人類の叡智である論理学の成果をプログラム言語に置き換えたものと言えるが、現在の Prolog でプログラムの制御に使われるカットオペレータに相当する機能が最初から導入されるなど、現在の Prolog と同様、単なる定理証明システムではなくプログラミング言語として設計されたものだった。以下にその当時の Prolog プログラムの一部を示す。論理変数名の最初の文字が "*" で始まるなど、現在の Prolog とはシンタックスが異なる。
彼らグループに理論的な助言を与えていたエジンバラ大学のロバート・コワルスキとデービッド・H・D・ウォレンは汎用機 DECsystem10 上にマルセイユ大学とはシンタックスが異なる処理系を作り上げた。これは後に DEC-10 Prolog と呼ばれることになるが、ISO 標準規格を含む今日動作する Prolog 処理系はほとんどがこの系統のシンタックスに従っている。
コワルスキはその後、インペリアル・カレッジ・ロンドンに移り、1979年に集大成ともいえる「Logic for Problem Solving」を著し、その後のこの言語と論理プログラミングの研究に決定的な影響を与えた。
コワルスキの活動と DEC-10 Prolog の存在によって、英国は Prolog 研究の中心地となった。エジンバラ大学のW・F・クロックシンとC・S・メリシュの著わした「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年MITに留学中の中島秀之が「情報処理」誌に紹介記事を寄稿して、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が近山隆により設計されて使われた。ESPは多重継承を特徴とする当時としては先鋭のオブジェクト指向言語であったが、後にカプセル化の不備などが指摘されて、今日あまり話題となることはない。しかし、OSを記述するという課題を通じて、論理型言語にオブジェクト指向言語的要素を加えることによって、可読性が高まりプログラム管理がしやすくなることが確認された。その反面、Prolog のみでオペレーティングシステムを完全に記述してみる絶好の機会を逸したことも確かである。ESPはPSIを前提にせずに利用できるように、C言語で書き直したCESPが開発されたが、これが普及への起爆剤になることはなかった。後に述べるように、PrologのISO標準規格のモジュール仕様としてESPの採用が否決された1995-6年頃以降はほとんど利用されることはなくなった。
ここまで述べたように、Prologは ICOT によって持ち上げられた言語 Prolog との印象が強いが、Prolog というプログラミング言語から見ての ICOT の影響は実は限定的だった。淵所長ら ICOT の主研究テーマは並列論理型言語にあり、研究後半では Prolog そのものからは離れて行くことになる。PSI に使用した電子基盤を利用して並列推論マシン PIM が製作されて、Guarded Horn Clauses(GHC)に基づく並列演算処理を追加した KL1 が設計された。この環境に依存する形で、並列論理プログラム言語のKL1は知識プログラミング全般の研究に利用された。PSI と SIMPOS を使った研究も続けられはしたが、割り当てられた研究員の数は極めて少なかった。
ICOT の活動を総括して、知識プログラミング各課題において準備不足からくる未消化を指摘する向きが強いのだが、こと Prolog から見ての前半期の活動は、今日語られることも少ないが、極めて充実したものであったといえる。
ICOT の活動盛期の1984年京都大学の学生3名が研究課題として製作した Prolog-KABA がその性能の高さとアセンブラで記述されたことからくる高速性で世界を驚かせた。この処理系は MS-DOS 上で製品化されて Prolog の普及に大きく貢献した。Successful pop や末尾再帰の最適化など高い安定した性能で黎明期のパソコン上のビジネスソフトの基礎言語としての展開も期待されたが、16ビットの整数しか持たず、浮動小数点数も扱えない仕様であったため、この分野への展開は起こらなかった。この点はアセンブラで記述されて簡単には拡張できない点が裏目に出た。結果としてこの仕様の乏しさが、日本のビジネスソフトが知識プログラミングの水準との間に横たわる分水嶺を越えることができなかった原因の一つとなった。
1990年代に入ると制約論理プログラミングが注目され処理系が多数誕生した。これは Prolog から見ると引数の論理変数間の関係(制約)を記述可能に拡張したものである。制約論理型言語は、変数評価に遅延実行などを持ち込むことが必要となるが、連立方程式をはじめとする多くの課題で Prolog より記述が柔軟になる。Prolog の組込述語には引数が変数で渡るとエラーとなるものが多く、このため Prolog プログラマは変数が具体化されるように副目標の記述順序に気を配る必要がある。結果としてプログラミングに逐次性が生じる。制約論理プログラミングにおいては、後に変数が具体化されたときに検査されるための変数の間の制約を記述するだけで、この逐次性の拘束を解決して通過することができる。実はこの制約はPrologから見ても自然な拡張であり、むしろ Prolog の単一化が制約論理プログラミングの制約を「=」のみに限定したものだと解釈することができる。しかし、簡素で逐次的な性格を強く持つ Prolog の処理系に慣れた利用者が、制約論理プログラミングの述語中に更に変数制約の宣言を追加しなくてはならない負担を、受け入れているとは言い難い。制約論理プログラム処理系が Prolog のそれに置き換わる気配は、2013年11月現在においてもない。
ISO の標準化作業は1987年頃から作業委員会(WG17)が作られ、日本委員も情報処理学会から15名ほどがこれに加わった。1995年 ISO標準規格がISO/IEC 13211-1 Prolog-Part 1: General Coreとして制定された。さらに、2000年にはISO/IEC 13211-2 Prolog-Part 2: Moduleとしてモジュール仕様が追加して規格化された。モジュール仕様については日本委員から、ICOTによって作成されたESP(Extended Self-contained Prolog)を以てその標準とする案が出されていたが、これは否決された。
ISO標準規格はエジンバラ仕様 DEC-10Prolog を基調に既に一家をなしていた Quintus Prolog など有力ベンダと主としてヨーロッパの学者を主体にこれに日本などの委員が参加して作成された。この規格は現在 Prolog 処理系の製作者に指針を与え、大きな逸脱を心理的に妨げる役割を果たしているが、組込述語の個々の仕様ではベンダの意向が強く反映されたものの、全体としては最初に述べた論理学的立場を尊重して保守的で極めて小さな仕様となっている。そのため多くの Prolog 処理系はこの規格の述語を搭載しつつ、独自の拡張部分を修正したり削除することに消極的である。結果として個々の処理系の互換性の乏しさは残り、それは Prolog の弱点として認識されている。
JIS規格も一旦は2001年にJIS X 3013:2001が、"標題 プログラム言語Prolog―第1部:基本部"が要約JISとして発行されたが、2012年1月に何ら実効を見ること無く、「周知としての目的は終了した」として廃止された。
日本において、ICOT の活動時期から1990年代前半に掛けては、いわゆる人工知能ブームの時期であり、人工知能研究への期待はこの時期再び異様に高まった。LISP マシンによる医療情報エキスパートシステムでの成果は、人工知能の研究の成果の一部は情報処理に於いても利用可能なのではないかとの夢を抱かせた。このような評価の中で Prolog は人工知能のアセンブリ言語的な位置づけを期待された。知識情報処理はこの水準の言語を基礎にその上側に築かれるべきだとの意味である。手っ取り早く利用可能な人工知能技術としてエキスパートシステムが選別され、これを支えるナレッジエンジニアの存在とそれを養成するための教育が必要とされた。Prolog はその中心に存在した。日本も例外ではないが、日本以外の国では特に、Prolog の名著は1990年代前半に刊行されている。これは、ICOT の活動とは若干のタイムラグがあるが、この時期社会的に 人工知能向き言語としての Prolog に大きな期待が寄せられていたことの証しである。エキスパートシステムはビジネス分野において広範囲に応用可能な基礎技術であったが、このような低水準な分野への適用はあまり試みられず、この分野からの Prolog 言語への要請はほとんど見られないまま終った。
機械翻訳などの自然言語処理もまた人工知能の一翼を担う分野であるが、歴史的経緯から人工知能ブーム以前から、この言語に最も期待が掛けられた分野であった。しかし、左再帰問題の回避でトップダウン解析の明解さをいきなり殺がれた。さらに句構造文法への適用においては、Prolog が得意とする、句構造に分解して意味に相当するグラフを形成することの他に、極めて膨大な辞書を構造体として定義する必要が展望された。この辞書作成は Prolog とは直接関係しないタスクであることから、次第に Prolog は句構造文法によるアプローチの前線から後退してしまった。統計的言語処理のアプローチでは、単一化等に多くの計算量を費やす Prolog は大量データを扱うのに不向きとされて、利用されることはほとんどない。自然言語処理のテキストの多くが Prolog を用いて解説されているにも関わらず、期待が大きかった割に実務的には、表面に現れている成果はIBM社のワトソン程度にとどまり、自然言語処理はむしろ Prolog 評価の足を引っ張る傾向にさえある。