perm filename LECTUR.PUB[L70,TES] blob sn#009932 filedate 1972-05-17 generic text, type T, neo UTF8

00100 LISP70 is an extendable language based on LISP. Two standard 00200 languages are provided in the system -- MLISP (which is Algol-like) 00300 and LISP. The translator from MLISP to LISP is table-driven. By 00400 extending or replacing the tables, a programmer may define his own syntax. 00500 Furthermore, the compiler from 00600 LISP to an "ideal machine" language is table-driven. By extending these 00700 tables, the semantics of the language can be augmented. 00800 00900 MLISP, LISP, and the ideal machine language are all 01000 machine-independent. The translator from ideal machine language to a 01100 particular machine's assembly language (LAP) is table-driven. 01200 This has two advantages. The compiler can be made to generate code 01300 for different machines merely by replacing these short tables. Also, 01400 the ideal machine can be extended by adding new rules, thus 01500 augmenting the intrinsic capability of the language. For example, 01600 new control structures can be defined by new ideal machine 01700 primitives, showing their translation from LISP and to an actual 01800 machine language. 01900 02000 The tables that drive the various translators that comprise LISP70 are 02100 all of the same form: rewrite tables. A rewrite table is a LISP function 02200 that is defined by a set of rewrite rules. Each rewrite rule is a 02300 pattern-matcher, showing what form of input it will match and what 02400 form of output it will produce should it match an input. New rewrite rules 02500 can be added to a rewrite table at any time, thus extending its domain. 02600 For this reason, a function that is defined as a rewrite table is called an 02700 "extendable function". 02800 02900 Extendable functions are used throughout the LISP70 compiler, and may 03000 also be defined in user programs. For example, in a theorem prover, 03100 a system of inference rules may be defined as a rewrite table, to which 03200 new inference rules may be added at any time. It is also possible to 03300 remove rewrite rules from a table and to define an ssociative data base of 03400 assertions as a rewrite tablle. 03500 03600 Before any discussion of rewrite tables can be understood in depth, 03700 a familiarity with LISP70's backtracking feature is necessary. 03800 03900 The state of a LISP process is completely defined at any moment by 04000 the ALIST, the OBLIST (including the properties of the atoms on it), 04100 the PC (Program Counter or Point of Control) and input-output pointers. 04200 It is not hard to make a LISP system write out the entire state of 04300 a running process by printing the values of these items. One can also 04400 conceive of stacking the state of a LISP process on a "State Stack" and 04500 after running awhile, restoring one of the former states that has been 04600 saved on the State Stack. Proceeding from the restored PC would then 04700 cause an exact repetition of the previous action of the process. This 04800 state-saving feature is useful for debugging and is provided in LISP70. 04900 05000 State-saving is useful not only in debugging but also in problem-solving. 05100 In particular, it is useful in the implementation of "non-deterministic" 05200 algorithms. A non-deterministic algorithm performs actions whose results 05300 are not determined solely by past events but partially by future events. 05400 Compare the Algol statement below with the accompanying statement that 05500 might appear in a mythical non-deterministic language: 05600 05700 if x>10 then y ← y + 1 ; 05800 05900 if later x > 10 then y ← y + 1 ; 06000 06100 In the first case, the decision whether to step y is determined completely 06200 by past events, for the decision is based on the current value of x. 06300 In the second case, the decision whether to step y is not determined 06400 completely by past events, for the decision is based on a future value 06500 of x. One way to execute this statement would be to create two identical 06600 processes, in one assume that x will be greater than 10 and in the other 06700 that it will not. When x finally recieves a value, the process operating 06800 under the incorrect assumption can be eliminated. Another way to 06900 execute the statement would be to save the state on a state stack and assume 07000 that x will be 10 or smaller. When x finally receives a value, if the 07100 assumption was correct, the stacked state can be discarded. If the 07200 assumption turns out to be incorrect, the current state can be discarded, 07300 the stacked state restored, and the computation reiterated based on the 07400 corrected assumption. 07500 Other implementations are possible in special cases, but these two are 07600 both generally applicable and conceptually simple. 07700 07800 Floyd first used the term "non-deterministic algorithms", and also 07900 suggested three primitive operations that are sufficient to define 08000 them. The operations are called "choice", "success", and "failure". 08100 In LISP70, these are all the names of functions. "Choice" is a 08200 function of one integer argument and returns one integer value. 08300 For example, the call "I ← CHOICE(3)" sets I to 1, 2, or 3. 08400 Conceptually, it creates three processes that are identical except 08500 for the value of I. Should the function FAILURE() be called within 08600 any of these processes, that process is eliminated. Should the 08700 function SUCCESS() be called within any of these processes, that 08800 process is terminated successfully (at that time, all other 08900 unfinished processes may be eliminated if desired). 09000 09100 It is possible for a process spawned by a CHOICE to call CHOICE and 09200 thus be replaced by several descendant processes. Eventually, a 09300 large number of processes may be created, creating excessive space 09400 demands in a conventional computer. Thus, the state-saving method 09500 of implementing non-determinism must be employed to prevent such 09600 occurrences. Using this method, a call on CHOICE stacks the state 09700 and returns only the value 1. Should FAILURE() subsequently be called, 09800 the current state is discarded and replaced by the top state on the 09900 stack, only this time CHOICE returns the value 2. Should failures 10000 exhaust all N values of CHOICE(N), then the top state on the stack is 10100 discarded and the CHOICE waiting in the next stacked state is dealt 10200 with. 10300 10400 Even the state-saving method can demand excessive storage if the entire 10500 ALIST and OBLIST are stacked at every call on CHOICE. Instead, a real 10600 implementation only stacks the difference DELTA-S between successive 10700 states. Thus, if the current state is S4 and stacked states are S3, S2, and 10800 S1, then all that needs to really be stacked are S4-S3, S3-S2, and S2-S1. 10900 FAILURE() merely changes the current state S4 according to the state difference 11000 S4-S3 in order to restore the state S3. To maintain a correct record of 11100 state differences takes a little bit of bookkeeping every time the state 11200 is changed. Frequently changed components of the state can be saved 11300 at every CHOICE to avoid the bookkeeping at every change. 11400 11500 Some so-called "backtracking" systems avoid this complexity by 11600 neglecting to save the entire state. For example, the OBLIST (including 11700 atom properties and arrays) may not be restored upon failure. Sometimes 11800 even ALIST variable settings are not restored, although all known 11900 implementations do restore the ALIST to its former size and ordering. 12000 Input-output pointers are restored by hardly any implementations. 12100 To make up for these shortcomings, such systems usually provide for 12200 explicit saving of programmer-specified state components such as 12300 variable settings. This forces the user to analyze the interactions 12400 of his data carefully to determine which components really must be 12500 restored. The approach in LISP70 is to automatically save everything, 12600 except for components explicitly exempted by the programmer. This 12700 assures the programmer that the state that each choice works on will 12800 be identical unless he has explicitly demanded otherwise. 12900 13000 Let us return to rewrite rules. 13100 13200 Syntax Productions (BNF-like) 13300 <term> = <term> * <factor> 13400 = <factor> 13500 13600 Labelling constituents 13700 13800 <term> = <term>:a * <factor>:b 13900 = <factor>:a 14000 14100 Semantics 14200 14300 <term> = <term>:a * <term>:b →→ (TIMES :a :b) 14400 = <factor>:a →→ :a 14500 14600 <term> as a function 14700 14800 Extending a function 14900 15000 <term> ALSO = <term>:a / <term>:b →→ (QUOTIENT :a :b) 15100 15200 Ordering, factoring, backtracking 15300 15400 LISP→→ML 15500 (CAR :X) :X (CONS :X :Y) superfluous MOVE-PUSH 15600 PEEPHOLE 15700 15800 POINTERS 15900 arg or .P ---> [...→→...] ---> value or .P 16000 16100 to lists; to files; to processes 16200 16300 COROUTINES 16400 16500 Multi-alists & PCs, shared OBLIST 16600 show RANDGEN, PROVIDE 16700 show COROUTINE CALL 16800 show PROCURE 16900 17000 Coroutine backtracking 17100 17200 Show optimizer, macro expander