論理プログラミング
問題解決(problem solving)とその実践の導出原理は、数理論理学の膨大な知識から様々なものが存在する。ここではシンプルなロジックの代表格のホーン節を例にする。ホーン節は最大1個の正リテラルを持つ選言標準形をベースにしており、命題論理のホーン節は、素直にAND-OR木(英語版)に投影できる。(右図はこの説明には不向きだが、これしか無かったのであしからず)右図のAND-OR木では、最上ノードのPがゴールになり、末端ノードのT・U・R・Sはファクトになって、このように解釈できる。
if Q and R then P, if S then P, if T then Q, if U then Q.
それへの導出原理は、ファクトから問題解決する前向き連鎖と、ゴールから問題解決する後向き連鎖に大別される。前向き連鎖は、与えられたファクトから様々な別のファクトをゴールとして解答する演繹手法である。TとRを与えるとPが解答される。Sを与えるとPが解答される。前向き連鎖はエキスパートシステムなどに使われている。後向き連鎖は、与えられたゴールがファクトかどうかを解答する演繹手法である。Pを与えるとその前件のRおよびQのそのまた前件のTがファクトなのでPはファクトと解答される。後向き連鎖は論理型言語の代表Prologに使われている。
述語論理のホーン節は、AND-OR木の各ノードが命題から述語になるので複雑になる。各ノードの述語記号の項は、定項と変項に分かれるが、定項がファクトで、変項が単一化によるファクトに束縛可能なら、そのノードは述語から命題になれる。
手続き的の支持者は、マサチューセッツ工科大学中心のマービン・ミンスキー、シーモア・パパート、カール・ヒューイット、ジェラルド・サスマン、テリー・ウィノグラード、ユージン・チャニアク(英語版)らであった。
Plannerの登場
1969年、カール・ヒューイット設計の論理型言語「Planner」がマサチューセッツ工科大学で開発された。メインフレーム前提のPlannerの大規模さは運用できる環境を制限したので、1971年にポータビリティ重視のサブセット版「Micro-Planner」が、ジェラルド・サスマンとテリー・ウィノグラードらによって開発された。
1971年、パパート、サスマン、チャニアクらのMIT勢が、エディンバラ大学を訪問してMicro-PlannerとSHRDLUを披露した。当時の同大学は、対話型自動定理証明プロジェクト「Logic for computable functions」が始動されていた論理プログラミングのメッカであった。Micro-Plannerなどを見たパット・ヘイズ(英語版)らは手続き的の価値を認め、同大学でもMicro-Plannerのサブセット版を実装してその有用性を確認した。Plannerを研究したロバート・コワルスキ(英語版)は、アルフレッド・ホーン発案のホーン節の論理プログラミング導入を提唱し、それへのSLD導出を考案している。更にエディンバラ大学ではPlannerのスーパーセット版「Popler」も開発された。
Prologの登場