john lask wrote:
test1 = readFile "big.dat" >>= (\x->print $ parse x) test2 = readFile "big.dat" >>= (\x->print $ fst $ parse x)
test1 (on a large file) will succeed in ghc but fail in hugs test2 on same file will succeed in both ghc and hugs
big.dat is just some large data file say 1MB. (not particularly large by todays standards!)
The question: is there any changes that can be made to the code to make test1 work in hugs without changing the essence of the function?
parse x = sqnc item x where
item =( \ ts -> case ts of [] -> ( Nothing, []) ts -> ( Just (head ts), tail ts) )
sqnc p ts = let ( r, ts' ) = p ts in case r of Nothing -> ([],ts') Just x -> let (r',ts'') = (sqnc p ts') in ( x:r', ts'' )
Strange, this shouldn't happen :) You may want to try item [] = (Nothing, []) item (t:ts) = (Just t , ts) but that shouldn't help ;) Let's try to find out what's going on by doing graph reduction with our bare hands. The preliminary material on http://en.wikibooks.org/wiki/Haskell/Graph_reduction should help a bit. Ideally, there would be tool support (hat? other debugger?) but when things become too complicated, tools can only keep you a few minutes longer above the water before drowning in complexity, too. The main point is that (print $ parse x) and (print $ fst $ parse x) differ in that the latter only computes the answer but not the remaining tokens. So, the stack overflow is triggered when evaluating the remaining tokens, but I don't see why. What happens for (print $ snd $ parse x) ? Let's rewrite your code to figure out what's going on item [] = (Nothing, []) item ts = (Just (head ts), tail ts) For sqnc , we need to translate stuff like let (a,b) = e in . Let-bound patterns aren't explained in the wikibook and in fact they're tricky. When done wrong, there may be space leaks, see also J. Sparud. Fixing Some Space Leaks without a Garbage Collector. http://citeseer.ist.psu.edu/sparud93fixing.html I don't know whether its implemented in Hugs (probably not?) and GHC (probably, but maybe with bugs?). We'll use the not so good translatation let (a,b) = e in e' <=> let x = e; a = fst x; b = snd x; in e' I'd like to call sqnc differently, namely many . We get many p ts = let z = p ts r = fst z ts' = snd z in case r of Nothing -> ([], ts') Just x -> let z' = many p ts' r' = fst z' ts''= snd z' in (x:r', ts'') Intimidating, no? :) Now, let's evaluate an example expression, like many item (1:2:3:...) (the list is intended to be finite, but we'll decide later about its length). To preserve space and stay sane, we'll only focus on the things that get evaluated and write ... for the rest. Let's start: many item (1:2:3:...) => let ts = 1:2:3:... in let ... z = item ts; r = fst z; ... in case r of ... => let ... z = (Just (head ts), tail ts); r = fst z ... => let ... z = (r, tail ts); r = Just (head ts) ... in case r of The above step is not clear from the description in the wikibook, but it's a handy notation of saying that the first component and r point to the same thing. Expanding the case expression yields (in full form) => let ts = 1:2:3: ... in let z = (r, tail ts) r = Just x x = head ts ts'= snd z in let z' = many item ts' r' = fst z' ts''= snd z' in (x:r', ts'') This is the weak head normal form of our expression. Of course, we wanted print (many item ts) = putStrLn (show ...) which means evaluating the first component and then the second component in the pair to full normal form. So, the next redex to be reduced is x followed by r' which forces z' which at least forces ts' => ... => let ts = x:ts' x = 1 ts' = 2:3:... in let z = (r, ts') r = Just x in let z' = let ... in (..,..) r' = fst z' ts''= snd z' in (x:r',ts'') To stay sane, we garbage collect z and r and rename variables before expanding the expression for z' which is obtained in the same way we obtained it before let ts0 = x0 : ts1 x0 = 1 ts1 = 2:3:... z0 = let z = (r, tail ts1) r = Just x x = head ts1 ts'= snd z in let z' = many item ts' r' = fst z' ts''= snd z' in (x:r', ts'') r0 = fst z0 us0 = snd z0 in (x0:r0, us0) Collecting lets and renaming yields let ts0 = x0 : ts1 x0 = 1 ts1 = 2:3:... z = (r, tail ts1) r = Just x1 x1 = head ts1 ts' = snd z z1 = many item ts' r1 = fst z1 us1 = snd z1 z0 = (x1:r1, us1) r0 = fst z0 us0 = snd z0 in (x0:r0, us0) The insight is that the original naming was bad, r and z are quite different from r0 and z0. Reducing r0 and x1 yields => let ts0 = x0 : ts1 x0 = 1 ts1 = x1 : ts2 x1 = 2 ts2 = 3:... z = (r, tail ts1) r = Just x1 ts' = snd z z1 = many item ts' r1 = fst z1 us1 = snd z1 z0 = (r0, us1) r0 = x1:r1 us0 = snd z0 in (x0:r0, us0) The general scheme should be clear now: z,r and ts' are temporary variables and further reduction of r1, r2 and so on leads to a chain let x0 = 1; ts0 = x0 : ts1 x1 = 2; ts1 = x1 : ts2 x2 = 3; ts2 = x2 : ts3 ... x8 = .. z = (r, tail ts8) r = Just x8 ts' = snd z z8 = many item ts' r8 = fst z8 us8 = snd z8 z7 = (r7, us8) r7 = x8:r8 us7 = snd z7 ... z0 = (r0, us1) r0 = x1:r1 us0 = snd z0 in (x0:r0, us0) So, after forcing the first component of the overall result to normal form, the result looks like (1:2:3:..., snd (_,snd (_,snd (_,...))) ) and it seems that Hugs fails to evaluate the tail recursive chain of snd ?? In the end, here's our decisive result: either Hugs or my analysis has a bug :D Regards, apfelmus