Evaluation order, ghc versus hugs, lazy vs. strict
Hello, I am wrestling with having Haskell (using ghc(i) version 5.02.2) evaluate things in good order and to garbage collect what he no longer needs. I could simplify the problem to this simple example: main = print $ sum [0..1000000] When you use a sufficiently large number (perhaps 10000000 instead of 1000000), both ghci and ghc terminate with "Stack space overflow". On the other hand, Hugs (dated December 2001) runs the example OK and produces the result of 500000500000. I have the following questions: 1. Why does this happen? Why does not ghc Haskell generate the list lazily, summing as he goes and forgetting what he no longer needs? 2. How can I find out what happens? The normal profiling ( -prof -auto-all ) does not seem to be very helpful. Could not we get some kind of tracing, printing out what is being evaluated? 3. How can I tell Haskell what I want ? a) that the (+) in sum is strict. It is in this case but in other more complex, like "foldl1 f [0..1000000]" I end up with closures f ( f ( f ( f ( ....)))) which are not evaluated until the end. b) that the list [0..1000000] should be lazy, e.g. evaluated only as needed I will be very grateful for any help. I am trying to use Haskell for numerical calculations but so far I am not very satisfied: the code is very elegant but runs of the order of many magnitudes slower than the corresponding C implementation. Please help me avoid going to C again. Thanks, Jan -- ------------------------------------------------------------------------- Jan Kybic <kybic@ieee.org> Odyssee, INRIA, Sophia-Antipolis, France or <Jan.Kybic@sophia.inria.fr>,tel. work +33 492 38 7589, fax 7845 http://www-sop.inria.fr/robotvis/personnel/Jan.Kybic/
main = print $ sum [0..1000000]
When you use a sufficiently large number (perhaps 10000000 instead of 1000000), both ghci and ghc terminate with "Stack space overflow". On the other hand, Hugs (dated December 2001) runs the example OK and produces the result of 500000500000.
I have the following questions:
1. Why does this happen? Why does not ghc Haskell generate the list lazily, summing as he goes and forgetting what he no longer needs?
As you've apparently discovered, the trick is to be lazy but not too lazy. That is, you want to generate the list lazily but compute a partial result (i.e., the running total of that part of the list processed so far) strictly. GHC and Hugs both produce the list lazily. Hugs uses foldl' instead of foldl to define sum: foldl' :: (a -> b -> a) -> a -> [b] -> a foldl' f a [] = a foldl' f a (x:xs) = (foldl' f $! f a x) xs sum = foldl' (+) 0 foldl' behaves exactly like foldl except that it is a little stricter. (To turn foldl' into foldl, replace the $! on the 3rd line with $. $! is the strict version of 'apply' ($).) With a great deal of effort, one could construct examples where Hugs fails to behave as the Haskell report requires. My guess is that GHC doesn't have this optimization. But I'd also have guessed that GHC would have automatically inferred this optimization if you compile with -O2
3. How can I tell Haskell what I want ? a) that the (+) in sum is strict. It is in this case but in other more complex, like "foldl1 f [0..1000000]" I end up with closures f ( f ( f ( f ( ....)))) which are not evaluated until the end.
Use foldl' More importantly, understand how foldl' works and be ready to apply the same analysis and fix to any similar function. -- Alastair Reid alastair@reid-consulting-uk.ltd.uk Reid Consulting (UK) Limited http://www.reid-consulting-uk.ltd.uk/alastair/
On Mon, Aug 19, 2002 at 11:34:48PM +0100, Alastair Reid wrote:
main = print $ sum [0..1000000] ... Hugs uses foldl' instead of foldl to define sum:...
Does it really? That's a violation of the standard: a user's instance of (+) need not be strict in its left argument. Consider
data Foo = Foo Integer deriving (Eq, Show)
instance Num Foo where fromInteger = Foo a + b = b
v1 = undefined + Foo 2 v2 = sum [undefined, Foo 2]
Both v1 and v2 should have the value 'Foo 2'. However, hugs (December 2001) gives Program error: {undefined} in response to v2. ghci gets it right. --Dylan
On Mon, Aug 19, 2002 at 11:19:41PM +0200, Jan Kybic wrote:
Hello, I am wrestling with having Haskell (using ghc(i) version 5.02.2) evaluate things in good order and to garbage collect what he no longer needs. I could simplify the problem to this simple example:
main = print $ sum [0..1000000]
When you use a sufficiently large number (perhaps 10000000 instead of 1000000), both ghci and ghc terminate with "Stack space overflow". On the other hand, Hugs (dated December 2001) runs the example OK and produces the result of 500000500000.
ghc -O2 seems to run the program above in constant space. I guess strictness analysis (which knows how to evaluate the foldl) only happens at -O2 or above? Best, Dylan Thurston
As you've apparently discovered, the trick is to be lazy but not too lazy. That is, you want to generate the list lazily but compute a partial result (i.e., the running total of that part of the list processed so far) strictly.
Thanks for all reactions. Now my simplified examples indeed run in constant space. Unfortunatelly, my original code still suffer from the same problem and even '-O2' does not help.
More importantly, understand how foldl' works and be ready to apply the same analysis and fix to any similar function.
This is what I cannot do for the moment. How do I find out what is really going on. Any pointers to a relevant articles/literature? As an example, here is my earlier attempt to define strictFoldl1: strictFoldl1' f (a:b:c) = let strictFoldl1' f a (b:c) = let fab = seq a $ seq b $ f a b in case c of [] -> fab otherwise -> seq fab (strictFoldl1' f fab c) in strictFoldl1' f a (b:c) However, it does not seem to do the trick, why Alastair's code does it: foldl' :: (a -> b -> a) -> a -> [b] -> a foldl' f a [] = a foldl' f a (x:xs) = (foldl' f $! f a x) xs foldl1' f (x:xs) = foldl' f x xs Thanks. Jan -- ------------------------------------------------------------------------- Jan Kybic <kybic@ieee.org> Odyssee, INRIA, Sophia-Antipolis, France or <Jan.Kybic@sophia.inria.fr>,tel. work +33 492 38 7589, fax 7845 http://www-sop.inria.fr/robotvis/personnel/Jan.Kybic/
More importantly, understand how foldl' works and be ready to apply the same analysis and fix to any similar function.
This is what I cannot do for the moment. How do I find out what is really going on. Any pointers to a relevant articles/literature?
Read the heap profiling papers from Chalmers, York and Glasgow - both because you probably want to use one and because their analyses of various leaks found with the profilers can be illuminating. http://www.math.chalmers.se/~augustss/AFP/overview.html http://www.math.chalmers.se/~rojemo/thesis.html http://research.microsoft.com/Users/simonpj/Papers/papers.html http://www.cs.york.ac.uk/fp/profile.html [York don't seem to put links to their pages on the web. Citeseer may have some of them.] You will probably end up learning some of what Haskell's syntactic sugar really means along the way. -- Alastair Reid alastair@reid-consulting-uk.ltd.uk Reid Consulting (UK) Limited http://www.reid-consulting-uk.ltd.uk/alastair/
Alastair Reid <alastair@reid-consulting-uk.ltd.uk> writes:
http://www.cs.york.ac.uk/fp/profile.html
[York don't seem to put links to their pages on the web. Citeseer may have some of them.]
Thanks for pointing this out. I've now added lots of links for papers on that webpage. Regards, Malcolm
More importantly, understand how foldl' works and be ready to apply the same analysis and fix to any similar function.
Hi, just a little summary of what I found, in case it might be useful to other beginners struggling with the same problems: * A good page is http://users.aber.ac.uk/ajc99/stricthaskell.html * You want to think hard about which functions you want to make strict and which are better left lazy. * Once you have it, the DeepSeq module together with some syntactic sugar permits you to annotate functions as strict easily: -- strictness annotation, to be used as -- f a x | strict a, deepStrict x = annotation -- f a x = the_true_function_body annotation = undefined strict a = seq a False deepStrict a = deepSeq a False This worked for me, nicely. In doubt, I tried both the strict and lazy versions... * Optimization often changes the behavior. * It helps to have strict versions of some common high-order functions, for example -- strict foldl, just as foldl' strictFoldl :: (a -> b -> a) -> a -> [b] -> a strictFoldl f a [] = a strictFoldl f a (x:xs) = (strictFoldl f $! f a x) xs strictFoldl1 f (x:xs) = strictFoldl f x xs * I could not find any tracing tool for ghc that would enable me to see step by step what happens. Hugs has it (look for Observe). * The heap profiling helps but I have difficulties associating the entities it shows with actual code of my program. Hope this helps, Jan -- ------------------------------------------------------------------------- Jan Kybic <kybic@ieee.org> Odyssee, INRIA, Sophia-Antipolis, France or <Jan.Kybic@sophia.inria.fr>,tel. work +33 492 38 7589, fax 7845 http://www-sop.inria.fr/robotvis/personnel/Jan.Kybic/
Jan Kybic <kybic@ieee.org> writes:
* Once you have it, the DeepSeq module together with some syntactic sugar permits you to annotate functions as strict easily:
-- strictness annotation, to be used as -- f a x | strict a, deepStrict x = annotation -- f a x = the_true_function_body
annotation = undefined strict a = seq a False deepStrict a = deepSeq a False
The 'False' her is rather arbitrary, or am I missing something? Its just that reading the GUM docs, I notice Strategies do something similar, but they return () as the dummy result (which I think may be a better choice) Please let me know if I'm misunderstanding something! -kzm -- If I haven't seen further, it is by standing in the footprints of giants
-- strictness annotation, to be used as -- f a x | strict a, deepStrict x = annotation -- f a x = the_true_function_body strict a = seq a False
The 'False' her is rather arbitrary, or am I missing something?
It must be 'False', to prevent the body = 'annotation' = 'undefined' from getting evaluated.
Hal Daume III <hdaume@ISI.EDU> writes:
It must be 'False', to prevent the body = 'annotation' = 'undefined' from getting evaluated.
I see the conditional now, thanks for pointing it out. (Sigh. I never should have started drinking decaf.) -kzm -- If I haven't seen further, it is by standing in the footprints of giants
Hal Daume III wrote:
-- strictness annotation, to be used as -- f a x | strict a, deepStrict x = annotation -- f a x = the_true_function_body strict a = seq a False
The 'False' her is rather arbitrary, or am I missing something?
It must be 'False', to prevent the body = 'annotation' = 'undefined' from getting evaluated.
Yes, and the ',' is illegal; to get the desired behaviour of both strictness annotations to be effective, it has to be replaced with '||'. All the best Christian Sievers
-- strictness annotation, to be used as -- f a x | strict a, deepStrict x = annotation -- f a x = the_true_function_body
annotation = undefined strict a = seq a False deepStrict a = deepSeq a False
The 'False' her is rather arbitrary, or am I missing something?
[Disclaimer: I only discovered this yesterday, so I am not really an expert.] I think False has the effect that the guard expression (after |) evaluates to False and therefore the first line (f.. = annotation) is never used and f is evaluated according to the second line.
Its just that reading the GUM docs, I notice Strategies do something similar, but they return () as the dummy result (which I think may be a better choice)
What are GUM and Strategies? Could you provide any links? Jan -- ------------------------------------------------------------------------- Jan Kybic <kybic@ieee.org> Odyssee, INRIA, Sophia-Antipolis, France or <Jan.Kybic@sophia.inria.fr>,tel. work +33 492 38 7589, fax 7845 http://www-sop.inria.fr/robotvis/personnel/Jan.Kybic/
Jan Kybic <kybic@ieee.org> writes:
What are GUM and Strategies? Could you provide any links?
http://www.cee.hw.ac.uk/~dsg/gph/docs/Gentle-GPH/sec-gph.html GUM is an implementation of GPH (a parallel Haskell) that runs on top of PVM. Strategies are about making sure parallel threads actually do the work they're intended to before returning control to the main thread; in other words, ensuring sufficient strictness. Or something like that. Grain of salt as applicable, I'm not using any of this yet. -kzm -- If I haven't seen further, it is by standing in the footprints of giants
I think there's more to strategies than this. They are not necessarily related to parallel programming and can be used for tuning (in the seq sense) "sequential" (perhaps "non-parallel" would be a better word) programs. The type of strategies is: type Strategy a = a -> () for example, a strategy which reduces its argument to weak head normal form could be given by: stratWHNF x = x `seq` () We define a funciton 'using' which uses strategies to do a computation: v `using` s = s x `seq` x These are used in parallel programming something like: fib 0 = 1 fib 1 = 1 fib n = a + b `using` strategy where a = fib (n-1) b = fib (n-2) strategy result = a `par` b `par` result This clearly separates the computation "a+b" from the way it is evaluated "a in parallel to b in parallel to the result (i.e., a+b)". But this can of course be used for sequential programming, too, simply by using seq instead of par in the above example. This enables you to write clean code (your functions stay the same, except they are appended with `using` strategy), but you can control more precisely when things get reduced. - Hal -- Hal Daume III "Computer science is no more about computers | hdaume@isi.edu than astronomy is about telescopes." -Dijkstra | www.isi.edu/~hdaume On 23 Aug 2002, Ketil Z. Malde wrote:
Jan Kybic <kybic@ieee.org> writes:
What are GUM and Strategies? Could you provide any links?
http://www.cee.hw.ac.uk/~dsg/gph/docs/Gentle-GPH/sec-gph.html
GUM is an implementation of GPH (a parallel Haskell) that runs on top of PVM.
Strategies are about making sure parallel threads actually do the work they're intended to before returning control to the main thread; in other words, ensuring sufficient strictness. Or something like that.
Grain of salt as applicable, I'm not using any of this yet.
-kzm -- If I haven't seen further, it is by standing in the footprints of giants _______________________________________________ Haskell mailing list Haskell@haskell.org http://www.haskell.org/mailman/listinfo/haskell
Dear All, Hal's comments on the use of Evaluation Strategies for controlling strictness are substantially right, and they are used this way in Eden, a parallel Haskell. In Glasgow parallel Haskell(GpH) we use them to control parallel evaluation as well. The key reference is Algorithm + Strategy = Parallelism, Journal of Functional Programming, 8(1):23--60, January 1998. http://www.cee.hw.ac.uk/~dsg/gph/papers/ Highlights are as follows. There are three basic strategies: r0, rwhnf, rnf :: Strategy a r0 - does no evaluation, rwhnf - reduces it's argument to Weak Head Normal Form (WHNF). Hal defines this as stratWHNF), and rnf - reduces it's argument to normal form (i.e. containing no redexes). It's defined in a class similar to the Eval class Strategies can be composed, e.g. seqList applies a strategy to every element of a list: seqList :: Strategy a -> Strategy [a] seqList s [] = () seqList s (x:xs) = s x 'seq' (seqList s xs) so seqList r0 :: Stratgy [a] - evaluates just the spine of a list seqList rwnf :: Strategy [a] - evaluates every element to WHNF seqList (seqList r0) :: Strategy [[a]] - evaluates just spines of every sublist in a list of lists Analogous parallel strategies, like parList, also exist. The Strategies.lhs module is distributed with GHC (since version 0.29), so simply 'import Strategies' if you want to play. HTH Phil On Fri, 23 Aug 2002 05:10:05 -0700 (PDT) Hal Daume III <hdaume@ISI.EDU> wrote:
I think there's more to strategies than this. They are not necessarily related to parallel programming and can be used for tuning (in the seq sense) "sequential" (perhaps "non-parallel" would be a better word) programs.
The type of strategies is:
type Strategy a = a -> ()
for example, a strategy which reduces its argument to weak head normal form could be given by:
stratWHNF x = x `seq` ()
We define a funciton 'using' which uses strategies to do a computation:
v `using` s = s x `seq` x
These are used in parallel programming something like:
fib 0 = 1 fib 1 = 1 fib n = a + b `using` strategy where a = fib (n-1) b = fib (n-2) strategy result = a `par` b `par` result
This clearly separates the computation "a+b" from the way it is evaluated "a in parallel to b in parallel to the result (i.e., a+b)".
But this can of course be used for sequential programming, too, simply by using seq instead of par in the above example. This enables you to write clean code (your functions stay the same, except they are appended with `using` strategy), but you can control more precisely when things get reduced.
- Hal
-- Hal Daume III
"Computer science is no more about computers | hdaume@isi.edu than astronomy is about telescopes." -Dijkstra | www.isi.edu/~hdaume
On 23 Aug 2002, Ketil Z. Malde wrote:
Jan Kybic <kybic@ieee.org> writes:
What are GUM and Strategies? Could you provide any links?
http://www.cee.hw.ac.uk/~dsg/gph/docs/Gentle-GPH/sec-gph.html
GUM is an implementation of GPH (a parallel Haskell) that runs on top of PVM.
Strategies are about making sure parallel threads actually do the work they're intended to before returning control to the main thread; in other words, ensuring sufficient strictness. Or something like that.
Grain of salt as applicable, I'm not using any of this yet.
-kzm -- If I haven't seen further, it is by standing in the footprints of giants _______________________________________________ Haskell mailing list Haskell@haskell.org http://www.haskell.org/mailman/listinfo/haskell
_______________________________________________ Haskell mailing list Haskell@haskell.org http://www.haskell.org/mailman/listinfo/haskell
-------------------------------------------------- Phil Trinder Department of Computing and Electrical Engineering Heriot Watt University Riccarton Edinburgh, EH14 4AS E-mail: trinder@cee.hw.ac.uk Teleph: +44 (0)131 451 3435 Depart: +44 (0)131 451 3328 Fasmly: +44 (0)131 451 3327 Intrnt: http://www.cee.hw.ac.uk/~trinder
On Tue, Aug 20, 2002 at 10:43:39AM +0200, Jan Kybic wrote:
This is what I cannot do for the moment. How do I find out what is really going on. Any pointers to a relevant articles/literature? ...
In addition to the other suggestions, see Chapter 6 ("Advice on: sooner, faster, smaller, thriftier") of the GHC user's manual. --Dylan Thurston
participants (8)
-
Alastair Reid -
Christian Sievers -
Dylan Thurston -
Hal Daume III -
Jan Kybic -
ketil＠ii.uib.no -
Malcolm Wallace -
Phil Trinder