5

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

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

4

2 回答 2

5

这是我对 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定义中。

于 2016-02-05T08:48:03.147 回答
5

概念

组合词的定义Y原则上可以很短。例如，使用 SP-Forth 中的低级代码生成器词汇表，可以表示为：

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

而且由于体积小，很容易理解。这里CONCEIVE开始一个单词定义，GERM给出正在定义的单词的xtLIT, ，推迟一个数字（从堆栈中），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

迈向 Standard Forth 的一步

不幸的是，在当前的 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
;

Standard Forth 中的解决方案

并且仅使用标准单词会变得稍长：

: 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在实际代码中使用 word，因为 Forth 有RECURSE直接递归的 word。

于 2016-02-10T17:59:07.707 回答