Aiuto per capire continuazioni in Scheme

Question

Ho lavorato a fianco di The Little Schemer per imparare Scheme e l'utilizzo di PLT-Scheme per il mio ambiente.

The Little Schemer mi ha aiutato enormemente con la ricorsione (è semplice per me ora), ma mi sono bloccato su una porzione del libro che introduce "collezionisti" e chiama la funzione nel suo complesso una continuazione.

Ecco il codice di esempio che hanno usato. Capisco gli elementi ricorsivi ma sono bloccati, in particolare sulle funzioni lambda - la mia mente non può seguire il percorso e di come gli argomenti per quella funzione lambda sono impostati (dal momento che il loro unico invito è quello di chiamare di nuovo in ricorsione, non v'è nessun uso di cemento all'interno del corpo della funzione).

Se qualcuno potesse più o meno darmi una ripartizione del percorso di calcolo attraverso la ricorsività della funzione nei collettori lambda, che possono aiutare me.

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

Grazie in anticipo !!

Answer 1

Provare qualcosa di più semplice per vedere come funziona. Ad esempio, ecco una versione di una funzione list-sum che riceve un argomento di continuazione (che viene spesso chiamato k):

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

Il modello di base è lì, e le parti mancanti sono dove accadono le cose interessanti. L'argomento continuazione è una funzione che si aspetta di ricevere il risultato - così se la lista è nullo, è chiaro che dovremmo inviarlo 0, dal momento che è la somma:

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

Ora, quando la lista non è nullo, chiamiamo la funzione ricorsivamente con la coda della lista (in altre parole, si tratta di un'iterazione), ma il problema è quello che dovrebbe essere la continuazione. In questo modo:

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

è chiaramente sbagliato - vuol dire che k finirà per ricevere il la somma di (cdr l) invece di tutti di l. Invece, utilizzare una nuova funzione lì, che riassumere il primo elemento di l anche insieme al valore che riceve:

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

Questa è sempre più vicino, ma ancora sbagliata. Ma è un buon punto di pensare a come le cose stanno funzionando - stiamo chiamando list-sum con una continuazione che vi si riceverà la somma complessiva, e aggiungere il primo elemento che vediamo oggi ad esso. La parte mancante è evidente nel fatto che stiamo ignorando k. Ciò di cui abbiamo bisogno è di composizione k con questa funzione - così noi la stessa operazione di somma, quindi inviare il risultato al k:

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

che sta finalmente lavorando. (A proposito, ricordate che ciascuna di queste funzioni lambda ha la sua "copia" di l.) Si può provare questo con:

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

E infine notare che questa è la stessa:

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

se si effettua la composizione esplicito.

(È inoltre possibile utilizzare questo codice nel linguaggio studente intermedio + lambda, e fare clic sul pulsante passo-passo per vedere come i proventi di valutazione - ci vorrà un po 'per andare oltre, ma vedrete come le funzioni di continuazione ottengono nidificati, ciascuno con il proprio punto di vista della lista.)

Answer 2

Ecco un modo per aiutare a "ottenere un'idea più concreta". Immaginate se il collettore sono stati definiti in tal modo:

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

Si può vedere nel caso di base, se si passa in una lista vuota, si chiamerà la funzione con gli argomenti '(), 1 e 0. Ora, il lavoro con una lista di un elemento e vedere quello che chiameremo la funzione con. Continuare a lavorare con liste più lunghe e più a lungo, fino a capire che cosa sta succedendo.

In bocca al lupo!