Enhancing the Capabilities of Backtracking M.L.Gassananko St.Petersburg, Russia mlg@iias.spb.su Abstract The technique of backtracking enables one to create abstract iterator and filter modules responsible for looking over sets of all possible values and rejecting "undue" ones. Loops controlled by backtrackable iterators are often very convenient, and there are no problems if the loop body uses no backtracking, but there is a severe restriction if the body does use backtracking: the iterator can generate a new value only after the body fails. This paper introduces a generalization of backtracking: a loop-like control structure that eliminates this restriction. A backtrackable procedure is used in it as an iterator that controls repeating execution of a backtrackable body; control is transferred to the iterator when the loop body succeeds (and not when it fails). 1 Introduction 1.1 Backtracking Backtracking was introduced into the Prolog[Hog84,Ste86] and Planner[Pil83] languages as a means of automatic theorem proving. In addition, it turned out that backtracking is a convenient technique of programming processes of looking through sets of values. It enables one to write loops following the basic pattern: --> --> ... --> --> which resembles a dataflow diagram. The generator (iterator) yields values one by one, a filter either passes a value (and control) on, or discards the value and returns control to the generator; when finishes processing of the value, control backtracks to the generator (it goes back through the filters which do not terminate backtracking). Thus, control may be transferred either "forwards" or "backwards". A forwards control transfer is called a success, and a backwards control transfer is called a failure. When a backtrackable procedure succeeds, it leaves a return point on a special stack. The return point contains information necessary to resume execution of the procedure when control backtracks to it. If procedure cannot generate more values, etc., and has no reasons to succeed, it fails. On failure, control backtracks to the return point most recently established. "Normal" return is considered as a success without establishing a return point. The return points and other information left on the return stack by a procedure when it succeeds we shall call the trace of the procedure. Using two generators in the form: --> --> ... one can generate all possible pairs of values. (Prolog uses this technique to perform exhaustive search among the paths that might lead to solutions; control reaches when a solution is found.) 1.2 Implementation of Bactracking in BacFORTH One of possible methods of implementation of backtracking is "success as a call of continuation". That is, the syntax --> --> is implemented like following: uses a call to pass control to , uses a return to pass control back; in just the same way uses a call to pass control to which uses a return to pass control back to . As mentioned above, produces a new value only when processing of the previous one is completed, that is, when control returns to . To understand implementation details, one has to consider two levels of code: the code of caller procedure and the code of callee procedure. When a Forth procedure is called, the address of residue of caller's code is placed onto the return stack; this address of caller's code residue is the continuation. To perform success, the callee procedure calls this residue of the caller's code. The word ENTER : ENTER >R ; ( addr -- ; control transfer ; R: -- addr' ) calls the code fragment taking its address off the data stack. The code fragment R@ ENTER copies the address of residue of caller's code onto the data stack, and calls it, thus performing the call of continuation, or success. A failure is implemented as a return from the continuation (to the procedure that performed success, i.e. to the callee). This happens when execution encounters an EXIT in caller's code or when a procedure compiled into the caller's code executes code RDROP EXIT (RDROP removes the continuation (caller's code) address from the return stack, and EXIT returns control to the procedure that called the caller's code). In other words, the first callee procedure calls the residue of caller's code, which calls the second callee procedure. To perform a failure, the second callee performs "exit from two levels", back into the first callee. Thus, the history stack is the return stack, and the history (trace) consists of return addresses to procedures that have performed success and which execution is therefore suspended. Unfortunately, we cannot define a backtrackable procedure via other backtrackable procedures as an ordinary colon definition because we will discover that the return address contains backtracking information rather than the continuation address. Therefore we have to introduce a new stack (continuation stack, or L-stack) intended to hold continuation addresses of backtrackable procedures. The word PRO (Prolog-like procedure prologue), usually the first word in a procedure, moves the continuation address to the L-stack and performs a failure of the procedure when control backtracks to the word PRO. The word CONT performs a success of the procedure using the continuation address on the L-stack. A definition of a new backtrackable word looks like : PRO CONT ; BacFORTH includes a number of unstandard control structures; in this paper we will need the block of alternatives: { | | ... | } This is analgous to the Prolog-style "OR": each time any of the alternatives succeeds, the whole construct succeeds; when control backtracks into the block, it transfers to the last return point established by the current alternative, or (if there is no such return point or the alternative fails) to the next alternative. The block fails when the last alternative fails. 1.3 Strengths and Weaknesses of Classical Backtracking Procedures that use backtracking enable us to encapsulate knowledge about methods of looking through sets of values into single iterator modules with a simple and uniform interface, i.e. they can be "modules, expressing the idea of loop"[Tse90]. The code that uses iterators and filters is very readable and resembles a dataflow diagram. A BacFORTH loop may look like: or: ... For example, the following definition prints the stack contents: : S. STACK . ; The iterator STACK copies the stack elements onto the top one by one; the word . prints these elements. The word EXIT compiled by ; makes the control backtrack when the element is printed. The iterators may be reused, for example: : SU. STACK U. ; prints the stack elements as unsigned numbers. The second example illustrates how the block of alternatives works. The word TEST1: : TEST1 { 1 | 2 | 27 | 5 } . ; prints "1 2 27 5 ". The alternatives leave these numbers on the stack, and the word . prints them (here each of the alternatives is code that leaves a number on the stack; when a number is left on the stack, the block of alternatives succeeds and the word . executes; then the EXIT compiled by the word ; returns control into the block, where the next alternative receives control). The same iterator may be written as a separate word: : VALUES PRO { 1 | 2 | 27 | 5 } CONT ; : TEST2 VALUES . ; Note that the latter definition looks almost as a definition which prints only one value: : TEST0 5 . ; So, it is natural to consider backtrackable procedures as candidates to be a standard, universal representation for ideas of looking through and checking. It is very convenient to assign one of the following meanings to backtracking: the backwards control transfer may mean either that (1) the current value is rejected, and any steps taken while processing it must be undone, or that (2) processing of the current value is completed, and iterator must generate the next one. The problem with backtracking is that we can use backtracking in either way, but not in both at the same time. Therefore, iterators are not universal so far. If we follow the abovementioned pattern, cannot receive control again when succeeds, it receives control only when fails. There are cases when a backtrackable iterator cannot control a backtrackable body, and in these cases we loose the merits of employing iterators (although backtracking does add expressive power to the language, since there are no problems if does not use backtracking). One of the problems where the expressing power of classical backtracking is not enough is the following: given an oriented graph, generate all its spanning trees (they include all nodes of the original graph and their edges are edges of the graph). The algorithm (in backtracking form) looks like following: (repeatedly) select a root node (*) --> let the current tree consist of only the root node; (repeatedly) select an edge adjacent to one of the current tree nodes (**) ==> either add it (***) (and its second node) to the current tree or do not add it to the current tree (****); (when there are no more such edges) if the current tree includes all nodes of the graph, then the current tree is a spanning tree, print it; backtrack to find another tree. (*) We select a root node and apply the rest of the algorithm to it; when this is done (i.e. when control "backtracks"), we select another node as the root and apply the rest of the algorithm to it, and so on. (**) Select an edge and perform the following double-indented part for it, then again select an edge, and so on. Note that the set of the edges that may be selected changes as the current tree changes. (***) This alternative cannot be performed if the node is already added to the current tree. (****) To generate a tree we need to execute only one of the alternatives for an edge; since we generate all possible trees, both alternatives are tried for each edge, first time the first one, second time (when control backtracks) the second one. Unfortunately, although we can easily create an iterator that "repeatedly selects an edge adjacent to one of the current tree nodes", we cannot use it there: an iterator can generate a new value when control backtracks to it, but we are planning to backtrack when we have "to find another tree", i.e. to change the decisions about adding or not adding edges to the tree, and therefore we cannot initiate backtracking to let the iterator generate a new value. In other words, in the above example it would be natural to use an iterator, but it is not technically possible unless we extend the execution scheme. It is important to mention why we do not want to use auxiliary data and control structures to implement processing in the desired order (remember that FORTRAN used to force programmers to follow this approach and rewrite recursive algorithms in an iterative form): this adds one more level of complexity between our understanding of the problem and the source code. When we extend the execution scheme, we hide complexity there, below the level of source code. This kind of complexity gives us power, and not only requires our efforts, because the power prowided by the complexity exists when we write or read the application source code. Such complexity requires efforts to create, debug, learn and maintain it, but when we work on the application problem, this complexity becomes power. With the early FORTRAN approach, complexity becomes power only when we run the code. Below we present a control structure that removes the restriction mentioned above and enables backtrackable iterators to serve as an universal representation of algorithms of looking through a set of variants. 2 Passing control to iterator when loop body succeeds The structure looks like following: AMONG EACH ITERATE As usual, generates some values, but the structure returns control to it when succeeds, i.e. when the value is successfully processed. When fails, the state of gets restored. So, if fails rejecting the value, does not receive control. The first example on the AMONG construct illustrates the fact that in the case that performs reversal actions when backtracking, the --> scheme tries the values alternatively, while the AMONG structure tries them sequentially. : from1to4 PRO { 1 | 2 | 3 | 4 } CONT ; \ an iterator : B. PRO ( N -> / <- ) \ print 2 times DUP . >R CONT \ print the number, succeed R> . ; \ print it once more when backtracking : X from1to4 B. ." # " ; : Y AMONG from1to4 EACH B. ITERATE ." # " ; The procedure X prints: 1 # 1 2 # 2 3 # 3 4 # 4 while the procedure Y prints: 1 2 3 4 # 4 3 2 1 (each value is printed first time when control passes "forwards", and the second time when control backtracks; '#' gets printed immediately before initiation of backtracking). Let us give one more illustration: a program which prints out the subsets of the { 1, 2, 5 } set. Its algorithm looks like following (if we try all combinations of choices, we shall generate all possible subsets): let the current set be empty (*) (repeatedly) yield an element of the original set (**) ==> either let the element be added to the current set (***) or do not add it to the current set (****); (when there are no more such elements) print the current set (*****); backtrack to generate a new subset (reject the current set). (*) In this simple program we use the data stack to hold the elements of the current set, so, initially the data stack must be empty. (**) Leave it on the data stack. (***) Just do nothing and leave it on the data stack. (****) Remove it from the data stack. (*****) That is, print the contents of the data stack. : (S.) ( x*n -- x*n ) \ print out the stack elements STACK . ; : SUBSETS AMONG { 1 | 2 | 5 } \ an iterator that leaves \ the set elements on the stack EACH { \ either leave the element (tried first) | DROP \ or remove it (tried when control backtracks) } ITERATE \ ITERATE lets the iterator run again \ now stack contains the next subset ." { " (S.) ." } " \ print the stack contents as a set ; The word SUBSETS prints: { 1 2 5 } { 1 2 } { 1 5 } { 1 } { 2 5 } { 2 } { 5 } { } Now let us describe how the AMONG construct works. When it receives control, is initiated, it generates its first value and succeeds. The return stack contains 's trace, which determines the state of (the state of must be wholely determined by the trace, since only that trace gets restored automatically). Then control passes to . When succeeds, the return stack trace gets copied onto the return stack top. After that a failure is simulated, and control backtracks to . It generates a new value, it gets processed by , and so on. When fails, control backtracks not to the iterator but to the last return point established by at the previous iteration, and the state of gets restored (actually, a copy of trace that represents the previous iterator state holds on the return stack, and all we need to make it the current one is to restore the pointers). When failure is performed at the first iteration, the whole construct fails. Note that we can (and do) return to previous iterations by means of backtracking. When iterator cannot generate more values, it fails, and control transfers to . When fail, control will return to the latest return point established by (and execution of body will be resumed). Thus, the iterator is a process, its state is determined by its trace, which is held at the return stack. When we need to run one more time, we copy the process (i.e. its trace) and pass control to the new copy. When control backtracks from , we restore the state of and do not pass control to it. Note that runs "in a separate time": control backtracks to it when succeeds, and 's time is backtrackable: the state of gets restored when fails. When succeeds, receives control to process the next value, and when fails, the AMONG structure succeeds. The iterators that depend on external data structures (i.e. those which state is not wholely defined by the trace) may be found useful as well. An iterator over the elements of a queue to which body adds new elements may serve as a reasonable example. 3 Notes on Implementation and Compatibility with Cut Statements Our current implementation requires an ANS Forth [ANS93] system with the following additional requirements: the return stack is allocated within the data memory space, the words RP@ ( -- addr ) and RP! ( addr -- ) provide access to the return stack pointer. Return adresses have the same representation as data addresses, the inner interpreter places them on the return stack and a program may change them. The system includes a number of words that provide access to the generated code: TOKEN+ ( code-addr -- code-addr' ), REF@ ( orig -- dest ), REF+ ( orig -- code-addr ), the Forth-83 >MARK and >RESOLVE . L-stack contains iterator's trace start and end pointers, which imposes some restrictions on the use of L-stack inside the AMONG structure. The standard DO loop posesses the same property with respect to the return stack. The technique of copying the return stack fragments imposes additional requirements on the implementations of cut statements. There are two cut constructs in BacFORTH, and we had to modify implementations of both. The first variation of cut statement, "structured cut", looks like following (the brackets are a punctuation mark and signify that enclosed part may be omitted): CUT: ... -[NO]CUT The word CUT: marks the beginning of the fragment which return points must be deleted; -CUT deletes the return point established after that mark. -NOCUT is a pair for CUT: to be used in case when it turns out that return points must not be deleted. In other words, the CUT: ... -CUT structure prevents control from returning to the code inside this structure. In the following example: : numbers ( --> n ) ( <-- ) \ yield the numbers below PRO { 0 | 2 | 3 | 4 | 5 | 7 } CONT ; : ?odd ( n --> n ) ( <-- ) PRO \ backtrack if n is even DUP 2 MOD IF CONT ELSE DROP THEN ; : .ALL-NUMBERS numbers . ; : .ODD-NUMBERS numbers ?odd . ; : .1ST_ODD CUT: numbers ?odd -CUT . ; the word .ALL-NUMBERS prints "0 2 3 4 5 7 ", the word .ODD-NUMBERS prints "3 5 7 ", and the word .1ST_ODD prints "3 ". The "deferred cut" structure looks like following: CUT: ... [NO]CUT< ... [NO]CUT! ... >CUT It enables one first to mark the code fragment which return points must be deleted (by the words CUT: and CUT< ) and later to decide whether to delete the trace or not (by words NOCUT! and CUT! ); the word >CUT closes the structure. In other words, it enables us to mark a fragment of code first, and later to decide whether or not control is allowed to backtrack into it. In addition to these, the AMONG construct itself contains a "built-in" cut statement that deletes the trace of iterator when control backtracks from body. The technique of copying return stack fragments required their relocatability. The return stack fragments may contain absolute addresses of threaded code fragments, but may not contain absolute addresses of return stack fragments. The BacFORTH implementations of cut statements were modified to fit these new requirements. For example, the "structured cut" was rewritten to be: : CUT: \ mark the beginning of the fragment to cut R> RP@ >L \ copy r-stack top addr. to L-stack BACK LDROP TRACKING \ delete this mark when backtracking >R ; : -CUT R> L> RP! >R ; \ delete return points upto the marked addr. : -NOCUT \ remove the mark, but not the return points R> L> RP@ - >R \ keep the mark as a relative address BACK R> RP@ + >L TRACKING \ restore it when backtracking >R ; 4 Discussion The AMONG construct follows the same direction as almost all enhancements of programming languages do: to let program units reflect the concepts of the application area, and to enable the code interpreter to cope with them. The AMONG construct allows backtrackable iterators to serve as an universal representation of ideas of looking through a set of values. When we use backtrackable iterators as an universal representation of ideas of looking through some values, in a system that lacks a construct like AMONG there's a certain risk since there are some cases in which a backtrackable procedure cannot control a backtrackable body. Introduction of the AMONG structure removes this restriction. The AMONG construct does not automatically entail more efficient execution or discovering new classes of algorithms. It adds a new notion to our system of notions, and therefore enables us to make some complex programs and algorithms simpler (to think about, to program, to debug, to read, to understand). It enables us to arrange algorithm elements in a more natural, more understandable manner. It is a tool that enables us to be more efficient. Among practically important problems for which the AMONG construct is useful, mention can be made of the problem of finding the spanning trees of a graph. Such problems as reconstruction of syntactic structure of a sentence in Russian, given the morphological information, can be considered as variations of this problem. Both "deferred cut" and the AMONG construct turned out to be very useful in rapid prototyping: at this stage it is preferrable to have more powerful means than the minimal sufficient set remaining in the final version. The first, prototype, version of the program may be inefficient, but once it exists, we can reason not only about the problem, but about the solution as well, and can move towards more efficient versions. The presence of AMONG construct enables one to implement all ideas of loops (all looking-through modules) as backtrackable iterators, concentrating the attention on the problem itself rather than on the applicability issues; it removes the risk that all necessary notions will be implemented, but the implementations will not be compatible. So, it speeds up the development even if it is not used at all, or if subsequent analysis will show that it is inadequate to the problem and the goals can be accomplished by means of less powerful structures. The "deferred cut" statement provides a conveniens basement for creation of problem-oriented "macrocommand" selective cut statements (useful e.g. in syntax parsing). In addition, it enables one to prevent redesigning of already implemented solutions when it turns out that the problem does not exactly fit into the selected general scheme. There are no reasons to avoid these constructs in the final software, if they are adequate to the problem. But in rapid prototyping we can solve our problems by inadequately powerful means. We also can recommend not to use AMONG when has only one alternative. If has several alternatives, the return stack space needed to keep the copies of 's trace grows as the logarithm of the number of examined choices (and time), which is acceptable. If has only one alternative, the return stack space demands grow linearly, which may be acceptable only if the number of processed values is limited. The AMONG construct may be considered as an implementation of the universal quantifier: if procedure M yields values x from the set M, and procedure P tests predicate P(x), then AMONG M EACH P ITERATE implements checking of the condition "for_all x in M P(x)" (although there are more efficient methods for a mere check). In systems that employ backtrackable iterators it is convenient to implement checks as filter procedures, that succeed if condition is met and fail otherwise. Once called, a filter succeeds only once; it can establish return points, but it does not succeed again when control backtracks to it. The syntax resembles a dataflow diagram: It is of interest that such filters also can be used in the AMONG structure: AMONG EACH ITERATE If fails, the construct succeeds immediately; otherwise are performed (after which control backtracks to , the filter fails and the construct succeeds). A feature of this construct is that control backtracks to filter when succeeed. A backtrackable iterator procedure is a process which alternately gets postponed (to process generated data) and resumed (to generate new data). The method of copying the process state enables us to run the iterator when the loop body succeeds and to restore the process state when the body fails. 5 Conclusion The technique of backtracking allows us to incapsulate knowledge about algorithms of looking through a set of values into single iterator modules. This is very convenient, but there's a restriction on the use of backtracking inside the body of a loop controlled by such iterator (although there are no problems if backtracking is not used inside it). The AMONG construct removes this restriction and enables one to use backtrackable iterator procedures as an universal means of representation of looking-through algorithms. In addition, it turned out that the means like "deferred cut" and the AMONG construct speed up prototyping even if these super-powerful means do not remain in the final version. [ANS93] American National Standard for Information Systems --- Programming Languages --- Forth. --- American National Standard Institute, Inc., 1993. --- 212 p. [Hog84] Hogger J. Introduction to Logic Programming. Academic Press,Inc.:London,1984. [Pil83] Pilschikoff V.N. The PLANNER Language. Nauka:Moscow, 1983. (in Russian). [Ste86] Sterling L.,Shapiro E. The Art of Prolog. Advanced Programming Techniques. The MIT Press, Cambridge,1986. [Gas94] Gassanenko, M.L. BacFORTH: an Approach to New Control Structures.//Proceedings of the EuroForth'94 Conference, 4-6 November 1994, Royal Hotel, Winchester. --- p. 39--43. [Gas93R] Gassanenko M.L. Novye sintaksicheskie konstruktsii i b‚ktreking dlya jazyka Fort.//Problemy tehnologii programmirovaniya - SPb: SPIIRAN, 1993, p.148-162. (New Control Structures and Backtracking for the Forth Language, in Russian.) [Tse90] Tseytin G.S. Na puti k sborochnomu programmirovaniyu.// Programmirovanie, 1990, N 1, p. 78-92. (Towards programming via assembly from modules, in Russian.)