computer-science - 如何在 Forth 中实现 Y-combinator？

Question

在 Rosetta Code Forth 中没有 Y-combinator 的实现。

我怎样才能做到这一点？如何在 Forth 中使用 Y-combinator？为什么？

Answer 1

这是我对 Y 组合器的尝试。申请时y到一个 xt，你得到另一个 xt 回来。当你执行这个新的 xt 时，它会执行第一个 xt 并传入第二个 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 ;

使用例如像这样:

\ 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.

至于为什么，没有实际原因。这是函数递归调用自身而不显式命名函数的一种方式。但是(标准)Forth 有 RECURSE , 即使在 :NONAME定义。