🚀 go-pugleaf

In article <1992Oct28.154755.24815@crl.dec.com> nikhil@crl.dec.com (R.S.
Nikhil) writes: 
>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.

Two questions:

1. Is this kind of "pseudocircular" programming actually allowed in existing
lazy languages?

2. Doesn't the benefits of the tail-recursive optimization in general depend
on arguments being strict? A single cell in the stack is used for each
argument, and it is overwritten at each recursive call. For non-strict
argument a closure must be kept until its value is actually needed, so a
pointer to that structure is kept in the cell. If such an un-evaluated
argument is used in a recursive call, then a new closure must be built for
each actual non-strict argument using it, even if the tail-recursive
optimization is used. So the heap will grow even though the stack will not.

A funny observation: in the particular example above, a very smart compiler
could still find a constant space implementation of f. Associativity gives
that (b+m)+2 = b+(m+2) for all values of m. A simple induction then yields
that in all calls to f, the third argument is of the form b+m where b is the
original argument.  Thus, a closure for this argument need only represent
values of the form b+m. In a recursive call f (n-1) (a+1) (b+2), where
b=b'+m (for original argument b'), we evaluate m+2 and pass a closure for
b'+m', where m'=m+2.

This optimization is of course very particular to the actual call pattern.

Bjorn Lisper