🚀 go-pugleaf

In article <BJORNL.92Oct29101000@rama.sics.se>, bjornl@sics.se (Bj|rn Lisper) writes:
|> In article <1992Oct28.154755.24815@crl.dec.com> nikhil@crl.dec.com (R.S.
|> Nikhil) writes: 
|> 
|> >       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?

Yes, here is a Haskell version, compiled with hbc:

main = print (let (x,y) = f 10 100 x in (x,y))

f 0 x y = (x,y)
f n x y = f (n-1) (x+1) (y+2)

When run, it gives the result: (110, 130).

|> 2. Doesn't the benefits of the tail-recursive optimization in general depend
|> on arguments being strict?

This is also an interesting example of the intricacies of strictness
analysis over non-flat domains:

(1) In the definition of main, both x and y occurs in a strict context
    (since print wants its argument fully evaluated in order to convert
    it to a string and print it on stdout).

(2) The function f is strict in all its arguments when called in a
    completely strict context.

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


Cheers,
        Karl-Filip

------------------------------------------------------------
Make the frequent case fast, and the fast case frequent!