How do collector functions work in Scheme?

Question

I am having trouble understanding the use of collector functions in Scheme. I am using the book "The Little Schemer" (by Daniel P. Friedman and Matthias Felleisen). A comprehensive example with some explanation would help me massively. An example of a function using a collector function is the following snippet:

(define identity
  (lambda (l col)
    (cond
      ((null? l) (col '()))
      (else (identity
              (cdr l)
              (lambda (newl)
                (col (cons (car l) newl))))))))

... with an example call being (identity '(a b c) self) and the self-function being (define self (lambda (x) x)). The identity function returns the given list l, so the output of the given call would be (a b c). The exact language used is the R5RS Legacy-language.

Radiate

Check out my answer to Building the built-in procedure “build-list” in Racket – I didn't know this technique was used in the The Little Schemer. Now I feel compelled to read it! – Marqueritemarques

Answer 1

Given how those "collector" functions are defined in the identity definition, calling

(identity xs col)

for any list xs and some "collector" function col, is equivalent to calling

(col xs)

so the same list will be "returned" i.e. passed to its argument "collector" / continuation function col. That explains its name, identity, then.

For comparison, a reverse could be coded as

(define reverse     ; to be called as e.g. (reverse l display)
  (lambda (l col)
    (cond
      ((null? l) (col '()))        ; a reversed empty list is empty
      (else (reverse (cdr l)       ; a reversed (cdr l) is newl --
                     (lambda (newl)    ; what shall I do with it when it's ready?
                       (col            ; append (car l) at its end and let col
                          (append newl                           ; deal with it!
                                  (list (car l))))))))))

This style of programming is known as continuation-passing style: each function is passed a "continuation" that is assumed that it will be passed the result of the rest of computation, so that the original continuation / collector function will be passed the final result eventually. Each collector's argument represents the future "result" it will receive, and the collector function itself then specifies how it is to be handled then.

Don't get confused by the terminology: these functions are not "continuations" captured by the call/cc function, they are normal Scheme functions, representing "what's to be done next".

The definition can be read as

identity :
  to transform a list xs 
        with a collector function col,
    is 
    | to call (col xs)                              , if xs is empty, or
    | to transform (cdr xs)  
        with a new collector function col2  
        such that
              (col2 r)  =  (col (cons (car xs) r))  , otherwise.

(or we can write this in a pseudocode, as)

(identity list col)  =
  | empty? list           ->  (col list)
  | match? list (x . xs)  ->  (identity xs col2)
                                where 
                                (col2 r)  =  (col (cons x r))

col2 handles its argument r by passing (cons x r) to the previous handler col. This means r is transformed into (cons x r), but instead of being returned as a value, it is fed into col for further processing. Thus we "return" the new value (cons x r) by passing it to the previous "collector".

A sample call, as an illustration:

(identity (list 1 2 3) display)     

= (identity (list 2 3) k1)
      ; k1 =  (lambda (r1) (display (cons 1 r1)))           =  display ° {cons 1}

= (identity (list 3)  k2)
      ; k2 =  (lambda (r2) (k1 (cons 2 r2)))                     =  k1 ° {cons 2} 

= (identity (list )  k3)
      ; k3 =  (lambda (r3) (k2 (cons 3 r3)))                     =  k2 ° {cons 3} 

= (k3 '())                        ; (((display ° {cons 1}) ° {cons 2}) ° {cons 3}) []

= (k2 (cons 3 '()))                    ; ((display ° {cons 1}) ° {cons 2}) [3]

= (k1 (cons 2 (list 3)))                    ; (display ° {cons 1}) [2,3]

= (display (cons 1 (list 2 3)))                  ; display [1,2,3]

= (display (list 1 2 3))

---

update: in a pattern-matching pseudocode I've been fond of using as of late, we could write

identity []        col  =  col []
identity [a, ...d] col  =  identity d ( newl =>  col [a, ...newl] )

and

reverse  []        col  =  col []
reverse  [a, ...d] col  =  reverse  d ( newl =>  col [...newl, a] )

which hopefully is so much visually apparent that it almost needs no explanation!

Thill

Am I right to think, that it's just some kind of lazy-execution structure? – Purr

Not necessarily. But anything can be lazy if you put it behind another lambda. You are in charge here, with the continuation-passing. The "LiSP in Small Pieces" book uses it in its chapter on denotational semantics extensively, to give various implementations, IIRC. – Thill

Answer 2

^{I'm adding the second answer in the hopes it can clarify the remaining doubts in case you have any (as the lack of the "accepted" mark would indicate).}

In the voice of Gerald J. Sussman, as heard/seen in the SICP lectures of which the videos are available here and there on the internet tubes, we can read it as we are writing it,

(define identity

"identity" is defined to be

  (lambda

that function which, when given

           (l col)

two arguments, l and col, will

    (cond
      ((null? l)

-- in case (null? l) is true --

• OK, this means l is a list, NB

                 (col '()))
  

return the value of the expression (col '())

• OK, this now means col is a function, expecting of one argument, as one possibility an empty list,

      (else (identity (cdr l)

or else it will make a tail recursive call with the updated values, one being (cdr l),

                      (lambda (newl)
                        (col (cons (car l) newl)))))))

and the other a newly constructed function, such that when it will be called with its argument newl (a list, just as was expected of col -- because it appears in the same role, it must follow the same conventions), will in turn call the function col with the non-empty list resulting from prefixing (car l) to the list newl.

Thus this function, identity, follows the equations

( identity   (cons (car l) (cdr l))           col                        )
==
( identity       (cdr l)     (lambda (newl)  (col  (cons (car l) newl))) )

and

( identity   '()   col )
==
( col        '()       )

describing an iterative process, the one which turns the function call

(identity [a,      b,      c, ...,    n]    col      )

into the call

(col
     (cons a (cons b (cons c ... (cons n '()) ... ))))

recreating the same exact list anew, before feeding it as an argument to the function col it has been supplied with.

Thill