Hello First, thank you for all answers. Le Thu, 03 Dec 2009 18:58:33 +0300, Miguel Mitrofanov a écrit :

Does this really mean that you want to know how the garbage collector works?

Well, I try to understand your question... I will take an example: f x y= x+y The program ask the user to enter two numbers and print the sum. If the user enter "1 2" "f 1 2=3" is stored and a gargage collector is used to remove this dandling expression later ? If the user enter again "1 2", ghc search in dandling results to try to find the result without computing it again ? For Eugene: I use "magic" to mean beautiful and difficult to understand. I believe in magic: I believe everything can be understood with time. -- Emmanuel Chantréau

2009/12/4 Evan Laforge :

The interesting thing is CAFs, which at the top level will never be out of scope and hence live forever.

Untrue! CAFs can be garbage collected as well. See: http://www.haskell.org/pipermail/glasgow-haskell-users/2005-September/009051...

Emmanuel CHANTREAU wrote:

I will take an example:

f x y= x+y

The program ask the user to enter two numbers and print the sum. If the user enter "1 2" "f 1 2=3" is stored and a gargage collector is used to remove this dandling expression later ? If the user enter again "1 2", ghc search in dandling results to try to find the result without computing it again ?

Hi, I think what you're asking is how Haskell knows at run-time for which expressions it can re-use the results. The answer is: it doesn't, it works it out at compile-time. So if you have: f x y = x + y And at some point in your program you call f 1 2, and later on from a totally separate function you call f 1 2, the function will be evaluated twice (assuming 1 and 2 weren't known constants at compile-time). But let's say you have: g x y = f x y * f x y Now the compiler (i.e. at compile-time) can do some magic. It can spot the common expression and know the result of f x y must be the same both times, so it can convert to: g x y = let z = f x y in z * z Now, the Haskell run-time will evaluate f x y once, store the result in z, and use it twice. That's how it can use commonalities in your code and avoid multiple evaluations of the same function call, which I *think* was your question. Thanks, Neil.

On Dec 4, 2009, at 2:43 AM, Luke Palmer wrote:

So GHC leaves it to the user to specify sharing. If you want an expression shared, let bind it and reuse.

Does GHC treat where and let the same in this regard? Or in code, are these treated the same?

x'' = sum l + product l where l = [1..10^6]

x' = let l = [1..10^6] in sum l + product l

I couldn't tell if the report implies that or not. - Mark Mark Lentczner http://www.ozonehouse.com/mark/ mark@glyphic.com

Luke Palmer wrote:

On Fri, Dec 4, 2009 at 9:44 AM, Mark Lentczner wrote:

...

On Dec 4, 2009, at 2:43 AM, Luke Palmer wrote:

...

So GHC leaves it to the user to specify sharing. If you want an expression shared, let bind it and reuse. Does GHC treat where and let the same in this regard? Or in code, are these treated the same?

where is just sugar for let.

Well, they have different scoping properties because they're in different syntactic classes in the parser (let is an expression whereas where is a modifier on statements), but other than that yes they're the same. -- Live well, ~wren

Fixing my errors:

x = sum [1..10^6] + product [1..10^6] x' = let l = [1..10^6] in sum l + product l

-- Define: bar m n = foo (enumFromTo m n) foo xs = sum xs + prod xs -- We're given: sum = foldl (+) 0 product = foldl (*) 1 foldl f z xs = case xs of [] -> [] x:xs -> foldl f (f z x) xs enumFromTo m n = case n < m of True -> [] False -> m : enumFromTo (m+1) n -- The fused loop becomes: foo xs = go0 0 1 xs where go0 a b xs = case xs of [] -> a+b x:xs -> go0 (a+x) (b*x) xs -- Now inline foo in bar: bar m n = go2 0 1 m n where go2 a b m n = go0 a b (go1 m n) go0 a b xs = case xs of [] -> a+b x:xs -> go0 (a+x) (b*x) xs go1 m n = case m < n of True -> [] False -> m : go1 (m+1) n -- considering go2 go2 a b m n = go0 a b (go1 m n) ==> case (go1 m n) of [] -> a+b x:xs -> go0 (a+x) (b*x) xs ==> case (case n < m of True -> [] False -> m : go1 (m+1) n) of [] -> a+b x:xs -> go0 (a+x) (b*x) xs ==> case n < m of True -> case [] of [] -> a+b x:xs -> go0 (a+x) (b*x) xs False -> case (m : go1 (m+1) n) of [] -> a+b x:xs -> go0 (a+x) (b*x) xs ==> case n < m of True -> a+b False -> go0 (a+m) (b*m) (go1 (m+1) n) -- So, go2 a b m n = case n < m of True -> a+b False -> go0 (a+m) (b*m) (go1 (m+1) n) -- And by the original def of go2 go2 a b m n = go0 a b (go1 m n) -- We get go2 a b m n = case m < n of True -> a+b False -> go2 (a+m) (b*m) (m+1) n -- go0 and go1 and now dead in bar bar m n = go2 0 1 m n where go2 a b m n = case n < m of True -> a+b False -> go2 (a+m) (b*m) (m+1) n -- (furthermore, if (+) here is for Int/Double etc, -- we can reduce go2 further to operate on machine -- ints/doubles and be a register-only non-allocating loop) -- So now finally returning to our original code:

x = sum [1..10^6] + product [1..10^6] x' = let l = [1..10^6] in sum l + product l

-- We get: x' = bar 1 (10^6) Matt On 12/4/09, Matt Morrow wrote:

Although, in Luke's example,

...

x = sum [1..10^6] + product [1..10^6] x' = let l = [1..10^6] in sum l + product l

We can do much much better, if we're sufficiently smart.

-- Define: bar m n = foo (enumFromTo m n) foo xs = sum xs + prod xs

-- We're given: sum = foldl (+) 0 product = foldl (*) 1 foldl f z xs = case xs of [] -> [] x:xs -> foldl f (f z x) xs enumFromTo m n = case m < n of True -> [] False -> m : enumFromTo (m+1) n

-- The fused loop becomes: foo xs = go0 0 1 xs where go0 a b xs = case xs of [] -> a+b x:xs -> go0 (a+x) (b*x) xs

-- Now inline foo in bar: bar m n = go2 0 1 m n where go2 = go0 a b (go1 m n) go0 a b xs = case xs of [] -> a+b x:xs -> go0 (a+x) (b*x) xs go1 m n = case m < n of True -> [] False -> m : go1 (m+1) n

-- considering go2 go2 = go0 a b (go1 m n)

==> case (go1 m n) of [] -> a+b x:xs -> go0 (a+x) (b*x) xs

==> case (case m < n of True -> [] False -> m : go1 (m+1) n) of [] -> a+b x:xs -> go0 (a+x) (b*x) xs

==> case m < n of True -> case [] of [] -> a+b x:xs -> go0 (a+x) (b*x) xs

False -> case (m : go1 (m+1) n) of [] -> a+b x:xs -> go0 (a+x) (b*x) xs

==> case m < n of True -> a+b False -> go0 (a+m) (b*m) (go1 (m+1) n)

-- So, go2 = case m < n of True -> a+b False -> go0 (a+m) (b*m) (go1 (m+1) n)

-- And by the original def of go2 go2 = go0 a b (go1 m n)

-- We get go2 = case m < n of True -> a+b False -> go2 (a+m) (b*m) (m+1) n

-- go0 and go1 and now dead in bar bar m n = go2 0 1 m n where go2 = case m < n of True -> a+b False -> go2 (a+m) (b*m) (m+1) n

-- (furthermore, if (+) here is for Int/Double etc, -- we can reduce go2 further to operate on machine -- ints/doubles and be a register-only non-allocating loop)

-- So now finally returning to our original code:

...

x = sum [1..10^6] + product [1..10^6] x' = let l = [1..10^6] in sum l + product l

-- We get: x' = bar 1 (10^6)

And the intermediate list never exists at all.

Matt

On 12/4/09, Luke Palmer wrote:

...

On Fri, Dec 4, 2009 at 3:36 AM, Neil Brown wrote:

...

But let's say you have:

g x y = f x y * f x y

Now the compiler (i.e. at compile-time) can do some magic. It can spot the common expression and know the result of f x y must be the same both times, so it can convert to:

g x y = let z = f x y in z * z

GHC does *not* do this by default, quite intentionally, even when optimizations are enabled. The reason is because it can cause major changes in the space complexity of a program. Eg.

x = sum [1..10^6] + product [1..10^6] x' = let l = [1..10^6] in sum l + product l

x runs in constant space, but x' keeps the whole list in memory. The CSE here has actually wasted both time and space, since it is harder to save [1..10^6] than to recompute it! (Memory vs. arithmetic ops)

So GHC leaves it to the user to specify sharing. If you want an expression shared, let bind it and reuse.

Luke _______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe