Monday, June 09, 2025
DOES> RECURSE doesn't DOES> RECURSE does't DOES> RECURSE …
Recursion in Forth isn't as straitforward as you would think. The obvious:
: FOO ... FOO .. ;
doesn't work.
It will either error out as FOO isn't found,
or it will call the previous definition of FOO if it exists.
This is a quirk of Forth,
and it one reason why globals aren't as much of an issue as they are in other languages—if you define the word REPEAT it won't break existing code that called REPEAT,
they will just keep using the old version of REPEAT while new words will use the new version.
In fact,
the ANS Forth standard says as much: “The current definition shall not be findable in the dictionary until [colon] is ended.”
Thus the reason for the word RECURSE,
an immedate word
(which is run durring compilation, not compiled)
to exist in Forth—to do recursion.
This was an easy word to implement:
forth_core_recurse ; ( -- ) fdb forth_core_r_fetch fdb _IMMED | _NOINTERP :: .xt - .name .name fcc "RECURSE" .xt fdb .body .body ldx forth__here ; get current comp location ldd forth__create_xt ; get xt of current word std ,x++ ; recurse stx forth__here ldx ,y++ ; NEXT jmp [,x]
So the above would be written as:
: FOO ... RECURSE ... ;
And the resulting code would look like:
foo fdb ... fdb .xt - .name .name fcc "FOO" .xt fdb forth_core_colon.runtime .body fdb dot_dot_dot.xt fdb foo.xt ; FOO's xt fdb dot_dot_dot.xt fdb forth_core_exit.xt
The only reason I'm mentioning this word is because of this bit from the Standard:
“An ambiguous condition exists if RECURSE appears in a definition after DOES>.”
There's a reason for that—depending upon the implementation,
it may be impossible to do recursion after DOES>.
Why?
In my Forth implementation,
the code following DOES> doesn't have an xt to reference.
The xt of any word is the address of the .xt field.
So using the example from my explaination of DOES>,
the xt of MAN would be of its .xt field:
man fdb shape ; link to next word fdb .xt - .name .name fcc 'man' .xt fdb shape.does ; the XT of this word is this address .body fcb $24 fcb $24 fcb $24 fcb $99 fcb $5A fcb $3C fcb $18 fcb $18
But the problem is—that address doesn't exist until the word is defined!
If,
for example,
the definition of SHAPE used RECURSE:
: SHAPE CREATE 8 0 DO C, LOOP DOES> ... RECURSE ... ;
when RECURSE is executed,
there is no xt for it to use.
We can't use the xt for SHAPE—that's not the word we want to recurse on.
And we can't use the address of shape.does
because that's not an actual xt.
And the code following DOES> can be shared by multiple words:
... SHAPE MAN ... SHAPE FACE-HUGGER ... SHAPE ALIEN ... SHAPE FLAME-THROWER
so there's no single xt that RECURSE could use when compiling the code after DOES>
(never mind the fact that that happens before the words that use the code are created).
So,
in my Forth implementation,
no RECURSE after DOES>.
Which is fine,
because it's an ambiguous condition.
Could I make it work? Maybe. But it would be a lot of work for a feature that Forth programmers can't rely upon anyway.
