| Planner Programming Language |
Article Index for Planner |
Website Links For Planner |
Information AboutPlanner Programming Language |
| CATEGORIES ABOUT PLANNER PROGRAMMING LANGUAGE | |
| history of artificial intelligence | |
| domain-specific programming languages | |
| logic programming languages | |
| robotics | |
| theorem prover languages | |
| SHOPPER'S DELIGHT | |
|
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. EARLY HISTORY OF PLANNER According to Hewitt {Link without Title} , 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 and was used in Winograd's natural-language understanding program SHRDLU , Eugene Charniak's story understanding work, 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. CONTROL STRUCTURE CONTROVERSY As related in Hewitt {Link without Title} , 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! People were dumbfounded. In this and several other ways, backtracking proved unwieldy helping to fuel the great control structure debate. Hewitt investigated some alternatives in his thesis. Control structure characterizations Using program schemas, Hewitt in collaboration with Mike Paterson proved that Recursion is more powerful than Iteration and Parallelism more powerful than sequential recursion. (He also conjectured that Coroutine s are more powerful than recursion but couldn't convincingly prove it until recently using a more powerful formalism.) Hairy control structure According to Hewitt {Link without Title} , 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. Control structures are patterns of passing messages 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. LIMITATION OF MATHEMATICAL LOGIC This developed into a controversy about the possibility of using Mathematical Logic as a programming language. See Indeterminacy In Computation . The upshot is that the procedural approach has a different mathematical semantics (see Denotational Semantics ) from the semantics of mathematical logic. REFERENCES
EXTERNAL LINKS |