在haskell中调试堆栈溢出

Question

我是 Haskell 和函数式编程的新手，我有一个程序可以运行，但几秒钟后就会溢出堆栈。我的问题是，我应该从这里做什么？我怎样才能至少知道它发生在哪里，打印堆栈或任何东西？

该程序在使用 :trace 的 ghci 中运行时非常慢，因此不会发生堆栈溢出。 runhaskell 也不会发生这种情况，它只会消耗越来越多的内存。仅在使用 ghc 编译并执行时才会出现错误。

Answer 1

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

它只适用于实现 NFData 的类型。虽然类型类。幸运的是，deepseq-th library 中有一个模板 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在 map 中，lambda 意味着大多数值永远不必在列表中进行评估，并且可能会随着程序的继续而建立巨大的 thunk。