From Wikipedia, the free encyclopedia

Planner (often seen in publications as "PLANNER") is a programming language designed by Carl Hewitt at MIT, and first published in 1969. First subsets such as Micro-Planner and Pico-Planner were implemented and then essentially the whole language was implemented in Popler, and derivations such as QA-4, Conniver, QLISP and Ether (see Scientific Community Metaphor) were important tools in Artificial Intelligence research in the 1970s, which influenced commercial developments such as KEE and ART.

Hewitt (then a student of Marvin Minsky, Seymour Papert and Mike Paterson) championed the "procedural embedding of knowledge" in the form of high level procedural plans in contrast to the logical approach pioneered by John McCarthy who advocated expressing knowledge declaratively in mathematical logic for artificial intelligence (AI). This raised a fundamental question: "What is the difference between the procedural and logical approaches?" It took several years to provide an answer to this question.

Contents 1 Procedural Embedding of Knowledge 2 History 2.1 Control structure controversy 2.2 Control structure characterizations 2.3 Hairy control structure 2.4 Control structures are patterns of passing messages 3 The Genesis of Prolog 4 References 5 See also 6 External links

The two major paradigms for constructing semantics software systems were procedural and logical. The procedural paradigm was epitomized by Lisp [McCarthy et. al. 1962] which featured recursive procedures that operated on list structures. The logical paradigm was epitomized by uniform proof procedure resolution theorem provers [Robinson 1965]. According to the logical paradigm it was “cheating” to incorporate procedural knowledge.

Planner was a kind of hybrid between the procedural and logical paradigms because it featured a procedural interpretation of logical sentences where an implication of the form (P implies Q) can be procedurally interpreted in the following ways:

1. Forward chaining (antecedently):

• If assert P, assert Q

  If assert not Q, assert not P

1. Backward chaining (consequently)

• If goal Q, goal P

  If goal not P, goal not Q

In this respect, the development of Planner was influenced by natural deductive logical systems (especially the one by Frederic Fitch [1952]).

According to Hewitt [2006], Planner was the first language to feature procedural plans that were called by pattern-directed invocation using goals and assertions. A subset called Micro-Planner was implemented by Gerry Sussman, Eugene Charniak and Terry Winograd [Sussman, Charniak, and Winograd 1971] and was used in Winograd's natural-language understanding program SHRDLU, Eugene Charniak's story understanding work, Thorne McCarty's work legal reasoning, and some other projects. This generated a great deal of excitement in the field of AI. It also generated controversy because it proposed an alternative to the logic approach that had been one of the mainstay paradigms for AI.

Bruce Anderson at the University of Edinburgh implemented a subset of Planner called PICO-PLANNER and Julian Davies at Edinburgh implemented Popler, essentially the whole of Planner. At SRI, Jeff Rulifson, Jan Derksen, and Richard Waldinger developed QA4 which built on the constructs in Planner and introduced a context mechanism to provide modularity for expressions in the data base. Also at SRI, Earl Sacerdoti and Rene Reboh implemented QA4 as an extension of Interlisp, in a language called QLISP which was efficient enough to be used in several applications. Bob Kowalski, who had been one of the principal members of the logic paradigm community, then adapted, in collaboration with Alain Colmerauer, some theorem proving ideas into a form similar to a subset of Micro Planner called Prolog. Indeed, Hewitt considers Prolog to be largely a reinvention of a subset of Micro Planner, e.g., Micro Planner (unlike Prolog) had the capability to use pattern-directed invocation of procedural plans from assertions as well as goals. But compare Kowalski's paper on the early history of logic programming. Using Prolog, Kowalski hoped to save the logic paradigm as a viable approach to Artificial Intelligence.

As related in Hewitt [2006], computer memories were very small by current standards because they were expensive, being made of iron ferrite cores at that time. So Planner adopted the then common expedient of using backtracking control structures to economize on the use of computer memory. In this way, the computer only had to store one possibility at a time in exploring alternatives.

One implementation decision in Micro Planner had unfortunate consequences. Lisp had adopted the programming pun of identifying NIL, the empty list with logical false (at memory location 0) because testing for 0 was faster than anything else. Because of the pun, testing for NIL was extremely common in Lisp programs. Micro Planner extended this pun also to use NIL as a signal to begin backtracking. In Micro Planner, it was common to write programs to perform some operation on every element of a list by using a loop to process the first element of a list, take the rest of the list, and then jump back to the top of the loop to test if the list was empty. If the list tested empty, then the program would go on to do other things. Such a program never made it to testing the empty list after processing all the elements because when the last element was processed and the rest of the list was taken, NIL was returned as a value. The Micro Planner interpreter took this as the signal to begin backtracking and began undoing all the work of processing the elements of the list.

In this and several other ways, backtracking proved unwieldy, helping to fuel the great control structure debate. Hewitt investigated some alternatives in his thesis.

Using program schemas, Hewitt in collaboration with Mike Paterson proved that recursion is more powerful than iteration and parallelism more powerful than sequential recursion.^{[citation needed]} (He also conjectured that coroutines are more powerful than recursion but couldn't convincingly prove it until recently using a more powerful formalism.)

According to Hewitt [2006], Peter Landin had introduced an even more powerful control structure using his J (for Jump) operator that could perform a nonlocal goto into the middle of a procedure invocation. In fact the J operator could jump back into the middle of a procedure invocation even after it had already returned. Drew McDermott and Gerald Sussman called Landin's concept the "Hairy Control Structure" and used it in the form of a nonlocal goto for the Conniver programming language. Scott Fahlman used Conniver in his planning system for robot construction tasks. This is related to what are now called Re-invocable Continuations.

Difficulties in communication were a root cause of the control structure difficulties.

Hewitt reported: ... we have found that we can do without the paraphernalia of "hairy control structure" (such as possibility lists, non-local gotos, and assignments of values to the internal variables of other procedures in CONNIVER.)... The conventions of ordinary message-passing seem to provide a better structured, more intuitive foundation for constructing the communication systems needed for expert problem-solving modules to cooperate effectively. The Actor model provided the foundation for solving the Artificial Intelligence control structure problem. It took considerable time to develop programming methodologies for the Actor model. Indeed, the implementation of the Scientific Community Metaphor requires sophisticated message passing that is still the subject of research.

Gerry Sussman [Sussman, Winograd and (Charniak 1971), Seymour Papert (Minsky and Papert 1971), and Terry Winograd (Winograd 1971); visited Edinburgh spreading the news about Micro-Planner and SHRDLU casting doubt on the resolution uniform proof procedure approach that had been the mainstay of the Edinburgh Logicists. At the University of Edinburgh, Bruce Anderson implemented a subset of Micro-Planner called PICO-PLANNER (Anderson 1972) and Julian Davies (1973) implemented essentially all of Planner.

The above developments generated tension among the Logicists at Edinburgh. These tensions were exacerbated when the UK Science Research Council commissioned Sir James Lighthill to write a report on the AI research situation. The resulting report Lighthill 1973; McCarthy 1973] was highly critical although SHRDLU was favorably mentioned.

The Edinburgh Logicists Bob Kowalski (1973) and Pat Hayes (1973) (correctly) perceived that much of Micro-Planner could be carried out in classical mathematical logic. So Kowalski (influenced by Hayes) adapted some of the ideas of Micro-Planner (in collaboration with Alain Colmerauer) to create a subset of Micro-Planner called Prolog.

Prolog duplicated the following aspects of Micro-Planner:

• Pattern directed invocation of procedures from goals (i.e. backward chaining)
• An indexed data base of pattern-directed procedures and ground sentences.
• Giving up on the completeness paradigm that had characterized previous work on theorem proving and replacing it with the programming language procedural embedding of knowledge paradigm.

Prolog also duplicated the following capabilities of Micro-Planner which were pragmatically useful for the computers of the era because they saved space and time:

• Backtracking control structure
• Unique Name Assumption by which different names are assumed to refer to distinct entities, e.g., Peking and Beijing are assumed to be different.
• Reification of Failure. The way that Planner established that something was provable was to successfully attempt it as a goal and the way that it establish that something was unprovable was to attempt it as a goal and explicitly fail. Of course the other possibility is that the attempt to prove the goal runs forever and never returns any value. Planner also had a (not expression) construct which succeeded if expression failed, which gave rise to the “Negation as Failure” terminology in Planner.

Use of the Unique Name Assumption and Negation as Failure became more questionable when attention turned to Open Systems [Hewitt and de Jong 1983, Hewitt 1985, Hewitt and Inman 1991].

The following capabilities of Micro-Planner were omitted from Prolog:

• Pattern-directed invocation of procedural plans from assertions (i.e., forward chaining)
• Logical negation, e.g., (not (human Socrates)).

Prolog did not include negation in part because it raises implementation issues. Consider for example if negation were included in the following Prolog program:

not Q.

Q  :- P.

The above program would be unable to prove not P even though it follows by the rules of mathematical logic. This is an illustration of the fact that Prolog (like Planner) is intended to be a programming language and so does not (by itself) prove many of the logical consequences that follow from a declarative reading of its programs.

The work on Prolog was valuable in that it was much simpler than Planner. However, as the need arose for greater expressive power in the language, Prolog began to include many of the capabilities of Planner that were left out of the original version of Prolog.

• Frederic Fitch. Symbolic Logic: an Introduction Ronald Press, New York, 1952.
• John McCarthy, Paul Abrahams, Daniel Edwards, Timothy Hart, and Michael Levin. Lisp 1.5 Programmer’s Manual MIT Computation Center and Research Laboratory of Electronics. 1962.
• John Alan Robinson, A Machine-Oriented Logic Based on the Resolution Principle. CACM. 1965.
• 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.
• James Lighthill. Artificial Intelligence: A General Survey Artificial Intelligence: a paper symposium. UK Science Research Council. 1973.
• John McCarthy. Review of ‘Artificial Intelligence: A General Survey Artificial Intelligence: a paper symposium. UK Science Research Council. 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.
• L. Thorne McCarty. Reflections on TAXMAN: An Experiment on Artificial Intelligence and Legal Reasoning Harvard Law Review. Vol. 90, No. 5, March 1977
• 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.
• Bill Kornfeld and Carl Hewitt. The Scientific Community Metaphor IEEE Transactions on Systems, Man, and Cybernetics. January 1981.
• Bill Kornfeld. The Use of Parallelism to Implement a Heuristic Search IJCAI 1981.
• Bill Kornfeld. Parallelism in Problem Solving MIT EECS Doctoral Dissertation. August 1981.
• Bill Kornfeld. Combinatorially Implosive Algorithms CACM. 1982
• Carl Hewitt. The Challenge of Open Systems Byte Magazine. April 1985
• Robert Kowalski. The Limitations 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 Jeff Inman. DAI Betwixt and Between: From ‘Intelligent Agents’ to Open Systems Science IEEE Transactions on Systems, Man, and Cybernetics. Nov. /Dec. 1991.
• Carl Hewitt and Gul Agha. Guarded Horn clause languages: are they deductive and Logical? International Conference on Fifth Generation Computer Systems, Ohmsha 1988. Tokyo. Also 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.

• Prolog
• Scientific Community Metaphor

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