如何在 Forth 中实现 Y 组合器

Question

在罗塞塔代码上，Forth中没有Y-combinator的实现。

我该怎么做？如何在 Forth 中使用 Y 组合器？为什么呢？

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.

至于为什么，没有实际原因。 这是函数在不显式命名函数的情况下递归调用自身的一种方式。 但是(标准的(福斯有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标准中没有办法获得正在定义的单词的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直接递归这个词。