🚀 go-pugleaf

In article <WAND.92Oct28092609@dec5120z.ccs.northeastern.edu>, wand@dec5120z.ccs.northeastern.edu (Mitchell Wand) writes:
> The Scheme language standard (IEEE Std1178-1990) requires that tail-recursive
> procedures be executed iteratively:
> 
> "Implementations of Scheme are required to be properly tail-recursive.  This
> allows the execution of an iterative computation in constant space, even if
> the iterative compuation is described by a syntactically recursive procedure.
> ..."
> 
> I don't know offhand how specific the Haskell or ML definitions are on this
> subject. 
> 
> --Mitch


I don't think you can guarantee constant space for all tail-recursive functions in a
non-strict language like Haskell.  Consider this (tail-recursive) function:

    f  n  a  b  =  if (n == 0) then
                      (a,b)
                   else
                      f (n-1) (a+1) (b+2)

which simply increments a and b by n and 2n, respectively, and returns them.
In a non-strict language, you can feed an output back to an input, e.g.:

    (x,y) = f 10 100 x                        (A)

i.e., it increments 100 by 10, binds x to the result, feeds it back as the second
argument which gets incremented by 20, and binds y to that result.  The net effect is
to bind x to 110 and y to 130.

Conceptually, f has to ``unfold'' completely before you can ``recover'' the ``first
iteration'' of f, because the first iteration depends on the last iteration.  In other
words, you need O(n) space (of course, some implementations may use constant stack
space for f, but they'll build an O(n) structure in the heap corresponding to the
pending b-increments).

Bindings like (A) are disallowed in strict languages like Scheme and ML, so these
languages can always run f in constant space.

Nikhil (nikhil@crl.dec.com)