perm filename BACK.PUB[L70,TES] blob
sn#009933 filedate 1972-06-27 generic text, type T, neo UTF8
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.