The Little Schemer evens-only*&co

Question

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?

Answer 1

In equational pseudocode (a KRC-like notation, writing f x y for the call (f x y), where it is unambiguous), this is

evens-only*&co l col 
   = col [] 1 0                                     , IF null? l
   = evens-only*&co (cdr l) 
                    ( newl product sum =>
                        col (cons (car l) newl)
                            (opx (car l) product)
                            sum )                   , IF atom? (car l) && even? (car l)
   = evens-only*&co (cdr l) 
                    ( newl product sum =>
                        col  newl  product  (op+ (car l) sum) )      , IF atom? (car l)
   = evens-only*&co (car l) 
                    ( anewl aproduct asum =>
                         evens-only*&co (cdr l)
                                        ( dnewl dproduct dsum =>
                                             col (cons anewl    dnewl)
                                                 (opx  aproduct dproduct)
                                                 (op+  asum     dsum) ) )   , OTHERWISE

This is a CPS code which collects all evens from the input nested list (i.e. a tree) while preserving the tree structure, and also finds the product of all the evens; as for the non-evens, it sums them up:

• if l is an empty list, the three basic (identity) values are passed as arguments to col;

• if (car l) is an even number, the results of processing the (cdr l) are newl, product and sum, and then they are passed as arguments to col while the first two are augmented by consing  ⁄  multiplying with the (car l) (the even number);

• if (car l) is an atom which is not an even number, the results of processing the (cdr l) are newl, product and sum, and then they are passed as arguments to col with the third one augmented by summing with the (car l) (the non-even number atom);

• if (car l) is a list, the results of processing the (car l) are anewl, aproduct and asum, and then the results of processing the (cdr l) are dnewl, dproduct and dsum, and then the three combined results are passed as arguments to col.

[], 1 and 0 of the base case are the identity elements of the monoids of lists, numbers under multiplication, and numbers under addition, respectively. This just means special values that don't change the result, when combined into it.

As an illustration, for '((5) 2 3 4) (which is close to the example in the question), it creates the calculation

evens-only*&co [[5], 2, 3, 4] col
=
col  (cons []                   ; original structure w only the evens kept in,
           (cons 2              ;   for the car and the cdr parts
              (cons 4 [])))
     (opx 1                     ; multiply the products of evens in the car and 
          (opx 2 (opx 4 1)))    ;   in the cdr parts
     (op+ (op+ 5 0)             ; sum, for the non-evens
          (op+ 3 0))     

---

Similar to my other answer (to a sister question), here's another way to write this, with a patter-matching pseudocode (with guards):

evens-only*&co  =  g   where
  g [a, ...xs...] col 
         | pair? a    = g a  ( la pa sa =>
                         g xs ( ld pd sd =>
                                        col [la, ...ld...] (* pa pd) (+ sa sd) ) )
         | even? a    = g xs ( l p s => col [ a, ...l... ] (* a  p )       s     )
         | otherwise  = g xs ( l p s => col         l            p   (+ a  s )   )
  g []            col =                 col []              1         0

The economy (and diversity) of this notation really makes it all much clearer, easier to just see instead of getting lost in the word salad of long names for functions and variables alike, with parens overloaded as syntactic separators for list data, clause groupings (like in cond expressions), name bindings (in lambda expressions) and function call designators all looking exactly alike. The same uniformity of S-expressions notation so conducive to the ease of manipulation by a machine (i.e. lisp's read and macros) is what's detrimental to the human readability of it.

Answer 2

I have been reading How To Design Programs (felleisen et.al.). I am going through the section where they define local definitions. I have written a code that implements the above evens-only&co using a local definition. Here's what I wrote:

(define (evens-only&co l)
  (local ((define (processing-func sum prod evlst lst)
            (cond ((null? lst) (cons sum (cons prod evlst)))
                  ((atom? (car lst))
                   (cond ((even? (car lst)) (processing-func sum (* prod (car lst)) (append evlst (list (car lst))) (cdr lst)))
                         (else
                          (processing-func (+ sum (car lst)) prod evlst (cdr lst)))))
                  (else
                   (local ((define inner-lst (processing-func sum prod  '() (car lst))))
                   (processing-func (car inner-lst) (cadr inner-lst) (append evlst (list (cddr inner-lst))) (cdr lst)))))))
    (processing-func 0 1 '() l)))

For testing, when i enter (evens-only&co '((9 1 2 8) 3 10 ((9 9) 7 6) 2)) , it returns '(38 1920 (2 8) 10 (() 6) 2) as expected in the little schemer. But, my code fails in one condition: when there are no even numbers at all, the product of evens is still shown as 1. For example (evens-only&co '((9 1) 3 ((9 9) 7 ))) returns '(38 1 () (())). I guess i will need an additional function to rectify this. @melwasul: If you are not familiar with the local definition, sorry to post this here. I suggest you read HTDP too. It's an excellent book for beginners. But the guys who are experts in scheme can please post their comments on my code as well. Is my understanding of the local definition correct?

Answer 3

The answer by Jon O. is a really great in-depth explanation of underlying concepts. Though for me (and hopefully, for some other people too), understanding of concepts like this is a lot more easier when they have a visual representation.

So, I have prepared two flow-charts (similar to ones I did for multirember&co, untangling what is happening during the call of evens-only*&co

given l is:

'((9 1 2 8) 3 10 ((9 9) 7 6) 2) 

and col is:

(define the-last-friend
    (lambda (newl product sum)
        (cons sum (cons product newl))
    )
)

One flow-chart, reflecting how variables relate in different steps of recursion: Second flow-chart, showing the actual values, being passed:

My hope is, that this answer will be a decent addition to the Jon's explanation above.

Answer 4

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 length function 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 write someFunction(function (result) { ... }), and all of the code that uses result goes inside the callback function).

Here's length in continuation-passing style, just for comparison. I've called the continuation parameter return, 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 called k in this style).

(define (length/k lis return)
  (cond ((null? lis) (return 0))
        (else
         (length/k (cdr lis)
                   (lambda (cdr-len)
                     (return (+ cdr-len 1)))))))

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 else clause above says:

imagine you have the result of calling length/k on (cdr lis), and call it cdr-len, then add one and pass the result of this addition to your continuation (return).

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:

(evens-only*&co (cdr l)
                (lambda (newl product sum)
                  (col (cons (car l) newl)
                       (opx (car l) product)
                       sum)))

Imagine that you have the results of removing odd numbers, multiplying evens, and adding odd numbers from the cdr of the list, and call them newl, product, and sum respectively. cons the head of the list onto newl (since it's an even number, it should go in the result); multiply product by the head of the list (since we're calculating product of evens); leave sum alone; and pass these three values to your waiting continuation col.

Here's the case where the head of the list is an odd number:

(evens-only*&co (cdr l)
                (lambda (newl product sum)
                  (col newl product (op+ (car l) sum))))

As before, but pass the same values of newl and product to the continuation (i.e. "return" them), along with the sum of sum and 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:

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

Imagine you have the results from removing, summing and adding the numbers in (car l) and call these newl, product, and sum; then imagine you have the results from doing the same thing to (cdr l), and call them dnewl, dproduct and dsum. To your waiting continuation, give the values produced by consing newl and dnewl (since we're producing a list of lists); multiplying together product and dproduct; and adding sum and dsum.

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.