-----Ursprüngliche Nachricht----- Von: Neil Mitchell Gesendet: 23.03.2010 21:40:39 An: Bruno Schneider Betreff: Re: [Hugs-users] stack overflow in tail recursive function

Hi Bruno,

I suggest you ask this question on the haskell-cafe@ mailing list - it's a general Haskell question, and you'll get a much more detailed answer there.

Thanks, Neil

Yes, this sort of general Haskell questions will receive earlier and more answers in the cafe. Nevertheless, Neil, I'm not sure he'd get a much more detailed answer to this question there ;) Okay, so

On Tue, Mar 23, 2010 at 12:01 PM, Bruno Schneider wrote:

...

Hi all,

I have this tail recursive factorial function:

factorial :: Integer -> Integer factorial 0 = 1 factorial n = fat' n 1 where    fat' 1 fat = fat    fat' n fat = fat' (n-1) (n*fat)

Whenever I run it with a number of 20000 or more I get a stack overflow error. It doesn't seem a problem with the large resulting number because, if so, the message should be something like "Garbage collection fails to reclaim sufficient space". Other functions seem to able to handle a larger number of recursive calls.

So, what is the problem with this particular function?

Laziness is more pervasive than you expected. Your accumulator doesn't actually accumulate the product so far, it accumulates the way to obtain that product, because the multiplication isn't carried out but deferred until really needed. So the evaluation of factorial 4 goes fat' 4 1 (4 /= 1) fat' (4-1) (4*1) (4-1 = 3 /= 1) fat' (3-1) (3*(4*1)) (3-1 = 2 /= 1) fat' (2-1) (2*(3*(4*1))) (2-1 = 1 == 1) (2*(3*(4*1))) and this expression is only evaluated if necessary. factorial 20000 builds a thunk of 20000 nested multiplications, this is tried to evaluate when the value is demanded for printing, but the expression is too deeply nested to fit on the stack. You have to make sure the multiplications in the accumulator aren't deferred until the very end. Here, the only sensible way is to explicitly tell the Haskell system to evaluate the product immediately, factorial :: Integer -> Integer factorial n | n < 0 = error "factorial of negative argument" | n == 0 = 1 | otherwise = fac' n 1 where fac' 1 acc = acc fac' k acc = fac' (k-1) $! k*acc The ($!) says "evaluate now (to the outermost constructor)", for Integers that's complete evaluation, so you have no thunks building up and you can calculate factorials of far larger numbers (though it's slow this way). A stack overflow most of the time signals a laziness leak, that some part of a function built up a thunk where it shouldn't and you have to force some level of evaluation manually.

...

-- Bruno Schneider http://www.dcc.ufla.br/~bruno/ _______________________________________________ Hugs-Users mailing list Hugs-Users@haskell.org http://www.haskell.org/mailman/listinfo/hugs-users

_______________________________________________ Hugs-Users mailing list Hugs-Users@haskell.org http://www.haskell.org/mailman/listinfo/hugs-users

-----Ursprüngliche Nachricht----- Von: Bruno Schneider Gesendet: 24.03.2010 13:56:32 An: hugs-users@haskell.org Betreff: Re: [Hugs-users] stack overflow in tail recursive function

On Wed, Mar 24, 2010 at 7:27 AM, Daniel Fischer wrote: [...]

...

and this expression is only evaluated if necessary. factorial 20000 builds a thunk of 20000 nested multiplications, this is tried to evaluate when the value is demanded for printing, but the expression is too deeply nested to fit on the stack.

So it goes to the stack, hum? It thought it would be just a pointer to some computation type on the heap.

Well, the thunk is built on the heap, that's correct, but when it's evaluated, things go on the stack.

Anyway, thanks for the detailed answer. I asked here because I didn't test that code on any other compiler/interpreter, so it could be something related to hugs implementation.

That's okay, but as a rule of thumb, if you don't know that it's implementation-specific, haskell-cafe or beginners (depending on what sort of answer you want) is the better choice; hugs-users or glasgow-haskell-users are less frequented. In this case, the behaviour is a little implementation-dependent, if you use GHC and compile with optimisations, the strictness-analyser should see that the result of the multiplication is needed and the compiler should make it strict by itself. (I currently have no access to a computer with GHC installed, so I can't check that it does indeed.)

-- Bruno Schneider http://www.dcc.ufla.br/~bruno/

Cheers, Daniel