🚀 go-pugleaf

bjornl@sics.se (Bj|rn Lisper) writes:
    > 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?

Absolutely!  (and Karl-Filip Faxen shows a Haskell run of this example in his message).

Further, there are many examples where this style is useful:

    - Here is an Id program to compute an array of the first 100 Fibonacci numbers:

         {  A = {array (1,100) of
                 | [j] = 1               || j <- 1 to 2
                 | [j] = A[j-1] + A[j-2] || j <- 3 to 100 }
         In
            A }

      It uses this kind of circularity: A is defined in terms of A without any
      intervening lambda; this can't be expressed in strict languages.  And, it
      is trivially implemented in a non-strict language to construct exactly one
      size-100 array, whereas in a strict, purely functional language,  the natural
      way to define it is to build it incrementally, one location at a time, and
      then rely on array optimizations to avoid building 100 arrays of size 100.

    - Thomas Johnsson at Chalmers did some work on expressing attribute grammars
      using functional languages and it uses this kind of circularity in an
      essential way.

    - John Launchbury at Glasgow (and probably others) did some work on expressing parsers
      using higher-order  parsing combinators (such as ``sequence'', ``alternate'',
      ``star'', ``plus'', ...) and these programs also use this circularity in an
      essential way.

Further, (and I can hear many people groan because they've heard this from me a million
times!): you don't need laziness, just non-strictness (laziness is a stronger requirement
than non-strictness).  All the above examples work in Id, which is a non-strict, but not
lazy language.

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

Yes, this is what I meant when I said that some non-strict language implementations
will indeed run F with constant stack space, but they will build an O(n) structure
in the heap corresponding to ((((((b+2)+2)...)+2), i.e., you have to pay O(n) space
somewhere.

However, there are two separate ``benefits'' of tail-recursion optimization:

(1) ``short-circuited returns'':  if you have a chain of tail-calls:

              F -> G -> ... -> H

     then H can return its result directly to the original caller, instead of
     hopping back through ... G, F, ..  This is may be especially important in
     a parallel implementation, where returning results can involve communication.

(2)  Constant space execution.

In a non-strict language, you can still do optimization (1), but as I showed, you can't
always do optimization (2).

Note that optimization (2) does not imply using exactly one stack frame.  You can unfold
to any fixed amount, say 5 frames, and use them in a ``circular'' fashion (frame 1 sends
args to frame 2, which sends args to frame 3, ... frame 5 sends args to frame 1...).  This
is especially useful, again, in a parallel language, where you can get some parallelism
between iterations.

In the Id language, the above concept is called a ``bounded loop.''  The programmer can
annotate that he wants the constant-space optimization, and the degree of unfolding.  But,
the Id manual explicitly warns that if your loop has circular dependencies of the kind
we've been discussing, then bounding a loop may result in deadlock. 

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

True.  I tried to pick a simple arithmetic example to demonstrate the original point. In
general, I'm pessimistic about compiler optimizations for this, since the question of
whether or not F can run in constant space depends on the context of its call (in a strict
language, it is independent of context).

Karl-Filip Faxen says:

>    (3) And yet a strict implementation of f would fail to terminate in this 
>        example (when called with part of its result).
>
>    (4) Wheras it terminates beautifully with a lazy implementation.

(there's that use of ``lazy'' again, whereas what he really means is ``non-strict'' :-).

Actually in many strict languages, the question of termination does not arise because the
problem is simply ``defined away'':

In SML, circular bindings like "(x,y) = f 10 100 x" are disallowed by a syntax
restriction: recursive definitions must be given in a REC form, and in a REC form all
right-hand-sides must be FN forms (lambdas), and the lambda prevents circularity problems
by ``protecting'' the recursive reference (see Section 2.9, Bullet 4 in "The Definition of
Standard ML", Milner, Tofte and Harper).

In Scheme, also, such bindings are illegal.  To quote from R^4RS (Sec 4.2.2):

    "One restriction on LETREC is very important:  it must be
     possible to evaluate each <init> [read: RHS] without assigning or refer-
     ring to the value of any <variable> [read: LHS].  If this restriction is
     violated, then it is an error.  The restriction is necessary
     because Scheme passes arguments by value rather than by 
     name.  In the most common uses of LETREC, all the <init>s
     are lambda expressions and the restriction is satisfied au-
     tomatically."

I was quite pleasantly surprised to find that MIT C Scheme actually catches this error:

    (define (f n a b) (if (= n 0)
		          (cons a b)
		          (f (- n 1) (+ a 1) (+ b 2))))
    ;Value: f

    (f 10 100 200)
    ;Value 3: (110 . 220)

    (letrec ((c  (f 10 100 x))
	     (x  (car c))
	     (y  (cdr c)))
      (cons x y))
    ;Unassigned variable: x
    ;To continue, call RESTART with an option number:
    ; (RESTART 3) => Specify a value to use instead of x.
    ; (RESTART 2) => Set x to a given value.
    ; (RESTART 1) => Return to read-eval-print level 1.

I suspect some strict language implementations might ``terminate beautifully'' with the
wrong result--- for the third argument to F they'll just pick up whatever garbage old
value happens to be sitting in X's cell.

Cheers,

Nikhil  (nikhil@crl.dec.com)