Newbie question: mutually exclusive strict / lazy
Consider the function cond x y z = if x then y else z I guess we can certainly say cond is strict in x. But what about y and z? If x is true, then cond is strict in y If x is false, then cond is strict in z So we can't really say cond is lazy nor strict in its second or third argument. Of course, this is the case for many more functions, but in the case of the if-then-else primitive, does the strictness analyzer make use of this "mutually exclusive strictness" fact? Cheers, Peter
Am Samstag, 9. Februar 2008 17:33 schrieb Peter Verswyvelen:
Consider the function
cond x y z = if x then y else z
I guess we can certainly say cond is strict in x.
But what about y and z?
If x is true, then cond is strict in y If x is false, then cond is strict in z
So we can't really say cond is lazy nor strict in its second or third argument.
Of course, this is the case for many more functions, but in the case of the if-then-else primitive, does the strictness analyzer make use of this "mutually exclusive strictness" fact?
Cheers, Peter
Hope I remember correctly... A function is strict in an argument, if whenever that argument is _|_, the result is _|_, regardless of possible other arguments. Since if True then 0 else _|_ == 0, if-then-else is nonstrict in the third argument, similarly if False then _|_ else 0 == 0, so if-then-else is nonstrict in the second argument. Cheers, Daniel
I'm not sure what you mean by "the strictness analyzer". GHC's strictness
analyzer?
I don't know, but I would hope so since it was done already in 1980 by Alan
Mycroft.
-- Lennart
On Sat, Feb 9, 2008 at 4:33 PM, Peter Verswyvelen
Consider the function
cond x y z = if x then y else z
I guess we can certainly say cond is strict in x.
But what about y and z?
If x is true, then cond is strict in y If x is false, then cond is strict in z
So we can't really say cond is lazy nor strict in its second or third argument.
Of course, this is the case for many more functions, but in the case of the if-then-else primitive, does the strictness analyzer make use of this "mutually exclusive strictness" fact?
Cheers, Peter
_______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Yes, sorry, GHC's strictness analyzer.
What I meant with this email is that I guess that for a strictness analyzer,
the information that a function is strict in an argument *independent from
the other arguments* would not be good enough in itself for optimization, it
would be better to also use the dependencies between the arguments (as in
the case of the if.then.else).
It seems one can indicate in GHC that an argument is strict using
annotiations, but I don't see a way of specifying these dependencies (maybe
this does not make sense, and this is all newbie nonsense). Of course, with
whole program optimization this would not be necessary, but if the compiler
just sees the function signature, he must assume that a lazy argument is
always lazy, independent of the value of other strict arguments no?
Cheers,
Peter
From: lennart.augustsson@gmail.com [mailto:lennart.augustsson@gmail.com] On
Behalf Of Lennart Augustsson
Sent: maandag 11 februari 2008 0:28
To: Peter Verswyvelen
Cc: haskell-cafe@haskell.org
Subject: Re: [Haskell-cafe] Newbie question: mutually exclusive strict /
lazy
I'm not sure what you mean by "the strictness analyzer". GHC's strictness
analyzer?
I don't know, but I would hope so since it was done already in 1980 by Alan
Mycroft.
-- Lennart
On Sat, Feb 9, 2008 at 4:33 PM, Peter Verswyvelen
2008/2/11, Peter Verswyvelen
Yes, sorry, GHC's strictness analyzer.
What I meant with this email is that I guess that for a strictness analyzer, the information that a function is strict in an argument *independent from the other arguments* would not be good enough in itself for optimization, it would be better to also use the dependencies between the arguments (as in the case of the if…then…else).
It seems one can indicate in GHC that an argument is strict using annotiations, but I don't see a way of specifying these dependencies (maybe this does not make sense, and this is all newbie nonsense). Of course, with whole program optimization this would not be necessary, but if the compiler just sees the function signature, he must assume that a lazy argument is always lazy, independent of the value of other strict arguments no?
It may not always be the case, but, here, for your particular example, what you need is an inline followed by a reduction (dunno which). Reminder:
cond x y z = if x then y else z
The translation in core, is this: cond x y z = case x of True -> y False -> z So, suppose we know at some call site that x is True. So, the call cond x e1 e2 -- e1 and e2 are arbitrary expressions is equivalent to: cond True e1 e2 An inline replaces the call by this: cond x e1 e2 = case True of True -> e1 False -> e2 In this case, the compiler can easily determine at compile time the selected branch. Therefore, this "case" expression is replaced by the correct branch: e1 I would be surprised if GHC doesn't already perform this kind of optimization [1,2]. So, no need for a fancy strictness analyser for this code. About more complicated cases, I'm clueless, thought. Cheers, Loup [1] http://research.microsoft.com/~simonpj/Papers/inlining/ [2] http://citeseer.ist.psu.edu/jones91unboxed.html
participants (4)
-
Daniel Fischer -
Lennart Augustsson -
Loup Vaillant -
Peter Verswyvelen