Planner

Planner（"PLANNER"とも表記される）は、1969年にMITのカール・ヒューイットが設計したプログラミング言語。当初、サブセットの Micro-Planner や Pico-Planner が実装され、後に完全実装として Popler が登場。その後、派生言語として QA-4、Conniver、QLISP、Ether などが実装され、1970年代の人工知能研究の道具として重要な役割を果たし、商用の KEE や ART の開発にも影響を与えた。

当時マービン・ミンスキー、シーモア・パパート、Mike Peterson の学生だったヒューイットは、「知識の手続き的埋め込み」論者であり、高レベルの手続き的計画によるアプローチを信奉していた。当時、ジョン・マッカーシーらは人工知能(AI)のための知識表現として数理論理学を用いた宣言的かつ論理的アプローチを信奉しており、両者は対立関係にあった。このことは次のような基本的な疑問を生み出した。「手続き的アプローチと論理的アプローチの違いは何か?」である。これに答えが出せるようになるまで数年を要した。

Plannerの初期の歴史

ヒューイット[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では NIL を空のリストを表すと同時に false（メモリ番地 0）を表すようにしている。というのも 0 かどうかのチェックが高速に行えるからである。このため、LISPプログラムでは NILかどうかのチェックは非常に頻繁に行われる。Micro-Planner はこれを拡張して NIL をバックトラッキング開始のシグナルとしても扱った。Micro-Planner では、リストの各要素に何らかの処理をループで行うのが一般的だが、このとき先頭の要素をリストから除去した残りのリストを持ってループの先頭に分岐し、リストが空かどうかをチェックする。リストが空だった場合、プログラムは次の別の処理に分岐する。このようなプログラムで最後の要素が処理され、それをリストから取り除いた残りのリストが NIL になったとき、それをチェックする部分にはプログラムは到達しない。というのも、Micro-Planner は NIL に到達したときにそれをバックトラッキングのシグナルとして扱い、それまでリストの各要素に対して行った処理を取り消してしまうのである。このことに人々は驚かされた。

このことはバックトラッキングの扱いにくさを証明し、制御構造に関する議論が活性化されることとなった。ヒューイットは他の可能な実装方法を調査した。

制御構造のクラス分け

ヒューイットは Mike Paterson と共に、再帰呼び出し(recursion)が繰り返し(iteration)よりも強力であること、並列処理が逐次的再帰よりも強力であることを証明した。ヒューイットは同時にコルーチンが再帰よりも強力であると推測したが、最近の強力な形式手法を使うまでそれを証明できなかった。

Hairy Control Structure

ヒューイット[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の実装には洗練されたメッセージパッシングを必要とし、今も研究課題のひとつとなっている。

数理論理学の限界

制御構造の議論はプログラミング言語としての数理論理学の使用の可能性に関して議論を呼んだ。手続き的アプローチは、数理論理学とは異なる数学的意味論（表示的意味論参照）を持つ。数理論理学だけでは、非決定性を持つ並列システムや分散システムを記述できない。

参考文献

Carl Hewitt. PLANNER: A Language for Proving Theorems in Robots IJCAI 1969
Gerry Sussman and Terry Winograd. Micro-planner Reference Manual AI Memo No, 203, MIT Project MAC, July 1970.
Terry Winograd. Procedures as a Representation for Data in a Computer Program for Understanding Natural Language MIT AI TR-235. January 1971.
Carl Hewitt. Procedural Embedding of Knowledge In Planner IJCAI 1971.
Gerry Sussman, Terry Winograd and Eugene Charniak. Micro-Planner Reference Manual (Update) AI Memo 203A, MIT AI Lab, December 1971
Carl Hewitt. Description and Theoretical Analysis (Using Schemata) of Planner, A Language for Proving Theorems and Manipulating Models in a Robot AI Memo No. 251, MIT Project MAC, April 1972.
Bruce Anderson. Documentation for LIB PICO-PLANNER School of Artificial Intelligence, Edinburgh University. 1972
Bruce Baumgart. Micro-Planner Alternate Reference Manual Stanford AI Lab Operating Note No. 67, April 1972.
Eugene Charniak. Toward a Model of Children's Story Comprehension MIT AI TR-266. December 1972.
Julian Davies. Popler 1.6 Reference Manual University of Edinburgh, TPU Report No. 1, May 1973.
Jeff Rulifson, Jan Derksen, and Richard Waldinger. QA4, A Procedural Calculus for Intuitive Reasoning SRI AI Center Technical Note 73, November 1973.
Robert Kowalski Predicate Logic as Programming Language Memo 70, Department of Artificial Intelligence, Edinburgh University. 1973
Pat Hayes. Computation and Deduction Mathematical Foundations of Computer Science: Proceedings of Symposium and Summer School, Štrbské Pleso, High Tatras, Czechoslovakia, September 3-8, 1973.
Carl Hewitt, Peter Bishop and Richard Steiger. A Universal Modular Actor Formalism for Artificial Intelligence IJCAI 1973.
Drew McDermott and Gerry Sussman. The Conniver Reference Manual MIT AI Memo 259A. January 1974.
Earl Sacerdoti, et. al., QLISP A Language for the Interactive Development of Complex Systems AFIPS. 1976
William Kornfeld and Carl Hewitt. The Scientific Community Metaphor MIT AI Memo 641. January 1981.
Carl Hewitt. The Challenge of Open Systems Byte Magazine. April 1985
Robert Kowalski. The limitation of logic Proceedings of the 1986 ACM fourteenth annual conference on Computer science.
Robert Kowalski. The Early Years of Logic Programming CACM January 1988.
Carl Hewitt and Gul Agha. Guarded Horn clause languages: are they deductive and logical? in Artificial Intelligence at MIT, Vol. 2. MIT Press 1991.
Carl Hewitt. The repeated demise of logic programming and why it will be reincarnated What Went Wrong and Why: Lessons from AI Research and Applications. Technical Report SS-06-08. AAAI Press. March 2006.

外部リンク

Alain Colmerauer's and Philippe Roussel's 1992 account of the birth of Prolog