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.
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,
"identity" is defined to be
that function which, when given
two arguments,
l
andcol
, will-- in case
(null? l)
is true --OK, this means
l
is a list, NBreturn the value of the expression
(col '())
col
is a function, expecting of one argument, as one possibility an empty list,or else it will make a tail recursive call with the updated values, one being
(cdr l)
,and the other a newly constructed function, such that when it will be called with its argument
newl
(a list, just as was expected ofcol
-- because it appears in the same role, it must follow the same conventions), will in turn call the functioncol
with the non-empty list resulting from prefixing(car l)
to the listnewl
.Thus this function,
identity
, follows the equationsand
describing an iterative process, the one which turns the function call
into the call
recreating the same exact list anew, before feeding it as an argument to the function
col
it has been supplied with.Given how those "collector" functions are defined in the
identity
definition, callingfor any list
xs
and some "collector" functioncol
, is equivalent to callingso 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 asThis 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
(or we can write this in a pseudocode, as)
col2
handles its argumentr
by passing(cons x r)
to the previous handlercol
. This meansr
is transformed into(cons x r)
, but instead of being returned as a value, it is fed intocol
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:
update: in a pattern-matching pseudocode I've been fond of using as of late, we could write
and
which hopefully is so much visually apparent that it almost needs no explanation!