Re: [Haskell-cafe] Re: Shared thunk optimization. Looking to solidify my understanding

No one seems to have mentioned that this is a non-optimization in call-by-need lambda-calculus (Ariola et al.), where it follows from the standard reduction rules. Since lazy implementations of Haskell all use call-by-need evaluation in some form, I'd call this "playing by the rules" rather than "optimization". Unoptimized call-by-need indeed evaluates (nthPrime 100000) twice in test2, but only once in test1. (Challenge: prove observationl equivalence of these two fragments under call-by-need.) -Jan-Willem Maessen On Fri, Sep 24, 2010 at 5:58 PM, David Sankel wrote:

On Wed, Sep 22, 2010 at 11:10 AM, David Sankel wrote:

...

<snip> My questions are:

What is the optimization that test1 is taking advantage of called? Is said optimization required to conform to the Haskell98 standard? If so, where is it stated? Could someone explain or point to a precise explanation of this optimization? If I'm doing an operational reduction by hand on paper, how would I take account for this optimization?

Thanks everyone for your responses. I found them very helpful. This is my current understanding, please correct me where I am wrong: When using Launchbury's Natural Semantics (LNS) as an operational model, this optimization is called sharing which would lie in a category of optimizations called common subexpression elimination. Holger Siegel's email provided steps of an evaluation using LNS to show the different runtimes between test1 and test2. Because Haskell98 does not specify an operational semantics, there is no guarantee that an implementation will provide a sharing optimization. On the other hand, Haskell implementations are all similar enough that the sharing optimization can be depended on. LNS was indeed written to model what is common in implementations for languages characteristically like Haskell. When compiled with ghc with optimizations, test1 and test2 result in identical runtime behaviors. This is an artifact of another, more aggressive, optimization that falls within common subexpression elimination optimizations. It is not easy to describe or predict when this optimization occurs so depending on it when writing code is problematic. wren ng thornton provided an evaluation using another operational semantics (reference?). Under this semantics, this optimization would be called partial evaluation. Unfortunately I couldn't follow the steps or the reasoning behind them, perhaps a reference to the semantics would help. Thanks again!

David -- David Sankel Sankel Software www.sankelsoftware.com 585 617 4748 (Office)

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