Constant space infinite itteration ... solution?

[b.i.mills@massey.ac.nz]

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.