9

I'm new to Haskell and functional programming and I have a program which works but overflows the stack after a few seconds. My question is, what should I do from here? How can I get at least a hint of where it occurs, print the stack or anything?

The program is very slow when running in ghci with :trace so the stack overflow does not occur. It does not occur also with runhaskell which will just eat more and more memory. I get the error only when compiling with ghc and executing.

4

3 回答 3

3

在您的情况下，这是导致堆栈溢出的严格性问题。查找此类问题的一种非常简单的方法是使用deepseq 库。这增加了一些函数，允许您完全评估一个值（这比 更好seq，它只下降一级）。关键功能是force :: NFData a => a -> a。这需要一个值，完全评估它，然后返回它。

它只适用于实现NFData类型类的类型。幸运的是， deepseq-th 库中有一个模板 haskell 宏：deriveNFData. 这与您自己的数据类型一起使用，例如deriveNFData ''BfMachine.

要使用，您将force $可能存在严格性问题的函数（或liftM force $一元函数）放在前面。例如，对于你的代码，我把它放在前面step，因为这是文件中的关键函数：

{-# 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 }

这实际上解决了问题——即使运行了几分钟，它也没有崩溃，内存使用量只有 3.2MB。

您可以坚持使用该解决方案，或者尝试找出真正的严格性问题在哪里（因为这会使一切变得严格）。您可以通过从step函数中移除力，并在它使用的辅助函数（例如 、 等）上尝试它来setElem做到findPrevBacket这一点。原来那setElem是罪魁祸首，把force那个函数放在前面也解决了严格性问题。我猜这是因为if地图中的 lambda 意味着大多数值永远不必在列表中进行评估，并且可能会随着程序的继续而建立巨大的 thunk。

于 2013-08-29T09:38:37.620 回答
1

最简单的策略是使用跟踪功能。例如考虑这个函数：

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

例如，如果你跑步./program 13，你会得到42. 但是，如果你运行./program 29，你会得到一个堆栈溢出。

要对此进行调试，trace请为每种情况放置语句，（来自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具有 type String -> a -> a，并打印给定的字符串，然后返回第二个参数的值。它是一个特殊的函数，因为它在纯函数中执行 IO。虽然它非常适合调试。

在这种情况下，现在使用 运行程序./program 19，您将获得输出：

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

显示确切的名称。

如果你现在用 运行它./program 29，你会得到：

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

这很清楚地显示了循环是如何发生的。虽然在这个例子中问题出在哪里很明显，但它对于更复杂的函数很有用（特别是如果堆栈溢出涉及多个函数 - 只需对您怀疑可能是问题的所有函数执行此操作）。

于 2013-08-29T06:54:41.603 回答
1

有关分析的一般指南，请参阅http://book.realworldhaskell.org/read/profiling-and-optimization.html

于 2013-08-28T19:54:18.733 回答