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

[David Sankel]

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)
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://www.haskell.org/pipermail/haskell-cafe/attachments/20100924/4926be46/attachment.html