Прекращение z Combinator с Call-значением

Question

Я пытаюсь построить свой собственный интерпретатор Λ-Calculus. До сих пор он поддерживает как Call-значение, так и нормальный заказ.

Теперь я хочу попробовать рекурсию через фиксированные точки. $ y $ Комбинатор работает с нормальным порядком, протестирован с функцией факультета $$ \ Text {FAC}=Lambda F , \ lambda n. \ text {iszero} \, n \, 1 (\ text {mul} \, n \, (f (\ text {pret} \, n))) \ text {,} $$ А например, мой интерпретатор дает $ \, \ TEXT {FAC} \, 3 \ Stackrel {\ Text {NO}} {\ prightarrow} 6 $ . (Я напишу поведенчески эквивалентные церковные цифры как десятичные числа)

Насколько я знаю для Call-value, мне понадобится комбинатор $ Z $ Combinator:

$$ z=lambda f. (\ lambda x. f (\ lambda y. x x y)) (\ lambda x. f (\ lambda y. x x y)) \ text {,} $$

как $ y $ приведет к немедленному бесконечному регрессии.

Моя проблема в том, что я не понимаю, как $ Z \, \ Text {FIC} \, 0 $ должен завершаться. Это также не прекращается в моем переводчике, но я хочу понять его вручную первым.

После некоторых шагов Call-by-value должен прибыть на: $$ z \, \ text {fac} \, 0 \\=лямбда е. (\ lambda x. f (\ лямбда y. x x y)) (\ lambda x. f (\ lambda y. x x y)) \, \ text {fac} \, 0 \\\ stackrel {\ text {cbv}} {\ prevarrow} (\ lambda x. \ text {fac} (\ lambda y. xxy)) (\ lambda x. \ text {fac} (\ lambda y. xxy) ) \, 0 \\\ kackrel {\ text {cbv}} {\ prightarrow} \ text {fac} (\ lambda y} (\ lambda x. \ text {fac} (\ lambda y '. xxy y')) (\ lambda x . \ text {fac} (\ lambda y. xx y ')) y) \, 0 \\\ kackrel {\ text {cbv}} {\ prevarrow} \ text {fac} \, f \, 0 \ stackrel {\ text {cbv}} {\ \ prevarrow} \ text {ISZERO} \, 0 \, 1 \, a \ text {,} $$ < / span>

Где пропущенный термин

$$ a=text {mul} \, 0 \, (f \, (\ text {pret} \, 0)) $$ содержит < / P >.

$$ f=lambda y. (\ lambda x. \ text {fac} (\ lambda y.xxy ')) (\ lambda x. \ text {fac } (\ lambda y.xxy ')) \, y $$ снова.

Теперь, $ \ text {Issero} \, 0 \ Stackrel {\ Text {CBV}} {\ prightarrow}}} {\ \ \ lambda ft $ , ST

$$ \ text {Issero} \, 0 \, 1 \, a \ stackrel {\ text {cbv}} {\ prightarrow} (\ lambda t. \ lambda ft ) \, 1 \, a \ stackrel {\ text {CBV}} {\ prightarrow} (\ lambda f. 1) \, a \ text {.} $$

Если у нашего языка есть ветвящаяся конструкция, которая проигнорировала бы «математический контейнер $ a $ , которую мы бы сделали, но с Call-значением мы должны оценить < Spaness Class="Math-Container"> $ a $ к значению, то есть абстракция.

$ a=text {mul} \, 0 \, (f \, (\ text {pret} \, 0)) $ и <класс span="Математический контейнер"> $ \ text {mul} \, 0 $ Будет еще одна абстракция, поэтому я должен уменьшить $ f \, (\ text {pref } \, 0) $ .

$ \ text {pret} \, 0 \ stackrel {\ text {cbv}} {\ prightarrow} 0 $ , поэтому мы уменьшаем $ f \, 0 $ .

$$ f \, 0= (\ lambda y. \ \ lambda x. \ text {fac} (\ lambda y.xxy ')) (\ lambda x. \ text {fac} (\ lambda y.xxy ')) \, y.xxy')) \, y \, 0 \ stackrel {\ text {cbv}} {\ prightarrow} (\ lambda x. \ text {fac} (\ lambda y ' .xxy ')) (\ lambda x. \ text {fac} (\ lambda y.xxy')) \, 0 \ stackrel {\ text {cbv}} {\ priverarrow}} \ text {fac} \, f \ 0 $$

А теперь мы вернулись на квадратную. Я делаю что-то не так?

Answer 1

Я не думаю, что вы делаете уменьшение неправильно, но проблема не комбинатор z.Проблема в $ \ text {Issero} $ .Развлекательные конструкции в Call-value не могут просто предпринять прямые условия для каждой ветви, как аргументы, как они могут в вызове (или похоже), потому что оба ветка будут оцениваться независимо от теста.Это явно взаимодействует плохо с рекурсией, но это также нежелательно в целом.

Вместо этого разветвленные конструкции в Call-значения должны принять явными отложенными аргументами.Итак, что-то вроде: $$ \ TEXT {ISZERO} \ N \ (λ \ _. 1) (λ \ _. \ Text {mul} \n\ (f \ (\ text{pret} \ n)) $$ Таким образом, следует избегать рекурсивной оценки, если она не на самом деле не требуется. Вы могли бы, конечно, оставить $ \ Text {Issero}$ Как есть, всегда используйте его таким образом, и дайте дополнительный аргумент самостоятельно, но я думаю, что обычно он будет определен, чтобы ожидать отложенных аргументов.