Explain the continuation example on p.137 of The Little Schemer

Question

The code in question is this:

(define multirember&co
  (lambda (a lat col)
    (cond
     ((null? lat)
      (col (quote ()) (quote ())))
     ((eq? (car lat) a)
      (multirember&co a
                      (cdr lat)
                      (lambda (newlat seen)
                        (col newlat
                             (cons (car lat) seen)))))
     (else
      (multirember&co a
                      (cdr lat)
                      (lambda (newlat seen)
                        (col (cons (car lat) newlat)
                             seen))))))

I've stared at this all day but I can't quite seem to understand it. When you recur on the function you are re-defining col but in the examples they seem to use the original definition. Why wouldn't it change. How can you recur on it without passing in the parameters newlat and seen.

It's hard to explain my question because I seem to just be missing a piece. If perhaps someone could give a more explicit walk-through than the book I may be able to understand how it works.

Answer 1

Let's step through an example; maybe that will help. :-) For simplicity, I'm just going to use list as the collector/continuation, which will just return a list with the arguments to the continuation.

(multirember&co 'foo '(foo bar) list)

At the start,

a = 'foo
lat = '(foo bar)
col = list

At the first iteration, the (eq? (car lat) a) condition matches, since lat is not empty, and the first element of lat is 'foo. This sets up the next recursion to multirember&co thusly:

a = 'foo
lat = '(bar)
col = (lambda (newlat seen)
        (list newlat (cons 'foo seen))

At the next iteration, the else matches: since lat is not empty, and the first element of lat is 'bar (and not 'foo). Thus, for the next recursion, we then have:

a = 'foo
lat = '()
col = (lambda (newlat seen)
        ((lambda (newlat seen)
           (list newlat (cons 'foo seen)))
         (cons 'bar newlat)
         seen))

For ease of human reading (and avoid confusion), we can rename the parameters (due to lexical scoping), without any change to the program's semantics:

col = (lambda (newlat1 seen1)
        ((lambda (newlat2 seen2)
           (list newlat2 (cons 'foo seen2)))
         (cons 'bar newlat1)
         seen1))

Finally, the (null? lat) clause matches, since lat is now empty. So we call

(col '() '())

which expands to:

((lambda (newlat1 seen1)
   ((lambda (newlat2 seen2)
      (list newlat2 (cons 'foo seen2)))
    (cons 'bar newlat1)
    seen1))
 '() '())

which (when substituting newlat1 = '() and seen1 = '()) becomes

((lambda (newlat2 seen2)
   (list newlat2 (cons 'foo seen2)))
 (cons 'bar '())
 '())

or (evaluating (cons 'bar '()))

((lambda (newlat2 seen2)
   (list newlat2 (cons 'foo seen2)))
 '(bar)
 '())

Now, substituting the values newlat2 = '(bar) and seen2 = '(), we get

(list '(bar) (cons 'foo '()))

or, in other words,

(list '(bar) '(foo))

to give our final result of

'((bar) (foo))

Answer 2

I found a wonderful answer here: http://www.michaelharrison.ws/weblog/?p=34

I've been struggling through this too. The key is to understand lexical scoping (for me, à la Javascript) and the inner functions passed to multirember&co on the eq and not eq branches. Understand that, and you'll understand the entire procedure.