在haskell中調試堆棧溢出

Question

我是Haskell和函數式編程的新手，我有一個程序可以工作，但會在幾秒鐘後溢出堆棧。我的問題是，我應該從這裏做什麼？我怎麼能至少得到它發生的地方，打印堆棧或任何東西？

當在ghci中使用trace運行時，程序非常慢，所以堆棧溢出不會發生。這與runhaskell不會發生，它只會吃越來越多的記憶。只有使用ghc編譯並執行時纔會出錯。

Answer 1

見http://book.realworldhaskell.org/read/profiling-and-optimization.html一般準則剖析

Answer 2

最簡單的策略是使用跟蹤功能。例如，考慮這樣的功能：如果您運行./program 13

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 

例如，你會得到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具有類型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 
.... 

這個漂亮清楚地顯示了循環是如何發生的。在這個例子中，這個問題非常明顯，它對於更復雜的函數是非常有用的（特別是如果堆棧溢出涉及多個函數 - 只需對所有您懷疑可能存在問題的函數執行此操作）。

Answer 3

在你的情況，這是一個嚴重問題，導致堆棧溢出。找到這些問題的一個非常簡單的方法是使用deepseq library。這增加了一些功能，可以讓您充分評估一個值（這比seq更好，它只向下一級）。關鍵功能是force :: NFData a => a -> a。這需要一個值，完全評估它，並返回它。

它只適用於實現NFData類型類的類型。幸運的是，在deepseq-th library：deriveNFData中有一個模板haskell宏。這用於您自己的數據類型，例如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放在該函數的前面也解決了嚴格性問題。我猜這是因爲lambda表中的if意味着大多數值永遠不必在列表中進行評估，並且隨着程序的繼續可能會建立巨大的thunk。