Как мне реализовать Y-комбинатор в Forth?

На Rosetta Code нет реализации Y-комбинатора в Forth.

Как я могу это сделать? Как мне использовать Y-комбинатор в Forth? И почему?

Источник

2 ответа

Решение

Вот моя попытка 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 определения.

Источник

зачатие

Определение Y слово комбинатор может быть очень коротким в принципе. Например, используя словарь генератора низкоуровневого кода в SP-Forth, он может быть выражен как:

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

И это легко понять из-за его небольшого размера. Вот CONCEIVE начинается определение слова, GERM дает текст определяемого слова, 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 нет способа получить текст определяемого слова. Итак, чтобы определить 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
;

Решение в стандарте 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 слово в реальном коде, так как Форт RECURSE Слово для прямой рекурсии.

Источник
Другие вопросы по тегам