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

combinators y-combinator

Question

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

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

Página 170 (4ª ed) establece que A

devuelve una función cuando la aplicamos a un argumento

mientras B

no devuelve una función

produciendo así 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

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

Primero, usemos nombres sanos, fácilmente rastreados 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 combinador omega . Cuando se aplica a algo, causa la autoaplicación de ese término. Por lo tanto, lo 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 , se forma una nueva unión:

(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 ya no hay nada que aplicar, por lo que se devuelve la forma interna lambda , junto con los enlaces ocultos a los marcos del entorno (es decir, los que permiten las uniones) por encima de ella.

Este emparejamiento de una expresión lambda con su entorno definitorio 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 de list-length , la ejecución eventualmente llegará al punto de (gg) autoaplicación, y se realizarán nuevamente los mismos pasos de reducción descritos anteriormente. Pero no antes.

Ahora, los autores de ese libro quieren llegar al combinador Y, por lo que aplican algunas transformaciones de código en la primera expresión, para organizar de alguna manera que la autoaplicación (gg) se realice automáticamente, por lo que podemos escribir la aplicación de función recursiva de manera normal, (fx) , en lugar de tener que escribirlo como ((gg) 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 algunos 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))))

que es equivalente 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 autoaplicación de (gg) se realiza demasiado pronto, antes de que esa lambda interna pueda devolverse, incluso como cierre, al sistema de tiempo de ejecución. Solo queremos que se reduzca cuando la ejecución llegue a ese punto dentro de la expresión lambda, después de que se haya llamado al cierre. Reducirlo antes de que se cree el cierre es ridículo. Un error sutil :)

Por supuesto, dado que g está ligado a h , (gg) se reduce a (hh) y volvemos donde comenzamos, aplicando h en h . Looping.

Por supuesto, los autores son conscientes de esto. Quieren que lo entendamos también.

Entonces, el culpable es simple: es el orden de evaluación aplicativo : se evalúa el argumento antes de que el enlace se forme a partir del parámetro formal de la función y el valor de su argumento.

Esa transformación de código no fue del todo correcta. Habría funcionado bajo un orden normal donde los argumentos no son evaluados de antemano.

Esto se remedia fácilmente con " eta-expansion ", que retrasa la aplicación hasta el punto de llamada real: (lambda (x) ((gg) x)) dice: "llamará ((gg) x) cuando se le solicite un argumento de x ".

Y esto es realmente lo que debería haber sido la transformación del código en 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 se puede realizar el próximo paso de reducción:

(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 el cierre (lambda (lst) ...) se forma y se devuelve sin problemas, y cuando se llama ( (f (cdr lst)) (dentro del cierre) a ((gg) (cdr lst)) solo como lo quisimos

Por último, notamos que la expresión (lambda (f) (lambda (lst ...)) en C. no depende de ninguna de las h y g . Así que podemos sacarla, convertirla en un argumento, y dejarla 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

Entonces, llamar a Y en una función es equivalente a hacer una definición recursiva a partir de ella:

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

... pero usar letrec (o named let) es mejor , más eficiente, definir el cierre en el marco del entorno autorreferencial . 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, para crear enlaces con nombres que "apuntan" a cosas, refiriéndose a cosas.

A propósito, la capacidad de señalar las cosas es lo que distingue a los primates superiores del resto de las criaturas vivientes del reino animal, o al menos eso escucho. :)

Answer 2

Para ver qué pasa, usa el paso a paso en DrRacket. El paso a paso le permite ver todos los pasos intermedios (y avanzar y retroceder).

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

Luego elija el idioma de enseñanza "Estudiante intermedio con lambda". Luego haz clic en el botón de pasos (el triángulo verde seguido de una barra).

Este es el aspecto del primer paso:

Luego, haga un ejemplo para la segunda función y vea qué falla.