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.

Answer 1

^{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.