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	BACKTRACK PROGRAMMING SYSTEMS
00800	
00900	LAWRENCE G. TESLER, HORACE J. ENEA, AND DAVID SMITH
01000	
01100	STANFORD UNIVERSITY
01200	ARTIFICIAL INTELLIGENCE PROJECT
01300	
01400	NOVEMBER, 1971
01500	.END
01600	.PORTION REPORT
01700	.INDENT 5,0
01800	.MACRO b ⊂ BEGIN GROUP NOFILL ; NARROW 8 ; INDENT 0,0 ⊃ ;
01900	.MACRO tree ⊂ BEGIN GROUP ; SKIP 1 ; TURN OFF "↓_↑" ; NOFILL ; NARROW 15 ; INDENT 0,0 ⊃
02000	.MACRO m ⊂ BEGIN GROUP ; SKIP ; TURN OFF "↓_" ; NOFILL ; NARROW 8 ; INDENT 0,0 ⊃
02100	.MACRO e ⊂ END ⊃
02200	.TURN ON "↓_[]π#"
02300	.MACRO s(N) ⊂ SNAME←DATE ; NEXT PAGE ONCE CENTER ; "N" ;
02400	.	SKIP 2 ; SNAME ← "N" ⊃ ;
02500	.EVERY HEADING(BACKTRACK PROGRAMMING SYSTEMS,,{SNAME})
02600	.EVERY FOOTING(,{PAGE},)
     

00100	.s NON-DETERMINED DECISION POINTS
00200	Every programming language includes decision statements, such as:
00300	.b
00400	↓_if_↓ a<0 ↓_then_↓ P(a) ↓_else_↓ Q(a)
00500	↓_if_↓ (A.LT.0) GO TO 7
00600	↓_case_↓ j ↓_of_↓ ↓_begin_↓ P(a) ; Q(a) ; R(b,c) ↓_end_↓
00700	.e
00800	When a decision statement is encountered, the processor decides on
00900	the basis of a well-defined condition which one of several
01000	alternative paths to follow to continue the computation.  Each
01100	encounter of a decision statement during execution is called a
01200	↓_decision point_↓ of the process.  In the case of ordinary decision
01300	statements, the choice of path is said to be ↓_determined_↓ when the
01400	decision point is encountered.  
01500	
01600	There is an important class of algorithms which contain decision
01700	points at which the choice of path is not "determined".  A graphic
01800	example is an algorithm to find a path through a maze.  At every fork
01900	there are several alternative ways of proceeding, and no previously
02000	computed information can determine which one will lead to the goal.
02100	It may be necessary to try more than one branch of the fork before
02200	discovering one that works.  Algorithms with non-determined decision
02300	points have been given the name ↓_non-deterministic algorithms_↓ by
02400	Floyd [JACM 14, 4(Oct. 1967),636-644].  Such algorithms are excellent
02500	for theorem provers, robot planners, natural language parsers, and
02600	other complex problem-solving tasks.
02700	
02800	Floyd's method of handling non-determined decision points is the
02900	method called ↓_backtrack_↓, which is described in detail by Golomb
03000	and Baumert [JACM 12,4, (Oct. 1965),516-524].  It has also been
03100	called ↓_depth-first_↓ goal-search to distinguish it from
03200	↓_breadth-first_↓ search (see for example pp. 34-36 of Tesler, Enea,
03300	and Colby [↓_Mathematical Biosciences_↓ 2, 1-2(Feb. 1968), 19-40]).
03400	A depth-first search first chooses one branch of the fork and
03500	searches it until it reaches either the goal or a dead end.  If the
03600	branch dead ends, the search ↓_backs up_↓ to the last (non-determined) decision point
03700	and chooses to search some other untried branch.
03800	(From now on, the term "decision point" will always refer to the non-determined
03900	variety.)
04000	
04100	A breadth-first search does not insist that every branch be pursued
04200	to its end.  After a branch has been searched awhile, it can be
04300	↓_suspended_↓ so that other branches can be pursued, and it can be
04400	resumed at a later time.  A branch may be suspended and resumed many
04500	times before it reaches the goal, reaches a dead end, or is
04600	abandoned due to the success of an alternate branch.
04700	
04800	The order of selection of the alternatives at a decision point may
04900	as well be arbitrary for the solution of some problems.  For others,
05000	a good order of selection can reduce the probable search time, or
05100	can assure that the "best" among several paths that all lead to the
05200	goal will be tried first.
05300	
     

00100	.s THE CONTEXT TREE PARADIGM
00200	With the maze problem in mind, it is seen that a goal-search can be
00300	diagrammed as a tree in which the nodes are decision points and the
00400	branches are search paths.  To graphically distinguish the current path
00500	from all others, it will always be drawn on the vertical, comprised of
00600	downward pointing arrows.  Paths that have already been tried and that
00700	terminated at a dead end will be drawn as solid lines to the left of this "trunk",
00800	and yet untried paths will be drawn as broken lines to its right.
00900	
01000	.tree
01100			|
01200			|
01300			↓
01400			A
01500		      / | \
01600		    /   |   \
01700		  B     ↓
01800		/ |     D
01900	      /   |	| \		Figure 1
02000	    FAIL  |	|   \
02100		  C	↓
02200		/ |	E
02300	      /   |
02400	    FAIL  FAIL
02500	.e
02600	
02700	Figure 1 represents a search that has proceeded as follows.  From an initial
02800	state at the top of the diagram, the decision point A was reached.  Three
02900	choices were available; the first one that was chosen is represented by the
03000	line AB.  The search then encountered decision point B, where there were
03100	two alternatives.  The first one that was chosen led to a dead end, signified
03200	by the label "FAIL".  At this point, the search backed up to decision point
03300	B and chose the next alternative, represented by the path BC.  Upon encountering
03400	decision point C, two alternatives were available, both were tried, and both
03500	led to dead ends and backed up to C.  With no remaining alternatives at C,
03600	the search backed up once more to B.  No alternatives remained there either,
03700	so it backed up to A.  Two alternatives remained at A, and one was chosen,
03800	represented by the line AD.  At decision point D, there were two alternatives.
03900	The one chosen led to the current state, E.  If this state should lead to
04000	a dead end, the node D will be rotated clockwise so that the path DE
04100	becomes left of the trunk and the other path from D becomes
04200	current.
04300	
04400	Whenever the search backs up to a decision point, it is necessary to restore
04500	much of the process state to what it was when that decision point was departed.
04600	For example, if the value of a variable h had the value 14 at A and was
04700	changed to 35 on the path AB, then during back up from B to A, the value
04800	14 must be restored to h.  We say, "h is restored to the value it had in the
04900	↓_context_↓ A", or "the assignment to h was ↓_undone_↓ during backup".
05000	Similarly, function calls and exits, input, and output must be undone during
05100	backup, or to put it another way,
05200	the control state and i/o pointers must be restored to the
05300	values they had in the old context.
05400	
05500	The dual capability of restoring prior states and of undoing past operations
05600	is useful in other applications than non-deterministic algorithms.  The
05700	capability has been or is being included in PLANNER [Hewitt...] and its
05800	derivatives, Micro-Planner [...] and extensions of BBN-LISP[Bobrow &
05900	Titelman...].  In these systems, the view is taken that the operation FAIL
06000	performed at a dead end restores the control environment (function nestings
06100	and variable bindings) to what it was at the last call on
06200	a special function such as  FAILSET(label).  No variable values or data structure
06300	contents are restored by the operation FAIL.  Instead, a jump is made to
06400	the label of the restored FAILSET, and at this label may appear code
06500	to change back variable values or to UNDO data structure alterations.
06600	
06700	Separating the concepts of FAIL and UNDO in this way provides a certain
06800	flexibility, but requires the programmer to keep track of what is to be undone
06900	and what isn't.  To simplify this job, those systems provide for most every common operation of
07000	the language an analogous reversible operation: THSETQ
07100	(reversible assignment) for SETQ (assignment); THCOND for COND; THAND
07200	for AND, etc.  Each of these notes the prior state and does a FAILSET,
07300	so that the prior state can be restored during backup.  For example,
07400	(THSETQ X Y) saves the old value of X and calls FAILSET(label).
07500	Then it stores Y into X and proceeds.  A later FAIL passing this operation
07600	will jump to the (label), where code will store the saved old value back
07700	into X and then FAIL back to a prior reversible operation or to the last
07800	decision point.
07900	
08000	The philosophy of the present paper is based on ↓_context restoration_↓ instead
08100	of ↓_operation undoing_↓.  Only one set of primitives is needed.  Every
08200	change is potentially reversible, but provisions are made to assign values
08300	relative to selected contexts and to exempt certain variables from
08400	restoration, thus achieving the effect of
08500	irreversible operations without adding a second set of primitives.  The
08600	difference in philosophy is a case of the ↓_doing_↓ and ↓_being_↓
08700	metaphysical duality.  In the PLANNER philosophy, each step on the way back
08800	to a decision point is un↓_do_↓ne, while in the context philosophy, the
08900	values that ↓_exist_↓ed at a decision point are restored no matter how
09000	and no matter how many times they were changed since then.
     

00100	.s SUSPENDED SEARCH
00200	To account for breadth-first searches in the tree paradigm, two approaches
00300	are possible.  One approach splits the trunk into two forks while the other
00400	permutes the order of nodes on the trunk, leaving it linear.
00500	
00600	Let us examine the "split trunk" approach.  It allows two or more forks to
00700	be searched "simultaneously".
00800	On single processor computers, processing
00900	power is alternated among the forks.  Whenever a particular fork is in
01000	control, it must be sure to access information from memory with respect to the proper
01100	context.  Two methods of assuring correct access are available.  One requires
01200	the programmer to declare which variables are shared between forks and which
01300	belong to just one fork.  This requirement makes it impossible for two forks
01400	to call the same subroutine, because the variables local to the subroutine
01500	must be declared to belong to one fork or the other, or they will be shared and
01600	conflicts and anomalies will result.  The other method is to label every
01700	item in memory (variable values, buffers, etc.) with the name of the fork or
01800	hierarchy of forks to which its contents applies.  Then every memory
01900	reference is required to search for the value that is labelled with the
02000	name of the fork in control or of one of its ancestral forks.  Such a search
02100	slows down program execution drastically.  This approach is employed in
02200	QA-4 [Rulifson...] and PLANNER, where the search is sped up somewhat in
02300	certain cases by use of hash tables.
02400	
02500	Now let us examine the "permuted trunk" approach.  It keeps the trunk linear
02600	so that there is only one current value for each variable, one current input
02700	pointer, and in particular, only one current fork.  Instead of allowing several
02800	nodes to be at the bottom of the trunk, only one is allowed.  When it is time
02900	for the search around that node to be suspended so another path can get a
03000	chance, the trunk is permuted so that the node that was formerly current becomes
03100	an "old decision point" and some other old decision point becomes current.
03200	In the example of Figure 1, if a statement at E requests suspension
03300	of the current path until all other alternatives from both D and A have been tried,
03400	the diagram will be transformed to that of Figure 2.
03500	.tree
03600			|
03700			|
03800			↓
03900			E
04000			| \
04100			|   \
04200			↓
04300			A
04400		      / | \
04500		    /   |   \
04600		  B     ↓
04700		/ |     D
04800	      /   |	|		Figure 2
04900	    FAIL  |	|
05000		  C	↓
05100		/ |
05200	      /   |
05300	    FAIL  FAIL
05400	.e
05500	
05600	The node that had been current, E, has been moved up above node A.  It will become
05700	current once more should the search ever back up all the way to A, try
05800	all of the remaining alternatives at A, and after failure of all of them,
05900	back up one more time.  If all this should happen, the search will proceed from E
06000	where it left off, and the diagram will become Figure 3.
06100	.tree
06200				|
06300				|
06400				↓
06500				E
06600			      / |
06700			    /	|
06800			  /	↓
06900			A
07000		      / | \
07100		    /   |   \
07200		  B     |
07300		/ |     D
07400	      /   |	|		Figure 3
07500	    FAIL  |	|
07600		  C	|
07700		/ |    FAIL
07800	      /   |
07900	    FAIL  FAIL
08000	.e
08100	
08200	The current path leading from E is the one that would have been searched earlier
08300	had E not been suspended.
08400	
08500	Note that after E was placed above A in Figure 3, it looked
08600	just like a decision point, i.e., a node from which several paths
08700	emanate.  What is common about a decision point and a suspended path
08800	is that they both represent a ↓_context_↓ that may need to be restored should
08900	the search back up to it.
09000	The tree may be thought of as a ↓_context
09100	tree_↓, and the lines as ↓_transitions_↓ between contexts.  Forward
09200	search creates the transitions that derive lower contexts from higher ones;
09300	backup performs their inverses to recover higher contexts from lower ones.
     

00100	.s THE CONTEXT STACK PARADIGM
00200	In a goal-search algorithm, it is only
00300	necessary to be able to manipulate the contexts that are on the trunk of
00400	the tree.  Contexts to the left are "dead" and can never be restored.
00500	Contexts to the right will be generated when they are needed via paths that emanate from
00600	contexts on the trunk.
00700	
00800	Restoration of an old context does not affect all parts of the process state.
00900	Some things survive dead ends, e.g., the real-time clock,
01000	constants and functions, proved theorems, perceptual data, and fixed
01100	beliefs.  We divide the entire process state into two components,
01200	the ↓_absolute_↓ component and the ↓_relative_↓ component.  The absolute
01300	component is not saved and restored; it is the same in any context.  The
01400	relative component may differ from context to context.
01500	
01600	The relative component of the state is represented
01700	by a vector of values, one value for each relative variable.
01800	The term "variable" is used here in its general sense including not only
01900	program variables but also buffer pointers, control stacks, temporary
02000	result registers, etc.  If the relative component consists of
02100	five relative variables, the vector contains five values.  It is
02200	assumed that the compiler allocates to each variable in the program a unique position
02300	in the vector.  
02400	
02500	The linear trunk of the search tree can be represented by a stack of such vectors, one
02600	for each context.  The top vector on the stack represents the current context.  Vectors
02700	underneath represent older contexts still on the trunk.
02800	
02900	Figure 4 represents a context stack.  The vector of the current context
03000	is at the top, representing m=56, n=42, x=11, y=3, and choose=L1.  (L1 is
03100	a "label" or "program reference type of value, i.e., an instruction address.)
03200	Altogether, three vectors are on the stack, corresponding to
03300	a tree with three nodes on the trunk.
03400	
03500	
03600	.m
03700		     m     |     n     |     x     |     y     |   choose
03800		    ---    |    ---    |    ---    |    ---    |   ------
03900		           |           |           |           |
04000		    56     |    42     |    11     |     3     |     L1    ← TOP
04100		           |           |           |           |             ROW
04200		    50     |    -8     |    11     |     2     |     L2
04300		           |           |           |           |
04400		   117     |     6     |    11     |     2     |     SYS
04500	
04600					FIGURE 4
04700	.e
04800	
04900	Suppose a decision point is encountered.  To save the current context
05000	before embarking on a branch, the first row is duplicated so that the
05100	stack has four rows instead of three (see Figure 5).
05200	Duplication of the top row effectively saves the current context in the
05300	stack.  This is such an important operation that it is given a special name,
05400	"SAVE CONTEXT".
05500	
05600	.m
05700		     m     |     n     |     x     |     y     |   choose
05800		    ---    |    ---    |    ---    |    ---    |   ------
05900		           |           |           |           |
06000		    56     |    42     |    11     |     3     |     L1    ← TOP
06100		           |           |           |           |
06200		    56     |    42     |    11     |     3     |     L1
06300		           |           |           |           |
06400		    50     |    -8     |    11     |     2     |     L2
06500		           |           |           |           |
06600		   117     |     6     |    11     |     2     |     SYS
06700	
06800					FIGURE 5
06900	
07000	.e
07100	
07200	After duplication of the top row,
07300	the branch being searched may alter the current values (top row) of relative
07400	variables freely, without destroying the copies saved in the second row
07500	of the stack.  Suppose m gets changed to 67 and x to 75.  Then the
07600	stack will appear as in Figure 6.
07700	
07800	.m
07900		     m     |     n     |     x     |     y     |   choose
08000		    ---    |    ---    |    ---    |    ---    |   ------
08100		           |           |           |           |
08200		    67     |    42     |    75     |     3     |     L1    ← TOP
08300		           |           |           |           |
08400		    56     |    42     |    11     |     3     |     L1
08500		           |           |           |           |
08600		    50     |    -8     |    11     |     2     |     L2
08700		           |           |           |           |
08800		   117     |     6     |    11     |     2     |     SYS
08900	
09000					FIGURE 6
09100	
09200	.e
09300	
09400	Now suppose a dead end is encountered.  Two things must be done: a "pop" and
09500	a "jump".  The pop restores an old context; the jump resumes execution
09600	in that context.  Let us examine each part separately.
09700	
09800	First, the
09900	context must be restored to what it was when the last decision point
10000	was departed.  This is done by simply popping the top row off the
10100	stack, returning it to the exact state shown in Figure 4.
10200	Popping the context stack is such an important operation that it is given
10300	a name: "REVERT".  REVERT is used at every dead end to revert to the most recent
10400	context saved on the stack.
10500	
10600	Second, the
10700	next branch leading from the decision point must be generated.
10800	Notice that to do this
10900	it would be incorrect to resume execution at the exact
11000	instruction that saved the context last time; if that were done, the same path that
11100	was followed last time would be followed again, and the program would
11200	probably enter an endless loop.  Instead, a certain
11300	relative variable, "choose", of type "label" is reserved for the address 
11400	of the routine which will choose the next path.  After popping the stack,
11500	a jump is made indirectly through "choose" to that label.
11600	
11700	For example, after the stack of Figure 6 is popped to restore the stack
11800	of Figure 4, a jump through "choose" resumes execution in the restored
11900	context at label L1.  There, the program will generate the next untried
12000	branch, will SAVE CONTEXT again, and will continue as before.  However, should no
12100	branches remain untried, the program will again REVERT to restore a still
12200	older context and then jump indirect through its "choose" to L2.  The
12300	reader may verify for himself that after all branches from that context
12400	have also been tried, the stack will revert to the state shown in Figure
12500	7, and that a jump will be made to SYS.
12600	It should be arranged that in the bottom row of the stack, "choose" is
12700	the label SYS of a system routine that reports total failure.
12800	
12900	
13000	.m
13100		     m     |     n     |     x     |     y     |   choose
13200		    ---    |    ---    |    ---    |    ---    |   ------
13300		           |           |           |           |
13400		   117     |     6     |    11     |     2     |     SYS   ← TOP
13500	
13600					FIGURE 7
13700	
13800	.e
13900	
14000	Factoring the operation of backup into two parts, a pop and a jump,
14100	makes the definition of more complex operations quite simple.  To
14200	backup not one but three decision points, thus eliminating many
14300	paths from consideration in a blow, one could pop the stack three times
14400	before jumping indirect through "choose".
14500	
14600	Suspension of a search is somewhat different from reaching a dead end,
14700	because it must be possible to resume the suspended search at a later
14800	time.  This is accomplished by moving the top row of the context stack
14900	between two other rows; should several REVERTs follow, the suspended
15000	row will again be on top and can resume execution.
15100	
15200	Back in Figure 6, suppose that a dead end is not reached, but the
15300	program decides to suspend the current search (row 1) until after the
15400	previous two contexts (rows 2 and 3) both prove to be total failures.
15500	First, it is necessary to save the resumption address (say it is L3)
15600	in "choose".  Then, the top row of the stack is exchanged with rows
15700	2 and 3 as a block.  This results in the stack of Figure 8.  A jump is
15800	then made through "choose" to L1.
15900	
16000	.m
16100		     m     |     n     |     x     |     y     |   choose
16200		    ---    |    ---    |    ---    |    ---    |   ------
16300		           |           |           |           |
16400		    56     |    42     |    11     |     3     |     L1    ← TOP
16500		           |           |           |           |
16600		    50     |    -8     |    11     |     2     |     L2
16700		           |           |           |           |
16800		    67     |    42     |    75     |     3     |     L3
16900		           |           |           |           |
17000		   117     |     6     |    11     |     2     |     SYS
17100	
17200					FIGURE 8
17300	
17400	.e
17500	
17600	Should the top two contexts exhaust all their untried paths, two REVERTs
17700	will result, leaving the stack as shown in Figure 9.  A jump through
17800	"choose" at that point will go to L3 and thus resume the suspended search.
17900	
18000	.m
18100		     m     |     n     |     x     |     y     |   choose
18200		    ---    |    ---    |    ---    |    ---    |   ------
18300		           |           |           |           |
18400		    67     |    42     |    75     |     3     |     L3    ← TOP
18500		           |           |           |           |
18600		   117     |     6     |    11     |     2     |     SYS
18700	
18800					FIGURE 9
18900	
19000	.e
19100	
19200	Should the resumed path eventually dead end, a REVERT will restore the
19300	stack to that of Figure 7, and a jump will be made to SYS.
19400	
19500	Moving row 1 of the context stack below the next m rows is an important
19600	operation warranting a special name: "POSTPONE m".
19700	
19800	Another common operation in tree search is pruning.  This amounts to removing
19900	nodes from the trunk once it has been decided that their untried branches shall
20000	not be needed in the search.  In the context stack paradigm, this
20100	is done by deleting one or more rows from the stack.  The operation of
20200	deleting the n'th row of the context stack is important and is given
20300	the name "DELETE CONTEXT n".
20400	
20500	For efficiency of implementation, it is useful to restrict the possible operations
20600	on the context stack to a selected set of primitives.  A set of four such
20700	primitives that is both powerful and easy to implement is:
20800	
20900	.b
21000	SAVE CONTEXT
21100		The top row of the context stack is duplicated.
21200		This operation should be preceded by "choose←<label>".
21300	
21400	DELETE CONTEXT n
21500		Row n of the context stack is deleted.
21600		The case n=1 is REVERT; a jump through "choose" usually follows.
21700		The case n>1 prunes the search tree.
21800	
21900	EXCHANGE n WITH m
22000		Rows 1 through n are exchanged with rows n+1 through n+m.
22100		This operation should be preceded by "choose←<label>".
22200		It should be followed by a jump through "choose".
22300		The case n=1 is "POSTPONE m".
22400	
22500	x FROM n
22600		This references the variable x or evaluates the expression x
22700		with respect to the context n, i.e., any relative variables
22800		mentioned in x are obtained from row n.
22900		Example:  "m FROM 3 ← (x + y) FROM 2"
23000	.e
     

00100	.s APPLICATION TO NON-DETERMINISTIC ALGORITHMS
00200	Algol 60 procedures will be employed to illustrate the use of the primitives just
00300	defined.  To avoid confusion with regard to bindings of variables,
00400	procedure return addresses, go-to restrictions, etc., a literal
00500	interpretation of the Algol 60 report should be made.  Thus, every call on
00600	a procedure is replaced by a copy of the procedure body with appropriate
00700	systematic renaming of variables.  This definition of a procedure in
00800	Algol 60 corresponds to the "macro" in many programming languages.
00900	
01000	Some extensions to Algol 60 will be made.  A label may be assigned to the variable
01100	"choose", and "↓_go to_↓ choose" will jump to that label.  To distinguish
01200	absolute variables from relative variables, absolute variable names will
01300	be spelled with all capital letters, and relative variable names with all
01400	lower case letters.
01500	The statement "↓_while_↓ <boolean expression> ↓_do_↓ <statement>" is equivalent to
01600	"LOOP: ↓_if_↓ <boolean expression> ↓_then_↓ ↓_begin_↓ <statement> ; ↓_go to_↓ LOOP ↓_end_↓".
01700	
01800	Floyd's paper introduced notation for non-deterministic algorithms.
01900	A decision point is signified by a call on the multi-valued function ↓_choice_↓(X),
02000	a dead end by the label FAILURE, and goal attainment by the label
02100	SUCCESS.
02200	The effect of ↓_choice_↓(X) and FAILURE can be achieved as follows:
02300	.b
02400	↓_procedure_↓ REVERT ; DELETE CONTEXT 1 ;
02500	
02600	↓_procedure_↓ FAILURE ; ↓_begin_↓ REVERT ; ↓_go to_↓ choose ↓_end_↓ ;
02700	
02800	↓_integer_↓ ↓_procedure_↓ CHOICE(x) ; ↓_value_↓ x ; ↓_integer_↓ x ;
02900	↓_begin_↓
03000		choose ← NEXT ;  ↓_go to_↓ TRY ;
03100		NEXT:  x ← x - 1 ;
03200		TRY:  ↓_if_↓ x ≤ 0 ↓_then_↓ FAILURE ↓_else_↓ SAVE CONTEXT ;
03300		CHOICE ← x ;
03400	↓_end_↓ CHOICE ;
03500	.e
03600	At each dead end, the FAILURE routine recovers the last saved context
03700	and jumps through "choose" to the label NEXT of the corresponding incarnation
03800	of the CHOICE procedure.  If more values of x remain untried, the next one
03900	is selected and the context is again saved.  If none remain, another
04000	FAILURE occurs to recover a still earlier context.
04100	
04200	Let us trace a short program that uses these facilities.
04300	
04400		--- example to be added later ---
     

00100	.s ADDITIONAL CAPABILITIES
00200	It is possible using these primitives to replace FAILURE at a dead end by
00300	a sequence such as:
00400	.b
00500	REVERT ; r ← r + 4 ; x ← x - 3 ; ↓_if_↓ f(j,r) ↓_then_↓ FAILURE ; ↓_go to_↓ choose
00600	.e
00700	which can tamper with the relative variables of the restored context and even
00800	backup to an earlier decision point before going to "choose".
00900	
01000	A common operation in backtrack is to "fail to a label".  This really
01100	amounts to executing REVERT repeatedly until a specific decision point
01200	becomes current.  One way to accomplish this is to identify some predicate in
01300	terms of relative variables which is true in the context to be restored but
01400	false in every context above it in the stack.  For example, in a parser,
01500	to fail to the last decision point at which the scanner was pointing to
01600	a semicolon, one could write:
01700	.b
01800	↓_while_↓ scanchar ≠ SEMICOLON ↓_do_↓ REVERT ; ↓_go to_↓ choose
01900	.e
02000	
02100	One often would like to know the current subscript of some particular
02200	context in the stack.  It is difficult to keep track after a series of duplications,
02300	pops, and exchanges.  One way to solve this problem is by means of a procedure
02400	"WHEN(b)", which finds the first row of the context stack in which "b"
02500	is true and returns the number of that row.
02600	.b
02700	↓_integer_↓ ↓_procedure_↓ WHEN(b) ; ↓_boolean_↓ b ;
02800	↓_begin_↓ ↓_integer_↓ c ;
02900		c ← 1 ; ↓_while_↓ ¬(b FROM c) ↓_do_↓ c ← c - 1 ;
03000		WHEN ← c ;
03100	↓_end_↓ WHEN ;
03200	.e
03300	WHEN can be used in a routine to postpone the current path until after
03400	the failure of all contexts back to and including one in which p<0:
03500	.b
03600	EXCHANGE  1  WITH  WHEN( p<0 ) - 1  ;
03700	.e
03800	
03900	It is convenient to be able to subject input and output to backup.  One
04000	would like to perform output relative to the current context, and let the
04100	output disappear if the context should be deleted.  Similarly, while input
04200	is scanned in a forward direction during forward search, it should be
04300	possible to scan it backwards during backup so that alternative search
04400	paths have an opportunity to rescan the same data.  On the other hand,
04500	some input and much output -- such as progress reports to the user terminal
04600	-- should occur immediately and not be reversible.
04700	
04800	There are two approaches to handling reversible i/o.  One is to have a set
04900	of reversible i/o routines and a set of irreversible ones.  The reversible
05000	(relative) input routine calls the irreversible (absolute) input routine
05100	when the value desired by the current context has not yet been physically
05200	input.  All values physically input so far from each channel are
05300	kept in a list which the reversible input routine references when
05400	the value desired in the current context has already been physically input
05500	(by some other context that had since been abandoned).
05600	
05700	The other approach to i/o
05800	is to have absolute files and relative files.  The task of handling
05900	relative files is similar to that of handling relative variables
06000	of type array or list.  Relative output within the root context of the
06100	tree might go directly to external devices, while output within other
06200	contexts might be held back until pruning sifts it up to the root context.
06300	In implementation of reversible i/o, there are tradeoffs between using
06400	memory space for saved input and relative output versus actually performing
06500	operations on the i/o media and then reversing the operations.  The
06600	optimum method for a given set of operations on a given medium is an
06700	engineering question which should be decided separately in each case.
     

00100	.s COMPACTING THE CONTEXT STACK
00200	If the context stack paradigm were implemented literally, it would
00300	be necessary to copy the values of all relative variables before
00400	embarking on every branch from every decision point.  In a realistic
00500	problem, this might consume an enormous amount of space and time,
00600	especially since many of the values could be large list structures.
00700	
00800	In practice, it is not necessary to copy the entire context, because only
00900	part of it changes from one decision point to the next -- often just a few
01000	variables.  Any scheme which ↓_effectively_↓ implements primitives such as
01100	FROM, SAVE CONTEXT, DELETE CONTEXT, and EXCHANGE is an adequate scheme.
01200	It is not necessary that the context stack be structured as described
01300	earlier (or even that it exist at all) as long as the programs behave that way.
01400	
01500	We divide all relative variables into two categories, ↓_high frequency_↓
01600	variables and ↓_low frequency_↓ variables.  A high frequency variable is one
01700	that changes relatively often as compared to the frequency of embarking on
01800	new search branches.  A low frequency variable changes relatively less
01900	often.  The distinction is not precise; rough criteria that can be applied
02000	to many programming languages will be suggested later.  For the
02100	moment we will assume that the programmer has declared each variable to
02200	be ↓_high_↓ or ↓_low_↓, or that the compiler has performed a loop analysis
02300	and determined a categorization.
02400	
02500	Suppose a program has M relative variables, of which H are high frequency
02600	and L are low frequency, and that the length of the context stack is C.
02700	Then the stack can be thought of as a C#x#M matrix of values, which can be
02800	partitioned into a C#x#H and a C#x#L part.  The C#x#H part will be called the
02900	matrix "HIGH" and the C#x#L part the matrix "LOW".  The analysis of compaction
03000	for each of these matrices will be treated separately in the discussion.
     

00100	.s LOW FREQUENCY VARIABLES
00200	The rows of the matrix LOW represent contexts and the columns represent variables.
00300	Since the subscript of any particular context changes every time the
00400	stack is pushed or popped, it is useful to associate with each context
00500	a relatively permanent ↓_tag_↓.  The tag of the context represented
00600	by row r of LOW is stored in TAG[r].
00700	
00800	In the algorithms that appear in Appendix 1, use is made of the property
00900	that iff i<j, TAG[i]<TAG[j].
01000	For this reason, and to avoid confusion with row subscripts, the tag of
01100	the bottom row of the matrix will be 99,000 (99K) and that of each
01200	new context added on top will be 1000 (1K) less than that of the
01300	context immediately below it.
01400	
01500	An example of the TAG vector and the LOW matrix with 9 contexts
01600	and 5 variables is presented in Figure 4.
01700	.m
01800	row |  TAG  |     v     |     w     |     x     |     y     |     z
01900	--- |  ---  |    ---    |    ---    |    ---    |    ---    |    ---
02000	    |       |           |           |           |           |
02100	 1  |  91K  |     0     |     2     |    11     |     3     |    14
02200	    |       |           |           |           |           |
02300	 2  |  92K  |     0     |     2     |    11     |     2     |    14
02400	    |       |           |           |           |           |
02500	 3  |  93K  |    -7     |     2     |    11     |     2     |    14
02600	    |       |           |           |           |           |
02700	 4  |  94K  |    -7     |     2     |    11     |     2     |    -6
02800	    |       |           |           |           |           |
02900	 5  |  95K  |    -7     |     2     |    20     |     1     |     7
03000	    |       |           |           |           |           |
03100	 6  |  96K  |     5     |     2     |     8     |     1     |     7
03200	    |       |           |           |           |           |
03300	 7  |  97K  |     5     |     2     |     8     |     1     |     7
03400	    |       |           |           |           |           |
03500	 8  |  98K  |     5     |     2     |     8     |     0     |     7
03600	    |       |           |           |           |           |
03700	 9  |  99K  |     5     |     0     |     8     |     0     |     7
03800	
03900						FIGURE 4
04000	
04100	.e
04200	The variables v, w, x, y, and z are by definition low frequency.
04300	Thus adjacent entries in each column are usually equal.  This property
04400	suggests a compaction scheme such as the following.  Each sequence of
04500	equal values U in a column is replaced by the pair T:U where T is the
04600	tag of the last row in the sequence.  The pair T:U replaces the first
04700	member of the sequence, and the rest of the sequence is deleted.  If
04800	this transformation is applied to Figure 4, the result is Figure 5.
04900	.m
05000	row |  TAG  |     v     |     w     |     x     |     y     |     z
05100	--- |  ---  |    ---    |    ---    |    ---    |    ---    |    ---
05200	    |       |           |           |           |           |
05300	 1  |  91K  |  92K: 0   |  98K: 2   |  94K: 11  |  91K: 3   |  93K: 14
05400	    |       |           |           |           |           |
05500	 2  |  92K  |     ↓     |     ↓     |     ↓     |  94K: 2   |     ↓
05600	    |       |           |           |           |           |
05700	 3  |  93K  |  95K: -7  |     ↓     |     ↓     |     ↓     |     ↓
05800	    |       |           |           |           |           |
05900	 4  |  94K  |     ↓     |     ↓     |     ↓     |     ↓     |  94K: -6
06000	    |       |           |           |           |           |
06100	 5  |  95K  |     ↓     |     ↓     |  95K: 20  |  97K: 1   |  99K: 7
06200	    |       |           |           |           |           |
06300	 6  |  96K  |  99K: 5   |     ↓     |  99K: 8   |     ↓     |     ↓
06400	    |       |           |           |           |           |
06500	 7  |  97K  |     ↓     |     ↓     |     ↓     |     ↓     |     ↓
06600	    |       |           |           |           |           |
06700	 8  |  98K  |     ↓     |     ↓     |     ↓     |  99K: 0   |     ↓
06800	    |       |           |           |           |           |
06900	 9  |  99K  |     ↓     |  99K: 0   |     ↓     |     ↓     |     ↓
07000	
07100					FIGURE 5
07200	
07300	.e
07400	In a computer, the sparse matrix can be stored as a triply-chained list
07500	structure, with the entries of each row chained in arbitrary order
07600	and the entries of each column chained in strict order both from top to
07700	bottom and from bottom to top.
07800	It is straightforwrd to program FROM, SAVE CONTEXT, DELETE CONTEXT,
07900	and EXCHANGE to operate on such compacted structures.
08000	In a computer,
08100	the top row might occupy a fixed set of locations, so that the value of each
08200	variable in the current context can be fetched without searching.
08300	
08400	The first row of the compacted matrix is always full.  Thus, programs
08500	should avoid scanning the top row.  This is easy to arrange; for example,
08600	EXCHANGE n WITH m needs to scan only rows 2 through n+m+1 of the sparse
08700	compacted structure.  Complete algorithms for each primitive appear in
08800	Appendix 1.
08900	
09000	Assignment to a variable in this scheme incurs some overhead.  Before
09100	assigning a new value V to the variable X whose current entry in row 1 is
09200	T:U, a "compare-tag" instruction must compare TAG[1] with T.  If TAG[1]=T,
09300	the entry T:U is simply changed to T:V.  However, if TAG[1]>T, then to
09400	maintain the correctness of the compacted structure it is necessary to
09500	copy T:U to row 2 and then replace the entry in row 1 by TAG[1]:V.  Fetches
09600	incur no such overhead.
09700	
09800	So far, we have assumed that the number of relative variables is constant
09900	throughout execution.  In practical languages,
10000	it is possible to create new instances of variables by various means,
10100	but primarily by calling a procedure (or function or subroutine) and
10200	"binding" arguments or local variables.  Usually, such instances can
10300	be destroyed as well, for example, by leaving the procedure.
10400	
10500	To extend the context stack technique to handle varying numbers of
10600	variables is a simple matter.  Whenever a new variable is created, a new
10700	column is added to the LOW matrix.  Its entry in row 1 is its initial
10800	value; in other rows, the symbol "α" is entered to signify "this variable
10900	did not exist in this context".  Whenever a variable is destroyed,
11000	its column can not necessarily be destroyed because it might still exist in other
11100	contexts.  Thus, "α" is merely stored in its first row.  If the column
11200	should ever contain only "α", then it may be discarded.
11300	
11400	Compaction can be applied to matrices with "α" quite easily; "α" is
11500	treated just like any value that is repeated in a long sequence of
11600	contexts.  The case of a full column of "α" is easy to detect if checked
11700	for at every variable "unbinding" and by the DELETE CONTEXT routine.
11800	
11900	Practical programming languages allow several variables to have the same
12000	name.  Generally, a reference to the name "y" accesses the most recently created
12100	variable of that name.  All variables of the same name may be
12200	chained together from youngest to oldest.  The youngest "y" is
12300	pointed to from a fixed location Y known to the compiler.  When an
12400	assignment to "y" requires copying the old value to row 2 of LOW, only
12500	the pointer at Y need be copied; information about
12600	other variables named "y" is automatically accessible via the chain.
12700	
12800	The concept of ↓_environments_↓ in which the same name
12900	can refer to different variables is analogous to the concept of ↓_contexts_↓
13000	in which the same variable can have different values.
13100	That is why stacks are used to implement both the environments of Algol
13200	and LISP and the contexts of this paper.  In fact, the analogy extends
13300	further: coroutines can be implemented by permutation of the conventional
13400	environment stack just as suspension is implemented in this paper by
13500	permutation of the context stack.  Furthermore, the context stack can
13600	be viewed as a sort of two-dimensional stack; it grows upward for new
13700	contexts, and grows to the right for new environments.
     

00100	.s HIGH FREQUENCY VARIABLES
00200	A high frequency variable is changed one or more times in nearly every
00300	context.  Adjacent entries in any column of the HIGH matrix tend to be
00400	unequal, or equal only by coincidence.  If the HIGH matrix were compacted
00500	by the method applied to the LOW matrix, the resulting triply-chained
00600	structure would be even larger than the uncompacted matrix.  Furthermore,
00700	every store into a high frequency variable would be preceded by a compare-
00800	tag instruction which, considering the frequency of such stores, would
00900	incur a large overhead.
01000	
01100	In case a high frequency variable represents a data structure, it
01200	is possible that although changes to the structure occur frequently, the
01300	average element of the structure changes infrequently.  To take advantage
01400	of this common situation, high frequency variables will be divided into
01500	three categories: ↓_stacks_↓, ↓_arrays_↓, and ↓_units_↓.  A unit is a
01600	variable whose value is changed "as a unit", i.e., a "scalar" non-structure,
01700	a structure that changes in its entirety, or a structure most of whose
01800	elements change from context to context.  A stack is a structure to which
01900	changes are made at or near one end from context to context.  An array is
02000	a structure in which only a few elements change from context to context;
02100	the elements that change are not known to all lie at one end.
02200	
02300	Examples of unit variables are the computer's fast registers, heavily used
02400	global variables, and backtrack control variables such as "choose".
02500	There is no way of avoiding having a copy of these variables for every
02600	saved context, unless one is willing to recompute them from other
02700	information saved in that context.  Therefore, unit variables are
02800	in general copied at every SAVE CONTEXT.
02900	
03000	If a single decision point generates several branches, it is likely that the
03100	saved values of most unit variables will be the same from branch to branch.
03200	Recopying before embarking on every branch performs redundant work.  If the compiler can
03300	isolate those few unit variables that are affected by the next-branch generator,
03400	it can arrange for SAVE CONTEXT to copy those every time, but to copy the
03500	other unit variables only before embarking on the first branch.
03600	
03700	Array variables which change frequently but only in part are easy to
03800	handle.  Each element of each array is considered a separate low frequency
03900	variable and is assigned a column of the matrix LOW.  Thus, nothing is copied
04000	by SAVE CONTEXT and only changed elements are restored by REVERT.
04100	
04200	To avoid treating each element of a stack as a separate low frequency
04300	variable, the stack can be divided into sections.  The top section can
04400	be treated as a unit variable, copied at every SAVE CONTEXT, and the other
04500	sections can be treated as low frequency variables, copied only if the
04600	stack happens to shrink so far as to bring them to the top.  Sometimes,
04700	there is a natural division into sections; the local variable stack of
04800	an Algol program can be divided at procedure entry points.  Other times,
04900	it is best to mark the stack at every SAVE CONTEXT and REVERT and consider
05000	sections to lie between marks.
05100	
05200	Note that
05300	from one SAVE CONTEXT to the next, the top of the stack may descend instead of
05400	rise.
05500	To represent the status of a stack in some context, a linked list of
05600	sections can be used.  Each context has its own version of the list
05700	header, but whatever parts of the "tail" are common can be shared.
05800	In fact, such sharing can be done for any linked list that is
05900	changed only at the head, e.g., LISP linked lists that are operated upon by
06000	cons, car, and cdr, but not by rplaca and rplacd.
06100	
06200	Many execution systems employ an environment stack for subroutine return addresses,
06300	local variables, and temporary results.  The local variables in such a
06400	stack are often high frequency during execution of their owning routine
06500	but zero frequency when inaccessible deep in the stack.  Thus,
06600	the stack can efficiently fit into backtracking by the following
06700	scheme.  SAVE CONTEXT block transfers the accessible cells of the
06800	control stack (the local routine's variables, return address, and
06900	temporary results) to a copy area, links the copy area to the next lower
07000	section of the stack, and points the top of stack pointer at the copy
07100	area.  As long as only local changes are made or the stack grows, no damage is
07200	done to the original cells.  However, if the copy area is popped from the stack,
07300	it is necessary to make a copy of the newly accessible area below it
07400	in the same way.  This condition must be checked when each function is exited.
07500	If a REVERT occurs, the top of stack pointer is pointed
07600	back at the original cells and everything has been restored correctly.
07700	
07800	On the assumption that accessible local variables are high frequency,
07900	it is cheaper to do the block transfers than to use the tagging method
08000	of high frequency variables.  Each stack variable is copied at
08100	most once per decision point, and that copy takes a fraction of an
08200	instruction (block transfer) to accomplish.  At dead ends, nothing is
08300	copied; dead stack sections are merely abandoned to the memory
08400	reclaimer.  Notice that no copy at all is done unless the variable
08500	is actually exposed to change by being in the topmost section of the
08600	stack.
08700	
08800	In LISP as well as other languages, a useful distinction that can be
08900	declared by the programmer and sometimes deduced by the compiler is
09000	between ↓_private_↓ and ↓_public_↓ variables.  A private variable is
09100	only accessible from within the body of the function or procedure in
09200	which it is declared and bound.  A public variable is accessible from
09300	routines which that one calls as well.  Private variables
09400	tend to be high frequency when their binding function is being
09500	executed, but are zero frequency otherwise, so they fit well into the
09600	stack scheme just mentioned.  Public variables tend to be low frequency
09700	and fit well into the compacted structure scheme of the
09800	preceding section.
     

00100	.s METHODS OF IMPLEMENTATION
00200	Until the late 1960's, the standard method of
00300	restoring the correct context was to program each step of the restoration
00400	manually.  This proved tedious and at times prohibitively complex (We
00500	refrain from saying impossible).  Undoing recursive
00600	function exits by explicit programming is an exercise left to the
00700	doubting reader.
00800	Several methods of achieving automatic backup have since been developed.
00900	
01000	Floyd's paper suggested a method which may be
01100	called the ↓_inverse function method_↓.
01200	The compiler generates for each program statement both
01300	forward and backward code.  The forward code is executed to search
01400	paths.  It includes steps to save state information on auxiliary
01500	stacks whenever the state is about to be altered.  If the label FAILURE is encountered,
01600	the backward code is executed to
01700	work back to the last decision point.  For each step of the forward code that
01800	altered the state, the inverse of that step is executed in the backward code.
01900	For "functions" with uncomputable or difficult inverses (i.e., most assignments
02000	and all control state changes and input-output), the information on the
02100	auxiliary stacks is employed to restore the state to the old context.  When
02200	the decision point is reached, another choice
02300	is made and the forward code is again executed.  Output attempted by
02400	the forward code is diverted to one of the auxiliary stacks, which
02500	is finally output when the label SUCCESS is encountered.
02600	
02700	When the statement "i ← ↓_choice_↓(X)" is encountered in the forward
02800	code, it assigns the value of X to "i".  When it is encountered in
02900	the backward code, it decreases "i" by 1.  If i>0, the forward code is
03000	executed, but if i=0, all branches from the decision point have dead
03100	ended and a FAILURE condition is generated.  The backward code that
03200	leads back to an earlier decision point is then followed.
03300	
03400	Using the inverse function method is superior to copying the entire state
03500	at every branch of the goal search tree.  However, at times redundant information
03600	is pushed on an auxiliary stack.  The backward
03700	code is generally much smaller and faster than the forward code, so
03800	the proper context can be restored relatively quickly.  This advantage
03900	is lost if one attempts to extend the method to handle suspended paths.
04000	To restore a suspended path, forward code must be re-executed, often at
04100	a prohibitive cost.
04200	Alternatively, the compiler could be made to generate, in addition to
04300	forward and backward code for every statement, suspension and resumption
04400	code which would utilize an additional auxiliary stack.  The extra object
04500	code that would be necessitated is an unattractive prospect.
04600	
04700	A second method of automatic backup is being implemented in QA-4.
04800	The importance of breadth-first search to the QA-4 Theorem Prover
04900	compels the use of simultaneously active forks in the context tree.  Each
05000	variable va;ue is tagged with the unique number of the context to which it
05100	applies, or the number of the common ancestor of several contexts to which
05200	it applies.  Every memory access must perform a linked-list search or
05300	hash-guided search to find the relevant value in memory.  Switching among
05400	contexts is instantaneous.  To reject an alternative, its context tag is
05500	simply added to the garbage collect list.
05600	
05700	A third method is copying of the entire memory except read-only portions.
05800	This has been implemented in POP-2 [ref].  The
05900	advantage is that if no decision points occur, no overhead is incurred.
06000	However, at each branch and each dead end, secondary storage i/o is
06100	necessary.  If the search extends several levels, prohibitive amounts of
06200	secondary storage can be consumed.
06300	
06400	A fourth method uses a compacted context stack and segmented environment stack as elaborated in this paper.
06500	It has been implemented in MLISP-2 [Enea & Smith, ...] and used to
06600	program an English sentence conceptual analyzer [Schank, ... ;
06700	Enea & Smith, ....] and a theorem prover [Milner, ...].  An idea of
06800	the performance of the context stack method at work in a complex problem
06900	may be gained from some statistics for the conceptual analyzer.  In
07000	parsing a complex sentence, the stack reaches a search depth of as many as
07100	25 or more levels.  This requires up to 3000 words of saved information on the
07200	PDP-10.  Processing time is on the order of one second per sentence.  These
07300	statistics of course vary with the degree of ambiguity and with the length
07400	of the sentence in question.
07500	
07600	In MLISP-2, only the
07700	primitives SAVE CONTEXT, REVERT, FROM, and a variety of PRUNE are
07800	available.  In its successor, LISP-3 (currently under
07900	development by the authors), EXCHANGE and the general DELETE CONTEXT will
08000	be available, enabling the occasional use of breadth-first search.
08100	
08200	A fifth method is being implemented in PLANNER [Hewitt ...].  The
08300	control environment (function nesting and variable bindings) are
08400	restored instantaneously during backup by the same method as in QA-4.
08500	Suspension and resumption of paths are similarly rapid.
08600	The values of variables and the contents of global data structures
08700	are restored by a variation on inverse functions.  For every operation
08800	of conventional programming, such as ASSIGN, there is a reversible
08900	operation which arranges its own undoing
09000	by adding a little reversing process to a chain
09100	that is then followed during backup.
09200	
09300	A sixth method of automatic backup has been proposed for BBN-LISP
09400	[Bobrow, Titelman, Hartley...].  The control environment is restored,
09500	but only the bindings of variables -- not
09600	their values.  As in PLANNER, a chain of reversible
09700	operations is then followed to restore certain values.  This scheme
09800	allows more flexible UNDOing of data structure changes than is needed
09900	for non-deterministic algorithms, but requires explicit indication of
10000	each reversible step.  Thus, it is probably more suitable for powerful
10100	user-terminal interaction than for the complex problem-solving tasks addessed
10200	by this paper.