Ayuda para entender las Continuaciones en el Esquema

Question

He estado trabajando junto con The Little Schemer para aprender Scheme y usar PLT-Scheme para mi entorno.

El pequeño Schemer me ha ayudado enormemente con la recursividad (es sencillo para mí ahora), pero estoy atascado en una parte del libro que introduce "recolectores" y llama a la función en su conjunto una continuación.

Aquí está el código de ejemplo que han utilizado. Entiendo los elementos recursivos pero estoy atascado, en particular en las funciones lambda: mi mente no puede seguir el camino y cómo se establecen los argumentos para esa función lambda (ya que su única llamada es llamarlos nuevamente en recursión, hay sin uso concreto dentro del cuerpo de la función).

Si alguien podría más o menos darme un desglose de la ruta de cálculo a través de la recursión de la función en los colectores lambda, eso puede ayudarme.

;; Build a nested list of even numbers by removing the odd ones from its 
;; argument and simultaneously multiply the even numbers and sum the odd 
;; numbers that occur in its argument. 
(define (even-only-collector l col) 
    (cond 
    ((null? l) 
     (col (quote()) 1 0)) 
    ((atom? (car l)) 
     (cond 
     ((even? (car l)) 
      (even-only-collector (cdr l) 
      (lambda (newl p s) 
       (col (cons (car l) newl) 
       (* (car l) p) s)))) 
     (else 
      (even-only-collector (cdr l) 
      (lambda (newl p s) 
       (col newl 
       p (+ (car l) s))))))) 
    (else 
     (even-only-collector (car l) 
     (lambda (al ap as) 
      (even-only-collector (cdr l) 
      (lambda (dl dp ds) 
       (col (cons al dl) 
       (* ap dp) 
       (+ as ds))))))))) 

;; The collector function 
(define (collector newl product sum) 
    (cons sum 
    (cons product newl))) 

Gracias de antemano !!

Answer 1

Pruebe algo más simple para ver cómo funciona esto. Por ejemplo, he aquí una versión de una función list-sum que recibe un argumento de continuidad (que a menudo se llama k):

(define (list-sum l k) 
    (if (null? l) 
    ??? 
    (list-sum (cdr l) ???))) 

El patrón básico está ahí, y las partes que faltan son donde suceden las cosas interesantes. El argumento de continuación es una función que espera recibir el resultado - por lo que si la lista es nulo, está claro que debemos enviarlo 0, ya que es la suma:

(define (list-sum l k) 
    (if (null? l) 
    (k 0) 
    (list-sum (cdr l) ???))) 

Ahora, cuando la lista no es null, llamamos a la función recursivamente con la cola de la lista (en otras palabras, esta es una iteración), pero la pregunta es ¿cuál debería ser la continuación? Hacer esto:

(define (list-sum l k) 
    (if (null? l) 
    (k 0) 
    (list-sum (cdr l) k))) 

es claramente erróneo - significa que k será finalmente recibir la suma de la (cdr l) en lugar de todos l. En su lugar, utilice una nueva función allí, que resumir el primer elemento de l también junto con el valor que recibe:

(define (list-sum l k) 
    (if (null? l) 
    (k 0) 
    (list-sum (cdr l) (lambda (sum) (+ (car l) sum))))) 

Esto es cada vez más cerca, pero sigue siendo incorrecto. Pero es un buen punto para pensar cómo funcionan las cosas: llamamos al list-sum con una continuación que recibirá la suma total y agregaremos el primer elemento que ahora vemos. La parte faltante es evidente en el hecho de que estamos ignorando k.Lo que necesitamos es a componer k con esta función - por lo que hacemos la misma operación de suma, a continuación, enviar el resultado al k:

(define (list-sum l k) 
    (if (null? l) 
    (k 0) 
    (list-sum (cdr l) (compose k (lambda (s) (+ s (car l))))))) 

que finalmente está funcionando. (Por cierto, recordar que cada uno de estos lambda funciones tiene su propia "copia" de l.) Se puede probar esto con:

(list-sum '(1 2 3 4) (lambda (x) x)) 

Y finalmente en cuenta que esto es lo mismo que:

(define (list-sum l k) 
    (if (null? l) 
    (k 0) 
    (list-sum (cdr l) (lambda (s) (k (+ s (car l))))))) 

si haces que la composición sea explícita

(También puede usar este código en el idioma intermedio + estudiante de lambda, y hacer clic en el botón de paso para ver cómo procede la evaluación; esto llevará un tiempo para revisarlo, pero verá cómo funcionan las funciones de continuación conseguir anidados, cada uno con su propio punto de vista de la lista)

Answer 2

Aquí hay una manera de ayudarlo a "obtener una idea más concreta". Imagínese si el colector se define así:

(define (collector l p s) 
    (display l) 
    (newline) 
    (display p) 
    (newline) 
    (display s) 
    (newline)) 

Se puede ver en el caso base, si se pasa en una lista vacía, se llamará a su función con argumentos '(), 1 y 0. Ahora, el trabajo con una lista de un elemento, y vea con qué llamará a su función. Siga trabajando con listas cada vez más largas, hasta que descubra qué está pasando.

¡Buena suerte!