RE: how to tail recurse

["Frank A. Christoph" <christo@xxxxxxxxxxxxxxxxxx>]

Congratulations, you have just rediscovered continuation-passing style
(CPS).  In the general case, the "state" needed for the recursion is held
temporarily in a closure which gets built up on the way down to the base
case, and then invoked once on the way up.  The closure is called a
continuation, since it records "what happens after" you evaluate a term.

(define (succ n) (+ 1 n))
(define (id x) x)
(define (comp f g) (lambda (x) (f (g x))))

(define (depth-cps node kont)
 (let ((par (parent node)))
  (if (node-list-empty? p)
   (kont 0)
   (depth-cps par (comp kont succ)))))

(define (depth node)
 (depth-cps node id))

Your version is a specialization of depth-cps, in exactly the same sense
(incidentally) that a derived class is a specialization of a base class in
an object-based programming language.  Continuations are mind-bogglingly
useful things that can be used to obtain iterative and, when they are
first-class objects, even concurrent behavior.

You should be able to find a treatment of continuations and CPS in any good
Scheme textbook or, indeed, any good textbook on functional languages,
period.

--FC

>In my first DSSSL project, I had the need for a function giving me the
>depth of an element in the SGML structure.  I had this depth function
>defined thus:
>
>(define (depth node)
>  (let ((my-parent (parent node)))
>    (if (node-list-empty? my-parent)
>      0
>      (+ 1 (depth my-parent)))))
>
>This is clearly not tail recursive since it does something to the
>value returned by the recursive call.  It occured to me that to make
>it tail recursive, the solution was to carry the state forward as a
>parameter of the recursive call.  The result is this:
>
>(define (depth-recur node curdepth)
>  (let ((my-parent (parent node)))
>    (if (node-list-empty? my-parent)
>      curdepth
>      (depth-recur my-parent (+ 1 curdepth)))))
>
>(define (depth node)
>  (depth-recur node 0))
>
>The above can be taken as an illustration on how to transform a
>non-tail-recursive function into a tail-recursive one.  I think the
>key idea there is to "carry the state forward as a parameter of the
>recursive call".



 DSSSList info and archive:  http://www.mulberrytech.com/dsssl/dssslist