Y Mise en œuvre du combinateur

Question

Je suis vraiment novice en matière de programmation fonctionnelle. Je suis récemment tombé sur la fonction Y-combinator dans le calcul lambda, quelque chose comme ça Y ≡ (λy.(λx.y(xx))(λx.y(xx))). Je voulais l'implémenter dans le schéma, j'ai cherché beaucoup mais je n'ai trouvé aucune implémentation qui correspond exactement à la structure donnée ci-dessus. Certains d'entre eux je l'ai trouvé sont donnés ci-dessous:

(define Y 
(lambda (X) 
    ((lambda (procedure) 
    (X (lambda (arg) ((procedure procedure) arg)))) 
    (lambda (procedure) 
    (X (lambda (arg) ((procedure procedure) arg))))))) 

et

(define Y 
    (lambda (r) 
    ((lambda (f) (f f)) 
    (lambda (y) 
     (r (lambda (x) ((y y) x))))))) 

Comme vous pouvez le voir, ils ne correspondent à la structure de cette fonction Y ≡ (λy.(λx.y(xx))(λx.y(xx))) combinateur. Comment puis-je l'implémenter dans le schéma exactement de la même manière?

Answer 1

Dans un langage paresseux comme Lazy Racket, vous pouvez utiliser la version normale, mais pas dans les langages de programmation applicatifs comme Scheme. Ils vont juste aller dans une boucle infinie.

La version applicative de Y est souvent appelée Z Combinator:

(define Z 
    (lambda (f) 
    ((lambda (g) (g g)) 
    (lambda (g) 
     (f (lambda args (apply (g g) args))))))) 

Maintenant, la première chose qui se produit lorsque cela est appliqué est (g g) et puisque vous pouvez toujours remplacer une application tout à l'expansion de son corps le corps de la fonction peut être réécrit à:

(define Z 
    (lambda (f) 
    ((lambda (g) 
     (f (lambda args (apply (g g) args)))) 
    (lambda (g) 
     (f (lambda args (apply (g g) args))))))) 

Je n'ai vraiment rien changé. C'est juste un peu plus de code qui fait exactement la même chose. Notez que cette version utilise apply pour prendre en charge plusieurs fonctions d'argument. Imaginez la fonction Ackermann:

(define ackermann 
    (lambda (m n) 
    (cond 
     ((= m 0) (+ n 1)) 
     ((= n 0) (ackermann (- m 1) 1)) 
     (else (ackermann (- m 1) (ackermann m (- n 1))))))) 

(ackermann 3 6) ; ==> 509 

Cela peut être fait avec Z comme ceci:

((Z (lambda (ackermann) 
     (lambda (m n) 
     (cond 
     ((= m 0) (+ n 1)) 
     ((= n 0) (ackermann (- m 1) 1)) 
     (else (ackermann (- m 1) (ackermann m (- n 1)))))))) 
3 
6) ; ==> 509 

Notez les implémentations est exactement la même et la différence est la façon dont la référence à lui-même est gérée.

EDIT

Vous demandez donc comment l'évaluation est en retard. Eh bien la version de l'ordre normal ressemble à ceci:

(define Y 
    (lambda (f) 
    ((lambda (g) (g g)) 
    (lambda (g) (f (g g)))))) 

Si vous regardez comment cela serait appliqué avec un argument, vous remarquerez que Y ne retourne jamais depuis avant qu'il ne puisse appliquer f en (f (g g)) il a besoin d'évaluer (g g) qui à son tour évalue (f (g g)) etc. Pour sauver que nous n'appliquons pas immédiatement (g g). Nous savons que (g g) devient une fonction, donc nous donnons f une fonction qui, lorsqu'elle est appliquée, génère la fonction réelle et l'applique. Si vous avez une fonction add1 vous pouvez faire un wrapper (lambda (x) (add1 x)) que vous pouvez utiliser à la place et cela fonctionnera. De la même manière (lambda args (apply (g g) args)) est le même que (g g) et vous pouvez le voir en appliquant simplement des règles de substitution. L'idée ici est que cela arrête effectivement le calcul à chaque étape jusqu'à ce qu'il soit réellement utilisé.