Terminaison de la combinaison de Z avec une valeur appelée

Question

J'essaie de construire mon propre interprète λ-calcul. Jusqu'à présent, il soutient à la fois la valeur des appels et la commande normale.

Je veux maintenant essayer la récursion via des points fixes. La $ Y $ Combinator fonctionne avec ordre normal, testé avec la fonction faculté $$ \ texte {FAC}=lambda f . \ lambda n. \ Text {iszero} \, n \, 1 (\ text {mul} \, n \, (f (\ text {psy} \, n))) \ Text {,} $$ et par exemple, mon interprète donne $ y \, \ texte {FAC} \, 3 \ stackrel {\ text {no}} {\ wakearrow} 6 $ . (Je vais écrire des chiffres d'église équivalents comportementaux comme numéros décimaux)

Aussi loin que je sache pour appeler-by-valeur, j'aurai besoin de la $ Z $ Combinator à la place:

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

comme $ y $ provoquerait une régression infinie immédiate.

Mon problème est que je ne comprends pas comment $ z \, \ text {fac} \, 0 $ est censé se terminer. Il ne se termine pas non plus dans mon interprète, mais je veux la comprendre manuellement.

Après que certaines étapes, l'appel-valeur devrait arriver à: $$ z \, \ texte {fac} \, 0 \\=lambda f. (\ lambda x. F (\ lambda y. x x y)) (\ lambda x. F (\ lambda y. x x y)) \, \ text {fac} \, 0 \\\ stackrel {\ text {cbv}} {\ weightarrow} (\ lambda x. \ Text {FAC} (\ lambda y. xxy)) (\ lambda x. \ Text} (\ lambda y. xxy) ) \, 0 \\\ stackrel {\ text {cbv}} {\ \ weightarrow} \ text {FAC} (\ lambda y. (\ lambda x. \ Text {Texte {FAC} (\ lambda y '. xx Y') . \ Text {FAC} (\ lambda y. xx y ')) y) \, 0 \\\ stackrel {\ text {cbv}} {\ RightARrow} \ TEXT {FAC} \, F \, 0 \ Stackrel {\ Text {\ cbv}} {\ RightArrow} \ Text {iszero} \, 0 \, 1 \, un \ Text {,} $$ < / span>

où le terme omis

$$ a=text {mul} \, 0 \, (f \, (\ text {psy} \, 0) contient contient < / p>

$$ f=lambda y. (\ lambda x. \ Text {FAC} (\ lambda y'..xxy ')) (\ lambda x. \ Text \ Text } (\ lambda y'.xxy ')) \, y $$ $$ encore.

maintenant, $ \ text {iszero} \, 0 \ stackrel {\ text {cbv}} {\ rightarrow} \ lambda t. \ lambda ft $ , st

$$ \ texte {iszero} \, 0 \, 1 \, a \ stackrel {\ text {cbv}} {\ rightarrow} (\ lambda t. \ lambda ft ) \, 1 \, un \ stackrel {\ text {cbv}} {\ weightarrow} (\ lambda f. 1) \, un \ texte {.} $$

Si notre langue avait une construction de ramification qui ignorerait la A $ A $ DIRECT que nous serions terminés, mais avec une valeur appelée, nous devons évaluer < span class="math-conteneur"> $ a $ à une valeur, c'est-à-dire une abstraction.

$ a=texte {mul} \, 0 \, (f \, (\ text {PRED} \, 0)) $ et $ \ Text {mul} \, 0 $ sera une autre abstraction alors suivante que je dois réduire $ f \, (\ Text {Pred } \, 0) $ .

$ \ texte {PRED} \, 0 \ stackrel {\ text {cbv}} {\ rightarrow} 0 $ , donc nous réduisons $ f \, 0 $ .

$$ f \, 0= (\ lambda y. (\ lambda x. \ Text {FAC} (\ lambda y'..xxy ')) (\ lambda x. \ texte {fac} (\ lambda y'.xxy ')) \, y) \, 0 \ stackrel {\ text {cbv}} {\ rightarrow} (\ lambda x. \ Text {FAC} (\ lambda y' .xxy ')) (\ lambda x. \ Texte {FAC} (\ lambda y'.xxy')) \, 0 \ stackrel {\ text {cbv}} {\ rightarrow} \ Text {FAC} \, f \ , 0 $$

Et maintenant nous sommes de retour à la case carré. Est-ce que je fais quelque chose de mal?

Answer 1

Je ne pense pas que vous faites la réduction ne va pas, mais le problème n'est pas le combinateur Z.Le problème est $ \ text {iszero} $ .Les constructions de ramification dans la valeur appelée ne peuvent pas simplement prendre les conditions directes de chaque branche comme arguments comme ils peuvent être appelés par nom (ou similaires), car les deux branches seront évaluées quel que soit le test.Cela interagit clairement mal avec la récursion, mais il est également indésirable en général.

Au lieu de cela, les constructions de ramification dans la valeur appelée doivent prendre des arguments explicitement retardés.Alors quelque chose comme: $$ \ texte {iszero} \n\ (\ \ _. 1) (\ \ _. \ Text {MUL} \n\ (F \ (\ Text{PRED} \ N)) $$ De cette façon, l'évaluation récursive peut être évitée sauf si elle est réellement nécessaire. Vous pouvez bien sûr laisser $ \ text {iszero}$ tel quel, l'utilisez toujours de cette façon et fournissez un argument supplémentaire vous-même, mais je pense normalement qu'il serait défini pour s'attendre à des arguments retardés.