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.
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.
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".
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.
03600 Before any discussion of rewrite tables can be understood in depth,
03700 a familiarity with LISP70's backtracking feature is necessary.
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.
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:
05700 if x>10 then y ← y + 1 ;
05900 if later x > 10 then y ← y + 1 ;
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.
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).
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
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.
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.
13000 Let us return to rewrite rules.
13200 Syntax Productions (BNF-like)
13300 <term> = <term> * <factor>
13400 = <factor>
13600 Labelling constituents
13800 <term> = <term>:a * <factor>:b
13900 = <factor>:a
14300 <term> = <term>:a * <term>:b →→ (TIMES :a :b)
14400 = <factor>:a →→ :a
14600 <term> as a function
14800 Extending a function
15000 <term> ALSO = <term>:a / <term>:b →→ (QUOTIENT :a :b)
15200 Ordering, factoring, backtracking
15500 (CAR :X) :X (CONS :X :Y) superfluous MOVE-PUSH
15900 arg or .P ---> [...→→...] ---> value or .P
16100 to lists; to files; to processes
16500 Multi-alists & PCs, shared OBLIST
16600 show RANDGEN, PROVIDE
16700 show COROUTINE CALL
16800 show PROCURE
17000 Coroutine backtracking
17200 Show optimizer, macro expander