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