如何在Forth中实现Y-combinator？

Question

在Rosetta Code上,Forth中没有实现Y-combinator.

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

Answer 1

这是我对Y组合器的尝试.当你申请yxt时,你会得到另一个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定义中也是如此.

Answer 2

概念

Y组合词的定义原则上可能非常短.例如,在SP-Forth中使用低级代码生成器词汇表,它可以表示为:

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

由于体积小,可以很容易理解.这里CONCEIVE开始一个单词定义,GERM给出定义单词的xt,LIT,推迟一个数字(来自堆栈),EXEC,推迟执行(来自堆栈的xt),并BIRTH完成定义并给出它的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

标准Forth的一步

不幸的是,目前的Forth Standard没有办法获得定义一个单词的xt.因此,要Y以标准方式定义,我们应该使用某种间接.没有GERM功能,以前的定义Y可以重写为:

: 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
;

标准的解决方案

仅使用标准单词会变得稍长:

: 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
;

当然,没有理由Y在实际代码中使用单词,因为Forth有RECURSE直接递归的词.