Ajudar a entender as continuações no esquema

Question

Eu tenho trabalhado ao lado O pequeno esquema Para aprender o esquema e usar o PLT-Scheme para o meu ambiente.

O pequeno esquema me ajudou tremendamente com a recursão (é direto para mim agora), mas estou preso a uma parte do livro que apresenta "colecionadores" e chama a função como um todo uma continuação.

Aqui está o código de exemplo que eles usaram. Eu entendo os elementos recursivos, mas estou preso, em particular nas funções lambda - minha mente não pode seguir o caminho e como os argumentos para essa função lambda são definidos (já que sua única chamada é chamá -los novamente em recursão, existe nenhum uso concreto no corpo da função).

Se alguém pudesse mais ou menos me dar uma quebra do caminho da computação através da recursão da função nos colecionadores da Lambda, isso pode me ajudar.

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

Agradeço antecipadamente!!

Answer 1

Tente algo mais simples para ver como isso funciona. Por exemplo, aqui está uma versão de um list-sum função que recebe um argumento de continuação (que é frequentemente chamado k):

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

O padrão básico está lá, e as partes ausentes são onde as coisas interessantes acontecem. O argumento de continuação é uma função que espera receber o resultado - por isso, se a lista for nula, fica claro que devemos enviá -lo 0, já que essa é a soma:

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

Agora, quando a lista não é nula, chamamos a função recursivamente com a cauda da lista (em outras palavras, isso é uma iteração), mas a questão é o que deve ser a continuação. Fazendo isso:

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

está claramente errado - significa que k acabará recebendo a soma de (cdr l) em vez de todo l. Em vez disso, use uma nova função lá, que resumirá o primeiro elemento de l também junto com o valor que recebe:

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

Isso está se aproximando, mas ainda errado. Mas é um bom ponto pensar em como as coisas estão funcionando - estamos ligando list-sum Com uma continuação que receberá a soma geral e adicionará o primeiro item que vemos agora. A parte que falta é evidente no fato de que estamos ignorando k. O que precisamos é compor k Com esta função - então fazemos a mesma operação de soma e depois enviamos o resultado para 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. (Btw, lembre -se de que cada um deles lambda funções tem sua própria "cópia" de l.) Você pode tentar isso com:

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

E finalmente observe que é o mesmo que:

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

Se você tornar a composição explícita.

(Você também pode usar esse código no idioma intermediário+Lambda Student e clicar no botão de passo para ver como a avaliação prossegue - isso levará um tempo para passar, mas você verá como as funções de continuação são aninhadas, cada uma, cada uma com sua própria visão da lista.)

Answer 2

Aqui está uma maneira de ajudá -lo a "ter uma ideia mais concreta". Imagine se o colecionador fosse definido assim:

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

Você pode ver no caso base, se você passar em uma lista vazia, ele chamará sua função com argumentos '(), 1 e 0. Agora, trabalhe com uma lista de um elementos e veja com o que chamará sua função. Continue trabalhando com listas mais longas e mais longas, até descobrir o que está acontecendo.

Boa sorte!