perm filename ACMPAP.L70[L70,TES] blob sn#009944 filedate 1972-06-27 generic text, type T, neo UTF8

00100 .PAGE FRAME 54 HIGH 80 WIDE 00200 .COUNT PAGE FROM 0 00300 .PORTION TITLEPAGE 00400 .BEGIN 00500 .CENTER 00600 .SKIP TO LINE 20 00700 THE PROGRAMMING LANGUAGE "LISP70" 00800 00900 LAWRENCE G. TESLER, HORACE J. ENEA, AND DAVID C. SMITH 01000 01100 STANFORD UNIVERSITY 01200 ARTIFICIAL INTELLIGENCE PROJECT 01300 01400 FEBRUARY, 1972 01500 .END 01600 .PORTION REPORT 01700 .INDENT 5,0 01800 .MACRO BC ⊂ BEGIN GROUP CENTER SKIP 1 ; ⊃ 01900 .MACRO ec ⊂ SKIP 1 ; END CONTINUE ⊃ 02000 .MACRO e ⊂ SKIP 1 ; END ⊃ 02100 .TURN ON "↓_[]#α∂" 02200 .MACRO s(N) ⊂ SNAME←DATE ; NEXT PAGE ONCE CENTER ; "N" ; 02300 . SKIP 2 ; SNAME ← "N" ⊃ ; 02400 .EVERY HEADING(LISP70,,{SNAME}) 02500 .EVERY FOOTING(,{PAGE},) 00100 .S INTRODUCTION 00200 The language LISP [ref McCarthy] deals with recursive functions of symbolic 00300 expressions. There has recently emerged a trend towards creating 00400 "New LISPs" offering additional capabilities. Of primary interest are 00500 expanded control structures, including backtracking and multiple 00600 processing. Also of importance are varied methods of data access, 00700 such as associative data bases. The question of an appropriate successor 00800 to LISP is discussed elsewhere [ref Bobrow]. 00900 01000 Some of the "New LISPs" that are currently under development are PLANNER 01100 at MIT [ref Hewitt], QA-4 at SRI [ref Rulifson], POP-2 at ?? [ref ??], 01200 and LISP70, the subject of the present paper. Having 01300 evolved separately, they differ somewhat in detail. However, their 01400 similarities are more striking than their differences. All provide 01500 convenient vehicles for theorem proving, robot planning, natural 01600 language processing, and other complex problem solving tasks. 01700 01800 LISP70 is distinguished from the other "New LISPs" primarily by its 01900 extendability. The design goals of the language, in approximate order 02000 of importance, are: 02100 .bc 02200 (1) Extendability # 02300 (2) Inter-machine transferability 02400 (3) Facilitated debugging # 02500 (4) Convenient input and output # 02600 (5) Efficiency of operation # 02700 .ec 02800 Each of these goals will be discussed separately. 00100 .S EXTENDABILITY 00200 Every extendable language consists of a "core" and a method of extending 00300 that core. The core of LISP70 is actually much larger than necessary; 00400 that is, most parts of the core are defined in terms of more primitive 00500 parts. Some of the facilities offered are: 00600 .bc 00700 (1) LISP 1.5, a common standard [ref] # 00800 (2) MLISP, an Algol-like M-expression notation [ref Enea, ref Smith] # 00900 (3) Automatic Backtracking [ref Floyd] # 01000 (4) Pattern-Directed Computation # 01100 (5) Syntax-Directed Input-Output # 01200 (6) Extensive monitoring capabilities # 01300 (7) A variety of data types # 01400 (8) "Extendable Functions" # 01500 .e 01600 An Extendable Function is a function which is defined by an open-ended 01700 set of "rewrite rules" [ref somebody]. 01800 The "EXTEND Statement" adds new rules to an Extendable Function. 01900 The LISP70 compilers are defined primarily in terms of Extendable Functions. 02000 Thus, anyone can extend them by use of appropriate EXTEND Statements. The 02100 scope of an extension can be a whole program or any part of a program. 00100 .S EXTENDING MLISP 00200 MLISP is defined entirely by Extendable Functions such as "EXPRESSION", 00300 which translates an M-expression to an S-expression. For example, the 00400 conditional expression of MLISP is defined in terms of the conditional 00500 expression of LISP by the following rewrite rule in EXPRESSION: 00600 .bc 00700 ⊂IF <expression>:e1 THEN <expression>:e2 ELSE <expression>:e3⊃ # 00800 →→ (COND (:e1 :e2) (T :e3)) # 00900 .ec 01000 Every rewrite rule has a left side and a right side separated by right-pointing 01100 arrows. A rewrite rule can translate any input that matches its left 01200 side to an output constructed by its right side. Strictly local variables 01300 (preceded by the character ":") serve to carry information from the left 01400 side to the right side. 01500 01600 The above rule for translating conditionals is read from left to right 01700 as follows: 01800 .begin narrow 10,10 01900 An input stream ("⊂...⊃") which begins with the symbol `IF', followed 02000 by an <expression> (whose translation is bound to e1), followed by 02100 `THEN', followed by another <expression> (whose translation is 02200 bound to e2), followed by `ELSE', followed by another <expression> 02300 (whose translation is bound to e3), can definitely ("→→") be rewritten 02400 as a list of the following three elements: first, the symbol `COND'; 02500 second, a list containing the binding of e1 and the binding of e2; 02600 finally, a list containing `T' and the binding of e3. 02700 .end skip 02800 Each of the three occurrences of <expression> within this definition calls 02900 EXPRESSION recursively to translate portions of the conditional. Should 03000 any of these calls fail, the entire rewrite rule fails and a different 03100 rule of EXPRESSION is tried. Thus, more than one rule of the syntax may 03200 begin with the symbol `IF'. In fact, it is possible to define arbitrarily 03300 context-sensitive grammars with LISP70 rewrite rules, but this subject will 03400 not be explored here. 03500 03600 As an illustration of the operation of the above rewrite rule, the 03700 processing of the following input stream will be traced: 03800 .bc 03900 if a=b then 7 else cons(7,a) 04000 .ec 04100 After `IF' is matched, `a=b' is translated by a recursive call on EXPRESSION to 04200 `(EQUAL A B)', which is bound to e1. The other local variables are bound 04300 in a similar manner, yielding: 04400 .bc 04500 e1 = (EQUAL A B)# 04600 e2 = 7 # 04700 e3 = (CONS 7 A) # 04800 .ec 04900 These bindings are substituted into the right hand side, outputting the 05000 translation: 05100 .bc 05200 (COND ((EQUAL A B) 7) (T (CONS 7 A)) ) 05300 .e 05400 Example: 05500 .bc 05600 extendable function simplify = # 05700 (PLUS 0 ::X) →→ (PLUS ::X)*, # 05800 (PLUS :A ::B) →→ (PLUS :A (PLUS ::B)*@@CDR), # 05900 (PLUS) →→ 0 ; # 06000 .e 06100 Some notation must be explained: 06200 .bc 06300 :X Matches any one item and binds it to X. # 06400 :X On right side: the binding of X. # 06500 ::X Matches zero or more items, forms them into # 06600 a list, binds that list to X. # 06700 ::X On right side: the elements of X, i.e., the list# 06800 X with its outer parentheses stripped. # 06900 @F Postfix Function Call: Call function F with the# 07000 preceding value as its argument, e.g., # 07100 ((A) B C)@CAR yields (A). # 07200 @@F Call F and strip the result, e.g., # 07300 ((A) B C)@@CAR yields A. # 07400 * Call the current function recursively, i.e., # 07500 same as @SIMPLIFY. # 07600 ** In this case, same as @@SIMPLIFY. # 07700 (...) Match or construct a list. # 07800 ⊂...⊃ Match or construct a stream. # 07900 `...' Same as ⊂...⊃, but no special characters are # 08000 recognized except <>*@: # 08100 .e 08200 Let us trace the call (SIMPLIFY (QUOTE (PLUS HAT 0 J K))). 08300 .bc 08400 Argument Rule Applied Result 08500 -------- ---- ------- ------ 08600 08700 (PLUS HAT 0 J K)) 2 (PLUS HAT (PLUS 0 J K)*@@CDR) # 08800 (PLUS 0 J K) 1 (PLUS J K)* # 08900 (PLUS J K) 2 (PLUS J (PLUS K)*@@CDR) # 09000 (PLUS K) 2 (PLUS K (PLUS)*@@CDR) # 09100 (PLUS) 3 (PLUS) # 09200 09300 Expression After * After CDR After STRIP 09400 ---------- ------- --------- ----------- 09500 09600 (PLUS)*@@CDR (PLUS)@@CDR ()@STRIP ⊂ ⊃ # 09700 (PLUS K)*@@CDR (PLUS K)@@CDR (K)@@STRIP K # 09800 (PLUS 0 J K)*@@CDR (PLUS J K)@@CDR (J K)@STRIP J K # 09900 .ec 10000 When several rules occur in an extendable function, they are ordered Most 10100 Specific First. If the left side of the first rule matches the input, 10200 then the value of the function is computed by the right side of that rule. 10300 Otherwise, subsequent rules are tried in the same way. If no rule matches, 10400 a failure occurs, causing backtracking. 10500 10600 Proper ordering of rules is important both for speed and correctness. 10700 In the compiler, the Most Specific First heuristic is trivial to 10800 implement. For example, if the left sides of two rules are identical 10900 up to a point at which one has a literal symbol and the other has a 11000 local variable binding, then the former rule is ordered before the 11100 latter. This is because the literal symbol can only match one possible 11200 input entity while the local variable binding can match anything.