Pregunta Depuración de un desbordamiento de pila en haskell


Soy nuevo en Haskell y en la programación funcional y tengo un programa que funciona pero desborda la pila después de unos segundos. Mi pregunta es, ¿qué debería hacer desde aquí? ¿Cómo puedo obtener al menos una pista de dónde ocurre, imprimir la pila o algo?

El programa es muy lento cuando se ejecuta en ghci con: trace para que no ocurra el desbordamiento de la pila. No ocurre también con runhaskell que simplemente comerá más y más memoria. Me sale el error solo al compilar con ghc y ejecutar.


8
2017-08-28 19:45


origen


Respuestas:


En su caso, es un problema de rigor lo que está causando el desbordamiento de la pila. Una forma realmente fácil de encontrar estos problemas es usar el biblioteca deepseq. Esto agrega algunas funciones que le permiten evaluar completamente un valor (que es mejor que seq, que solo baja un nivel). La función clave es force :: NFData a => a -> a. Esto toma un valor, lo evalúa completamente y lo devuelve.

Solo funciona en tipos que implementan NFData tipo de clase sin embargo. Afortunadamente, hay una plantilla de haskell macro en el biblioteca deepseq-th: deriveNFData. Esto se usa con sus propios tipos de datos, por ejemplo deriveNFData ''BfMachine.

Para usar, pones force $ frente a sus funciones que pueden estar teniendo problemas de rigor (o liftM force $ para funciones monádicas). Por ejemplo, con su código, lo puse delante de step, ya que esa era la función clave en el archivo:

{-# 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 [email protected](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 [email protected](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 }

Esto realmente resuelve el problema, incluso después de unos minutos de funcionamiento, no se ha bloqueado y el uso de la memoria es de solo 3,2 MB.

Puedes mantenerte con esa solución, o tratar de encontrar dónde está el verdadero problema de rigor (ya que eso hace que todo sea estricto). Para hacer esto, quita la fuerza del step función, y probándolo en las funciones de ayuda que utiliza (por ejemplo, setElem, findPrevBacket, etc.) Resulta que setElem es el culpable, poniendo force frente a esa función también resuelve el problema de rigor. Supongo que es porque el if en el mapa, lambda significa que la mayoría de los valores nunca deben ser evaluados en la lista, y posiblemente acumulen grandes cantidades de datos a medida que el programa continúa.


3
2017-08-29 09:38



Ver http://book.realworldhaskell.org/read/profiling-and-optimization.html para lineamientos generales sobre el perfil


1
2017-08-28 19:54



La estrategia más simple es usar la función de rastreo. Por ejemplo, considere esta función:

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

Ej. Si corres ./program 13, conseguirás 42. Sin embargo, si corres ./program 29, obtendrás un desbordamiento de pila.

Para depurar esto, coloca trace declaraciones para cada caso, (de 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 tiene el tipo String -> a -> a, e imprime la cadena dada, luego devuelve el valor del segundo argumento. Es una función especial, ya que realiza IO en una función pura. Sin embargo, es genial para la depuración.

En este caso, ejecutar el programa ahora con ./program 19, obtendrás el resultado:

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

Mostrando exactamente lo que se llamó.

Si ahora lo ejecuta con ./program 29, usted obtiene:

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

Esto muestra claramente cómo está ocurriendo el ciclo. Mientras que en este ejemplo era bastante obvio dónde estaba el problema, es útil para funciones más complejas (especialmente si el desbordamiento de la pila implica múltiples funciones; solo hazlo con todas las funciones que sospechas que podría ser el problema).


1
2017-08-29 06:54