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

[Jan-Willem Maessen]

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 <camior at gmail.com> wrote:
> On Wed, Sep 22, 2010 at 11:10 AM, David Sankel <camior at gmail.com> 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 at haskell.org
> http://www.haskell.org/mailman/listinfo/haskell-cafe
>
>