perm filename BACK70.PUB[L70,TES] blob sn#009952
filedate 1972-06-27 generic text, type T, neo UTF8
00100 LISP70 BACKTRACKING IN BRIEF
00400 THE ALIST
00500 --- -----
00700 The control structure of LISP is most easily represented by a levelled
00800 ALIST. Here is such an ALIST with three levels:
01000 ( X:4,Y:3,PC:105 ) ( X:7,PC:350 ) ( Z:9,Y:18,PC:10 )
01200 Each level represents a function invocation. It contains the
01300 bindings of variables bound by that function and the address
01400 (PC) of the next instruction to be executed in that invocation.
01600 The current function invocation is represented by the leftmost level.
01700 The PC of that level is the current program counter, i.e., the
01800 address of the next instruction to be executed by the program.
01900 The current binding of any variable X is found by searching the ALIST
02000 from the left for the first occurrence of a pair X:v .
02200 To return from a function, its value is placed in the global variable
02300 RESULT (not shown) and the leftmost level of the ALIST is deleted.
02400 Doing this to the ALIST shown above yields:
02600 ( X:7,PC:350 ) ( Z:9,Y:18,PC:10 )
02800 The program continues from the new leftmost PC. Thus, this is the
02900 return address of the function.
03100 To call a function, a parameter binding list is formed as follows.
03200 It has each formal parameter of the called function bound to the
03300 actual parameter supplied by the calling function. It also
03400 has PC bound to the initial address of the called function.
03500 From the above ALIST, suppose that the call λx,y[<code>][2,3]
03600 is made. The parameter binding list formed is:
03800 ( X:2,Y:3,PC:<code> )
04000 This list becomes the new leftmost level of the ALIST. For the
04100 above call, suppose that PC has advanced to 370 in the calling function,
04200 and that the called function begins at 525. Then this would yield:
04400 ( X:2,Y:3,PC:525 ) ( X:7,PC:370) ( Z:9,Y:18,PC:10 )
04600 For consistency, we will consider that global variables and the
04700 property lists of atoms are also kept in the ALIST, but in a
04800 level to the right of all the function invocation levels.
00100 SETQ AND PROG
00200 ---- --- ----
00400 SETQ[X,9] changes the value bound to the leftmost X in the ALIST to 9.
00500 If no such X occurs, the global X (not shown) is changed.
00700 ( X:9,Y:3,PC:530 ) ( X:7,PC:370) ( Z:9,Y:18,PC:10 )
00900 PROG[[a,b] ...] adds the bindings A:NIL and B:NIL to the front of
01000 the leftmost level of the ALIST, but does not add a new level:
01200 ( A:NIL,B:NIL,X:2,Y:3,PC:535 ) ( X:7,PC:370) ( Z:9,Y:18,PC:10 )
01400 At the end of the PROG, those bindings are removed.
01900 There are many backtracking paradigms, but they all
02000 revolve around the same theme. Certain points in the computation are
02100 designated "failure points" or "choice points" or "decision
02200 points". Upon "failure", the computation backs up to the last such point.
02300 This requires the capability of restoring a prior state of the computation.
02500 One way to implement backtracking in LISP is to use a second
02600 association list called the CLIST ("context list") to save a record of
02700 the ALISTS that existed at each decision point. An over-simplified
02800 CLIST might look like this:
03000 ( ALIST#:((Y:3,PC:60)) ) ( ALIST#:((X:4,PC:510)(Y:3,PC:45)) )
03200 The current ALIST is inside the leftmost level of CLIST. To find the
03300 current value of a variable, only the current ALIST is searched,
03400 because the other ALISTs represent earlier states of the computation.
03600 Inside CLIST, a "#" is written after ALIST to emphasize that it is not
03700 the usual kind of LISP variable. Variables within the ALIST will
03800 be called "block variables" and variables within the CLIST will be
03900 called "contextual variables". The name of each contextual variable
04000 will end with one "#".
04200 Failure deletes the
04300 leftmost level or "context" of the CLIST. This returns to the
04400 previous context. To enter a context, a new level is added to the CLIST,
04500 containing a copy of the current ALIST.
04700 Thus, failure out of a context is analogous to return from a
04800 function, and entering a context is analogous to calling a function.
00100 CHOICE FUNCTIONS
00200 ------ ---------
00400 The trouble with the formulation so far is that failure restores the
00500 exact ALIST that led to failure, and thus the program will repeat its
00600 previous actions and fail again. To remedy this, it is necessary that
00700 some part of the state change from one restoration of the state to the
00800 next. One way to accomplish this is by the use of contextual variables.
01000 After a context is created, contextual variables can be bound in it
01100 just as PROG variables can be bound in a function. A BIND statement
01200 is used in LISP70. Thus:
01400 BIND N# TO 10, I# TO 0 ;
01600 changes the above CLIST to:
01800 ( N#:10,I#:0,ALIST#:(...) ) ( ALIST#:(...) )
02000 A new context can then be created by CREATE CONTEXT:
02200 ( ALIST#:(...) ) ( N#:10,I#:0,ALIST#:(...) ) ( ALIST#:(...) )
02400 Initially, the current and second ALIST are identical, except that the
02500 PC of the second ALIST is still pointing at the CREATE CONTEXT
02600 instruction while the PC of the current ALIST has passed it.
02700 Computations in the new context will not affect the ALIST of the old context.
02800 However, assignments to N# and I# will change the state saved in the
02900 old context. Subsequent failure will restore that context and cause
03000 CREATE CONTEXT to be repeated, but the program may not loop
03100 because this time N# and/or I# may have different values than last time.
00100 As an example, Floyd's function CHOICE(N) will be defined.
00300 Statement Resulting CLIST for CHOICE(10)
00400 --------- --------- ----- --- ----------
00600 function choice(n) = ( ALIST#:(...) ) (...)
00800 bind n# to n, i# to 0 ; ( N#:10,I#:0,ALIST#:(...) ) (...)
00900 create context ; ( ALIST:(...) ) ( N#:10,I#:0,ALIST#:(...) ) (...)
01000 i# ← i# + 1 ; ( ALIST:(...) ) ( N#:10,I#:1,ALIST#:(...) ) (...)
01100 if i# > n# then
01200 fail twice (...) Note: Backtracks to an earlier CHOICE.
01300 else return i# ; ( ALIST:(...) ) ( N#:10,I#:1,ALIST#:(...) ) (...)
01600 If CHOICE returns, then the calling
01700 function proceeds in the new context with RESULT = I# = 1.
01800 Subsequent failure erases the leftmost context, restores the previous
01900 ALIST to current status, and resumes execution at the CREATE CONTEXT
02000 instruction inside CHOICE. This steps I# to 2 and returns 2 as the
02100 result of CHOICE.
02300 When I# reaches N+1, CHOICE should fail. To accomplish this requires
02400 FAIL TWICE, which first erases the context created inside CHOICE
02500 and then erases the context that existed when CHOICE was called.
00400 A backtracking LISP interpreter could be developed literally following
00500 the formulation presented above, and would suffice for
00600 the programming of simple backtracking problems. However, backtracking
00700 is most helpful in very complex and thus very large recursive
00800 programs with large data bases. In such programs, copying the entire
00900 ALIST at every decision point -- including all function levels, global variables, and
01000 property lists of atoms -- can become prohibitively expensive.
01200 Fortunately it is not necessary to do this. In a large program,
01300 only a fraction of the entire ALIST changes from context to context, and
01400 to be able to restore the state, only changed parts need be saved.
01600 One common technique uses a "history list" or stack. Every time a change is
01700 made to the ALIST, an instruction for changing it back is pushed on the
01800 top of the history list. To fail, the history list is executed in reverse
01900 until the last decision point is reached. The essence of this technique
02000 was described by Floyd in [ref]. It has been used in numerous systems.
02200 The history list technique does not require CREATE CONTEXT to do
02300 anything but push the PC and a decision point signal onto the history
02400 list to catch failure. This is an attractive advantage. However, the
02500 technique has two flaws.
02700 One flaw is that if the same variable is changed many times in a loop
02800 within a single context, every change is recorded. None but the first
02900 change really needs to be recorded to provide for backup to the last
03000 decision point. The superfluous recording consumes both time and stack
03300 This flaw can be remedied by recording with each binding in the
03400 ALIST the unique number or "tag" of the context in which it was last
03500 changed. Each time it is changed, a check is made to see if it has
03600 already been saved in the current context. If so, it is not saved
03700 again, and the total cost of checking can amount to a single compare
03800 instruction. If not, the change is recorded on the history list and
03900 the tag recorded with the binding is updated.
04100 The remedy of the first flaw is the cause of the second flaw.
04200 Every bound variable (parametric, local, or global) and every atom
04300 property must contain an extra field to store the context tag.
04400 Unless this facility is built into the hardware or microprogrammed,
04500 the cost in both space and setup time is significant. However,
04600 the bulk of the cost involves the maintenance of high activity variables
04700 such as formal parameters and local variables. Low activity variables
04800 such as global variables and atom properties can demand extra maintenance
04900 without degrading overall performance significantly.
00100 Another technique is "incremental ALIST copying". When a context is
00200 created, instead of copying the entire ALIST, only a few (one or more)
00300 of the leftmost levels are copied, plus a link to the uncopied levels.
00400 If a failure occurs before all the copied function levels return,
00500 then it never becomes necessary to save the additional levels, and
00600 economy has indeed been achieved. However, if they all return and the
00700 link is reached, then a few more levels must be copied before proceeding.
00900 This scheme has two flaws. If an assignment is made to a free
01000 variable stored deep in the ALIST in the part that was not copied, then
01100 this condition must be detected and extra levels must be copied.
01200 Furthermore, assignments to global variables and atom property lists
01300 are not covered by the technique at all.
01500 The other flaw is that the ALIST copying can become a significant cost if
01600 it occurs frequently as compared with the frequency of changes to
01700 variables stored on the ALIST.
01900 All the flaws of both techniques are largely remedied by use of a mixed
02000 strategy developed by Enea and Smith for MLISP-2. Variables that can
02100 be accessed free ("special" variables in LISP 1.6 and MLISP2; "public"
02200 variables in LISP70) are not stored on the ALIST but elsewhere. Global
02300 variables and atom properties are not stored on the ALIST either. The
02400 history list technique is then used to record changes to these
02500 variables. This leaves on the ALIST only variables that can not be
02600 accessed free by functions ("private" variables in LISP70). These in
02700 fact tend to be the variables that change with high frequency. Thus,
02800 the incremental ALIST copying technique works well for them.