stack overflow in tail recursive function

Previous Topic Next Topic
 
classic Classic list List threaded Threaded
5 messages Options
Reply | Threaded
Open this post in threaded view
|

stack overflow in tail recursive function

Bruno Schneider
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?

--
Bruno Schneider
http://www.dcc.ufla.br/~bruno/
_______________________________________________
Hugs-Users mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/hugs-users
Reply | Threaded
Open this post in threaded view
|

Re: stack overflow in tail recursive function

Neil Mitchell
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

On Tue, Mar 23, 2010 at 12:01 PM, Bruno Schneider <[hidden email]> 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?
>
> --
> Bruno Schneider
> http://www.dcc.ufla.br/~bruno/
> _______________________________________________
> Hugs-Users mailing list
> [hidden email]
> http://www.haskell.org/mailman/listinfo/hugs-users
>
_______________________________________________
Hugs-Users mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/hugs-users
Reply | Threaded
Open this post in threaded view
|

Re: stack overflow in tail recursive function

Daniel Fischer-4
-----Ursprüngliche Nachricht-----
Von: Neil Mitchell <[hidden email]>
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
>> [hidden email]
>> http://www.haskell.org/mailman/listinfo/hugs-users
>>
>_______________________________________________
>Hugs-Users mailing list
>[hidden email]
>http://www.haskell.org/mailman/listinfo/hugs-users
_______________________________________________
Hugs-Users mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/hugs-users
Reply | Threaded
Open this post in threaded view
|

Re: stack overflow in tail recursive function

Bruno Schneider
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.

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.


--
Bruno Schneider
http://www.dcc.ufla.br/~bruno/
_______________________________________________
Hugs-Users mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/hugs-users
Reply | Threaded
Open this post in threaded view
|

Re: stack overflow in tail recursive function

Daniel Fischer-4
-----Ursprüngliche Nachricht-----
Von: Bruno Schneider
Gesendet: 24.03.2010 13:56:32
An: [hidden email]
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
_______________________________________________
Hugs-Users mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/hugs-users