Terminación del combinador Z con llamada por valor

Question

Estoy tratando de construir mi propio intérprete λ-cálculo. Hasta ahora admite tanto el valor de la llamada y el orden normal.

Ahora quiero probar la recursión a través de puntos fijos. El $ y $ combinador funciona con orden normal, probado con la función de facultad $$ \ texto {FAC}=LAMBDA F . \ lambda n. \ texto {iszero} \, n \, 1 (\ texto {mul} \, n \, (f (\ texto {pred} \, n))) \ texto {,} $$ y, por ejemplo, mi intérprete produce $ y \, \ texto {FAC} \, 3 \ stackrel {\ texto {no}} {\ rudowarrow} 6 $ . (Escribiré numerales de iglesia equivalentes conductualmente como números decimales)

En cuanto a yo sepa por la llamada por valor, necesitaré el $ z $ combinador en su lugar:

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

como $ y $ causaría una regresión infinita inmediata.

Mi problema es que no entiendo cómo se supone que se debe terminar la $ z \, \ texto {FAC}, 0 $ terminate. Tampoco termina en mi intérprete, pero quiero entenderlo manualmente primero.

Después de algunos pasos, la llamada por valor debe llegar a: $$ Z \, \ Text {FAC} \, 0 \\=lambda f. (\ lambda x. f (\ lambda y. x x y)) (\ lambda x. f (\ lambda y. x x y) \, \ texto {FAC} \, 0 \\\ stackrel {\ texto {cbv}} {\ rudowarrow} (\ lambda x. \ texto {fac} (\ lambda y. xxy)) (\ lambda x. \ texto {FAC} (\ lambda y. xxy) ) \, 0 \\\ stackrel {\ texto {cbv}} {\ rudowarrow} \ texto {fac} (\ lambda y. (\ lambda x. \ texto {FAC} (\ lambda y '. xx y')) (\ lambda x . \ Texto {FAC} (\ lambda y. xx y ')) y) \, 0 \\\ stackrel {\ texto {cbv}} {\ judowarrow} \ texto {fac} \, f \, 0 \ stackrel {\ texto {cbv}} {\ joyerwarrow} \ texto {iszero} \, 0 \, 1 \, A \ Text {,} $$ < / span>

donde el término omitido

$$ a=texto {mul} \, 0 \, (f \, (\ texto {pred} \, 0)) $$ contiene < / p>

$$ f=lambda y. (\ lambda x. \ texto {FAC} (\ lambda y'.xxy ')) (\ lambda x. \ texto {FAC } (\ lambda y'.xxy ')) \, y $$ otra vez.

ahora, $ \ text {iszero} \, 0 \ stackrel {\ texto {cbv}} {\ joymerow} \ lambda t. \ lambda ft $ , st

$$ \ texto {iszero} \, 0 \, 1 \, A \ stackrel {\ texto {cbv}} {\ boyarrow} (\ lambda t. \ lambda ft ) \, 1 \, a \ stackrel {\ texto {cbv}} {\ rudowarrow} (\ lambda f. 1) \, A \ texto {.} $$

Si nuestro idioma tuvo un constructo de ramificación que ignoraría el $ a $ sucursal que se haríamos, pero con la llamada por valor tenemos que evaluar < Span Class="Math-contenedor"> $ A $ a un valor, es decir, una abstracción.

$ a=texto {mul} \, 0 \, (f \, (\ texto {pred} \, 0)) $ y $ \ texto {mul} \, 0 $ será otra abstracción, así que, a continuación, tengo que reducir $ f \, (\ texto {pred } \, 0) $ .

$ \ texto {pred} \, 0 \ stackrel {\ texto {cbv}} {\ rudowarrow} 0 $ , por lo que reducimos $ F \, 0 $ .

$$ F \, 0= (\ lambda y. (\ lambda x. \ Texto {FAC} (\ lambda y'.xxy ')) (\ lambda x. \ Text {FAC} (\ lambda y'.xxy ')) \, y) \, 0 \ stackrel {\ texto {cbv}} {\ rudowarrow} (\ lambda x. \ texto {fac} (\ lambda y' .xxy ')) (\ lambda x. \ Texto {FAC} (\ lambda y'.xxy')) \, 0 \ stackrel {\ texto {cbv}} {\ rudowarrow} \ texto {FAC} \, F \ , 0 $$

y ahora estamos de vuelta en la Plaza uno. ¿Estoy haciendo algo mal?

Answer 1

No creo que estés haciendo lo incorrecto, pero el problema no es el combinador Z.El problema es $ \ texto {iszero} $ .Las construcciones de ramificación en la llamada por valor no pueden simplemente tomar los términos directos para cada sucursal como argumentos como pueden en llamadas por nombre (o similar), porque ambas sucursales se evaluarán independientemente de la prueba.Esto interactúa claramente mal con la recursión, pero también es indeseable en general.

En su lugar, las construcciones de ramificación en la llamada por valor deben tomar argumentos retrasados explícitamente.Así que algo así: $$ \ texto {iszero} \n\ (λ \ _. 1) (λ \ _. \ Texto {mul} \n\ (f \ (\ texto{pred} \ n)) $$ De esta manera, se puede evitar la evaluación recursiva a menos que sea realmente necesario. Podría, por supuesto, dejarlo $ \ texto {iszero}$ Como es, siempre úselo de esta manera, y proporcione un argumento adicional usted mismo, pero creo que normalmente se definiría para esperar argumentos retrasados.