00100			LISP70 BACKTRACKING IN BRIEF
00200	
00300	
00400	THE ALIST
00500	--- -----
00600	
00700	The control structure of LISP is most easily represented by a levelled
00800	ALIST.   Here is such an ALIST with three levels:
00900	
01000		( X:4,Y:3,PC:105 ) ( X:7,PC:350 ) ( Z:9,Y:18,PC:10 )
01100	
01200	Each level represents a function invocation.  It contains the
01300	bindings of variables bound by that function and the address
01400	(PC) of the next instruction to be executed in that invocation.
01500	
01600	The current function invocation is represented by the leftmost level.
01700	The PC of that level is the current program counter, i.e., the
01800	address of the next instruction to be executed by the program.
01900	The current binding of any variable X is found by searching the ALIST
02000	from the left for the first occurrence of a pair X:v .
02100	
02200	To return from a function, its value is placed in the global variable
02300	RESULT (not shown) and the leftmost level of the ALIST is deleted.
02400	Doing this to the ALIST shown above yields:
02500	
02600		( X:7,PC:350 ) ( Z:9,Y:18,PC:10 )
02700	
02800	The program continues from the new leftmost PC.  Thus, this is the
02900	return address of the function.
03000	
03100	To call a function, a parameter binding list is formed as follows.
03200	It has each formal parameter of the called function bound to the
03300	actual parameter supplied by the calling function.  It also
03400	has PC bound to the initial address of the called function.
03500	From the above ALIST, suppose that the call λx,y[<code>][2,3]
03600	is made.  The parameter binding list formed is:
03700	
03800		( X:2,Y:3,PC:<code> )
03900	
04000	This list becomes the new leftmost level of the ALIST.  For the
04100	above call, suppose that PC has advanced to 370 in the calling function,
04200	and that the called function begins at 525.  Then this would yield:
04300	
04400		( X:2,Y:3,PC:525 ) ( X:7,PC:370) ( Z:9,Y:18,PC:10 )
04500	
04600	For consistency, we will consider that global variables and the
04700	property lists of atoms are also kept in the ALIST, but in a 
04800	level to the right of all the function invocation levels.
     

00100	SETQ AND PROG
00200	---- --- ----
00300	
00400	SETQ[X,9] changes the value bound to the leftmost X in the ALIST to 9.
00500	If no such X occurs, the global X (not shown) is changed.
00600	
00700		( X:9,Y:3,PC:530 ) ( X:7,PC:370) ( Z:9,Y:18,PC:10 )
00800	
00900	PROG[[a,b] ...] adds the bindings A:NIL and B:NIL to the front of
01000	the leftmost level of the ALIST, but does not add a new level:
01100	
01200		( A:NIL,B:NIL,X:2,Y:3,PC:535 ) ( X:7,PC:370) ( Z:9,Y:18,PC:10 )
01300	
01400	At the end of the PROG, those bindings are removed.
01500	
01600	BACKTRACKING
01700	------------
01800	
01900	There are many backtracking paradigms, but they all
02000	revolve around the same theme.  Certain points in the computation are
02100	designated "failure points" or "choice points" or "decision
02200	points".  Upon "failure", the computation backs up to the last such point.
02300	This requires the capability of restoring a prior state of the computation.
02400	
02500	One way to implement backtracking in LISP is to use a second
02600	association list called the CLIST ("context list") to save a record of
02700	the ALISTS that existed at each decision point.  An over-simplified
02800	CLIST might look like this:
02900	
03000		( ALIST#:((Y:3,PC:60)) )  ( ALIST#:((X:4,PC:510)(Y:3,PC:45)) )
03100	
03200	The current ALIST is inside the leftmost level of CLIST.  To find the
03300	current value of a variable, only the current ALIST is searched,
03400	because the other ALISTs represent earlier states of the computation.
03500	
03600	Inside CLIST, a "#" is written after ALIST to emphasize that it is not
03700	the usual kind of LISP variable.  Variables within the ALIST will
03800	be called "block variables" and variables within the CLIST will be
03900	called "contextual variables".  The name of each contextual variable
04000	will end with one "#".
04100	
04200	Failure deletes the
04300	leftmost level or "context" of the CLIST.  This returns to the
04400	previous context.  To enter a context, a new level is added to the CLIST,
04500	containing a copy of the current ALIST.
04600	
04700	Thus, failure out of a context is analogous to return from a
04800	function, and entering a context is analogous to calling a function.
     

00100	CHOICE FUNCTIONS
00200	------ ---------
00300	
00400	The trouble with the formulation so far is that failure restores the
00500	exact ALIST that led to failure, and thus the program will repeat its
00600	previous actions and fail again.  To remedy this, it is necessary that
00700	some part of the state change from one restoration of the state to the
00800	next.  One way to accomplish this is by the use of contextual variables.
00900	
01000	After a context is created, contextual variables can be bound in it
01100	just as PROG variables can be bound in a function.  A BIND statement
01200	is used in LISP70.  Thus:
01300	
01400		BIND N# TO 10, I# TO 0 ;
01500	
01600	changes the above CLIST to:
01700	
01800		( N#:10,I#:0,ALIST#:(...) ) ( ALIST#:(...) )
01900	
02000	A new context can then be created by CREATE CONTEXT:
02100	
02200		( ALIST#:(...) ) ( N#:10,I#:0,ALIST#:(...) ) ( ALIST#:(...) )
02300	
02400	Initially, the current and second ALIST are identical, except that the
02500	PC of the second ALIST is still pointing at the CREATE CONTEXT
02600	instruction while the PC of the current ALIST has passed it.
02700	Computations in the new context will not affect the ALIST of the old context.
02800	However, assignments to N# and I# will change the state saved in the
02900	old context.  Subsequent failure will restore that context and cause
03000	CREATE CONTEXT to be repeated, but the program may not loop
03100	because this time N# and/or I# may have different values than last time.
     

00100	As an example, Floyd's function CHOICE(N) will be defined.
00200	
00300	Statement			Resulting CLIST for CHOICE(10)
00400	---------			--------- ----- --- ----------
00500	
00600	function choice(n) =		( ALIST#:(...) ) (...)
00700	    begin
00800	    bind n# to n, i# to 0 ;	( N#:10,I#:0,ALIST#:(...) ) (...)
00900	    create context ;		( ALIST:(...) ) ( N#:10,I#:0,ALIST#:(...) ) (...)
01000	    i# ← i# + 1 ;		( ALIST:(...) ) ( N#:10,I#:1,ALIST#:(...) ) (...)
01100	    if i# > n# then
01200	    	fail twice		(...)  Note: Backtracks to an earlier CHOICE.
01300	    	else return i#	;	( ALIST:(...) ) ( N#:10,I#:1,ALIST#:(...) ) (...)
01400	    end
01500	
01600	If CHOICE returns, then the calling
01700	function proceeds in the new context with RESULT = I# = 1.
01800	Subsequent failure erases the leftmost context, restores the previous
01900	ALIST to current status, and resumes execution at the CREATE CONTEXT
02000	instruction inside CHOICE.  This steps I# to 2 and returns 2 as the
02100	result of CHOICE.
02200	
02300	When I# reaches N+1, CHOICE should fail.  To accomplish this requires
02400	FAIL TWICE, which first erases the context created inside CHOICE
02500	and then erases the context that existed when CHOICE was called.
     

00100	IMPLEMENTATION
00200	--------------
00300	
00400	A backtracking LISP interpreter could be developed literally following
00500	the formulation presented above, and would suffice for
00600	the programming of simple backtracking problems.  However, backtracking
00700	is most helpful in very complex and thus very large recursive
00800	programs with large data bases.  In such programs, copying the entire
00900	ALIST at every decision point -- including all function levels, global variables, and
01000	property lists of atoms -- can become prohibitively expensive.
01100	
01200	Fortunately it is not necessary to do this.  In a large program,
01300	only a fraction of the entire ALIST changes from context to context, and
01400	to be able to restore the state, only changed parts need be saved.
01500	
01600	One common technique uses a "history list" or stack.  Every time a change is
01700	made to the ALIST, an instruction for changing it back is pushed on the
01800	top of the history list.  To fail, the history list is executed in reverse
01900	until the last decision point is reached.  The essence of this technique
02000	was described by Floyd in [ref].  It has been used in numerous systems.
02100	
02200	The history list technique does not require CREATE CONTEXT to do
02300	anything but push the PC and a decision point signal onto the history
02400	list to catch failure.  This is an attractive advantage.  However, the
02500	technique has two flaws.
02600	
02700	One flaw is that if the same variable is changed many times in a loop
02800	within a single context, every change is recorded.  None but the first
02900	change really needs to be recorded to provide for backup to the last
03000	decision point.  The superfluous recording consumes both time and stack
03100	space.
03200	
03300	This flaw can be remedied by recording with each binding in the
03400	ALIST the unique number or "tag" of the context in which it was last
03500	changed.  Each time it is changed, a check is made to see if it has
03600	already been saved in the current context.  If so, it is not saved
03700	again, and the total cost of checking can amount to a single compare
03800	instruction.  If not, the change is recorded on the history list and
03900	the tag recorded with the binding is updated.
04000	
04100	The remedy of the first flaw is the cause of the second flaw.
04200	Every bound variable (parametric, local, or global) and every atom
04300	property must contain an extra field to store the context tag.
04400	Unless this facility is built into the hardware or microprogrammed,
04500	the cost in both space and setup time is significant.  However,
04600	the bulk of the cost involves the maintenance of high activity variables
04700	such as formal parameters and local variables.  Low activity variables
04800	such as global variables and atom properties can demand extra maintenance
04900	without degrading overall performance significantly.
     

00100	Another technique is "incremental ALIST copying".  When a context is
00200	created, instead of copying the entire ALIST, only a few (one or more)
00300	of the leftmost levels are copied, plus a link to the uncopied levels.
00400	If a failure occurs before all the copied function levels return,
00500	then it never becomes necessary to save the additional levels, and
00600	economy has indeed been achieved.  However, if they all return and the
00700	link is reached, then a few more levels must be copied before proceeding.
00800	
00900	This scheme has two flaws.  If an assignment is made to a free
01000	variable stored deep in the ALIST in the part that was not copied, then
01100	this condition must be detected and extra levels must be copied.
01200	Furthermore, assignments to global variables and atom property lists
01300	are not covered by the technique at all.
01400	
01500	The other flaw is that the ALIST copying can become a significant cost if
01600	it occurs frequently as compared with the frequency of changes to
01700	variables stored on the ALIST.
01800	
01900	All the flaws of both techniques are largely remedied by use of a mixed
02000	strategy developed by Enea and Smith for MLISP-2.  Variables that can
02100	be accessed free ("special" variables in LISP 1.6 and MLISP2; "public"
02200	variables in LISP70) are not stored on the ALIST but elsewhere.  Global
02300	variables and atom properties are not stored on the ALIST either.  The
02400	history list technique is then used to record changes to these
02500	variables.  This leaves on the ALIST only variables that can not be
02600	accessed free by functions ("private" variables in LISP70).  These in
02700	fact tend to be the variables that change with high frequency.  Thus,
02800	the incremental ALIST copying technique works well for them.