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!!

Scevo

@lpthnc: have you looked at newLISP? – Scevo

Answer 1

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

Gravettian

Thank you so much, this is the answer I was looking for - the tip for the stepper is particularly helpful. Thank you! – Scevo

I just ran your exercise with the intermediate student with lambda language and stepper; I can't begin to tell you how immensely helpful that was. Being able to see the path of execution that way cleared up all of my confusion!! Thank you very much. – Scevo

very helpful, Eli, thank you. I didn't know about the student languages and steppers, very nice. – Affine

@EliBarzilay , thank you. I'm wondering what's the benefit of using continuation here? This shall work, and seen to be a little simpler:(define list-sum (lambda (l) (cond ((null? l) 0) (else (+ (car l) (list-sum (cdr l))))))) (list-sum '(1 2 3 4)) – Griddle

@liweijian: there's no real benefit here, it was just a demonstration. – Gravettian

+1: Thank you for this great example! I had been wondering what continuations are for a while and now I think I got it! (I solved your example before looking up the solution you give in the second half of your answer.) – Sentimentality

Answer 2

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!

Entablement

So, I understand exactly what happens when I pass in an empty list and I can see what is happening when I pass in smaller and successively larger lists; but I'm not grasping the "how" of those lambda expressions that have the collector for their body... – Scevo

Have you ever worked with an object-oriented language? If so, have you heard of the Decorator Pattern? Each of the lambdas are basically decorating your collector with one more layer. – Entablement

I have, but only in PHP and some Python. I've heard of Decorators in Python but never actually studied them. So is this function technically called a continuation too? – Scevo