[Haskell-cafe] Re: Web server continued

[Jake McArthur]

On Dec 31, 2007, at 6:50 AM, Cristian Baboi wrote:

> On Mon, 31 Dec 2007 14:36:02 +0200, Joost Behrends <webmaster at h-labahn.de 
> > wrote:
>
>> I forgot 2 things:
>>>
>>> The distinction between '=' and '==' is much like in C, although  
>>> mixing
>>> them up is not so dangerous like in C. ':=' and '=' like in Wirth
>>> languages would be nicer.
>>>
>
>> Strangely nobody reacted on this. That a=a+1 is an infinite  
>> recursion here
>
> What is more strange is that a = a + 1 and a = 1 + a are somehow  
> distinct.
> The second give a stack overflow almost instanly, but the first don't.

To explain this, let's look at the expansions. The first one looks  
like this:

      a + 1
      a + 1 + 1
      a + 1 + 1 + 1
      a + 1 + 1 + 1 + 1
      ...
      a + 1 + ... + 1

The second one looks like this:

      1 + a
      1 + 1 + a
      1 + 1 + 1 + a
      1 + 1 + 1 + 1 + a
      ...
      1 + ... + 1 + a

I suspect that GHC is evaluating the second one strictly, as though it  
was this instead:

      a = foldl1' (+) (repeat 1) + a

This way, the stack never gets any larger. The first one, however, has  
runtime behavior comparable to this:

      a = foldl' (+) a (repeat 1)

The first thing this version has to do is evaluate a, which starts  
infinite recursion. The second one doesn't suffer from this because it  
has real values to manipulate strictly instead of just substitution  
rules and thunks.

I'm speculating here, so somebody please correct me if I'm wrong.

- Jake