Brainfuck interpreter stack overflow
Hello, I just started using haskell and found it many uses for it (mainly for scripting purposes at the moment). Now, I have written a brainfuck parser and interpreter in haskell, but it produces a stack overflow if the program runs too long and I don't understand why. I thought I made the interpreter loop tail recursive, which I understood is the most common cause of a stack overflow. Can someone help my find my fault? I somehow miss something. I added the program as attachment. Thanks for your help. With kind regards, Edgar Klerks
Hello Edgar Does the interpreter fail actually fail on particular input rather than by it running to long? Tail recursion isn't very important for Haskell as it is a lazy language, however for any Parsec parser avoiding _left recursion_ is crucially important as it is a LL recursive descent parser. Also how are you running the program - GHCi, Hugs? The import declarations for Parsec suggest that you are using a old version. Best wishes Stephen
Hi Stephen, It parses the source fine, but with complicated programs with lots of loops -like calculating fibonacci- it fails after a while with a stack overflow. However it does produce correct output until that point. I am running it under ghci now, maybe I should try to compile it. I didn't know, I used an old version of parsec. I am using this one: http://hackage.haskell.org/packages/archive/parsec/3.0.0/doc/html/Text-Parse... Is that version ok? Thanks for your help, Edgar
Am Mittwoch 20 Januar 2010 16:45:41 schrieb Edgar Klerks:
Hello,
I just started using haskell and found it many uses for it (mainly for scripting purposes at the moment). Now, I have written a brainfuck parser and interpreter in haskell, but it produces a stack overflow if the program runs too long and I don't understand why. I thought I made the interpreter loop tail recursive, which I understood is the most common cause of a stack overflow. Can someone help my find my fault? I somehow miss something. I added the program as attachment.
Thanks for your help.
With kind regards,
Edgar Klerks
A quick look revealed that you use Control.Monad.State, which defaults to Control.Monad.State.Lazy. That is very often too lazy for longer calculations and produces a stack overflow. Maybe changing the import to Control.Monad.State.Strict helps (that isn't entirely strict either, but often reduces the opportunities for building large thunks sufficiently).
He Daniel,
Cool, I just found out the same with the profiler. I have removed the state
entirely (it is not really neccesary) and it results in a speedup of 10x.
Storing the instructions in an array instead of an list speeded also things
up.
But I will test the original with State.Strict and see how it will perform.
Thanks,
Edgar
2010/1/21 Daniel Fischer
Am Mittwoch 20 Januar 2010 16:45:41 schrieb Edgar Klerks:
Hello,
I just started using haskell and found it many uses for it (mainly for scripting purposes at the moment). Now, I have written a brainfuck parser and interpreter in haskell, but it produces a stack overflow if the program runs too long and I don't understand why. I thought I made the interpreter loop tail recursive, which I understood is the most common cause of a stack overflow. Can someone help my find my fault? I somehow miss something. I added the program as attachment.
Thanks for your help.
With kind regards,
Edgar Klerks
A quick look revealed that you use Control.Monad.State, which defaults to Control.Monad.State.Lazy. That is very often too lazy for longer calculations and produces a stack overflow. Maybe changing the import to Control.Monad.State.Strict helps (that isn't entirely strict either, but often reduces the opportunities for building large thunks sufficiently).
participants (3)
-
Daniel Fischer -
Edgar Klerks -
Stephen Tetley