types and number of evaluation steps

Previous Topic Next Topic
 
classic Classic list List threaded Threaded
12 messages Options
Reply | Threaded
Open this post in threaded view
|

types and number of evaluation steps

Heinrich Hördegen

Dear all,

I have a question about evaluation with respect to types and currying.
Consider this programm:

import Debug.Trace

-- add :: Integer -> Integer -> Integer
add :: Int -> Int -> Int
add x y = x + y

f a b c = trace "b" (add x c) where x = trace "a" (add a b)

main :: IO ()
main = do
   print (f 1 2 3)
   print (f 1 2 4)


Compiled with ghc-7.0.3:

$ ghc --make Main.hs -o main -O2

The function add has to types. When we use type Int -> Int -> Int, the
programm produces "b a 6 b a 7" as output which shows that the x from
the where clause in f is evaluated twice. However, when we use type
Integer -> Integer -> Integer, this will give "b a 6 b 7" which shows
that x is evaluated only once. This was rather unexpected to me.

Why does the number of evaluation steps depend on a type? Can anybody
explain this or give a hint?

Thank you very much,
Heinrich



--
--

[hidden email]
www.funktional.info

--


_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe
Reply | Threaded
Open this post in threaded view
|

Re: types and number of evaluation steps

MigMit
Different kinds of optimization. I expect you'd have different results even if you use one type, but different -O flags.

On 18 Feb 2012, at 13:28, Heinrich Hördegen wrote:

>
> Dear all,
>
> I have a question about evaluation with respect to types and currying. Consider this programm:
>
> import Debug.Trace
>
> -- add :: Integer -> Integer -> Integer
> add :: Int -> Int -> Int
> add x y = x + y
>
> f a b c = trace "b" (add x c) where x = trace "a" (add a b)
>
> main :: IO ()
> main = do
>  print (f 1 2 3)
>  print (f 1 2 4)
>
>
> Compiled with ghc-7.0.3:
>
> $ ghc --make Main.hs -o main -O2
>
> The function add has to types. When we use type Int -> Int -> Int, the programm produces "b a 6 b a 7" as output which shows that the x from the where clause in f is evaluated twice. However, when we use type Integer -> Integer -> Integer, this will give "b a 6 b 7" which shows that x is evaluated only once. This was rather unexpected to me.
>
> Why does the number of evaluation steps depend on a type? Can anybody explain this or give a hint?
>
> Thank you very much,
> Heinrich
>
>
>
> --
> --
>
> [hidden email]
> www.funktional.info
>
> --
>
>
> _______________________________________________
> Haskell-Cafe mailing list
> [hidden email]
> http://www.haskell.org/mailman/listinfo/haskell-cafe


_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe
Reply | Threaded
Open this post in threaded view
|

Re: types and number of evaluation steps

Heinrich Hördegen
  Hi,

this is true. The optimization only works with -O2. I'd like to have
more details about what's going on. How can I make sure, that this
optimization triggers?

Heinrich

On 18.02.2012 11:10, MigMit wrote:

> Different kinds of optimization. I expect you'd have different results even if you use one type, but different -O flags.
>
> On 18 Feb 2012, at 13:28, Heinrich Hördegen wrote:
>
>> Dear all,
>>
>> I have a question about evaluation with respect to types and currying. Consider this programm:
>>
>> import Debug.Trace
>>
>> -- add :: Integer ->  Integer ->  Integer
>> add :: Int ->  Int ->  Int
>> add x y = x + y
>>
>> f a b c = trace "b" (add x c) where x = trace "a" (add a b)
>>
>> main :: IO ()
>> main = do
>>   print (f 1 2 3)
>>   print (f 1 2 4)
>>
>>
>> Compiled with ghc-7.0.3:
>>
>> $ ghc --make Main.hs -o main -O2
>>
>> The function add has to types. When we use type Int ->  Int ->  Int, the programm produces "b a 6 b a 7" as output which shows that the x from the where clause in f is evaluated twice. However, when we use type Integer ->  Integer ->  Integer, this will give "b a 6 b 7" which shows that x is evaluated only once. This was rather unexpected to me.
>>
>> Why does the number of evaluation steps depend on a type? Can anybody explain this or give a hint?
>>
>> Thank you very much,
>> Heinrich
>>
>>
>>
>> --
>> --
>>
>> [hidden email]
>> www.funktional.info
>>
>> --
>>
>>
>> _______________________________________________
>> Haskell-Cafe mailing list
>> [hidden email]
>> http://www.haskell.org/mailman/listinfo/haskell-cafe
>


--
--

Funktionale Programmierung Dr. Heinrich Hördegen
Gutenbergstr. 26
80638 München

FON: +49 (89) 12 59 79 49
FAX: +49 (89) 12 59 79 50

[hidden email]
www.funktional.info

--


_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe
Reply | Threaded
Open this post in threaded view
|

Re: types and number of evaluation steps

Holger Siegel
Am 18.02.2012 um 11:56 schrieb Heinrich Hördegen:

> Hi,
>
> this is true. The optimization only works with -O2. I'd like to have more details about what's going on. How can I make sure, that this optimization triggers?

You cannot. Common subexpression elimination is done by GHC very conservatively, because it can not only affect impure programs: it can also affects strictness/lazyness and worsen memory usage of pure code. Like the HaskellWiki says: "If you care about CSE, do it by hand."

Holger

>
> Heinrich
>
> On 18.02.2012 11:10, MigMit wrote:
>> Different kinds of optimization. I expect you'd have different results even if you use one type, but different -O flags.
>>
>> On 18 Feb 2012, at 13:28, Heinrich Hördegen wrote:
>>
>>> Dear all,
>>>
>>> I have a question about evaluation with respect to types and currying. Consider this programm:
>>>
>>> import Debug.Trace
>>>
>>> -- add :: Integer ->  Integer ->  Integer
>>> add :: Int ->  Int ->  Int
>>> add x y = x + y
>>>
>>> f a b c = trace "b" (add x c) where x = trace "a" (add a b)
>>>
>>> main :: IO ()
>>> main = do
>>>  print (f 1 2 3)
>>>  print (f 1 2 4)
>>>
>>>
>>> Compiled with ghc-7.0.3:
>>>
>>> $ ghc --make Main.hs -o main -O2
>>>
>>> The function add has to types. When we use type Int ->  Int ->  Int, the programm produces "b a 6 b a 7" as output which shows that the x from the where clause in f is evaluated twice. However, when we use type Integer ->  Integer ->  Integer, this will give "b a 6 b 7" which shows that x is evaluated only once. This was rather unexpected to me.
>>>
>>> Why does the number of evaluation steps depend on a type? Can anybody explain this or give a hint?
>>>
>>> Thank you very much,
>>> Heinrich
>>>
>>>
>>>
>>> --
>>> --
>>>
>>> [hidden email]
>>> www.funktional.info
>>>
>>> --
>>>
>>>
>>> _______________________________________________
>>> Haskell-Cafe mailing list
>>> [hidden email]
>>> http://www.haskell.org/mailman/listinfo/haskell-cafe
>>
>
>
> --
> --
>
> Funktionale Programmierung Dr. Heinrich Hördegen
> Gutenbergstr. 26
> 80638 München
>
> FON: +49 (89) 12 59 79 49
> FAX: +49 (89) 12 59 79 50
>
> [hidden email]
> www.funktional.info
>
> --
>
>
> _______________________________________________
> Haskell-Cafe mailing list
> [hidden email]
> http://www.haskell.org/mailman/listinfo/haskell-cafe


_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe
Reply | Threaded
Open this post in threaded view
|

Re: types and number of evaluation steps

Victor Gorokgov
In reply to this post by Heinrich Hördegen
+ on Int is extremely cheap. It is always faster to add again rather
than store the value.
But Integer is a different story. Addition time on this type can grow to
several minutes.

18.02.2012 13:28, Heinrich Hördegen пишет:

>
> Dear all,
>
> I have a question about evaluation with respect to types and currying.
> Consider this programm:
>
> import Debug.Trace
>
> -- add :: Integer -> Integer -> Integer
> add :: Int -> Int -> Int
> add x y = x + y
>
> f a b c = trace "b" (add x c) where x = trace "a" (add a b)
>
> main :: IO ()
> main = do
> print (f 1 2 3)
> print (f 1 2 4)
>
>
> Compiled with ghc-7.0.3:
>
> $ ghc --make Main.hs -o main -O2
>
> The function add has to types. When we use type Int -> Int -> Int, the
> programm produces "b a 6 b a 7" as output which shows that the x from
> the where clause in f is evaluated twice. However, when we use type
> Integer -> Integer -> Integer, this will give "b a 6 b 7" which shows
> that x is evaluated only once. This was rather unexpected to me.
>
> Why does the number of evaluation steps depend on a type? Can anybody
> explain this or give a hint?
>
> Thank you very much,
> Heinrich
>
>
>


_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe
Reply | Threaded
Open this post in threaded view
|

Re: types and number of evaluation steps

Heinrich Hördegen

In case of +, the reason might be that it's cheap, but the function add
could do something else than + (It was just a small example).

Ok, thank you for your useful comments. I will read about cse.
Heinrich


On 18.02.2012 13:42, Victor Gorokgov wrote:

> + on Int is extremely cheap. It is always faster to add again rather
> than store the value.
> But Integer is a different story. Addition time on this type can grow
> to several minutes.
>
> 18.02.2012 13:28, Heinrich Hördegen пишет:
>>
>> Dear all,
>>
>> I have a question about evaluation with respect to types and
>> currying. Consider this programm:
>>
>> import Debug.Trace
>>
>> -- add :: Integer -> Integer -> Integer
>> add :: Int -> Int -> Int
>> add x y = x + y
>>
>> f a b c = trace "b" (add x c) where x = trace "a" (add a b)
>>
>> main :: IO ()
>> main = do
>> print (f 1 2 3)
>> print (f 1 2 4)
>>
>>
>> Compiled with ghc-7.0.3:
>>
>> $ ghc --make Main.hs -o main -O2
>>
>> The function add has to types. When we use type Int -> Int -> Int,
>> the programm produces "b a 6 b a 7" as output which shows that the x
>> from the where clause in f is evaluated twice. However, when we use
>> type Integer -> Integer -> Integer, this will give "b a 6 b 7" which
>> shows that x is evaluated only once. This was rather unexpected to me.
>>
>> Why does the number of evaluation steps depend on a type? Can anybody
>> explain this or give a hint?
>>
>> Thank you very much,
>> Heinrich
>>
>>
>>
>
>
> _______________________________________________
> Haskell-Cafe mailing list
> [hidden email]
> http://www.haskell.org/mailman/listinfo/haskell-cafe


--
--

[hidden email]
www.funktional.info

--


_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe
Reply | Threaded
Open this post in threaded view
|

Re: types and number of evaluation steps

Roman Cheplyaka-2
In reply to this post by Holger Siegel
* Holger Siegel <[hidden email]> [2012-02-18 12:52:08+0100]
> You cannot. Common subexpression elimination is done by GHC very
> conservatively, because it can not only affect impure programs: it can
> also affects strictness/lazyness and worsen memory usage of pure code.
> Like the HaskellWiki says: "If you care about CSE, do it by hand."

How can it affect strictness or laziness?

--
Roman I. Cheplyaka :: http://ro-che.info/

_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe
Reply | Threaded
Open this post in threaded view
|

Re: types and number of evaluation steps

Holger Siegel
       
Am 18.02.2012 um 14:38 schrieb Roman Cheplyaka:

> * Holger Siegel <[hidden email]> [2012-02-18 12:52:08+0100]
>> You cannot. Common subexpression elimination is done by GHC very
>> conservatively, because it can not only affect impure programs: it can
>> also affects strictness/lazyness and worsen memory usage of pure code.
>> Like the HaskellWiki says: "If you care about CSE, do it by hand."
>
> How can it affect strictness or laziness?

I don't know. HaskellWiki says so: http://www.haskell.org/haskellwiki/GHC_optimisations#Common_subexpression_elimination


_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe
Reply | Threaded
Open this post in threaded view
|

Re: types and number of evaluation steps

Victor Gorokgov
In reply to this post by Roman Cheplyaka-2
example = a + b + a + b

exampleCSE = x + x
   where x = a + b

With CSE we are introducing new thunk: x.

18.02.2012 17:38, Roman Cheplyaka пишет:
> * Holger Siegel<[hidden email]>  [2012-02-18 12:52:08+0100]
>> You cannot. Common subexpression elimination is done by GHC very
>> conservatively, because it can not only affect impure programs: it can
>> also affects strictness/lazyness and worsen memory usage of pure code.
>> Like the HaskellWiki says: "If you care about CSE, do it by hand."
> How can it affect strictness or laziness?
>


_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe
Reply | Threaded
Open this post in threaded view
|

Re: types and number of evaluation steps

MigMit
In reply to this post by Heinrich Hördegen
I'm not sure you can. Why do you need it?

Отправлено с iPad

18.02.2012, в 14:56, Heinrich Hördegen <[hidden email]> написал(а):

> Hi,
>
> this is true. The optimization only works with -O2. I'd like to have more details about what's going on. How can I make sure, that this optimization triggers?
>
> Heinrich
>
> On 18.02.2012 11:10, MigMit wrote:
>> Different kinds of optimization. I expect you'd have different results even if you use one type, but different -O flags.
>>
>> On 18 Feb 2012, at 13:28, Heinrich Hördegen wrote:
>>
>>> Dear all,
>>>
>>> I have a question about evaluation with respect to types and currying. Consider this programm:
>>>
>>> import Debug.Trace
>>>
>>> -- add :: Integer ->  Integer ->  Integer
>>> add :: Int ->  Int ->  Int
>>> add x y = x + y
>>>
>>> f a b c = trace "b" (add x c) where x = trace "a" (add a b)
>>>
>>> main :: IO ()
>>> main = do
>>>  print (f 1 2 3)
>>>  print (f 1 2 4)
>>>
>>>
>>> Compiled with ghc-7.0.3:
>>>
>>> $ ghc --make Main.hs -o main -O2
>>>
>>> The function add has to types. When we use type Int ->  Int ->  Int, the programm produces "b a 6 b a 7" as output which shows that the x from the where clause in f is evaluated twice. However, when we use type Integer ->  Integer ->  Integer, this will give "b a 6 b 7" which shows that x is evaluated only once. This was rather unexpected to me.
>>>
>>> Why does the number of evaluation steps depend on a type? Can anybody explain this or give a hint?
>>>
>>> Thank you very much,
>>> Heinrich
>>>
>>>
>>>
>>> --
>>> --
>>>
>>> [hidden email]
>>> www.funktional.info
>>>
>>> --
>>>
>>>
>>> _______________________________________________
>>> Haskell-Cafe mailing list
>>> [hidden email]
>>> http://www.haskell.org/mailman/listinfo/haskell-cafe
>>
>
>
> --
> --
>
> Funktionale Programmierung Dr. Heinrich Hördegen
> Gutenbergstr. 26
> 80638 München
>
> FON: +49 (89) 12 59 79 49
> FAX: +49 (89) 12 59 79 50
>
> [hidden email]
> www.funktional.info
>
> --
>

_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe
Reply | Threaded
Open this post in threaded view
|

Re: types and number of evaluation steps

Roman Cheplyaka-2
In reply to this post by Victor Gorokgov
It doesn't matter. Laziness would be affected if, for instance,
something is not evaluated without CSE and is evaluated with it.

In your example either all or none of 'a' and 'b' get evaluated,
depending on whether the top-level expression is evaluated.

* Victor Gorokgov <[hidden email]> [2012-02-18 18:23:19+0400]

> example = a + b + a + b
>
> exampleCSE = x + x
>   where x = a + b
>
> With CSE we are introducing new thunk: x.
>
> 18.02.2012 17:38, Roman Cheplyaka пишет:
> >* Holger Siegel<[hidden email]>  [2012-02-18 12:52:08+0100]
> >>You cannot. Common subexpression elimination is done by GHC very
> >>conservatively, because it can not only affect impure programs: it can
> >>also affects strictness/lazyness and worsen memory usage of pure code.
> >>Like the HaskellWiki says: "If you care about CSE, do it by hand."
> >How can it affect strictness or laziness?

--
Roman I. Cheplyaka :: http://ro-che.info/

_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe
Reply | Threaded
Open this post in threaded view
|

Re: types and number of evaluation steps

Jake McArthur

My understanding was that the reason is that CSE can cause things to be shared that take up a lot of space when normally they would be garbage collected sooner.

On Feb 18, 2012 11:57 AM, "Roman Cheplyaka" <[hidden email]> wrote:
It doesn't matter. Laziness would be affected if, for instance,
something is not evaluated without CSE and is evaluated with it.

In your example either all or none of 'a' and 'b' get evaluated,
depending on whether the top-level expression is evaluated.

* Victor Gorokgov <[hidden email]> [2012-02-18 18:23:19+0400]
> example = a + b + a + b
>
> exampleCSE = x + x
>   where x = a + b
>
> With CSE we are introducing new thunk: x.
>
> 18.02.2012 17:38, Roman Cheplyaka пишет:
> >* Holger Siegel<[hidden email]>  [2012-02-18 12:52:08+0100]
> >>You cannot. Common subexpression elimination is done by GHC very
> >>conservatively, because it can not only affect impure programs: it can
> >>also affects strictness/lazyness and worsen memory usage of pure code.
> >>Like the HaskellWiki says: "If you care about CSE, do it by hand."
> >How can it affect strictness or laziness?

--
Roman I. Cheplyaka :: http://ro-che.info/

_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe

_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe