The following code, when compiled with GHC 6.6.1 --make -O gives a stack overflow when I enter 1000000 as a command line argument: (please don't look at the efficiency of the code, it can of course be improved a lot both in time performance and numeric precision...) import System leibnizPI :: Integer -> Double leibnizPI n = sum (map leibnizTerm [0..n]) where leibnizTerm n = let i = fromIntegral n in 4 * (((-1) ** i) / (2*i+1)) main = do args <- getArgs let n = read (head args) print (leibnizPI n) However, if I replace main = print (leibnizPI 1000000) is does not stack overflow. Now, if I leave the original main, but replace sum in leibnizPI by mysum xs = aux 0 xs where aux s (x:xs) = aux (s+x) xs aux s [] = s then I don't get a stack overflow. However, I do get a stack overflow when I compile it without -O, in all cases. This puzzles me. I don't see any non-tail calls in my code... I guess it has to do with strictness? http://www.haskell.org/haskellwiki/Performance/Strictness Why isn't it possible to annotate strictness on the type signature in Haskell as in Clean? Is this on the TODO list? Many thanks, Peter
Peter Verswyvelen wrote:
The following code, when compiled with GHC 6.6.1 --make -O gives a stack overflow when I enter 1000000 as a command line argument:
(please don't look at the efficiency of the code, it can of course be improved a lot both in time performance and numeric precision...)
import System
leibnizPI :: Integer -> Double leibnizPI n = sum (map leibnizTerm [0..n]) where leibnizTerm n = let i = fromIntegral n in 4 * (((-1) ** i) / (2*i+1)) main = do args <- getArgs let n = read (head args) print (leibnizPI n)
However, if I replace
main = print (leibnizPI 1000000)
is does not stack overflow.
Now, if I leave the original main, but replace sum in leibnizPI by
mysum xs = aux 0 xs where aux s (x:xs) = aux (s+x) xs aux s [] = s
Then I don't get a stack overflow.
However, I do get a stack overflow when I compile it without -O, in all cases.
This puzzles me. I don't see any non-tail calls in my code...
I guess it has to do with strictness? http://www.haskell.org/haskellwiki/Performance/Strictness
Yes. The problem is that without optimizations, both sum and mysum build a large unevaluated expression of the form ((..((0+x1)+x2)+...)+xn) The stack overflow happens when this expression gets evaluated. At that point, the outermost (+) demands the result of the (+) on the next level, and so on. To prevent this you need a stricter version of sum. You can build one with foldl':
import Data.List
sum' :: Num a => [a] -> a sum' = foldl' (+) 0
Arguably this is the "correct" definition of sum. The problem you had is fairly common.
Why isn't it possible to annotate strictness on the type signature in Haskell as in Clean? Is this on the TODO list?
Strictness is independent from the type in Haskell (but see the fourth solution presented below). You can explicitely make one value at least as strict as another using seq:
mysum' xs = aux 0 xs where aux s (x:xs) = let s' = s+x in s' `seq` aux s' xs aux s [] = s
In ghc, you can mark arguments as strict
mysum'' xs = aux 0 xs where aux !s (x:xs) = aux (s+x) xs aux !s [] = s
This is a language extension, you need -fbang-patterns to allow it, or with a recent ghc (6.7, 6.9 or a 6.8 rc) a {-# LANGUAGE BangPatterns #-} pragma, or -XBangPatterns. A fourth possibility, which is Haskell 98 again, is to declare an auxiliary data type with a strict field:
data Strict a = Strict !a
mysum''' xs = aux (Strict 0) xs where aux (Strict s) (x:xs) = aux (Strict (s+x)) xs aux (Strict s) [] = s
Hope that helps, Bertram
Ouch, now I really feel stupid, because I *knew* about the stricter foldl' version. But great to know about the new strictness on vars! I really should get GHC 6.8 RC1 for Windows... I just got puzzled why mysum worked better than sum for some reason... mysym looks like an identical unfolded version of sum to me, yet it behaved differently. mysum, also being non-strict, did *not* stack overflow. Maybe because it is a simpler / more unfolded version, so it needs to keep less euh "unevaluated thunks" (how are these called?) on the stack? So I would also have gotten a stack overflow with mysum, it just needed more iterations? Many thanks, Peter Bertram Felgenhauer wrote:
Peter Verswyvelen wrote:
The following code, when compiled with GHC 6.6.1 --make -O gives a stack overflow when I enter 1000000 as a command line argument:
(please don't look at the efficiency of the code, it can of course be improved a lot both in time performance and numeric precision...)
import System
leibnizPI :: Integer -> Double leibnizPI n = sum (map leibnizTerm [0..n]) where leibnizTerm n = let i = fromIntegral n in 4 * (((-1) ** i) / (2*i+1)) main = do args <- getArgs let n = read (head args) print (leibnizPI n)
However, if I replace
main = print (leibnizPI 1000000)
is does not stack overflow.
Now, if I leave the original main, but replace sum in leibnizPI by
mysum xs = aux 0 xs where aux s (x:xs) = aux (s+x) xs aux s [] = s
Then I don't get a stack overflow.
However, I do get a stack overflow when I compile it without -O, in all cases.
This puzzles me. I don't see any non-tail calls in my code...
I guess it has to do with strictness? http://www.haskell.org/haskellwiki/Performance/Strictness
Yes.
The problem is that without optimizations, both sum and mysum build a large unevaluated expression of the form
((..((0+x1)+x2)+...)+xn)
The stack overflow happens when this expression gets evaluated. At that point, the outermost (+) demands the result of the (+) on the next level, and so on.
To prevent this you need a stricter version of sum. You can build one with foldl':
import Data.List
sum' :: Num a => [a] -> a sum' = foldl' (+) 0
Arguably this is the "correct" definition of sum. The problem you had is fairly common.
Why isn't it possible to annotate strictness on the type signature in Haskell as in Clean? Is this on the TODO list?
Strictness is independent from the type in Haskell (but see the fourth solution presented below). You can explicitely make one value at least as strict as another using seq:
mysum' xs = aux 0 xs where aux s (x:xs) = let s' = s+x in s' `seq` aux s' xs aux s [] = s
In ghc, you can mark arguments as strict
mysum'' xs = aux 0 xs where aux !s (x:xs) = aux (s+x) xs aux !s [] = s
This is a language extension, you need -fbang-patterns to allow it, or with a recent ghc (6.7, 6.9 or a 6.8 rc) a {-# LANGUAGE BangPatterns #-} pragma, or -XBangPatterns.
A fourth possibility, which is Haskell 98 again, is to declare an auxiliary data type with a strict field:
data Strict a = Strict !a
mysum''' xs = aux (Strict 0) xs where aux (Strict s) (x:xs) = aux (Strict (s+x)) xs aux (Strict s) [] = s
Hope that helps,
Bertram _______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
2007/10/6, Peter Verswyvelen
But great to know about the new strictness on vars! I really should get GHC 6.8 RC1 for Windows...
Just in case you misunderstood : this functionality was already there in GHC 6.4, it's just the new syntax to active it that is available only in recent versions of GHC : this new syntax will hopefully be adopted by others Haskell compilers and thus become a compiler-agnostic way of specifying extensions to Haskell98 (so that others compiler than GHC can tell you why they won't compile this wonderful code that use all the latest extensions that have been included into your release candidate of GHC, much better than the old way where they just told you the syntax was wrong, isn't it ?). -- Jedaï
Just to be clear, I doubt the difference had anything to do with
tail-recursion per se. My guess is that with the "mysum" version, ghc was
able to do some strictness analysis/optimization that it wasn't able to do
(for whatever reason) with the first version. The best solution (as others
have pointed out) is to create a strict version of sum with foldl'.
On 10/6/07, Peter Verswyvelen
Ouch, now I really feel stupid, because I *knew* about the stricter foldl' version.
But great to know about the new strictness on vars! I really should get GHC 6.8 RC1 for Windows...
I just got puzzled why mysum worked better than sum for some reason... mysym looks like an identical unfolded version of sum to me, yet it behaved differently. mysum, also being non-strict, did *not* stack overflow. Maybe because it is a simpler / more unfolded version, so it needs to keep less euh "unevaluated thunks" (how are these called?) on the stack? So I would also have gotten a stack overflow with mysum, it just needed more iterations?
Many thanks, Peter
Bertram Felgenhauer wrote:
Peter Verswyvelen wrote:
The following code, when compiled with GHC 6.6.1 --make -O gives a stack overflow when I enter 1000000 as a command line argument:
(please don't look at the efficiency of the code, it can of course be improved a lot both in time performance and numeric precision...)
import System
leibnizPI :: Integer -> Double leibnizPI n = sum (map leibnizTerm [0..n]) where leibnizTerm n = let i = fromIntegral n in 4 * (((-1) ** i) / (2*i+1)) main = do args <- getArgs let n = read (head args) print (leibnizPI n)
However, if I replace
main = print (leibnizPI 1000000)
is does not stack overflow.
Now, if I leave the original main, but replace sum in leibnizPI by
mysum xs = aux 0 xs where aux s (x:xs) = aux (s+x) xs aux s [] = s
Then I don't get a stack overflow.
However, I do get a stack overflow when I compile it without -O, in all cases.
This puzzles me. I don't see any non-tail calls in my code...
I guess it has to do with strictness? http://www.haskell.org/haskellwiki/Performance/Strictness
Yes.
The problem is that without optimizations, both sum and mysum build a large unevaluated expression of the form
((..((0+x1)+x2)+...)+xn)
The stack overflow happens when this expression gets evaluated. At that point, the outermost (+) demands the result of the (+) on the next level, and so on.
To prevent this you need a stricter version of sum. You can build one with foldl':
import Data.List
sum' :: Num a => [a] -> a sum' = foldl' (+) 0
Arguably this is the "correct" definition of sum. The problem you had is fairly common.
Why isn't it possible to annotate strictness on the type signature in Haskell as in Clean? Is this on the TODO list?
Strictness is independent from the type in Haskell (but see the fourth solution presented below). You can explicitely make one value at least as strict as another using seq:
mysum' xs = aux 0 xs where aux s (x:xs) = let s' = s+x in s' `seq` aux s' xs aux s [] = s
In ghc, you can mark arguments as strict
mysum'' xs = aux 0 xs where aux !s (x:xs) = aux (s+x) xs aux !s [] = s
This is a language extension, you need -fbang-patterns to allow it, or with a recent ghc (6.7, 6.9 or a 6.8 rc) a {-# LANGUAGE BangPatterns #-} pragma, or -XBangPatterns.
A fourth possibility, which is Haskell 98 again, is to declare an auxiliary data type with a strict field:
data Strict a = Strict !a
mysum''' xs = aux (Strict 0) xs where aux (Strict s) (x:xs) = aux (Strict (s+x)) xs aux (Strict s) [] = s
Hope that helps,
Bertram _______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.orghttp://www.haskell.org/mailman/listinfo/haskell-cafe
_______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
On 10/6/07, Bertram Felgenhauer
This is a language extension, you need -fbang-patterns to allow it, or with a recent ghc (6.7, 6.9 or a 6.8 rc) a {-# LANGUAGE BangPatterns #-} pragma, or -XBangPatterns.
LANGUAGE pragmas (including BangPatterns) work just fine in 6.6, by the way. Stuart
participants (5)
-
Bertram Felgenhauer -
Brent Yorgey -
Chaddaï Fouché -
Peter Verswyvelen -
Stuart Cook