Constant space infinite itteration ... solution?

[David Bergman]

Hi, Bruce.

Just want to clarify the "last call optimisation"/"tail recursion"
terminology.

One does not "remove" a tail recursive call, one just make it O(1)
w.r.t. stack (or any other "where have we been" call frame structure...)
with the help of "tail recursion optimisation". "Last call optimisation"
is a generalization of the latter optimisation, applicable to any call,
recursive or not.

In effect, implementers seldom care whether the last call is recursive
or not, they just skip the "return address" pushing, making "last call
optimisation" operationally equivalent to "tail recursion optimisation".

Richard was (and still is) completely correct in that last call
optimisation is not a crucial element in lazy evaluation, although that
is not necessarily true when strictness analysis or explicit strictness
annotations (!) allow the implementation to skip the general thunk
creation/inspection/destruction loop and instead use the much more
time-efficient eager evaluation (i.e., mapping to the C code you
referred to...), which can be memory-inefficient, similar to your Hugs
experience.

Good luck with that Ferrari (that is the only Ferrari we Haskellers will
ever see...)

/David

Bruce wrote:
> 
> 
> Hi all,
> 
> 
> Ok, I've got the Farari out of the garage, in to gear, and even driven
> it slowly around the block, but every time I put my foot down it just 
> stalls.
> 
> I'm trying to write a non trivial gui in Haskell. At the moment I'm 
> using Hugs, and rapidly coming to the conclusion that I should be 
> using something else such as GHC.
> 
> As I see it the problem is basically that of tail recursion removal or

> as David Bergman calls it "last call optimisation".
> 
> Specifically:
> 
> David Bergman wrote
> 
> > It is easy to get the feeling that the recursive call in
> > 
> >     recurse = do { f x ; recurse }
> > 
> > is the last one, but this is just an illusion of the iterative
> > layout of "do". Sometimes the monads lure us into old iterative 
> > thought patterns...
> >
> > Taking away the syntactic sugar, we end up with
> > 
> >     recurse = f x >> recurse
> > 
> > This reveals the fact that there can be no last call optimization,
> > because the last call is ">>".
> 
> In response Richard Uhtenwoldt echoed my own thoughts ...
> 
> > What do you mean by this?  Do you mean that that an implementation
> > cannot execute arbitrarily many iterations/recursions of that last 
> > loop/definition in constant space?
> 
> And also said ...
> 
> > If that's what you mean, you are wrong.  GHC does that.
> > The IO monad would be pretty damned useless for actual
> > work if implementations did not do that!
> 
> So, my problem is that I find that my program crashes with "garbage 
> collector can't collect enough memory" after about 64 Million output 
> operations.
> 
> What's really annoying is that I can write the whole thing
> *recursively* in C in a very "functional" manner, and it works just
> fine.
> 
> As I see it the problem is that >> and >>= are functions
> and David is right about the "not the last call" problem. But, Richard

> is right that related optimisations should be possible in Haskell, and

> if not then you can kiss the whole load good by and go back to system 
> programming in C.
> 
> In particular I would claim that the definition:
> 
>  recurse = f x >>= recurse
> 
> is essentially using >>= as a proxy temporal execution handler. So in
> the above definition the call to recurse
> *is* a "last-call", at least according to >>=.  I'm
> probably saying that in a rather unorthodox manner,
> but I hope my basic intention is clear.
> 
> In fact we can see >> in Haskell as rather kin to ; in C
> (Or perhaps it should be >>=, since ; does transfer the
> state to the subsequent computation).
> 
> So, I've loaded GHC and I'm looking to use it instead
> (I expected to eventually anyway), but does this solve
> my problem? Or have I misunderstood something here?
> 
> Also ... I've been using the graphics libs with HUGS,
> but I can't find the equivalent in GHC ... what is
> the recomended library for writing GUIs in GHC Haskell?
> And where do I get it?
> 
> Thanks in advance ...
> 
> Bruce (IIMS, Massey at Albany).
> 
> ps: I've also been looking at Fudgets, but the code seems
>     a bit cranky.
> 
> 
> _______________________________________________
> Haskell mailing list
> Haskell@haskell.org http://www.haskell.org/mailman/listinfo/haskell
>