How do I implement Y-combinator in Forth?

Question

On Rosetta Code there is no implementation of Y-combinator in Forth.

How can I do that? How do I use Y-combinator in Forth? And why?

Answer 1

Here's my attempt at a Y combinator. When you apply y to an xt, you get another xt back. When you execute this new xt, it will execute the first xt and pass in the second xt.

\ Address of an xt.
variable 'xt
\ Make room for an xt.
: xt, ( -- ) here 'xt !  1 cells allot ;
\ Store xt.
: !xt ( xt -- ) 'xt @ ! ;
\ Compile fetching the xt.
: @xt, ( -- ) 'xt @ postpone literal postpone @ ;
\ Compile the Y combinator.
: y, ( xt1 -- xt2 ) >r :noname @xt, r> compile, postpone ; ;
\ Make a new instance of the Y combinator.
: y ( xt1 -- xt2 ) xt, y, dup !xt ;

Use e.g. like this:

\ Count down from 10; passed to the anonymous definition.
10
\ Anonymous definition which recursively counts down.
:noname ( u xt -- ) swap dup . 1- ?dup if swap execute else drop then ;
\ Apply the Y combinator and execute the result.
y execute
\ Should print 10 9 8 7 6 5 4 3 2 1.

As for why, no practical reason. It's a way for a function to recursively call itself without explicitly naming the function. But (standard) Forth has RECURSE, even in :NONAME definitions.