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

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

What the link above (http://www.michaelharrison.ws/weblog/?p=34) explains well is how this whole exercise is about avoiding the imperative programming (C, Java) need to declare two "holder" or "collector" variables ( or lists, vectors) explicitly in memory to catch your answers as you iterate through the list. With FP language Scheme's use of continuation, you do not "push" the test results as you step through (strawberries tuna and swordfish) into any separately created "baskets;" instead, you are consing together two lists as you send the appropriate consing functions -- one for eq? true, the other for eq? false -- through the recurs . . . finally ending up at the third col function which, in TLS's first example, is "a-friend" which asks whether the list built to hold all the matches is empty (null?). TLS then asks you to "run" multirember&co again with a new "last" col that merely asks the list containing all the "not tuna" atoms how many it contains ("last-friend"). So there are two "first class" functions being used to work with the task of collecting, i.e. building two separate lists, then at the end of the recursion unwinding, the original col ("a-friend") ask the final question. Maybe the name "multirember&co" is not the greatest name, because it really doesn't rebuild the list minus the atom to be removed; rather, it builds two separate lists -- which never get displayed -- then applies the final col (a-friend or last-friend) . . . which displays either #t or #f, or the length of the "not tuna" list.

Here's some output:

> (multirember&co 'tuna '(and tuna) a-friend)
#f
> (multirember&co 'tuna '(and not) a-friend)
#t

Here's a col to give back a list of non-matches:

(define list-not  (lambda (x y) x))

and its use:

> (multirember&co 'tuna '(and not) list-not)
(and not)

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.

I have struggled myself, to understand what is happening inside the multirember&co, for quite a while. The problem is that the moment I thought I've got it - next task/example proved I have not.

What helped me was putting together a visual representation of what is happening (for me text walkthroughs are tough to grasp, for some reason).

So, I have put together two flow-charts:

One, just showing the relations between different steps of recursion:

---

And another one, reflecting actual values:



Now, whenever I feel like I'm loosing 'the thread of an argument' again, I just refer to this flow-charts and it puts me back on track.

Another thing I've understood after looking at the 'whole picture' via flow-chart, is that a-friend function is simply checks whether seen holds any values or not (though it returns it the other way around i.e. #f when there values in seen and #t when seen is empty, which might be confusing.

P.S.: I did similar flow-charts for evens-only*&co, which appears later in the book.