Article: 29302 of comp.lang.forth Path: osiris.wu-wien.ac.at!03-newsfeed.univie.ac.at!news.tuwien.ac.at!a0.complang.tuwien.ac.at!anton From: anton@a0.complang.tuwien.ac.at (Anton Ertl) Newsgroups: comp.lang.forth Subject: Backtracking in ANS Forth (Was: Manipulating Return Addresses) Date: 20 Aug 1996 11:59:31 GMT Organization: Institut fuer Computersprachen, Technische Universitaet Wien Lines: 132 Distribution: world Message-ID: <4vc9b3$b10@news.tuwien.ac.at> References: <320B3C25.6E4C@austin.finnigan.com> <320F1536.38E8@forth.com> <320FD2B3.522A@ix.netcom.com> <32132C17.5EAA@ix.netcom.com> NNTP-Posting-Host: a0.complang.tuwien.ac.at Let me first present the problem in a simplified context: Assume that ONE-or-TWO ( -- n ) can deliver two solutions: on calling it, it delivers 1; when backtracking into it, it succeeds again, delivering 2; then it fails on backtracking. The word FAIL always fails. Let's define : foo \ always fails ONE-or-TWO . FAIL ; Calling foo prints 1, then it prints 2, the fails. How can we implement this? I will use THROW to implement FAIL, but this does not work with calls and returns as we know them. So we have to use a different implementation of calling and EXITing. The trouble for backtracking is the EXIT, so let's make it explicit (if you ever see "continuation-passing style", that's what this is about). We have to make the return information explicit; in Forth (without locals), this is just the return stack. Let's implement it as linked list; a return address is represented as xt: : push-return ( ret-stack1 ret-addr -- ret-stack2 ) 2 cells allocate throw swap over cell+ ! swap over ! ; : pop-return ( ret-satck1 -- ret-stack2 ret-addr ) dup cell+ @ swap @ ; : return ( ret-stack1 -- ret-stack2 ) \ never EXITs; stack-effect with respect to the word returned to. pop-return execute ; This, of course, requires some transformations of the programs that should use this explicit return mechanism. E.g., : bar ( ... -- ... ) PRIM1 DEF1 PRIM2 PRIM3 ; becomes : bar-part2 ( ... ret-stack1 -- ... ret-stack2 ) >r PRIM2 PRIM3 r> return ; : bar ( ... ret-stack1 -- ... ret-stack2 ) \ does not EXIT; stack-effect with respect to "return"ing >r PRIM1 ['] bar-part2 r> push-return DEF1 \ def1 never EXITs, so no return is necessary ; This does not look pretty (and with control structures it's even worse), but the transformation can be done automatically. It also leaks memory, but in the context of backtracking we could use a memory management mechanism (instead of allocate) that reclaims memory on failure. Moreover, all these never returning definitions and EXECUTEs could overflow the return stack; but they are tail calls, so the Forth system can use tail call optimization. Let's get back to backtracking. : choice \ works like return ( ret-stack1 -- ret-stack2 ), but creates a choicepoint \ i.e., it catches a failure; \ EXITs upon failure with stack effect ( ret-stack -- ) pop-return CATCH dup 1 <> if \ it's not a failure, but something else THROW then drop ; Here's how FAIL and ONE-or-TWO could be implemented: : FAIL \ neither EXITs nor returns 1 THROW ; : ONE-or-TWO ( ret-stack1 -- n ret-stack2 ) >r 1 r@ choice 2 r> return ; It should be helpful to remember that choice behaves like return, except that it will catch a failure, upon which it will EXIT and continue with the rest of ONE-or-TWO. We have to convert foo to use the explicit return mechanism: \ original: \ : foo \ always fails \ ONE-or-TWO . FAIL ; : foo-part2 ( ret-stack -- ... ) \ never EXITs, never returns \ we can treat "." as primitive here; it does not do choicepoints, failure etc. >r . FAIL ; : foo ( ret-stack -- ... ) \ never EXITs, never returns ['] foo-part2 swap push-ret ONE-OR-TWO ; Now we just need a wrapper to get into and out of the return/backtracking execution mode: : success-throw \ get out of the return/backtracking mode 2 throw ; : wrapper ( xt -- ) \ execute xt in return/backtrackin mode ['] success-throw 0 push-return swap catch case 1 of ." failure" endof 2 of ." success" endof throw endcase ; and we can call foo thus: ' foo wrapper So: it's ugly, but it's ANS Forth. I'm sure you can find ways to make it syntactically more pleasant. In applications such as FOSM, it may even be possible to hide the mechanism completely. - anton -- M. Anton Ertl Some things have to be seen to be believed anton@mips.complang.tuwien.ac.at Most things have to be believed to be seen http://www.complang.tuwien.ac.at/anton/home.html