CAF's in Haskell
Hi, Are CAF's specified in the Haskell report? I couldn't find them mentioned. If not, why do all Haskell compilers support them? Is there some paper which persuaded everyone they were a good idea, or some reference I could look up? Thanks Neil
"Neil Mitchell"
Hi,
Are CAF's specified in the Haskell report? I couldn't find them mentioned.
CAF is a term of art. If you define fred = 2 + 2 that's a CAF.
If not, why do all Haskell compilers support them?
How could they not? I'm not sure I understand your question. -- Jón Fairbairn Jon.Fairbairn@cl.cam.ac.uk
Hi
Are CAF's specified in the Haskell report? I couldn't find them mentioned.
CAF is a term of art. If you define
fred = 2 + 2
that's a CAF.
I should have been more precise with my question. Given the code: fred = 2 + 2 bob = fred + fred In a Haskell implementation fred would be evaluated once to 4, then used twice. The 2+2 would only happen once (ignore defaulting and overloaded numerics for now). Is this sharing mandated by the standard? (I don't think so) Is there some paper that describes why this is desirable, and gives any detail?
If not, why do all Haskell compilers support them?
How could they not? I'm not sure I understand your question.
Do all Haskell compilers support the sharing. Thanks Neil
Well I certainly hope the standard defines that both fred and bob will only be evaluated once, because my programs depend on that :) Peter Neil wrote:
fred = 2 + 2 bob = fred + fred In a Haskell implementation fred would be evaluated once to 4, then used twice. The 2+2 would only happen once (ignore defaulting and overloaded numerics for now). Is this sharing mandated by the standard? (I don't think so) Is there some paper that describes why this is desirable, and gives any detail? Do all Haskell compilers support the sharing?
On 26 Dec 2007, at 12:30 PM, Peter Verswyvelen wrote:
Well I certainly hope the standard defines that both fred and bob will only be evaluated once, because my programs depend on that :)
If your programs depend on lazy evaluation, they can't be Haskell 98. Any complete reduction method is sound for Haskell 98. If you're using an extension (such as unsafePerformIO) that isn't Haskell 98, check your compiler documentation --- although you'll find that there is no guarantee that a CAF is evaluated only once (and in fact small CAFs may not be). jcc
Hi Neil,
On Dec 26, 2007 7:16 PM, Neil Mitchell
Given the code:
fred = 2 + 2
bob = fred + fred
In a Haskell implementation fred would be evaluated once to 4, then used twice. The 2+2 would only happen once (ignore defaulting and overloaded numerics for now).
Is this sharing mandated by the standard? (I don't think so) Is there some paper that describes why this is desirable, and gives any detail?
I think if the report does not mandate it, it's for the same reason that Haskell-the-language is "non-strict," not "lazy"-- it thinks that it's the compiler's business to decide things like this. (After all, there are situations where it might be better to evaluate Fred twice, and the compiler might recognize some of them.) But the Haskell design certainly anticipates that this is what compilers will normally do: the point of the dreaded monomorphism restriction is to make sure that 'fred' doesn't accidentally become (Num a => a), which would make it infeasible to evaluate it only once (because you would have to store the value for every instance of Num). It's a lot like you can expect Haskell implementations to be lazy, not call-by-name. (I don't know when this behavior originated.) - Benja
"Neil Mitchell"
I should have been more precise with my question. Given the code:
fred = 2 + 2
bob = fred + fred
In a Haskell implementation fred would be evaluated once to 4, then used twice. The 2+2 would only happen once (ignore defaulting and overloaded numerics for now).
Not necessarily. The Haskell 98 standard very carefully avoids mandating any particular evaluation strategy beyond that it should be non-strict. So bob is always going to be 8, but just how it gets there is up to the implementation. If you'd had fred = [1..] and bob = do something with fred a lot of other stuff something else with fred it's much less obvious that keeping the first-calculated value for fred around the whole time is the right thing to do.
Do all Haskell compilers support the sharing.
I don't know all Haskell compilers, but I'm pretty sure there have been implementations that don't, or don't always because of the above problem. -- Jón Fairbairn Jon.Fairbairn@cl.cam.ac.uk
On Wed, 26 Dec 2007 17:16:22 +0200, Neil Mitchell
Hi,
Are CAF's specified in the Haskell report? I couldn't find them mentioned.
If not, why do all Haskell compilers support them? Is there some paper which persuaded everyone they were a good idea, or some reference I could look up?
I found this in the wiki http://www.haskell.org/haskellwiki/Constant_applicative_form
participants (6)
-
Benja Fallenstein -
Cristian Baboi -
Jon Fairbairn -
Jonathan Cast -
Neil Mitchell -
Peter Verswyvelen