The Little Schemer: stuck on multiinsertLR&co example

Question

I was able to grok the multirember&co function after some work, but I can't really make much sense out of the following multiinsertLR&co code (p. 143):

(define multiinsertLR&co
  (lambda (new oldL oldR lat col)
    (cond
     ((null? lat)
      (col '() 0 0))
     ((eq? (car lat) oldL)
      (multiinsertLR&co
       new
       oldL
       oldR
       (cdr lat)
       (lambda (newlat L R) 
         (col (cons new
                    (cons oldL newlat))
              (add1 L) R))))
     ((eq? (car lat) oldR)
      (multiinsertLR&co
       new
       oldL
       oldR
       (cdr lat)
       (lambda (newlat L R)
         (col (cons oldR
                    (cons new newlat))
              L (add1 R)))))
     (else
      (multiinsertLR&co
       new
       oldL
       oldR
       (cdr lat)
       (lambda (newlat L R)
         (col (cons (car lat)
                    newlat) L R)))))))

The book doesn't seem to explain which collector one should initially pass when evaluating the function, so I used the a-friend collector and last-friend collector explained on pages 138 and 140, respectively. Evaluating the function with either collector results in the following error (using the trace function with petit chez scheme):

>> (multiinsertLR&co 'salty 'fish 'chips '(chips and fish or fish and chips) last-friend)

|(multiinsertLR&co salty fish chips (chips and fish or fish and chips)
   #<procedure>)
|(multiinsertLR&co salty fish chips (and fish or fish and chips)
   #<procedure>)
|(multiinsertLR&co salty fish chips (fish or fish and chips) #<procedure>)
|(multiinsertLR&co salty fish chips (or fish and chips) #<procedure>)
|(multiinsertLR&co salty fish chips (fish and chips) #<procedure>)
|(multiinsertLR&co salty fish chips (and chips) #<procedure>)
|(multiinsertLR&co salty fish chips (chips) #<procedure>)
|(multiinsertLR&co salty fish chips () #<procedure>)
Exception: incorrect number of arguments to #<procedure>
Type (debug) to enter the debugger.

I looked over the code several times, but couldn't find the error. If someone has any insight, please share it. If anyone could also point me to a (relatively speaking) gentle explanation of continuations with some good examples, that would be much appreciated as well.

dtg · Answer 1 · 2012-09-07T05:49:53.377

Here is the process I went through for solving the second of Chris's examples, as I thought it might be helpful for others who might be stuck. (Please correct any errors if there are any!)

;; Anonymous functions (collectors) in mutliinsertLR&co here defined as named  
;; functions for reference purposes
(define left-col
  (lambda (newlat L R)
    (col (cons new
               (cons oldL newlat))
         (add1 L) R)))              ; L counter gets incremented

(define right-col
  (lambda (new lat L R)
    (col (cons oldR
               (cons new newlat))
         L (add1 R))))              ; R counter gets incremented

(define else-col
  (lambda (newlat L R)
    (col (cons (car lat)
               (newlat) L R))))     ; neither counter gets incremented

;; Let's step through an example to see how this works:
;;
;; 1. ENTRY TO FUNCTION
;; new  = foo
;; oldL = bar
;; oldR = baz
;; lat  = (goo bar baz qux quux)
;; col  = list
;;
;; 1. Is lat null? No.
;; 2. Is car of lat equal to oldL? No.
;; 3. Is car of lat equal to oldR? No.
;; 4. Else? Yes. Recur on the function passing the new, oldL
;;    oldR, (cdr lat) and the new collector.
;;
;; 2. FIRST RECURSIVE STEP
;; new  = foo
;; oldL = bar
;; oldR = baz
;; lat  = (bar baz qux quux)
;; col  = else-col
;;
;; - Is lat null? No.
;; - Is car of lat equal to oldL? Yes. Recur on the function
;;   passing new, oldL, oldR, (cdr lat), and the new col.
;;
;; 3. SECOND RECURSIVE STEP
;; new  = foo
;; oldL = bar
;; oldR = baz
;; lat  = (baz qux quux)
;; col  = left-col
;;
;; - Is lat null? No.
;; - Is car of lat equal to oldL? No.
;; - Is car of lat equal to oldR? Yes. Recur on the function
;;   passing new, oldL, oldR, (cdr lat), and the new col.
;;
;; 4. THIRD RECURSIVE STEP
;; new  = foo
;; oldL = bar
;; oldR = baz
;; lat  = (qux quux)
;; col  = right-col
;;
;; - Is lat null? No.
;; - Is car of lat equal to oldL? No.
;; - Is car of lat equal to oldR? No.
;; - Else? Yes. Recur on the function passing new, oldL, oldR,
;;   (cdr lat) and the new collector.
;;
;; 5. FOURTH RECURSIVE STEP
;; new  = foo
;; oldL = bar
;; oldR = baz
;; lat  = (quux)
;; col  = else-col
;;
;; - Is the lat null? No.
;; - Is the car of lat equal to oldL? No.
;; - Is the car of lat equal to oldR? No.
;; - Else? Yes. Recur on the function passing new, oldL, oldR,
;;   (cdr lat) and the new collector.
;;
;; 6. FIFTH RECURSIVE STEP
;; new  = foo
;; oldL = bar
;; oldR = baz
;; lat  = ()
;; col  = else-col
;;
;; - Is the lat null? Yes. Call else-col, where newlat is (),
;;   L is 0 and R is 0.
;;
;; 7. ELSE-COL
;; newlat = ()
;; L      = 0
;; R      = 0
;; col    = else-col
;;
;; - Now call else-col on the (cons (car lat)), which is currently
;;   stored in memory as the atom "quux", onto newlat, as well as
;;   L and R.
;;
;; 8. ELSE-COL (again)
;; newlat = (quux)
;; L      = 0
;; R      = 0
;; col    = right-col
;;
;; - Now call right-col on the (cons (car lat)), which is currently
;;   stored in memory as the atom "qux", onto newlat, as well as L
;;   and R.
;;
;; 9. RIGHT-COL
;; newlat = (qux quux)
;; L      = 0
;; R      = 0
;; col    = left-col
;;
;; - Now call left-col on the cons of oldR and (cons new newlat),
;;   as well as L and the increment of R.
;;
;; 10. LEFT-COL
;; newlat = (baz foo qux quux)
;; L      = 0
;; R      = 1
;; col    = else-col
;;
;; - Now call else-col on the cons of new and (cons oldL newlat),
;;   as well as the increment of L and R.
;;
;; 11. ElSE-COL (last time)
;; newlat = (foo bar baz foo qux quux)
;; L      = 1
;; R      = 1
;; col    = list
;;
;; - Now we call list on the (cons (car lat)), which is currently
;;   stored in memory as the atom "goo", onto newlat, as well as L
;;   and R.
;; - This gives us the final, magical list:
;;   ((goo foo bar baz foo qux quux) 1 1)
;;
;; 12. FIFTH RECURSIVE STEP (redux)
;; new  = foo
;; oldL = bar
;; oldR = baz
;; lat  = (quux)
;; col  = else-col
;;
;; - Base case evaluated, with the result being
;;   ((goo foo bar baz foo qux quux) 1 1).
;; - Function ends.
;;
;; THE END

score 2 · Accepted Answer · edited May 23 '17 at 12:12

As seen in the base case in the code, your collector/continuation must take 3 arguments. It seems you passed in a function which doesn't.

It's good you worked through multirember&co: I wrote an answer about it, which you may wish to review.

Anyway, a general approach in testing these collector/continuations is to start by using list as your continuation, since list is variadic and simply returns the items given as a list. Here's an example:

> (multiinsertLR&co 'foo 'bar 'baz '(foo bar baz qux quux) list)
'((foo foo bar baz foo qux quux) 1 1)

Oh, I see two foos! Which one was inserted, and which one was in the original list?

> (multiinsertLR&co 'foo 'bar 'baz '(goo bar baz qux quux) list)
'((goo foo bar baz foo qux quux) 1 1)

Ah, so we're on to something! Any time the list contains a bar, foo is inserted before it; and any time the list contains a baz, foo is inserted after it. But the numbers?

> (multiinsertLR&co 'foo 'bar 'baz '(baz goo bar baz qux bar quux baz) list)
'((baz foo goo foo bar baz foo qux foo bar quux baz foo) 2 3)

Those numbers look like counters! Each "left" insertion increments the first counter, and each "right" insertion increments the second counter.

In looking at the code, if you look at each of the branches of the cond, you will see what happens in a left-match case, a right-match case, and a not-match case (and of course, an end-of-list case, which sets up the base/initial value). Notice how the insertion (and counter increment) happens in each case. Since you already get multirember&co, this should be fairly easy from here on. All the best!

Yes, you are absolutely right. I took a look at the stack trace again and noticed that it was failing at the terminal condition - and indeed, the `a-friend` and `last-friend` functions use two arguments instead of the required three. I will test it out again using your approach using `list` as the continuation. — dtg, Aug 31 '12 at 16:15
Also, I think what makes this function difficult to analyze is that, with each recursive step, the new continuation is composed of the previous continuation, the previous continuation before it, ..., and so on. Am I correct in this observation? — dtg, Sep 01 '12 at 01:47
And also, I think I see that each continuation is a "snapshot" of the environment and its state at any particularly point in the program... So each anonymous function, when the function is passed as an argument in each recursive step, contains the value for e.g. `(car lat)` for that precise moment, and when that function is finally evaluated when we reach the terminal condition, the state of `(car lat)` will be the same as when we initially passed it as an argument. Does this sound right? — dtg, Sep 01 '12 at 02:28

Will Ness · Answer 3 · 2019-02-22T18:56:41.427

Again rewriting this in my favorite pattern-matching pseudocode as of late,¹ we get the much more compact and visually apparent

multiinsertLR&co new oldL oldR lat col  =  g lat col 
  where
  g [a, ...t] col 
    | a == oldL  =  g t  ( newlat L R =>  col [new, oldL, ...newlat] (add1 L)  R  )
    | a == oldR  =  g t  ( newlat L R =>  col [oldR, new, ...newlat]  L  (add1 R) )
    | else       =  g t  ( newlat L R =>  col [a,         ...newlat]  L        R  )
  g [] col       =                        col []                      0        0

so L is the count of oldLs in lat; R is the count of oldRs in lat; and new is a special element that is inserted into the resulting list being built, to the right of oldR, and to the left of oldL elements in the input list-of-atoms lat:

multii&co 0 1 2 [1,4,5,2,4,5,1,4,5,1] col 
=
col [0,1,4,5, 2,0,4,5, 0,1,4,5, 0,1 ] 3 1

And that's all. With a helpful notation, it is easy enough.

¹ see this and this.

The Little Schemer: stuck on multiinsertLR&co example

3 Answers3