scheme - Ayudar a entender las continuaciones en el esquema

lisp racket

Question

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

The Little Schemer me ha ayudado enormemente con la recursión (ahora es muy sencillo para mí), pero estoy atascado en una parte del libro que presenta a los "coleccionistas" y considera que la función en su conjunto es 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 la ruta 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 uso concreto dentro del cuerpo de la función).

Si alguien pudiera darme más o menos un desglose de la ruta de cálculo a través de la recursión de la función en los recopiladores de lambda, eso podría 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

Aquí hay una manera de ayudarlo a "obtener una idea más concreta". Imagina 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 cómo llamará a su funcionar con. Siga trabajando con listas cada vez más largas, hasta que descubra qué está pasando.

¡Buena suerte!

Answer 2

Intenta algo más simple para ver cómo funciona esto. Por ejemplo, aquí hay una versión de una función de list-sum 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 tanto, si la lista es nula, está claro que debemos enviarlo a 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 recursivamente con la cola de la lista (en otras palabras, esto es una iteración), pero la pregunta es cuál debe 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 finalmente recibirá la suma de (cdr l) lugar de toda l . En su lugar, use 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 se está acercando, pero sigue siendo incorrecto. Pero es un buen punto para pensar cómo funcionan las cosas: estamos llamando a list-sum con una continuación que recibirá la suma global y agregaremos 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, recuerde que cada una de estas funciones lambda tiene su propia "copia" de l .) Puede intentar esto con:

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

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

(También puede usar este código en el idioma del estudiante intermedio + lambda, y hacer clic en el botón paso a paso para ver cómo procede la evaluación. Esto tomará un tiempo para revisar, pero verá cómo se anidan las funciones de continuación, cada una con su propia vista de la lista.