Отладка переполнения стека в haskell

Question

Я новичок в Haskell и функциональном программировании, и у меня есть программа, которая работает, но переполняет стек через несколько секунд. Мой вопрос: что мне делать дальше? Как я могу получить хотя бы намек на то, где это происходит, распечатать стек или что-нибудь еще?

Программа работает очень медленно при запуске в ghci с: trace, поэтому переполнение стека не происходит. Это не происходит также с runhaskell, который будет просто потреблять все больше и больше памяти. Я получаю ошибку только при компиляции с помощью ghc и выполнении.

Answer 1

См http://book.realworldhaskell.org/read/profiling-and-optimization.html для общих руководящих принципов по профилирующей

Answer 2

Самая простая стратегия использования функции трассировки. Например, рассмотрим эту функцию:

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 имеет тип 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. К счастью, есть макрос шаблона haskell в deepseq-th library: 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,2 МБ.

Вы можете придерживаться этого решения или попытаться найти, где находится настоящая проблема строгости (поскольку это делает все строгим). Вы делаете это, удаляя силу из функции step и пробуя ее на вспомогательные функции, которые она использует (например, setElem, findPrevBacket и т. Д.). Оказывается, виновником является setElem, поставив force перед этой функцией, также решая проблему строгости. Я предполагаю, что это связано с тем, что if на карте лямбда означает, что большинство значений никогда не нужно оценивать в списке и, возможно, создавать огромные трюки по мере продолжения программы.