Too lazy reduction when using seq. #67
Labels
Comments
|
Also I see the BUG. Ajhc output C source code is at https://gist.github.com/master-q/7998665. But it's difficult bug. Could you give time to fix it? |
|
Ajhc's foldl' is definded at https://github.com/ajhc/ajhc/blob/v0.8.0.10/lib/haskell-extras/Data/List.hs#L321. foldl' :: (a -> b -> a) -> a -> [b] -> a
foldl' f z xs = lgo z xs where
lgo z [] = z
lgo z (x:xs) = let z' = f z x in z' `seq` lgo z' xs |
|
Dump debug information ant put it on https://github.com/ajhc/ajhc-dumpyard/tree/master/issue67_too-lazy-reduction. |
|
"seq" is a foreign import primitive, defined at https://github.com/ajhc/ajhc/blob/v0.8.0.10/lib/jhc/Jhc/Basics.hs#L34. |
|
The "seq" primitive's implementation is defined at https://github.com/ajhc/ajhc/blob/v0.8.0.10/src/E/Values.hs#L153. prim_seq a b | isWHNF a = b
prim_seq a b = caseUpdate emptyCase { eCaseScrutinee = a, eCaseBind = (tVr emptyId (getType a)), eCaseDefault = Just b, eCaseType = getType b }isWHNF? https://github.com/ajhc/ajhc/blob/v0.8.0.10/src/E/E.hs#L25 isWHNF ELit {} = True
isWHNF ELam {} = True
isWHNF EPi {} = True
isWHNF ESort {} = True
isWHNF ELetRec { eBody = e } = isWHNF e
isWHNF _ = FalseUmm... |
|
I think "caseUpdate" should force "a" arity such like "seq"... |
swc d@(a,b,c) e = a `seq` b `seq` c `seq` d `seq` wwc d e
-- Equal...
swc d@(a,b,c) e = seq a (seq b (seq c (seq d (wwc d e)))) |
|
First E. in let Main.2_a[]∷(Main.v199[]∷*) = x4[]∷(Main.v199[]∷*); in let
Main.1_d[]∷(Main.v199[]∷*,Main.v200[]∷*,Bool) =
x2[]∷(Main.v199[]∷*,Main.v200[]∷*,Bool);
in (Jhc.Basics.seq[]∷∀Jhc.Basics.16_a.∀Jhc.Basics.17_b.
(Jhc.Basics.16_a[]∷*) → (Jhc.Basics.17_b[]∷*) → (Jhc.Basics.17_b[]∷*)) (Main.v199[]∷*) (Main.v199[]∷*
,Main.v200[]∷*
,Bool) (Main.2_a[]∷(Main.v199[]∷*)) ((Jhc.Basics.seq[]∷∀Jhc.Basics.16_a.
∀Jhc.Basics.17_b.
(Jhc.Basics.16_a[]∷*) → (Jhc.Basics.17_b[]∷*) → (Jhc.Basics.17_b[]∷*)) (Main.v200[]∷*) (Main.v199[]∷*
,Main.v200[]∷*
,Bool) (Main.3_b[]∷(Main.v200[]∷*)) ((Jhc.Basics.seq[]∷∀Jhc.Basics.16_a.
∀Jhc.Basics.17_b.
(Jhc.Basics.16_a[]∷*) → (Jhc.Basics.17_b[]∷*) → (Jhc.Basics.17_b[]∷*)) Bool (Main.v199[]∷*
,Main.v200[]∷*
,Bool) (Main.4_c[]∷Bool) ((Jhc.Basics.seq[]∷∀Jhc.Basics.16_a.
∀Jhc.Basics.17_b.
(Jhc.Basics.16_a[]∷*) → (Jhc.Basics.17_b[]∷*) → (Jhc.Basics.17_b[]∷*)) (Main.v199[]∷*
,Main.v200[]∷*
,Bool) (Main.v199[]∷*
,Main.v200[]∷*
,Bool) (Main.1_d[]∷(Main.v199[]∷*
,Main.v200[]∷*
,Bool)) ((Main.wwc[]∷∀Main.v133.
∀Main.v134. |
|
Before remove seq. in
(Jhc.Basics.seq[Arity 4 False,\\\\ArT,<4,[A,A,S,S]>,[INLINE,_EXPORTED],λλλλ⊤]∷∀Jhc.Basics.16_a.
∀Jhc.Basics.17_b.
(Jhc.Basics.16_a[]∷*) → (Jhc.Basics.17_b[]∷*) → (Jhc.Basics.17_b[]∷*)) (Integer
,Integer
,Bool) (Integer
,Integer
,Bool) (Main.1_d[Arity 0 False,ArT]∷(Integer
,Integer
,Bool)) (x114617052[Arity 0 False,ArT]∷(Integer
,Integer
,Bool));
in let
Main.4_c[Arity 0 False,ArT,UseInfo {useOccurance = Many, minimumArgs = 0}]∷Bool =
x6[]∷Bool;
in
(Jhc.Basics.seq[Arity 4 False,\\\\ArT,<4,[A,A,S,S]>,[INLINE,_EXPORTED],λλλλ⊤]∷∀Jhc.Basics.16_a.
∀Jhc.Basics.17_b.
(Jhc.Basics.16_a[]∷*) → (Jhc.Basics.17_b[]∷*) → (Jhc.Basics.17_b[]∷*)) Bool (Integer
,Integer
,Bool) (Main.4_c[Arity 0 False,ArT]∷Bool) (x94502784[Arity 0 False,ArT]∷(Integer
,Integer
,Bool));
in let
Main.3_b[Arity 0 False,ArT,UseInfo {useOccurance = Many, minimumArgs = 0}]∷Integer =
x5[]∷Integer;
in
(Jhc.Basics.seq[Arity 4 False,\\\\ArT,<4,[A,A,S,S]>,[INLINE,_EXPORTED],λλλλ⊤]∷∀Jhc.Basics.16_a.
∀Jhc.Basics.17_b.
(Jhc.Basics.16_a[]∷*) → (Jhc.Basics.17_b[]∷*) → (Jhc.Basics.17_b[]∷*)) Integer (Integer
,Integer
,Bool) (Main.3_b[Arity 0 False,ArT]∷Integer) (x103712075[Arity 0 False,ArT]∷(Integer
,Integer
,Bool));
in let
Main.2_a[Arity 0 False,ArT,UseInfo {useOccurance = Many, minimumArgs = 0}]∷Integer =
x4[]∷Integer;
in
(Jhc.Basics.seq[Arity 4 False,\\\\ArT,<4,[A,A,S,S]>,[INLINE,_EXPORTED],λλλλ⊤]∷∀Jhc.Basics.16_a.
∀Jhc.Basics.17_b.
(Jhc.Basics.16_a[]∷*) → (Jhc.Basics.17_b[]∷*) → (Jhc.Basics.17_b[]∷*)) Integer (Integer
,Integer
,Bool) (Main.2_a[Arity 0 False,ArT]∷Integer) (x35823661[Arity 0 False,ArT]∷(Integer
,Integer
,Bool));
_[]∷(Integer,Integer,Bool) →
<⊥:Main.hs:4:17: Unmatched pattern∷(Integer
,Integer
,Bool)>;∷(Integer
,Integer
,Bool); |
|
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
If you want to make a pass of a BIG list with foldl you run the risk of stack overflow.
The solution is to use foldl' that is stric in the accumulator.
and your function should be stric in the accumulator.
here is an example that will count the words and lines in an input.
import Data.Char import Data.List swc d@(a,b,c) e = a `seq` b `seq` c `seq` d `seq` wwc d e wwc (0,0,False) c = wwc (1,0,False) c wwc (l,w,_) '\n' = (l + 1, w,False) wwc (l,w,False) c | isSpace c = (l,w,False) | otherwise = (l,w+1,True) wwc (l,w,_) c | isSpace c = (l,w,False) | otherwise = (l,w,True) main = interact (show . foldl' swc (0,0,False))If I compile with ghc or hugs I get a constant space execution no matter the input.
With ajhc it will do stack overflow because we are using a recursive call (seen with gdb at the coredump).
The text was updated successfully, but these errors were encountered: