Y-combinateur en Scheme, utilisant l'évaluation paresseuse ?

Question

Quelqu'un sait-il comment implémenter le Y-combinator dans Scheme, en particulier avec une évaluation paresseuse et un argument supplémentaire ? Je crois savoir que Scheme (promise ?) (delay) et (force) fournissent un support pour l'évaluation paresseuse.

Je crois comprendre que le Y-combinator avec application est le suivant, mais il ne fonctionnera pas dans Scheme en raison de l'évaluation de l'ordre applicatif par défaut.

((lambda (f)
   ((lambda (x) (f (x x)))
    (lambda (x) (f (x x)))))
 (lambda (r) (r)))

Il s'agit d'une solution suggérée (le Z-combinateur), mais elle utilise une autre fonction lambda avec des arguments comme solution :

;; Z-combinator
(define Z
  (lambda (f)
    ((lambda (g) (f (g g)))
     (lambda (g) (f (lambda args (apply (g g)
                                        args)))))))
;Value: z

((Z (lambda (r)
      (lambda (x)
        (if (< x 2)
            1
            (* x (r (- x 1))))))) 5)
;Value: 120

;; end Z-combinator

Mise à jour en fonction des solutions

Le Y-combinator est le suivant :

;; Y-combinator
(define Y
  (lambda (f)
      ((lambda (x) (f (delay (x x))))
       (lambda (x) (f (delay (x x)))))))
;Value: y

;; end Y-combinator

;; Non tail recursive
((Y (lambda (r)
      (lambda (x)
        (if (< x 2)
            1
            (* x ((force r) (- x 1)))))))
   5)
;Value: 120

;; Tail - recursive
((Y (lambda (r)
      (lambda (x acc)
        (if (< x 2)
            acc
            ((force r) (- x 1) (* x acc))))))
   5 1)

;Value: 120

J'apprécie vos conseils !

Answer 1

Oui, avec une évaluation stricte, l'auto-application (x x) provoque une boucle infinie. Si vous retardez cette application, vous pouvez utiliser le combinateur y à condition de " forcer " cet objet retardé à son emplacement d'utilisation :

(define (test)
  (((lambda (f)
      ((lambda (x) (f (delay (x x))))
       (lambda (x) (f (delay (x x))))))
    (lambda (r)
      (lambda (x)
        (if (< x 2)
            1
            (* x ((force r) (- x 1)))))))
   5))

La façon normale de faire une variation du y-combinator qui fonctionne dans un cadre strict est d'eta-expandre l'application du self, ce qui est une autre façon de le retarder mais ne nécessite pas une application explicite de la force. Au lieu de cela, le forçage est effectué par l'application de la fonction.

Answer 2

Le combinateur Y d'ordre normal, calculant ici (ack 3 6) dans Lazy Racket :

#lang lazy

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

((Y (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

Scheme n'est pas un langage paresseux comme Lazy Racket, donc le Y doit être un peu différent. On l'appelle maintenant un combinateur Z :

#!r6rs
(import (rnrs base))

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

((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

Utilisation de delay y force ne le rend pas vraiment meilleur :

#!r6rs
(import (rnrs base)
        (rnrs r5rs))

(define DY
  (lambda (f)
    ((lambda (g) (g g))
     (lambda (g) (f (delay (g g)))))))

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

Normalement Y et Z nous permet de nommer notre procédure récursive, mais dans cette dernière nous obtenons une promesse que nous devons résoudre et donc nous laissons échapper des détails d'implémentation et cela devient plus difficile à utiliser. En général, lorsqu'il s'agit de promesses, nous voulons éviter toute exécution inutile, mais l'appel doit alors renvoyer une promesse.