Recursion in Forth

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.

You have my permission to link freely to any entry here. Go ahead, I won't bite. I promise.

The dates are the permanent links to that day's entries (or entry, if there is only one entry). The titles are the permanent links to that entry only. The format for the links are simple: Start with the base link for this site: https://boston.conman.org/, then add the date you are interested in, say 2000/08/01, so that would make the final URL:

https://boston.conman.org/2000/08/01

You can also specify the entire month by leaving off the day portion. You can even select an arbitrary portion of time.

You may also note subtle shading of the links and that's intentional: the “closer” the link is (relative to the page) the “brighter” it appears. It's an experiment in using color shading to denote the distance a link is from here. If you don't notice it, don't worry; it's not all that important.

It is assumed that every brand name, slogan, corporate name, symbol, design element, et cetera mentioned in these pages is a protected and/or trademarked entity, the sole property of its owner(s), and acknowledgement of this status is implied.