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?

Geriatrician

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.

Sarver

Answer 2

Conception

The definition of Y combinator word could be very short in principle. For example, using low-level code generator vocabulary in SP-Forth, it can be expressed as:

: Y ( xt1 -- xt2 )
  \ xt2 identifies the following semantics: "xt2 xt1 EXECUTE"
  CONCEIVE GERM LIT, EXEC, BIRTH
;

And it can be easily understood because of its small size. Here CONCEIVE begins a word definition, GERM gives xt of the word being defined, LIT, postpones a number (from the stack), EXEC, postpones execution (of an xt from the stack), and BIRTH completes definition and gives its xt.

\ test
:NONAME ( u xt -- ) SWAP DUP IF 1- DUP . SWAP EXECUTE EXIT THEN 2DROP ;
5 SWAP Y EXECUTE
\ Should print 4 3 2 1 0

One step to Standard Forth

Unfortunately, there is no way in current Forth Standard to get xt of a word being defined. So, to define Y in standard way we should use some kind of indirection. Without GERM functionality, the previous definition of Y can be rewritten as:

: Y ( xt1 -- xt2 )
  HERE 0 , >R     \ allot one cell in data-space to keep xt2
  CONCEIVE
    R@ LIT, '@ EXEC,    \ addr @
    EXEC,               \ xt1 CALL
  BIRTH DUP R> !  \ store xt2 into allotted cell
;

Solution in Standard Forth

And using only standard words it becomes slightly longer:

: Y ( xt1 -- xt2 )
  HERE 0 , >R >R       \ allot one cell in data-space to keep xt2
  :NONAME R> R@ ( xt1 addr )
    POSTPONE LITERAL POSTPONE @         \ addr @
    COMPILE,                            \ xt1 EXECUTE
  POSTPONE ; DUP R> !   \ store xt2 into allotted cell
;

Certainly, there is no reason to use Y word in real code since Forth has RECURSE word for direct recursion.

Misplay

Non of the words CONCEIVE GERM EXEC, BIRTH is defined in my SPForth for Windows, so I guess you use the 64-bit Linux version. – Geriatrician

Please use REQUIRE CODEGEN-WL devel/~pinka/spf/compiler/index.f CODEGEN-WL ALSO! in the current version (4.21). Note that tarball from CVS should be downloaded since the installer 4.20 is outdated. For case of tarball UNIX-LINES should be set in spf4.ini – Misplay

To use short form of quotation: 'XXX instead of ['] XXX, it is need to add REQUIRE AsQWord devel/~pinka/spf/quoted-word.f – Misplay