Help understanding Continuations in Scheme

Question

I have been working alongside The Little Schemer to learn Scheme and using PLT-Scheme for my environment.

The Little Schemer has helped me tremendously with recursion (it is straightforward for me now) but I'm stuck on a portion of the book that introduces "collectors" and calls the function as a whole a continuation.

Here is the example code they have used. I understand the recursive elements but I am stuck, in particular on the lambda functions - my mind can't follow the path and how the arguments for that lambda function are set (since their only call is to call them again in recursion, there is no concrete use within the function body).

If someone could more-or-less give me a break down of the path of computation through the recursion of the function into the lambda collectors, that may help 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)))

Thank you in advance!!

Answer 1

Here's one way to help you "get a more concrete idea". Imagine if the collector were defined thus:

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

You can see in the base case, if you pass in an empty list, it will call your function with arguments '(), 1, and 0. Now, work with a one-element list, and see what it'll call your function with. Keep working up with longer and longer lists, until you figure out what's going on.

Good luck!

Answer 2

Try something simpler to see how this works. For example, here's a version of a list-sum function that receives a continuation argument (which is often called k):

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

The basic pattern is there, and the missing parts are where the interesting things happen. The continuation argument is a function that expects to receive the result -- so if the list is null, it's clear that we should send it 0, since that is the sum:

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

Now, when the list is not null, we call the function recursively with the list's tail (in other words, this is an iteration), but the question is what should the continuation be. Doing this:

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

is clearly wrong -- it means that k will eventually receive the the sum of (cdr l) instead of all of l. Instead, use a new function there, which will sum up the first element of l too along with the value that it receives:

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

This is getting closer, but still wrong. But it's a good point to think about how things are working -- we're calling list-sum with a continuation that will itself receive the overall sum, and add the first item we see now to it. The missing part is evident in the fact that we're ignoring k. What we need is to compose k with this function -- so we do the same sum operation, then send the result to k:

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

which is finally working. (BTW, remember that each of these lambda functions has its own "copy" of l.) You can try this with:

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

And finally note that this is the same as:

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

if you make the composition explicit.

(You can also use this code in the intermediate+lambda student language, and click the stepper button to see how the evaluation proceeds -- this will take a while to go over, but you'll see how the continuation functions get nested, each with it's own view of the list.)