Discusión de Y combinator en "The Little Schemer"

Question

Por lo tanto, he pasado mucho tiempo leyendo y volviendo a leer el final del capítulo 9 en The Little Schemer, donde el combinador Y de aplicación se desarrolla para la función length . Creo que mi confusión se reduce a una sola declaración que contrasta dos versiones de longitud (antes de que el combinador se descompone en factores hacia fuera):

A: 
    ((lambda (mk-length) 
    (mk-length mk-length)) 
    (lambda (mk-length) 
    (lambda (l) 
     (cond 
     ((null? l) 0) 
     (else (add1 
       ((mk-length mk-length) 
       (cdr l)))))))) 

B: 
((lambda (mk-length) 
     (mk-length mk-length)) 
    (lambda (mk-length) 
     ((lambda (length) 
     (lambda (l) 
      (cond 
      ((null? l) 0) 
      (else (add1 (length (cdr l))))))) 
     (mk-length mk-length)))) 

Page 170 (4th ed.) establece que un

devuelve una función cuando lo aplicamos a un argumento

mientras que B

no RET Une una función

produciendo una regresión infinita de auto-aplicaciones. Estoy perplejo por esto. Si B está plagado por este problema, no veo cómo A lo evita.

Answer 1

Una gran pregunta. Para el beneficio de aquellos sin una instalación de DrRacket en funcionamiento (incluido yo), intentaré responderla.

En primer lugar, vamos a usar nombres sanos, fácilmente rastreables por un ojo/mente humana:

((lambda (h)  ; A. 
    (h h))   ; apply h on h 
(lambda (g) 
    (lambda (lst) 
     (if (null? lst) 0 
     (add1 
       ((g g) (cdr lst))))))) 

El primer término lambda es lo que se conoce como omega combinator. Cuando se aplica a algo, causa la autoaplicación de ese término. Así, el anterior es equivalente a

(let ((h (lambda (g) 
      (lambda (lst) 
      (if (null? lst) 0 
       (add1 ((g g) (cdr lst)))))))) 
    (h h)) 

Cuando h se aplica en h, nueva unión se forma:

(let ((h (lambda (g) 
      (lambda (lst) 
      (if (null? lst) 0 
       (add1 ((g g) (cdr lst)))))))) 
    (let ((g h)) 
    (lambda (lst) 
      (if (null? lst) 0 
       (add1 ((g g) (cdr lst))))))) 

Ahora no hay nada para aplicar más, así que se devuelve la forma interna lambda - junto con el enlaces ocultos a los marcos de entorno (es decir, aquellos que permiten enlaces) arriba.

Este emparejamiento de una expresión lambda con su entorno definido se conoce como closure. Para el mundo exterior, es simplemente otra función de un parámetro, lst. No hay más pasos de reducción para realizar allí en este momento.

Ahora, cuando se llame a ese cierre - nuestra función list-length -, la ejecución eventualmente llegará al punto de autoaplicación (g g), y se realizarán nuevamente los mismos pasos de reducción descritos anteriormente. Pero no antes.

---

Ahora, los autores de ese libro que desee llegar al combinador Y, por lo que aplicar algunas transformaciones de código en la primera expresión, para organizar de alguna manera para que la auto-aplicación (g g) a realizar de forma automática - para que podamos escribir la aplicación función recursiva de una manera normal, (f x), en lugar de tener que escribir como ((g g) x) para todas las llamadas recursivas:

((lambda (h)  ; B. 
    (h h))   ; apply h on h 
(lambda (g) 
    ((lambda (f)   ; 'f' to become bound to '(g g)', 
     (lambda (lst) 
     (if (null? lst) 0 
      (add1 (f (cdr lst)))))) ; here: (f x) instead of ((g g) x)! 
    (g g))))      ; (this is not quite right) 

Ahora, después de unos pocos pasos de reducción llegamos a

(let ((h (lambda (g) 
      ((lambda (f)  
       (lambda (lst) 
       (if (null? lst) 0 
        (add1 (f (cdr lst)))))) 
      (g g))))) 
    (let ((g h)) 
    ((lambda (f) 
     (lambda (lst) 
      (if (null? lst) 0 
       (add1 (f (cdr lst)))))) 
    (g g)))) 

lo que equivale a

(let ((h (lambda (g) 
      ((lambda (f)  
       (lambda (lst) 
       (if (null? lst) 0 
        (add1 (f (cdr lst)))))) 
      (g g))))) 
    (let ((g h)) 
    (let ((f (g g)))   ; problem! (under applicative-order evaluation) 
     (lambda (lst) 
      (if (null? lst) 0 
       (add1 (f (cdr lst)))))))) 

Y aquí viene el problema: la auto-aplicación de (g g) se realiza demasiado pronto, antes de que lambda interior puede ser incluso volvió, como cierre, a la Run- sistema de tiempo Solo queremos que se reduzca cuando la ejecución llegue a ese punto dentro de la expresión lambda, después de llamar al cierre. Reducirlo antes de que se cree el cierre es ridículo. Un error sutil. :)

Por supuesto, ya g está obligado a h, (g g) se reduce a (h h) y estamos de vuelta al punto de partida, la aplicación de h en h. Looping.

---

Por supuesto, los autores son conscientes de esto. Quieren us para entenderlo también.

Así que el culpable es simple - es applicative order of evaluation: evaluar el argumento antes de la unión se forma de parámetro formal de la función y el valor de su argumento.

Esa transformación de código no fue del todo correcta. Hubiera funcionado bajo normal order donde los argumentos no se evalúan de antemano.

Esto se remedia con bastante facilidad por "eta-expansion", lo que retrasa la aplicación hasta el punto de llamada real: (lambda (x) ((g g) x)) realidad dice: "se llamada ((g g) x) cuando se le solicite con un argumento de x".

Y esto es en realidad lo que la transformación de código debería haber estado en el primer lugar:

((lambda (h)  ; C. 
    (h h))   ; apply h on h 
(lambda (g) 
    ((lambda (f)   ; 'f' to become bound to '(lambda (x) ((g g) x))', 
     (lambda (lst) 
     (if (null? lst) 0 
      (add1 (f (cdr lst)))))) ; here: (f x) instead of ((g g) x) 
    (lambda (x) ((g g) x))))) 

Ahora que el próximo paso de reducción puede ser realizada:

(let ((h (lambda (g) 
      ((lambda (f)  
       (lambda (lst) 
       (if (null? lst) 0 
        (add1 (f (cdr lst)))))) 
      (lambda (x) ((g g) x)))))) 
    (let ((g h)) 
    (let ((f (lambda (x) ((g g) x)))) 
     (lambda (lst) 
      (if (null? lst) 0 
       (add1 (f (cdr lst)))))))) 

y se forma el cierre (lambda (lst) ...) y regresó sin problemas, y cuando se llama (f (cdr lst)) (dentro del cierre) se reduce a ((g g) (cdr lst)) exactamente como lo deseamos.

---

Por último, se observa que (lambda (f) (lambda (lst ...)) expresión en C. no depende de ninguna de las h y g. Así podemos llevarlo a cabo, lo convierten en un argumento, y se quedará con el combinador ... Y:

(((lambda (rec)   ; D. 
     ((lambda (h) (h h)) 
     (lambda (g) 
      (rec (lambda (x) ((g g) x)))))) ; applicative-order Y combinator 
    (lambda (f)  
     (lambda (lst) 
      (if (null? lst) 0 
      (add1 (f (cdr lst))))))) 
    (list 1 2 3))       ; ==> 3 

Así que ahora, llamando Y en una función es equivalente a hacer una definición recursiva de ella:

(y (lambda (f) (lambda (x) .... (f x) ....))) 
=== define f = (lambda (x) .... (f x) ....) 

... pero utilizando letrec (o dejar que el nombre) es mejor - más eficiente, defining the closure in self-referential environment frame. Todo lo de Y es un ejercicio teórico para los sistemas donde eso no es posible — es decir, donde no es posible nombrar cosas, crear enlaces con nombres "apuntando" a cosas, refiriéndose a cosas.

Por cierto, la capacidad de punto a las cosas es lo que distingue a los primates superiores del resto de los seres vivos reino animal ⁄, o eso me han dicho. :)

Answer 2

Para ver qué pasa, use el paso a paso en DrRacket. El stepper le permite ver todos los pasos intermedios (y para ir y venir).

pegue lo siguiente en DrRacket:

(((lambda (mk-length) 
    (mk-length mk-length)) 
    (lambda (mk-length) 
    (lambda (l) 
     (cond 
     ((null? l) 0) 
     (else (add1 
       ((mk-length mk-length) 
       (cdr l)))))))) 
'(a b c)) 

A continuación, seleccione el idioma de la enseñanza "Estudiante intermedio con lambda". Luego haga clic en el botón de paso a paso (el triángulo verde seguido de una barra).

Esto es lo que el primer paso será similar a:

A continuación, crea un ejemplo para la segunda función y ver lo que va mal.