Ayuda a comprender las continuaciones en el esquema

Question

He estado trabajando junto El pequeño esquema Aprender esquema y usar PLT-Scheme para mi entorno.

El pequeño esquema Me ha ayudado enormemente con la recursión (ahora es sencillo para mí), pero estoy atrapado en una parte del libro que presenta "coleccionistas" y llama a la función en su conjunto una continuación.

Aquí está el código de ejemplo que han usado. Entiendo los elementos recursivos, pero estoy atrapado, en particular en las funciones de 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 No se usa concreto dentro del cuerpo de la función).

Si alguien pudiera darme un desglose de la ruta de cálculo a través de la recursión de la función en los coleccionistas 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

Prueba algo más simple para ver cómo funciona esto. Por ejemplo, aquí hay una versión de un list-sum función que recibe un argumento de continuación (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 faltantes 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 nula, está claro que debemos enviarla 0, ya que esa es la suma:

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

Ahora, cuando la lista no es nula, llamamos a la función de manera recursiva con la cola de la lista (en otras palabras, esto es una iteración), pero la pregunta es lo que debería ser la continuación. Haciendo esto:

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

está claramente equivocado, significa que k eventualmente recibirá la suma de (cdr l) en lugar de todo l. En su lugar, use una nueva función allí, que resumirá el primer elemento de l demasiado 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 se está acercando, pero aún está equivocado. Pero es un buen punto pensar en cómo funcionan las cosas, estamos llamando list-sum Con una continuación que recibirá la suma general y agregue el primer elemento que vemos ahora. La parte faltante es evidente en el hecho de que estamos ignorando k. Lo que necesitamos es componer k con esta función, por lo que hacemos la misma operación de suma, luego enviamos el resultado a 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, recuerda que cada uno de estos lambda las funciones tienen su propia "copia" de l.) Puedes probar esto con:

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

Y finalmente tenga 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 hace explícita la composición.

(También puede usar este código en el idioma intermedio+estudiante lambda, y hacer clic en el botón Paso para ver cómo procede la evaluación; esto llevará un tiempo para pasar, pero verá cómo las funciones de continuación se anidan, cada uno. con su propia vista de la lista).

Answer 2

Aquí hay una forma de ayudarlo a "obtener una idea más concreta". Imagínese si el coleccionista se definiera así:

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

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

¡Buena suerte!