Debugging in haskell

Question

I am new to Haskell and functional programming, and I have a program that works, but after a few seconds overflows the stack. My question is: what should I do next? How can I get at least a hint of where this happens, print a stack, or something else?

The program runs very slowly when launched in ghci with: trace, so the stack does not overflow. This does not happen either with runhaskell, which will simply consume more and more memory. I get an error only when compiling with ghc and executing.

Answer 1

In your case, this is a strictness problem causing a stack overflow. One very easy way to find such problems is to use the deepseq library . This adds a few functions that allow you to fully appreciate the value (which is better than seq , which is only one level down). The key function force :: NFData a => a -> a . This takes a value, fully evaluates it, and returns it.

It works only for types that implement a class of type NFData . Fortunately, there is a haskell template macro in deepseq-th library : deriveNFData . This is used with your own data types, e.g. deriveNFData ''BfMachine .

To use, you put force $ in front of your functions, which may have strictness problems (or liftM force $ for monadic functions). For example, with your code, I put it before step , as it was a key function in the file:

 {-# LANGUAGE TemplateHaskell #-} import Data.Char import Debug.Trace import Control.DeepSeq import Control.DeepSeq.TH import Control.Monad (liftM) type Stack = [Int] data BfMachine = BfMachine { program :: String , pc :: Int , stack :: Stack , sp :: Int } deriving Show deriveNFData ''BfMachine setElem :: [Int] -> Int -> Int -> [Int] setElem list n value = map (\(i, v) -> if i == n then value else v) (zip [0..] list) step :: BfMachine -> IO (BfMachine) step m@(BfMachine { program = program, pc = pc, stack = stack, sp = sp }) = liftM force $ case program !! pc of '-' -> return m { pc = pc + 1, stack = setElem stack sp ((stack !! sp) - 1) } '+' -> return m { pc = pc + 1, stack = setElem stack sp ((stack !! sp) + 1) } '<' -> return m { pc = pc + 1, sp = sp - 1 } '>' -> return m { pc = pc + 1, sp = sp + 1 } '[' -> return $ if stack !! sp /= 0 then m { pc = pc + 1 } else m { pc = (findNextBracket program $ pc + 1) + 1 } ']' -> return m { pc = findPrevBracket program $ pc - 1 } '.' -> do putChar $ chr $ stack !! sp return m { pc = pc + 1 } ',' -> do c <- getChar let s' = setElem stack sp $ ord c in return m { stack = s', pc = pc + 1 } a -> return m { pc = pc + 1 } findNextBracket :: String -> Int -> Int findNextBracket program pos = case program !! pos of '[' -> findNextBracket program $ (findNextBracket program $ pos + 1) + 1 ']' -> pos x -> findNextBracket program (pos + 1) findPrevBracket :: String -> Int -> Int findPrevBracket program pos = case program !! pos of ']' -> findPrevBracket program $ (findPrevBracket program $ pos - 1) - 1 '[' -> pos x -> findPrevBracket program (pos - 1) isFinished :: BfMachine -> Bool isFinished m@(BfMachine { program = p, pc = pc }) | pc == length p = True | otherwise = False run :: BfMachine -> IO () run m = do if isFinished m then return () else do m <- step m run m fib = ">++++++++++>+>+[ [+++++[>++++++++<-]>.<++++++[>--------<-]+<<<]>.>>[ [-]<[>+<-]>>[<<+>+>-]<[>+<-[>+<-[>+<-[>+<-[>+<-[>+<- [>+<-[>+<-[>+<-[>[-]>+>+<<<-[>+<-]]]]]]]]]]]+>>> ]<<< ] This program doesn't terminate; you will have to kill it. Daniel B Cristofani (cristofdathevanetdotcom) http://www.hevanet.com/cristofd/brainfuck/" main = run BfMachine { program = fib , pc = 0, stack = replicate 1024 0, sp = 0 } 

This actually solves the problem - even after a few minutes it did not crash, and the memory usage is only 3.2 MB.

You can stick to this solution or try to find where the problem is real rigor (as it makes everything rigorous). You do this by removing the force from the step function and trying it on the helper functions that it uses (e.g. setElem , findPrevBacket , etc.). It turns out that setElem is the culprit, putting force in front of this function also solves the strictness problem. I suppose this is because if on a lambda map means that most of the values ​​never need to be evaluated on the list and possibly create huge tricks as the program continues.

Answer 2

See http://book.realworldhaskell.org/read/profiling-and-optimization.html for general profiling guidelines

Answer 3

The simplest strategy is to use the trace function. For example, consider this function:

 badFunction :: Int -> Int badFunction x | x < 10 = x * 2 | x == 15 = badFunction 480 | even x = badFunction $ x `div` 2 | odd x = badFunction $ x + 1 main = print . badFunction . read . head =<< getArgs 

For example, if you run ./program 13 , you will get 42 . However, if you run ./program 29 , you will get a stack overflow.

To debug this, put trace expressions for each case (from Debug.Trace ):

 badFunction :: Int -> Int badFunction x | x < 10 = trace ("badF -> small " ++ show x) x * 6 | x == 15 = trace "badF -> x == 15" $ badFunction 480 | even x = trace ("badF -> even " ++ show x) $ badFunction $ x `div` 2 | odd x = trace ("badF -> odd " ++ show x) badFunction $ x + 1 

trace is of type String -> a -> a and prints the given string and then returns the value of the second argument. This is a special function because it performs IO in a pure function. This is great for debugging.

In this case, starting the program now with ./program 19 , you will get the result:

 badF -> odd 19 badF -> even 20 badF -> even 10 badF -> small 5 30 

Displays what was called.

If you run it with ./program 29 , you will get:

 badF -> odd 29 badF -> even 30 badF -> x == 15 badF -> even 960 badF -> even 480 badF -> even 240 badF -> even 120 badF -> even 60 badF -> even 30 badF -> x == 15 badF -> even 960 badF -> even 480 badF -> even 240 badF -> even 120 badF -> even 60 badF -> even 30 badF -> x == 15 badF -> even 960 badF -> even 480 badF -> even 240 badF -> even 120 badF -> even 60 badF -> even 30 badF -> x == 15 badF -> even 960 .... 

This pretty clearly shows how the cycle occurs. Although in this example it was pretty obvious where the problem is, it is useful for more complex functions (especially if the stack overflow includes several functions - just do it with all the functions that you suspect might be the problem).