BACFORTH: AN APPROACH TO NEW CONTROL STRUCTURES M.L. Gassanenko St.Petersburg Institute for Informatics and Automation, St.Petersburg, Russia gml@gym.samson.spb.su BacFORTH is a Forth extension that supports backtracking. This paper describes its main control structures and an efficient technique of implementation of backtracking. 1. INTRODUCTION BacFORTH is a Forth extension that supports backtracking. It enables programmer to use both classical and PROLOG-like control structures. The author supposes that the reader is familiar with PROLOG or knows what is backtracking. 2. THE SIMPLEST IMPLEMENTATION OF BACKTRACKING The Forth address interpreter and threaded code are described elsewhere. We will consider two levels of the threaded code: a caller high-level procedure and a callee one (and therefore there is a caller threaded code fragment an a callee one). The top return stack item contains the address of residue of caller threaded code. The implementation of backtracking may be briefly described as following: 1) the residue of the caller procedure threaded code is called continuation; 2) a success is a call of the continuation; 3) a failure is a return from the continuation. (To perform failure a procedure compiled into the continuation should exit both its threaded code and the continuation threaded code). The word ENTER : ENTER >R ; \ remember that ; compiles EXIT calls the threaded code fragment taking its address from the stack. To call the residue of the caller threaded code the callee may execute the code R@ ENTER . To perform failure, i.e. exit the code fragment which called the procedure, the callee may perform the code RDROP EXIT . Note that since the top return stack item contains the address of continuation, exiting to this address is scarcely meaningful. For example: : 1-10 1 BEGIN DUP R@ ENTER 1+ DUP 11 = UNTIL DROP RDROP EXIT ; : X 1-10 . ; Execution of the word X will print numbers from 1 to 10. The phrases R@ ENTER and RDROP EXIT may be replaced by the words SUCC and FAIL which may be implemented as following: : succ compile r@ compile enter ; immediate : fail compile rdrop compile exit ; immediate and the above definition could look like this: : 1-20 1 begin dup succ 1+ dup 21 = until drop fail ; : //2 dup 2 mod 0= if succ else drop then fail ; : //3 dup 3 mod 0= if succ else drop then fail ; : xx 1-20 . ; : yy 1-20 //2 . ; : zz 1-20 //2 //3 . ; XX prints all numbers from 1 to 20, YY prints odd ones, ZZ prints ones that are divisible by 6. 3. STACK NOTATION A backtrackable procedure is described by four stack states: ( before-execution -> after-success ) ( after-failure <- returning-back ) Several notations are possible: ( before -> success / failure <- back ) ( before -> success -- back -> failure ) Each of the notations has its benefits. It is also convenient to use the notation ( before&after <-> success&back ) if the corresponding stack states are the same. 4. BACKTRACKING IN GENERAL CASE The technique described above cannot work if we use the return stack to hold temporary data. The use of one more stack to keep continuation addresses solves the problem. The new stack is called L-stack (stack of continuations) and accessed via the words >L L> L@ LP! LP@ LDROP. The success and prologue operators are defined like this: : CONT L> >R SUCC R> >L ; \ succes using L-stack : PRO \ PROLOG-like procedure prologue R> \ address of callee code R> >L \ address of continuation (caller code) ENTER \ execute the callee code LDROP \ remove the caller code address ; \ exit to what called the caller threaded code fragment, \ i.e. callee fails, which results in exit from caller code Using them, we may define 1-10 as follows: : 1-10 PRO \ rearrange return addresses 10 0 DO I CONT \ success with I on the stack LOOP ; \ exit the callee code fragment \ NB: control transfers inside PRO, to LDROP EXIT : X 1-10 . ; \ use it just as before 5. THE MAIN CONTROL STRUCTURES START ... DIVE ... EMERGE Recursive block. START and EMERGE denote the bounds, DIVE means recursive call. DIVE may be used from inside other structures and even several times. DIVE# calls the n-th enclosing block (counting them from 1). START EMERGE Equivalent to the use of an auxiliary colon definition: when executes, the address of is on the return stack. is followed by a compiled EXIT. START EMERGE BACK TRACKING Specifies what to do at backtracking time. Simply places the address of onto return stack. Both EMERGE and TRACKING compile EXITs after the enclosed code fragments. { | | ... } Block of alternatives. The same as PROLOG's "or". Executes alternatives, succeeds each time they succeed, then fails. The block places the address of its next alternative onto the return stack, and each alternative is followed by a compiled BRANCH. ONTRUE ( true -- ) ( false -- ; exit ) ONFALSE ( false -- ) ( true -- ; exit ) Probably most frequent operators. Exit the threaded code fragment (in this case we may say that the procedures fail) depending on the stack top. : ONFALSE IF FAIL THEN ; CUT: ... -CUT CUT: ... -NOCUT -CUT deletes all the backtracking information left after executing CUT: . -NOCUT deletes nothing and may be used as a pair for CUT: . Unpaired CUT: is a error which may lead to a reboot. NOT: ... -NOT "Negation as failure". Fails if the enclosed code succeeds, otherwise succeeds when it fails. 6. BACKTRACKABLE OPERATIONS There are backtrackable operations. Their names consist of a B prefix or postfix and a traditional Forth operation name. The prefix B means "backtrackable", the postfix B means "when backtracking". For example, : BSWAP ( a b <-> b a ) SWAP SUCC SWAP FAIL ; : SWAPB ( -> / b a <- a b ) SUCC SWAP FAIL ; 7. STATUS OF THE WORK Since 1989 the work was revised several times. Now it is clear which constructs are used often and which are rare. Although programming in BacFORTH requires some specific skills, the typical problems, solutions and methods are known by now. The BacFORTH technique was used in a number of projects. In some cases the use of BacFORTH technique allowed to greatly simplify the problem; in others it was just one of possible ways (but the easiest one) to the solution. By now the current BacFORTH implementation may be converted into a program product and interested people are invited to cooperate. -------------- Changes: 14.09.2000 Line 55 originally contained a typo and was DUP I R@ ENTER now it is DUP R@ ENTER -- thanks to Xiao Zhen