殆んどのプログラム言語は, Lispも含め, 数学的関数の値の計算の回りに構成されている. (Lisp, FortranおよびAlgolのような)式主導の言語は, 関数の値を記述する式は, またその値を計算する方法として解釈されるという「しゃれ」を利用している. この故に, 殆んどのプログラム言語は一方向性計算(明確に定義した入力と出力を持つ計算)へ強く偏っている. しかしこの偏りを緩める全く異ったプログラム言語も存在する. その一つの例を3.3.5節で見た. そこでは計算のオブジェクトが算術的制約であった. 制約システムでは, 計算の方向と順序は, 十分には規定されない; 計算を実行するのに, システムは通常の算術演算の場合より遥かに詳細な「いかにして」の知識を用意しなければならない. しかしこれは利用者が命令的知識を用意する責任からすっかり解放されたということではない. 同一の制約の組を実装する多くの制約ネットワークが存在し, 利用者は数学的に等価なネットワークの集合から特定の計算を規定するのに適したネットワークを選ぶ必要がある.
4.3節の非決定性プログラム評価器もまた, プログラミングは一方向性関数を計算するアルゴリズムを構成することだという視点から遠ざかった. 非決定性言語では, 式は一つを超える値をとることが出来, その結果, 計算は一価関数というよりは, 関係を扱う. 論理型プログラミングは, プログラミングの関係的視点と, ユニフィケーション(unification)という強力な記号パターンマッチを組み合せて, この考えを拡張する.58
この解決法は, うまくいく時は, プログラムを書く極めて強力な方法となり得る. その力の一部は, 単一の「何である」の事実が, 多くの「いかにして」の要素を持つ, 複数の異る問題を解くのに使えるということに由来する. 例として, 引数として二つのリストをとり, その要素を組み合せて単一のリストを形成する append演算を考えよう. Lispのような手続き型言語では, appendを2.2.1節でやったように, 基本的なリスト構成子consを使って定義出来る:
(define (append x y)
(if (null? x)
y
(cons (car x) (append (cdr x) y))))
この手続きは, 次の二つの規則をLispに翻訳したものと考えられる. 第一の規則は, 第一のリストが空の場合を扱い, 第二は二つの部分のconsである, 空ではないリストの場合を扱う: (a b)と(c d)のappendを見つけよ.というような質問に答えることが出来る. しかしこの同じ二つの規則は, 手続きには答えられない次のような質問に答えるのに十分である.
(a b)とappendすると(a b c d)になるリストyを見つけよ.
appendすると(a b c d)になるすべてのxとyを見つけよ.
論理型プログラム言語では, プログラマはappend「手続き」を, 上に示したappendについての二つの規則を述べることで書く. 「いかにして」の知識は, この単純な一対の規則がappendに関する三つの型の質問の回答に使えるよう, 解釈系が自動的に用意する.60
(ここで実装するものも含め)現代の論理型プログラム言語は, その一般的な「いかにして」方法が, まがいの無限ループや, その他の望ましくない振舞いにいき着くという, 本質的な欠陥を持っている. 論理型プログラミングは, 計算機科学における活発な研究分野である.61
本章の初めの方では, 解釈系を実装する技法を調べ, Lisp風言語の解釈系(実際には一般の言語の解釈系)に本質的な要素について述べた. ここではこれらの考えを論理型プログラム言語の解釈系の議論に応用しよう. この言語は, それで表現された
質問
(query), つまり問合せを構成して, データベースから情報を検索するのに有効なので,
質問言語(query language)と呼ぼう. 質問言語はLispとは非常に違っているが,
これまで使ってきたのと同じ一般的枠組によって, 言語を記述するのが便利なことが分る. 枠組とは, 基本要素の集りと, 単純な要素を組み合せ, より複雑な要素を作り出す組合せの手段と, 複雑な要素を一つの概念的な単位と見なす抽象の手段である. 論理型プログラム言語の解釈系は, Lispのような言語の解釈系より, かなり複雑である. それにも拘らず, われわれの
質問言語の解釈系は, 4.1節の解釈系に見られたのと同じ要素の多くを含んでいるのが分る. 特に, 式を型に従って分類する「eval」部分と,
言語の抽象機構(Lispの場合は手続き, 論理型プログラミングの場合は規則
(rule))を実装する「apply」部分があるであろう. また実装の中心的役割を演ずるのは, 記号とそれに対応した値の関係を決める, フレームデータ構造である. 質問言語の実装のもう一つの面白い点は, 3章で説明したストリームを本格的に使うことである.
58
論理型プログラミングは, 自動定理証明の研究の長い
歴史から成長した. 初期の定理証明のプログラムは, 可能な証明の空間をしらみつぶしに探したので, 殆んど何も出来なかった. そういう探索を可能にした突破口は, 1960年代の初めの
ユニフィケーションアルゴリズム(unification algorithm)と
導出原理(resolution
principle)の発見であった(Robinson 1965). 導出原理は例えば
Greenと
Raphael(1968)(Green 1969も参照)により, 推論的質問回答システムの基盤として使われた. この時期の殆んどで, 研究者は証明が存在するならその発見を保証するアルゴリズムに注力した. そういうアルゴリズムは, 証明に向け制御し, 誘導するのが困難であった.
Hewitt(1969)は, プログラム言語の制御構造を, 論理操作システムの演算と混ぜ合せる可能性を認め, 4.3.1節(脚注47)に述べた自動探索の研究に進んだ. これと同じ頃, マルセーユの
Colmerauerは, 自然言語を操作する規則主導システムを開発していた(Colmerauer他1973参照). 彼はこれらの規則を表現するため,
Prologというプログラム言語を発明した. エディンバラの
Kowalski(1973; 1979)は, Prologプログラムの実行は,
(線形
Horn節導出という証明技法を使って) 定理の証明と解釈出来ると認めた. この二つの流れは合流して論理型プログラミング運動になった. このように論理型プログラミングの開発の名誉を与えるのに, フランス人は
マルセーユ大学のPrologの創世記を指すことが出来, イギリス人は
エディンバラ大学の研究を強調出来る.
MITの人たちによれば, 論理型プログラミングは, Hewittの見事だが不可解な学位論文でいっていることを解明しようという試みからこれらの人々により開発された. 論理型プログラミングの歴史については
Robinson 1983を参照のこと.
59
規則と手続きの対応を見るには, (x
が空でないとして)手続きのxが規則の(cons u v)に対応するとする. その時, 規則のzは(cdr x)とyのappendに対応する.
60
確かにこれは利用者を, 解をいかに計算するかの全体的な問題から解放するのではない. appendの関係を形式化する数学的に等価で異る多くの組が存在し, そのうちのほんの一部が, どの方向の計算にも有効な仕掛けであることが分る. その上時には「何である」情報は, 時には解を「いかにして」計算するかの手がかりを与えない. 例えば$y^2 = x$なる$y$を計算する問題を考えてみよう.
61
論理型プログラミングへの関心は, 80年代初めに頂点に達した.
その頃日本政府は論理型プログラム言語を走らせるのに最適化した超高速計算機建設を目標とした野心的プロジェクトを開始した. そういう計算機の速さは,
FLOPS(FLoating-point Operations Per Second)ではなく, LIPS(Logical Inferences
Per Second)で計測することになっていた. プロジェクトは最初に計画したようなハードウェアとソフトウェアの開発には成功したが, 国際的な計算機産業は異る方向へ向った. 日本のプロジェクトの総括的評価については,
Feigenbaumおよび
Shrobe 1993参照. 論理型プログラミング社会もまた, 単なるパターンマッチ以外の, 3.3.5節の制約伝搬システムに示すような数量制約が扱えるような技法に基づく, 関係プログラミングを検討する方向へ進んだ.