Debugging eines Stack-Überlaufs in Haskell

Question

Ich bin neu in Haskell und funktionale Programmierung und ich habe ein Programm, das funktioniert, aber den Stack nach ein paar Sekunden überläuft. Meine Frage ist, was soll ich von hier aus machen? Wie kann ich zumindest einen Hinweis darauf bekommen, wo es auftritt, den Stapel ausdrucken oder so?

Das Programm ist sehr langsam beim Ausführen in Ghci mit: Trace, so dass der Stapelüberlauf nicht auftritt. Es tritt auch nicht mit runhaskell auf, die nur mehr und mehr Gedächtnis essen werden. Ich bekomme den Fehler nur beim Übersetzen mit ghc und Ausführen.

Answer 1

Siehe http://book.realworldhaskell.org/read/profiling-and-optimization.html für allgemeine Richtlinien auf

Profilierungs

Answer 2

Die einfachste Strategie, um die Trace-Funktion verwendet. Zum Beispiel betrachten Sie diese Funktion:

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 

Wenn Sie zB ./program 13 ausführen, werden Sie 42 bekommen. Wenn Sie jedoch ./program 29 ausführen, erhalten Sie einen Stapelüberlauf.

Um dies zu debuggen, setzen trace Anweisungen für jeden Fall (von 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 hat den Typ String -> a -> a und druckt die angegebene Zeichenfolge, gibt dann den Wert des zweiten Arguments. Es ist eine spezielle Funktion, da es IO in einer reinen Funktion ausführt. Es ist jedoch großartig zum Debuggen.

In diesem Fall das Programm nun mit ./program 19 ausgeführt wird, wird die Ausgabe erhalten:

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

genau Zeigen, was genannt wurde.

Wenn Sie jetzt mit ./program 29 laufen, erhalten Sie:

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

Dieses hübsche zeigt deutlich, wie die Schleife auftritt. Während in diesem Beispiel es ziemlich offensichtlich war, wo das Problem war, ist es nützlich für komplexere Funktionen (besonders wenn der Stapelüberlauf mehrere Funktionen umfasst - tun Sie dies nur mit allen Funktionen, die Sie vermuten, könnte das Problem sein).

Answer 3

In Ihrem Fall ist es ein Striktheitsproblem, das den Stapelüberlauf verursacht. Eine wirklich einfache Möglichkeit, solche Probleme zu finden, ist die Verwendung der deepseq library. Dies fügt ein paar Funktionen hinzu, mit denen Sie einen Wert vollständig auswerten können (was besser ist als seq, was nur eine Ebene tiefer geht). Die Schlüsselfunktion ist force :: NFData a => a -> a. Dies nimmt einen Wert, bewertet es vollständig und gibt es zurück.

Es funktioniert jedoch nur auf Typen, die die Klassenklasse NFData implementieren. Glücklicherweise gibt es ein Template-Haskell-Makro im deepseq-th library: deriveNFData. Dies wird mit Ihren eigenen Datentypen verwendet, zB deriveNFData ''BfMachine.

Um zu verwenden, setzen Sie force $ vor Ihren Funktionen, die Strenge Probleme haben können (oder liftM force $ für monadische Funktionen).ZB mit Ihrem Code, ich habe es vor step, denn das ist die Schlüsselfunktion in der Datei war:

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

Dies löst das Problem tatsächlich - auch nach einem paar Minuten laufen, es ist nicht abgestürzt und Speicher Die Nutzung ist nur 3,2 MB.

Sie können mit dieser Lösung bleiben, oder versuchen zu finden, wo das echte Striktheitsproblem ist (wie das macht alles streng). Sie tun dies, indem Sie die Kraft von der step Funktion entfernen und es auf den Hilfsfunktionen versuchen, die es benutzt (zB setElem, findPrevBacket, usw.). Es stellt sich heraus, dass setElem der Schuldige ist, setzen force vor dieser Funktion auch das Striktheitsproblem löst. Ich vermute, es ist, weil die if in der Map Lambda bedeutet, dass die meisten Werte nie in der Liste ausgewertet werden müssen und möglicherweise riesige Thunks aufbauen, während das Programm weitergeht.