RE: how to tail recurse

Subject: RE: how to tail recurse
From: "Frank A. Christoph" <christo@xxxxxxxxxxxxxxxxxx>
Date: Thu, 23 Jul 1998 11:12:33 +0900
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,


>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:

Current Thread
  • how to tail recurse
    • Louis-Dominique Dubeau - from mail1.ability.netby (8.8.5/8.6.12) with ESMTP id JAA02198Wed, 22 Jul 1998 09:53:45 -0400 (EDT)
      • Toby Speight - from mail1.ability.netby (8.8.5/8.6.12) with ESMTP id LAA05285Wed, 22 Jul 1998 11:02:12 -0400 (EDT)
      • Toby Speight - from mail1.ability.netby (8.8.5/8.6.12) with ESMTP id LAA06170Wed, 22 Jul 1998 11:04:34 -0400 (EDT)
      • <Possible follow-ups>
      • Frank A. Christoph - from mail1.ability.netby (8.8.5/8.6.12) with ESMTP id WAA25717Wed, 22 Jul 1998 22:04:43 -0400 (EDT) <=