Brainfuck interpreter stack overflow
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
2010/1/21 Edgar Klerks
I am using this one: http://hackage.haskell.org/packages/archive/parsec/3.0.0/doc/html/Text-Parse... Is that version ok?
Ah ha - that's the later than the one I use. The authors must have decided to change its place in the modules hierarchy. In your case, you have already IO as part of the monad stack so you can write debug output to the console. This might produce a lot of output before a stack overflow though. A minor nit-pick - language pragmas generally go at the top of the file. It might even be that they _should_ go at the top of the file, I had to move it to make it run for me. Best wishes Stephen
Thanks for your help Stephen and Daniel. The interpreter now doesn't show any stackoverflows anymore. By using the profiler, I identified some problems. The State Monad seemed to cause a memory leak. It also made the interpreter run slow. I removed it, because it isn't neccesary. I also used Immutable Arrays to store the instructions in, which seemed to speed it also up. I made the code more functional and the evaluation loop tail-recursive, which helped a lot. I am now testing different storage models for the data tape. I now use Data.Map, but Data.Zipper.List maybe more appropiate. I didn't know about the profiler and I am suprised it is such a big help. I never used one before. Best Wishes, Edgar
Hi Edgar You might want to look at Data.Sequence... The transform function in your original code did both a cons (add to the front) and an append / snoc (add one to the end). transform :: BF -> [BF] transform (Loop bs) = Jmpz (2 + lengthbs bs) : (bs >>= transform) -- cons ++ [Jmpb (1 + lengthbs bs)] --snoc / append transform a = [a] snoc-ing is expensive on standard lists because you have to implement it as an appending a singleton list (which you did). Append performs a full traversal of the first list - here is the implementation copied from the GHC's libraries: (++) :: [a] -> [a] -> [a] (++) [] ys = ys (++) (x:xs) ys = x : xs ++ ys In contrast, Data.Sequence has cheap operations for cons (<|), snoc (|>) and append (><). Best wishes Stephen
participants (2)
-
Edgar Klerks -
Stephen Tetley