Planner

Planner：手続き型AI言語の先駆け

Planner（プランナー）は、1969年にMITのカール・ヒューイットによって設計されたプログラミング言語です。人工知能（AI）研究において、手続き的な知識表現を重視した初期の言語として重要な役割を果たしました。当初、サブセットとしてMicro-PlannerやPico-Plannerが実装され、その後完全な実装であるPoplerが登場しました。

Plannerの誕生と背景

当時、マービン・ミンスキー、シーモア・パパート、マイク・ピーターソンの学生であったヒューイットは、「知識の手続き的埋め込み」を提唱し、高レベルな手続き的計画によるアプローチを支持していました。これは、ジョン・マッカーシーらが提唱する数理論理学を用いた宣言的アプローチとは対立するものでした。この対立は、「手続き的アプローチと論理的アプローチの違いは何か？」という基本的な疑問を生み出し、その答えを見つけるまで数年を要しました。

Plannerの初期の歴史

ヒューイットによれば、Plannerは「手続き的計画」機能を持つ世界初の言語であり、これを「ゴール」と「表明」を使った「パターン管理呼び出し」と定義しました。サブセットであるMicro-Plannerは、ジェリー・サスマン、ユージーン・チャーニアック、テリー・ウィノグラードらによって実装され、ウィノグラードの自然言語理解プログラムSHRDLUやチャーニアックのストーリー理解プロジェクトなどに利用されました。これらの成果は人工知能分野を活性化させましたが、同時に論理的アプローチとは異なる手法を提案していたため、論争を呼ぶことにもなりました。

エジンバラ大学のブルース・アンダーソンはPlannerのサブセットであるPico-Plannerを実装し、同じ大学のジュリアン・デイビスは完全なPlanner言語処理系であるPoplerを開発しました。SRIでは、ジェフ・ルリフソン、ヤン・ダーケセン、リチャード・ワルディンガーらがPlannerの文法をベースに、データベースのモジュール化を可能にするコンテキスト機構を備えたQA4を開発しました。また、アール・サセルドティとレネ・リボーはQA4をInterLisp上に実装したQLISPを開発し、いくつかのアプリケーション開発に利用しました。

論理的アプローチ派のロバート・コワルスキーは、アラン・コルメローと共同でMicro-Plannerに類似したPrologの開発に関わりました。ヒューイットはPrologをMicro-Plannerのサブセットの再発明とみなしましたが、コワルスキー自身はPrologを論理パラダイムに基づく人工知能開発のアプローチと捉えていました。

制御構造に関する議論

Planner開発当時のコンピュータメモリは高価で容量も小さかったため、メモリ使用を節約するためにバックトラッキングが採用されました。しかし、この実装上の決定はMicro-Plannerに不運な結果をもたらしました。LISPでは、NILが空のリストとfalseの両方を表すために、Micro-Plannerではこれをバックトラッキング開始のシグナルとして扱いました。このため、リスト処理時にNILが検出されると処理が取り消されてしまうという問題が発生し、制御構造に関する議論が活発化しました。

制御構造のクラス分け

ヒューイットはマイク・パターソンと共に、再帰呼び出しが反復処理よりも強力であり、並列処理が逐次再帰よりも強力であることを証明しました。また、コルーチンが再帰よりも強力であると推測しましたが、最近になって形式手法によって証明されました。

Hairy Control Structure

ピーター・ランディンは、J（ジャンプ）演算子を使って強力な制御構造を導入しました。これはプロシージャ呼び出しの途中に飛び込むことが可能なローカルでないgotoです。ドリュー・マクダーモットとジェラルド・サスマンは、このコンセプトを「Hairy Control Structure（複雑な制御構造）」と呼び、Conniver言語に実装しました。スコット・ファールマンはこれをロボット開発に応用しました。このコンセプトは現在、再呼び出し可能な継続と呼ばれているものに関連しています。

制御構造はメッセージパッシングのパターンである

ヒューイットは、複雑な制御構造を使わないで、通常のメッセージパッシングが問題解決モジュール間の協調動作に関してより構造化された直観的な通信システムを構築する基礎となることを示しました。つまり、アクターモデルが人工知能の制御構造問題を解決する基盤となるとしました。アクターモデルのためのプログラミング方法論の開発には時間がかかりましたが、Scientific Community Metaphorの実装には洗練されたメッセージパッシングが必要であり、現在も研究課題となっています。

数理論理学の限界

制御構造の議論は、プログラミング言語としての数理論理学の可能性に関する議論を呼びました。手続き的アプローチは、数理論理学とは異なる数学的意味論を持ちます。数理論理学だけでは、非決定性を持つ並列システムや分散システムを記述することができません。

まとめ

Plannerは、人工知能分野における手続き型プログラミングの先駆けとして、その後の研究に大きな影響を与えました。特に、制御構造に関する議論やアクターモデルの基礎となるメッセージパッシングの概念は、現代のプログラミングパラダイムにも重要な示唆を与えています。Plannerの歴史を辿ることは、人工知能の発展を理解する上で不可欠と言えるでしょう。

参考文献

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

もう一度検索