Planner
Planner("PLANNER"とも表記される)は、1969年にMITのカール・ヒューイットが設計したプログラミング言語。当初、サブセットの Micro-Planner や Pico-Planner が実装され、後に完全実装として Popler が登場。その後、派生言語として QA-4、Conniver、QLISP、Ether などが実装され、1970年代の人工知能研究の道具として重要な役割を果たし、商用の KEE や ART の開発にも影響を与えた。
当時マービン・ミンスキー、シーモア・パパート、Mike Peterson の学生だったヒューイットは、「知識の手続き的埋め込み」論者であり、高レベルの手続き的計画によるアプローチを信奉していた。当時、ジョン・マッカーシーらは人工知能(AI)のための知識表現として数理論理学を用いた宣言的かつ論理的アプローチを信奉しており、両者は対立関係にあった。このことは次のような基本的な疑問を生み出した。「手続き的アプローチと論理的アプローチの違いは何か?」である。これに答えが出せるようになるまで数年を要した。
ヒューイット[2006]によれば、Planner は「手続き的計画; procedural plan」機能を持つ世界初の言語であり、これを「ゴール」と「表明; assertion」を使った「パターン管理呼び出し; pattern-directed invocation」と呼ぶ。Planner のサブセット Micro-Planner は Gerry Sussman、Eugene Charniak、テリー・ウィノグラードらが実装し、ウィノグラードの自然言語理解プログラム SHRDLU、Eugene Charniak のストーリー理解のプロジェクトなどに使われた。これらの成果は人工知能分野を活気付かせた。また、当時主流であった論理的アプローチとは異なる手法を提案していたため、論争を呼ぶこととなった。
エジンバラ大学の Bruce Anderson は Planner のサブセット Pico-Planner を実装し、同じエジンバラ大学の Julian Davies は完全な Planner 言語処理系である Popler を実装した。SRIでは、ジェフ・ルリフソン、Jan Derksen、Richard Waldinger らは、Planner の文法をベースにしてデータベースのモジュール性を提供する機構としてコンテキスト機構を導入した QA4 を開発した。同じ SRI の Earl Sacerdoti と Rene Reboh は QA4 を InterLisp 上に実装した QLISP を開発し、これをいくつかのアプリケーション開発に使用した。論理的アプローチ派の Robert Kowalski は Alain Colmerauer と共同で Micro-Planner によく似た Prolog の開発に関わった。実際、ヒューイットは Prolog を Micro-Planner のサブセットの再発明とみなした。というのは、Prolog が単にパターンの一致によってゴールを得るだけなのに対して、Micro-Planner は手続き的計画を呼び出すこともできたからである。しかし、Kowalski 自身は Prolog を人工知能開発へのアプローチのひとつとして論理的パラダイムを保持するものと考えていた。
ヒューイット[2006]にもあるように、Planner 開発当時のコンピュータメモリは高価であり容量が小さかった。そこでメモリの使用を節約するため、制御構造として当時一般的だったバックトラッキングを採用した。この手法では、コンピュータはいくつもの可能性のうちひとつだけをメモリに保持しておけばよかったのである。
この実装上の決断により、Micro-Planner は不運な結果を招くこととなった。LISPでは <tt>NIL</tt> を空のリストを表すと同時に <tt>false</tt>(メモリ番地 0)を表すようにしている。というのも 0 かどうかのチェックが高速に行えるからである。このため、LISPプログラムでは <tt>NIL</tt>かどうかのチェックは非常に頻繁に行われる。Micro-Planner はこれを拡張して <tt>NIL</tt> をバックトラッキング開始のシグナルとしても扱った。Micro-Planner では、リストの各要素に何らかの処理をループで行うのが一般的だが、このとき先頭の要素をリストから除去した残りのリストを持ってループの先頭に分岐し、リストが空かどうかをチェックする。リストが空だった場合、プログラムは次の別の処理に分岐する。このようなプログラムで最後の要素が処理され、それをリストから取り除いた残りのリストが <tt>NIL</tt> になったとき、それをチェックする部分にはプログラムは到達しない。というのも、Micro-Planner は <tt>NIL</tt> に到達したときにそれをバックトラッキングのシグナルとして扱い、それまでリストの各要素に対して行った処理を取り消してしまうのである。このことに人々は驚かされた。
このことはバックトラッキングの扱いにくさを証明し、制御構造に関する議論が活性化されることとなった。ヒューイットは他の可能な実装方法を調査した。
ヒューイットは Mike Paterson と共に、再帰呼び出し(recursion)が繰り返し(iteration)よりも強力であること、並列処理が逐次的再帰よりも強力であることを証明した。ヒューイットは同時にコルーチンが再帰よりも強力であると推測したが、最近の強力な形式手法を使うまでそれを証明できなかった。
ヒューイット[2006]によれば、Peter Landin は J (Jump) 演算子を使って非常に強力な制御構造を導入した。これはプロシージャ呼び出しの途中に飛び込むことが可能なローカルでない goto である。実際、J 演算子は既にリターン済みのプロシージャ呼び出しの途中に分岐して戻ることができる。Drew McDermott と Gerald Sussman は、Landin のコンセプトを 「Hairy Control Structure; 複雑な制御構造(Hairy はハッカー用語。本来の意味は"毛深い")」と呼び、Conniver 言語に実装した。スコット・ファールマンはこれをロボット開発に活用した。このコンセプトは現在再呼び出し可能な継続と呼ばれているものと関連している。
ヒューイットは次のように述べている。「…"Hairy control structure"(例えば CONNIVER のような可能性リスト、ローカルでない goto、他のプロシージャの内部変数への値の代入など)を使わない手法を発見した…通常のメッセージパッシングが問題解決モジュール間の協調動作に関して、より構造化され直観的な通信システムを構築する基礎となる。」すなわち、アクターモデルが人工知能の制御構造問題を解決する基礎となるとした。アクターモデルのためのプログラム方法論を開発するにはかなりの時間を要した。しかし、Scientific Community Metaphorの実装には洗練されたメッセージパッシングを必要とし、今も研究課題のひとつとなっている。
制御構造の議論はプログラミング言語としての数理論理学の使用の可能性に関して議論を呼んだ。手続き的アプローチは、数理論理学とは異なる数学的意味論(表示的意味論参照)を持つ。数理論理学だけでは、非決定性を持つ並列システムや分散システムを記述できない。