Backtracking Forth
Samuel A. Falvo II
under Windows. Bar none, it's the smallest assembler I've ever
written. I used "continuations" in it for the purposes of enhancing
readability, not strictly because I had to. For example:
: (CONTINUE) >R ;
: YIELD ( -- ) POSTPONE R@ POSTPONE (CONTINUE) ; IMMEDIATE
: ForEachOpcode: ( -- )
0 BEGIN DUP Opcodes/Word < WHILE
DUP CELLS PendingOpcodes + @ YIELD
1+
REPEAT DROP R> DROP ;
: BuildInstructionWord ( -- )
ForEachOpcode: ( opc -- )
4* Instruction @ 32* OR Instruction ! ;
: DumpAssembledOpcodes ( -- )
ForEachOpcode:
." Opcode " . CR ;
I find that this technique really works quite well for me, and allows
me to use the ForEachOpcode: iterator in multiple places without any
difficulty, really cutting back on code size. To be honest, I can't
figure out why I didn't do this sooner.
At any rate, this reminded me of a document I've seen by M. L.
Gassanenko (http://www.forth.org.ru/~mlg/ef94/ef94-2-paper.txt), where
I admit my iterators are inspired from, where he describes various
other structures using these "continuations" to implement Prolog-like
capabilities in his Forth software.
The first half of the document is reasonably clear; however, the
second half, starting at the START/DIVE/EMERGE section, is utterly
undecipherable to me. Their operation is described only at the
absolute highest level, with no supporting example code to help
demonstrate how they'd be used.
I was wondering if someone familiar with his work, or if ~mlg still
reads this newsgroup :), could be kind enough to help clarify and/or
give examples of how the alternative control structures are actually
implemented and how they'd be used.
Thanks. :)
--
Samuel A. Falvo II
Michael L.Gassanenko
Try to read http://www.forth.org.ru/~mlg/BacFORTH-88/BF-diplom.html (Forth is Forth),
and probably translate it with http://www.translate.ru
By example:
: _foo do-this RECURSE do-that ;
: foo prepare _foo wind-up ;
vs
: foo prepare START do-this DIVE do-that EMERGE wind-up ;
DIVE is a call of the code within the START...EMERGE block.
And when you need an auxiliary definition:
: x'es ... BEGIN ... SUCC ... REPEAT ... FAIL ;
: _foo x'es process-them ;
: foo prepare _foo wind-up ;
vs
: x'es ... SUCC ... FAIL ;
: foo prepare START x'es process-them EMERGE wind-up ;
It's a bit late now, I will be able to tell you more tomorrow.
But the ability to use iterators as modules that express ideas of
loops is the most valuable thing.
(NB: condition checking == loop that executes 0 or 1 times)
I rarely use RECURSE and rarely use DIVE -- most likely because
I can use backtracking when I need something complex.
PS
\ -----------------------------------------------------------
( START ... EMERGE , BACK ... TRACKING 22/03/93 )
\ : (CALL) RR@ REF+ >RR< REF@ >RR ;
\ : (START) RR@ REF@ >RR< REF+ >RR ;
: START ?COMP POSTPONE (START) >MARK <MARK 201 ; IMMEDIATE
: EMERGE ?COMP 201 ?PAIRS 2DROP POSTPONE EXIT >RESOLVE ; IMMEDIATE
: BACK ?COMP POSTPONE (CALL) >MARK 202 ; IMMEDIATE
: TRACKING ?COMP 202 ?PAIRS POSTPONE EXIT >RESOLVE ; IMMEDIATE
\ -----------------------------------------------------------
\ DIVE 26.09.2000
\ ищем #-ый набор ( forward backward 201 ),
\ при этом addr после (START)
: (DIVE#) ( an .. a1 # --> an a1 )
DEPTH 5 > IF
DEPTH 5 - 1+ 1 DO
( an .. a1 # ) CASE
I PICK 201 = IF
I 1+ PICK backward = IF
I 3 + PICK forward = IF
I 2 + PICK I 4 + 1+ PICK REF+ = IF
I 4 + PICK REF- TOKEN@ ['] (START) = IF
1- DUP 0= IF \ # -- счетчик
DROP ( одно значение сброшено!)
COMPILE (CALL)
I 1+ PICK ( это значение номер i+2 )
I 1+ PICK ( это значение номер i+1 )
<RESOLVE
UNLOOP EXIT ESAC LOOP THEN
1 ABORT" more than nesting level" ;
: DIVE ?COMP 1 (DIVE#) ; IMMEDIATE
: DIVE# ( "n" -- )
?COMP
S$GETWORD S$NUMBER? -1 <> ABORT" single number expected"
D>S (DIVE#)
; IMMEDIATE
\ DIVE# n calls the n-th enclosing block.
\ DIVE# 1 is equivalent to DIVE .
\ -----------------------------------------------------------
\ Блок альтернатив 22/03/93; 28.09.2000
: {| ?COMP 204 POSTPONE (START) >MARK 203 ; IMMEDIATE
: || ?COMP 203 ?PAIRS POSTPONE BRANCH >MARK CS-SWAP 205 -ROT
>RESOLVE POSTPONE (START) >MARK 203 ; IMMEDIATE
: |} ?COMP 203 ?PAIRS POSTPONE BRANCH >MARK CS-SWAP 205 -ROT
>RESOLVE POSTPONE EXIT
BEGIN DUP 204 - WHILE
205 ?PAIRS >RESOLVE REPEAT
DROP ; IMMEDIATE
PPS
Prolog-like or:
: foo {| 1 || 2 || 4 |} . ;
will print "1 2 4 "
Michael L.Gassanenko
ECHOING ON
: x'es PRO {| 1 || 10 || 100 || 1000 |} CONT ;
: t1 x'es . ;
t1
: t2 ." the x'es are: " START x'es . EMERGE ." that's all! " ;
: .sum-of-x'es 0 START x'es + EMERGE . ;
.sum-of-x'es
t2
: t3 BACK ." that's all! " TRACKING ." the x'es are: " x'es . ;
t3
: in-brackets PRO ." [ " BACK ." ] " TRACKING CONT ;
: t4 x'es in-brackets . ;
t4
: t5 x'es ." [ " BACK ." ] " TRACKING . ;
t5
: in_brackets R> ." [ " BACK ." ] " TRACKING >R ;
: t6 x'es in_brackets . ;
t6
outputs
: x'es PRO {| 1 || 10 || 100 || 1000 |} CONT ;
: t1 x'es . ;
t1
1 10 100 1000
: t2 ." the x'es are: " START x'es . EMERGE ." that's all! " ;
: .sum-of-x'es 0 START x'es + EMERGE . ;
.sum-of-x'es
1111
t2
the x'es are: 1 10 100 1000 that's all!
: t3 BACK ." that's all! " TRACKING ." the x'es are: " x'es . ;
t3
the x'es are: 1 10 100 1000 that's all!
: in-brackets PRO ." [ " BACK ." ] " TRACKING CONT ;
: t4 x'es in-brackets . ;
t4
[ 1 ] [ 10 ] [ 100 ] [ 1000 ]
: t5 x'es ." [ " BACK ." ] " TRACKING . ;
t5
[ 1 ] [ 10 ] [ 100 ] [ 1000 ]
: in_brackets R> ." [ " BACK ." ] " TRACKING >R ;
: t6 x'es in_brackets . ;
t6
[ 1 ] [ 10 ] [ 100 ] [ 1000 ]
Samuel A. Falvo II
> Try to read http://www.forth.org.ru/~mlg/BacFORTH-88/BF-diplom.html (Forth is Forth),
> and probably translate it with http://www.translate.ru
The translation with http://www.translate.ru failed. All it produced
was an HTTP header and a broken META tag. :) And although the Forth
is Forth, I work best reading the documentation content in conjuction
with the source code, and not the source code to exclusion. (I think
it might have broke because of the size of the document. :))
I'll try Babelfish on AltaVista to see if I get better results.
> : _foo do-this RECURSE do-that ;
> : foo prepare _foo wind-up ;
>
> vs
>
> : foo prepare START do-this DIVE do-that EMERGE wind-up ;
Ah, this now makes much more sense to me. Thank you! :)
> And when you need an auxiliary definition:
>
> : x'es ... BEGIN ... SUCC ... REPEAT ... FAIL ;
> : _foo x'es process-them ;
> : foo prepare _foo wind-up ;
>
> vs
>
> : x'es ... SUCC ... FAIL ;
> : foo prepare START x'es process-them EMERGE wind-up ;
This also makes some more sense, but is it possible to give a more
concrete example? I would suspect that x'es would still need its
BEGIN...REPEAT structure for iteration?
I take it that START and EMERGE are used to delineate the scope of a
continuation, then. This is good to know, since right now, I have a
few auxiliary words defined, where I wish I could have done something
like START and EMERGE above.
> But the ability to use iterators as modules that express ideas of
> loops is the most valuable thing.
Yes, I find that this is a *very* powerful concept in a language like
Forth. I am very pleased with the results I've seen thus far, and am
eager to learn more of the backtracking techniques.
> I rarely use RECURSE and rarely use DIVE -- most likely because
> I can use backtracking when I need something complex.
>
> PS
>
> \ -----------------------------------------------------------
> ( START ... EMERGE , BACK ... TRACKING 22/03/93 )
Thanks for listing the code. Many things escape me, however, such as
what REF+, >RR<, >MARK, <MARK, and other similar words do. I was kind
of hoping to learn the rationale for these words in the document's
text.
Samuel A. Falvo II
> : x'es PRO {| 1 || 10 || 100 || 1000 |} CONT ;
> : t1 x'es . ;
> t1
> 1 10 100 1000
Ahhh.... I am seeing more clearly now.
> : t2 ." the x'es are: " START x'es . EMERGE ." that's all! " ;
> : .sum-of-x'es 0 START x'es + EMERGE . ;
> .sum-of-x'es
> 1111
> t2
> the x'es are: 1 10 100 1000 that's all!
OK, this is as I'd expect, based on the previous message I replied to.
> : t3 BACK ." that's all! " TRACKING ." the x'es are: " x'es . ;
> t3
> the x'es are: 1 10 100 1000 that's all!
Expressed with the above example, it's very counter-intuitive, and
seems to have little to no applicability. However, ...
> : in-brackets PRO ." [ " BACK ." ] " TRACKING CONT ;
> : t4 x'es in-brackets . ;
> t4
> [ 1 ] [ 10 ] [ 100 ] [ 1000 ]
..., this is a thing of pure beauty. This has great application with
respect to text formatting applications, which just so happens to be
one of my primary needs for my job.
> : t5 x'es ." [ " BACK ." ] " TRACKING . ;
> t5
> [ 1 ] [ 10 ] [ 100 ] [ 1000 ]
A condensation of the above...
> : in_brackets R> ." [ " BACK ." ] " TRACKING >R ;
> : t6 x'es in_brackets . ;
> t6
> [ 1 ] [ 10 ] [ 100 ] [ 1000 ]
Example of caching a value on the return stack for use with the body
of the continuation.
I think I see a bit more clearly how these things can be used in a
Forth environment. Thanks for the examples and their results. It
helps out greatly!! :)
Samuel A. Falvo II
> The translation with http://www.translate.ru failed. All it produced
> was an HTTP header and a broken META tag. :) And although the Forth
> is Forth, I work best reading the documentation content in conjuction
> with the source code, and not the source code to exclusion. (I think
> it might have broke because of the size of the document. :))
Oops -- never mind! :) With the help of a fellow Russian co-worker,
I was able to get it translated. Thanks!
jb...@mountpoint.nl
> Oops -- never mind! :) With the help of a fellow Russian co-worker,
> I was able to get it translated. Thanks!
Perhaps you can post it? I'm also interested.
--
Cheers,
Jan Bernard
Samuel A. Falvo II
> sfa...@hifn.com (Samuel A. Falvo II) writes:
>
> > Oops -- never mind! :) With the help of a fellow Russian co-worker,
> > I was able to get it translated. Thanks!
>
> Perhaps you can post it? I'm also interested.
I can post my document only with permission; however, I lack webspace
to post it on. However, going to http://www.translate.ru and having
them translate the page (note: it can potentially time out on you,
like it did for me). There is also a lot of Russian words that aren't
translated, which I've later come to realize are really English words
spelt phonetically using Cyrillic characters. Even so, there are some
words which neither I nor my co-worker can translate, as the context
is lost through translation.
But most of it comes through pretty well, if you are patient with the
translation website.
BTW: Don't bother translating with Babelfish -- they just crap out (it
times out on the server). Babelfish is optimized for translating
webpages that are short and interactive; translate.ru appears to be
more for technical publications and other "long" documents.
Michael L.Gassanenko
>
> > sfa...@hifn.com (Samuel A. Falvo II) writes:
> >
> > > Oops -- never mind! :) With the help of a fellow Russian co-worker,
> > > I was able to get it translated. Thanks!
> >
> > Perhaps you can post it? I'm also interested.
>
> I can post my document only with permission; however, I lack webspace
> to post it on.
Hint understood.
http://www.forth.org.ru/~mlg/BacFORTH-88/bf88-autotran.html
> However, going to http://www.translate.ru and having
> them translate the page (note: it can potentially time out on you,
> like it did for me). There is also a lot of Russian words that aren't
> translated, which I've later come to realize are really English words
> spelt phonetically using Cyrillic characters. Even so, there are some
> words which neither I nor my co-worker can translate, as the context
> is lost through translation.
then ask me
most likely, the word was "backtrackable" (lit."tracing") or "syntactic"
or "otkat" = going-back.
Michael L.Gassanenko
> >
> > \ -----------------------------------------------------------
> > ( START ... EMERGE , BACK ... TRACKING 22/03/93 )
>
> Thanks for listing the code. Many things escape me, however, such as
> what REF+, >RR<, >MARK, <MARK, and other similar words do. I was kind
> of hoping to learn the rationale for these words in the document's
> text.
>
<MARK is from Forth-83, available at http://forth.sf.net
>R< is R> SWAP >R
>RR is >R that works on return addresses.
In Win32Forth it will be REL>ABS >R and in F-PC it will be 2>R .
Read the paper about the Open Interpreter, it's an approach to portability
of return address manipulations.
OTOH, now I am inclined to assume a system of Class 1 (without any navorots
[unnecessary complications] like REL>ABS).
PS
see IF
: IF ?COMP COMPILE ?BRANCH >MARK EXIT ok[Dec]
see THEN
: THEN ?COMP >RESOLVE EXIT ok[Dec]
see AHEAD
: AHEAD ?COMP COMPILE BRANCH >MARK EXIT ok[Dec]
see BEGIN
: BEGIN ?COMP <MARK EXIT ok[Dec]
see AGAIN
: AGAIN ?COMP COMPILE BRANCH <RESOLVE EXIT ok[Dec]
see UNTIL
: UNTIL ?COMP COMPILE ?BRANCH <RESOLVE EXIT ok[Dec]
see ELSE
: ELSE AHEAD 2SWAP ( CS-SWAP ) THEN EXIT ok[Dec]
see WHILE
: WHILE IF 2SWAP ( CS-SWAP ) EXIT ok[Dec]
Samuel A. Falvo II
> > Even so, there are some
> > words which neither I nor my co-worker can translate, as the context
> > is lost through translation.
>
> then ask me
I didn't feel the need to, since the intent of the message contained
in the document was plenty clear enough to me.
I didn't intend to offend...
> most likely, the word was "backtrackable" (lit."tracing") or "syntactic"
> or "otkat" = going-back.
Actually, for me, it was otkat. I believe most of the others were the
names of authors.