Re: Why is there a space leak here?
Fergus Henderson <fjh@cs.mu.oz.au> writes:
If experts like Alastair Reid have trouble understanding the operational behaviour of simplified examples like this one, how are ordinary programmers to cope with complicated programs? Is lazy functional programming too difficult for ordinary mortals?
Of course, you can just go the strict route, and generate the whole list before processing it. Which will blow up (since it requires an equal amount of space), but do so in a more predictable and comprehensible way. :-) -kzm -- If I haven't seen further, it is by standing in the footprints of giants
Ok... I'm doing a lot of testing with monadic parsers. My current test consists on a Haskell program that parses a C++ source file and: - Separates individual lines - Removes comments - Parses quoted literal strings and characters - Removes indentation and trailing blanks - Remembers the original file position of each portion of the result. The problem is that my test program runs out of stack (not heap) on both GHC and Hugs when parsing a large-enough file (about 150K for GHC, a lot less for Hugs). And, the real weird part is that it does so after printing most of the output. I don't know, I can't claim to understand the inner workings of GHC/Hugs, but it sounds to me that, in order to have a stack overflow, nothing should have been printed yet. It's as if, say, in order to parse the next line, the stack has to contain the complete file up to the point that's being parsed. So... any suggestions on what can be wrong? I'm posting a bit of the main code (maybe I'm lucky and the problem lies there). I don't want to force everyone in the list to get an attachment, so if anyone is interested or would like to help, please, just ask and I'll send the whole thing. --- This part does the actual parsing. I call it the "quoting resolver" data UnquotedText q = CODE String | QUOTE q instance Show q => Show (UnquotedText q) where show (CODE s) = "CODE <" ++ s ++ ">" show (QUOTE q) = "QUOTE <" ++ show q ++ ">" type QuotingResolver q = LayoutTextParser [(FilePos,UnquotedText q)] resolveQuoting :: QuotingResolver q -> (FilePos,String) -> [(FilePos,UnquotedText q)] resolveQuoting r s = rq s where rq s = case applyInputParser r s of [] -> [] ((result,ns):_) -> result ++ rq ns quotingResolver :: LayoutTextParser (LayoutTextParser (Maybe (UnquotedText q)),FilePos) -> LayoutTextParser () -> QuotingResolver q quotingResolver startQuote skipBlanks = do (_,_,col) <- getFilePos if col == 1 then skipBlanks else return () filePosBeforeQuote <- getFilePos (textBeforeQuote,endQuote) <- manynot extractItem (skipBlanks >> startQuote) tlist <- case textBeforeQuote of "" -> return [] _ -> return [(filePosBeforeQuote,CODE textBeforeQuote)] if isNothing endQuote then case tlist of [] -> mzero _ -> return tlist else do Just (endQuoteParser,quotefilePos) <- return endQuote quote <- endQuoteParser if isNothing quote then return tlist else do Just textInQuote <- return quote qlist <- case textInQuote of (CODE "") -> return [] _ -> return [(quotefilePos,textInQuote)] return (tlist ++ qlist) --- This part does the quoting of a C++ file data CppQuotedText = STRING String | CHAR Char instance Show CppQuotedText where show (STRING s) = "STRING \"" ++ s ++ "\"" show (CHAR s) = "CHAR '" ++ [s] ++ "'" type CppUnquotedText = UnquotedText CppQuotedText cppSingleLineComment :: LayoutTextParser (Maybe CppUnquotedText) cppMultiLineComment :: LayoutTextParser (Maybe CppUnquotedText) cppSingleQuote :: LayoutTextParser (Maybe CppUnquotedText) cppDoubleQuote :: LayoutTextParser (Maybe CppUnquotedText) cppSingleLineComment = do { (_ ,mb) <- manynot extractChar (char '\n'); if isNothing mb then return Nothing else return (Just (CODE "" )) } cppMultiLineComment = do { (_ ,mb) <- manynot extractChar (string "*/"); if isNothing mb then return Nothing else return (Just (CODE "" )) } cppSingleQuote = do { c <- literalCharacterParserRest; return (Just (QUOTE (CHAR c))) } cppDoubleQuote = do { s <- literalStringParserRest; return (Just (QUOTE (STRING s))) } cppQuotingStart :: LayoutTextParser (LayoutTextParser (Maybe CppUnquotedText),FilePos) cppQuotingStart = do filePos <- getFilePos result <- (do { char '\n'; return (return (Just (CODE ""))) } +++ do { string "//"; return cppSingleLineComment } +++ do { string "/*"; return cppMultiLineComment } +++ do { char '\''; return cppSingleQuote } +++ do { char '"' ; return cppDoubleQuote }) return (result,filePos) cppQuotingResolver :: QuotingResolver CppQuotedText cppQuotingResolver = quotingResolver cppQuotingStart skipBlanksNoNewLine --- This is the main program doTest s fname = (resolveQuoting cppQuotingResolver ((fname,1,1), s)) printLines [] = return () printLines (x:xs) = do print x; printLines xs main = do args <- getArgs putStr "Parser v0.0!\n" fname <- return (if args == [] then "E:/Ronin/RE3D/3DRenderer.cpp" else (head args)) s <- readFile fname printLines (doTest s fname) --- In my example file, the output begins (in Hugs) with: --- Main> main Parser v0.0! (("E:/Ronin/RE3D/3DRenderer.cpp",6,1),CODE <#include>) (("E:/Ronin/RE3D/3DRenderer.cpp",6,10),QUOTE <STRING "StdAfx.h">) (("E:/Ronin/RE3D/3DRenderer.cpp",8,1),CODE <#include>) (("E:/Ronin/RE3D/3DRenderer.cpp",8,10),QUOTE <STRING "3DRenderer.h">) (("E:/Ronin/RE3D/3DRenderer.cpp",10,1),CODE <#include>) --- and ends with: --- (("E:/Ronin/RE3D/3DRenderer.cpp",813,5),CODE <if (mipMapBias != bias) {>) (("E:/Ronin/RE3D/3DRenderer.cpp",814,9),CODE <++changeID;>) (("E:/Ronin/RE3D/3DRenderer.cpp",815,5),CODE <}>) (("E:/Ronin/RE3D/3DRenderer.cpp",816,5),CODE <mipMapBias = bias;>) (("E:/Ronin/RE3D/3DRenderer.cpp",817,5),CODE <return SetLastError(RE3DERR_NONE);>) (("E:/Ronin/RE3D/3DRenderer.cpp",818,1),CODE <}>) ERROR - Control stack overflow Main> --- Salutaciones, JCAB --------------------------------------------------------------------- Juan Carlos "JCAB" Arevalo Baeza | http://www.roningames.com Senior Technology programmer | mailto:jcab@roningames.com Ronin Entertainment | ICQ: 10913692 (my opinions are only mine) JCAB's Rumblings: http://www.metro.net/jcab/Rumblings/html/index.html
Juan Carlos Arevalo Baeza <jcab@roningames.com> writes:
Ok... I'm doing a lot of testing with monadic parsers. My current test consists on a Haskell program that parses a C++ source file and: [...] The problem is that my test program runs out of stack (not heap) on both GHC and Hugs when parsing a large-enough file (about 150K for GHC, a lot less for Hugs).
The classic cause of this problem in parsers is tracking line numbers. The problem is that line numbers have to be built but rarely get observed. This means that a line number like 33 will be represented by a thunk like this: 1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1 This uses a lot of heap space (though it may not be too bad because of sharing) but, more seriously, it takes stack space proportional to the line number - hence the stack overflows you've been seeing. The fix is to add strictness annotations to force evaluation of the line number every time you increment it. The easiest way to do this is to represent source locations by a data structure like this: data SrcLoc = MkSrcLoc FileName !Int !Int and use "seq" (or "$!") in the function that gets the next token. For example, if the function to get the next token looks like this: token :: Parser a token = Parser (\ (input, srcloc) -> case input of (t : new_input) -> return (a, (new_input, inc srcloc)) ... ) you would change the 4th line to: (t : new_input) -> let srcloc' = inc srcloc in srcloc' `seq` return (a, (new_input, srcloc')) [A similar problem can happen in pretty-printers that track column numbers.] -- Alastair Reid reid@cs.utah.edu http://www.cs.utah.edu/~reid/ ps You might want to have a look at this Prelude function: unlines :: [String] -> String
participants (3)
-
Alastair David Reid -
Juan Carlos Arevalo Baeza -
Ketil Malde