perm filename SHORT.PAP[L70,TES] blob sn#009949 filedate 1972-07-08 generic text, type T, neo UTF8

␈⊃ ␈⊃ ␈⊃ ␈⊃ ␈⊃ ␈⊃ ␈⊃ ␈⊃ ␈⊃ ␈⊃ ␈⊃ ␈⊃ ␈⊃ ␈⊃ ␈⊃ ␈⊃ ␈⊃ ␈⊃ ␈⊃ ␈⊃ ␈⊃ ␈⊃ THE PROGRAMMING LANGUAGE "LISP70" ␈⊃ ␈⊃ LAWRENCE G. TESLER, HORACE J. ENEA, AND DAVID C. SMITH ␈⊃ ␈⊃ STANFORD UNIVERSITY ␈⊃ ARTIFICIAL INTELLIGENCE PROJECT ␈⊃ ␈⊃ FEBRUARY, 1972 ␈⊃LISP70 July 8, 1972 ␈⊃ ␈⊃ ␈⊃ INTRODUCTION ␈⊃ ␈⊃ ␈⊃ ␈⊃ The language LISP [ref McCarthy] deals with recursive functions of symbolic ␈⊃expressions. There has recently emerged a trend towards creating "New LISPs" ␈⊃offering additional capabilities. Of primary interest are expanded control ␈⊃structures, including backtracking and multiple processing. Also of importance ␈⊃are varied methods of data access, such as associative data bases. The question ␈⊃of an appropriate successor to LISP is discussed elsewhere [ref Bobrow]. ␈⊃ ␈⊃ Some of the "New LISPs" that are currently under development are PLANNER at ␈⊃MIT [ref Hewitt], QA-4 at SRI [ref Rulifson], POP-2 at ?? [ref ??], and LISP70, ␈⊃the subject of the present paper. Having evolved separately, they differ ␈⊃somewhat in detail. However, their similarities are more striking than their ␈⊃differences. All provide convenient vehicles for theorem proving, robot ␈⊃planning, natural language processing, and other complex problem solving tasks. ␈⊃ ␈⊃ LISP70 is distinguished from the other "New LISPs" primarily by its ␈⊃extendability. The design goals of the language, in approximate order of ␈⊃importance, are: ␈⊃ ␈⊃ (1) Extendability ␈⊃ (2) Inter-machine transferability ␈⊃ (3) Facilitated debugging ␈⊃ (4) Convenient input and output ␈⊃ (5) Efficiency of operation ␈⊃ ␈⊃Each of these goals will be discussed separately. ␈⊃ ␈⊃ ␈⊃ ␈⊃ ␈⊃ ␈⊃ ␈⊃ ␈⊃ ␈⊃ ␈⊃ ␈⊃ ␈⊃ ␈⊃ ␈⊃ ␈⊃ ␈⊃ ␈⊃ ␈⊃ ␈⊃ ␈⊃ ␈⊃ 1 ␈⊃LISP70 July 8, 1972 ␈⊃ ␈⊃ ␈⊃ EXTENDABILITY ␈⊃ ␈⊃ ␈⊃ ␈⊃ Every extendable language consists of a "core" and a method of extending ␈⊃that core. The core of LISP70 is actually much larger than necessary; that is, ␈⊃most parts of the core are defined in terms of more primitive parts. Some of ␈⊃the facilities offered are: ␈⊃ ␈⊃ (1) LISP 1.5, a common standard [ref] ␈⊃ (2) MLISP, an Algol-like M-expression notation [ref Enea, ref Smith] ␈⊃ (3) Automatic Backtracking [ref Floyd] ␈⊃ (4) Pattern-Directed Computation ␈⊃ (5) Syntax-Directed Input-Output ␈⊃ (6) Extensive monitoring capabilities ␈⊃ (7) A variety of data types ␈⊃ (8) "Extendable Functions" ␈⊃ ␈⊃ ␈⊃ An Extendable Function is a function which is defined by an open-ended set ␈⊃of "rewrite rules" [ref somebody]. The "EXTEND Statement" adds new rules to an ␈⊃Extendable Function. The LISP70 compilers are defined primarily in terms of ␈⊃Extendable Functions. Thus, anyone can extend them by use of appropriate EXTEND ␈⊃Statements. The scope of an extension can be a whole program or any part of a ␈⊃program. ␈⊃ ␈⊃ ␈⊃ ␈⊃ ␈⊃ ␈⊃ ␈⊃ ␈⊃ ␈⊃ ␈⊃ ␈⊃ ␈⊃ ␈⊃ ␈⊃ ␈⊃ ␈⊃ ␈⊃ ␈⊃ ␈⊃ ␈⊃ ␈⊃ ␈⊃ ␈⊃ ␈⊃ ␈⊃ 2 ␈⊃LISP70 July 8, 1972 ␈⊃ ␈⊃ ␈⊃ EXTENDING MLISP ␈⊃ ␈⊃ ␈⊃ ␈⊃ MLISP is defined entirely by Extendable Functions such as "EXPRESSION", ␈⊃which translates an M-expression to an S-expression. For example, the ␈⊃conditional expression of MLISP is defined in terms of the conditional ␈⊃expression of LISP by the following rewrite rule in EXPRESSION: ␈⊃ ␈⊃ ⊂IF <expression>:e1 THEN <expression>:e2 ELSE <expression>:e3⊃ ␈⊃ →→ (COND (:e1 :e2) (T :e3)) ␈⊃ ␈⊃Every rewrite rule has a left side and a right side separated by right-pointing ␈⊃arrows. A rewrite rule can translate any input that matches its left side to an ␈⊃output constructed by its right side. Strictly local variables (preceded by the ␈⊃character ":") serve to carry information from the left side to the right side. ␈⊃ ␈⊃ The above rule for translating conditionals is read from left to right as ␈⊃follows: ␈⊃ ␈⊃ An input stream ("⊂...⊃") which begins with the symbol ␈⊃ `IF', followed by an <expression> (whose translation is ␈⊃ bound to e1), followed by `THEN', followed by another ␈⊃ <expression> (whose translation is bound to e2), followed by ␈⊃ `ELSE', followed by another <expression> (whose translation ␈⊃ is bound to e3), can definitely ("→→") be rewritten as a ␈⊃ list of the following three elements: first, the symbol ␈⊃ `COND'; second, a list containing the binding of e1 and the ␈⊃ binding of e2; finally, a list containing `T' and the ␈⊃ binding of e3. ␈⊃ ␈⊃ ␈⊃ Each of the three occurrences of <expression> within this definition calls ␈⊃EXPRESSION recursively to translate portions of the conditional. Should any of ␈⊃these calls fail, the entire rewrite rule fails and a different rule of ␈⊃EXPRESSION is tried. Thus, more than one rule of the syntax may begin with the ␈⊃symbol `IF'. In fact, it is possible to define arbitrarily context-sensitive ␈⊃grammars with LISP70 rewrite rules, but this subject will not be explored here. ␈⊃ ␈⊃ As an illustration of the operation of the above rewrite rule, the ␈⊃processing of the following input stream will be traced: ␈⊃ ␈⊃ if a=b then 7 else cons(7,a) ␈⊃ ␈⊃After `IF' is matched, `a=b' is translated by a recursive call on EXPRESSION to ␈⊃`(EQUAL A B)', which is bound to e1. The other local variables are bound in a ␈⊃similar manner, yielding: ␈⊃ ␈⊃ ␈⊃ 3 ␈⊃LISP70 EXTENDING MLISP ␈⊃ ␈⊃ ␈⊃ ␈⊃ e1 = (EQUAL A B) ␈⊃ e2 = 7 ␈⊃ e3 = (CONS 7 A) ␈⊃ ␈⊃These bindings are substituted into the right hand side, outputting the ␈⊃translation: ␈⊃ ␈⊃ (COND ((EQUAL A B) 7) (T (CONS 7 A)) ) ␈⊃ ␈⊃ ␈⊃ Example: ␈⊃ ␈⊃ extendable function simplify = ␈⊃ (PLUS 0 ::X) →→ (PLUS ::X)*, ␈⊃ (PLUS :A ::B) →→ (PLUS :A (PLUS ::B)*@@CDR), ␈⊃ (PLUS) →→ 0 ; ␈⊃ ␈⊃ ␈⊃ Some notation must be explained: ␈⊃ ␈⊃ :X Matches any one item and binds it to X. ␈⊃ :X On right side: the binding of X. ␈⊃ ::X Matches zero or more items, forms them into ␈⊃ a list, binds that list to X. ␈⊃ ::X On right side: the elements of X, i.e., the list ␈⊃ X with its outer parentheses stripped. ␈⊃ @F Postfix Function Call: Call function F with the ␈⊃ preceding value as its argument, e.g., ␈⊃ ((A) B C)@CAR yields (A). ␈⊃ @@F Call F and strip the result, e.g., ␈⊃ ((A) B C)@@CAR yields A. ␈⊃ * Call the current function recursively, i.e., ␈⊃ same as @SIMPLIFY. ␈⊃ ** In this case, same as @@SIMPLIFY. ␈⊃ (...) Match or construct a list. ␈⊃ ⊂...⊃ Match or construct a stream. ␈⊃ `...' Same as ⊂...⊃, but no special characters are ␈⊃ recognized except <>*@: ␈⊃ ␈⊃ ␈⊃ Let us trace the call (SIMPLIFY (QUOTE (PLUS HAT 0 J K))). ␈⊃ ␈⊃ ␈⊃ ␈⊃ ␈⊃ ␈⊃ ␈⊃ ␈⊃ 4 ␈⊃LISP70 EXTENDING MLISP ␈⊃ ␈⊃ ␈⊃ ␈⊃ Argument Rule Applied Result ␈⊃ -------- ---- ------- ------ ␈⊃ ␈⊃ (PLUS HAT 0 J K)) 2 (PLUS HAT (PLUS 0 J K)*@@CDR) ␈⊃ (PLUS 0 J K) 1 (PLUS J K)* ␈⊃ (PLUS J K) 2 (PLUS J (PLUS K)*@@CDR) ␈⊃ (PLUS K) 2 (PLUS K (PLUS)*@@CDR) ␈⊃ (PLUS) 3 (PLUS) ␈⊃ ␈⊃ Expression After * After CDR After STRIP ␈⊃ ---------- ------- --------- ----------- ␈⊃ ␈⊃ (PLUS)*@@CDR (PLUS)@@CDR ()@STRIP ⊂ ⊃ ␈⊃ (PLUS K)*@@CDR (PLUS K)@@CDR (K)@@STRIP K ␈⊃ (PLUS 0 J K)*@@CDR (PLUS J K)@@CDR (J K)@STRIP J K ␈⊃ ␈⊃When several rules occur in an extendable function, they are ordered Most ␈⊃Specific First. If the left side of the first rule matches the input, then the ␈⊃value of the function is computed by the right side of that rule. Otherwise, ␈⊃subsequent rules are tried in the same way. If no rule matches, a failure ␈⊃occurs, causing backtracking. ␈⊃ ␈⊃ Proper ordering of rules is important both for speed and correctness. In ␈⊃the compiler, the Most Specific First heuristic is trivial to implement. For ␈⊃example, if the left sides of two rules are identical up to a point at which one ␈⊃has a literal symbol and the other has a local variable binding, then the former ␈⊃rule is ordered before the latter. This is because the literal symbol can only ␈⊃match one possible input entity while the local variable binding can match ␈⊃anything. ␈⊃ ␈⊃ ␈⊃ ␈⊃ ␈⊃ ␈⊃ ␈⊃ ␈⊃ ␈⊃ ␈⊃ ␈⊃ ␈⊃ ␈⊃ ␈⊃ ␈⊃ ␈⊃ ␈⊃ ␈⊃ ␈⊃ ␈⊃ 5 ␈⊃