I'm having difficulty understanding what's going on with The Little Schemer's evens-only*&co example on page 145.
Here's the code:
(define evens-only*&co
(lambda (l col)
(cond
((null? l)
(col '() 1 0))
((atom? (car l))
(cond
((even? (car l))
(evens-only*&co (cdr l)
(lambda (newl product sum)
(col (cons (car l) newl)
(opx (car l) product)
sum))))
(else
(evens-only*&co (cdr l)
(lambda (newl product sum)
(col newl product (op+ (car l) sum)))))))
(else
(evens-only*&co (car l)
(lambda (newl product sum)
(evens-only*&co (cdr l)
(lambda (dnewl dproduct dsum)
(col (cons newl dnewl)
(opx product dproduct)
(op+ sum dsum))))))))))
The initial col can be:
(define evens-results
(lambda (newl product sum)
(cons sum (cons product newl))))
What I'm not getting is, with l as '((1) 2 3), it goes immediately into the final else with (car l) as (1) and (cdr l) as (2 3). Good, but my mind goes blank trying to sort out the dnewl, dproduct, dsum from the newl, product, sum. It also would be helpful if somebody could coach me on how to set up DrRacket or Chez Scheme or MIT-Scheme for running a stepper.
But maybe I'm spazzing too early. Is any beginner reading this for the first time actually supposed to understand this wild continuation?
I found this section confusing on first reading too, and only started to get it after I'd read up elsewhere about continuations and continuation-passing style (which is what this is).
At the risk of explaining something that you already get, one way of looking at it that helped me is to think of the "collector" or "continuation" as replacing the normal way for the function to return values. In the normal style of programming, you call a function, receive a value, and do something with it in the caller. For example, the standard recursive
lengthfunction includes the expression(+ 1 (length (cdr list)))for the non-empty case. That means that once(length (cdr list))returns a value, there's a computation waiting to happen with whatever value it produces, which we could think of as(+ 1 [returned value]). In normal programming, the interpreter keeps track of these pending computations, which tend to "stack up", as you can see in the first couple of chapters of the book. For example, in calculating the length of a list recursively we have a nest of "waiting computations" as many levels deep as the list is long.In continuation-passing style, instead of calling a function and using the returned result in the calling function, we tell the function what to do when it produces its value by providing it with a "continuation" to call. (This is similar to what you have to do with callbacks in asynchronous Javascript programming, for example: instead of writing
result = someFunction();you writesomeFunction(function (result) { ... }), and all of the code that usesresultgoes inside the callback function).Here's
lengthin continuation-passing style, just for comparison. I've called the continuation parameterreturn, which should suggest how it functions here, but remember that it's just a normal Scheme variable like any other. (Often the continuation parameter is calledkin this style).There is a helpful tip for reading this kind of code in an article on continuations by Little Schemer co-author Dan Friedman. (See section II-5 beginning on page 8). Paraphrasing, here's what the
elseclause above says:Note that this is almost exactly what the interpreter has to do in evaluating
(+ 1 (length (cdr lis)))in the normal version of the function (except that it doesn't have to give a name to the intermediate result(length (cdr lis)). By passing around the continuations or callbacks we've made the control flow (and the names of intermediate values) explicit, instead of having the interpreter keep track of it.Let's apply this method to each clause in
evens-only*&co. It's slightly complicated here by the fact that this function produces three values rather than one: the nested list with odd numbers removed; the product of the even numbers; and the sum of the odd numbers. Here's the first clause, where(car l)is known to be an even number:Here's the case where the head of the list is an odd number:
As before, but pass the same values of
newlandproductto the continuation (i.e. "return" them), along with the sum ofsumand the head of the list, since we're summing up odd numbers.And here's the last one, where
(car l)is a nested list, and which is slightly complicated by the double recursion:Notice: each time we make a recursive call, we construct a new continuation for the recursive call, which "closes over" the current values of the argument,
l, and the return continuation -col, in other words, you can think of the chain of continuations which we build up during the recursion as modelling the "call stack" of a more conventionally written function!Hope that gives part of an answer to your question. If I've gone a little overboard, it's only because I thought that, after recursion itself, continuations are the second really neat, mind-expanding idea in The Little Schemer and programming in general.