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

[Bernie Pope]

On 25 September 2010 07:58, David Sankel <camior at gmail.com> wrote:

> 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!

Hi David,

If you are interested in exploring operational semantics you might
also get some use out of MiniSTG:

   http://www.haskell.org/haskellwiki/Ministg

It implements the push-enter and eval-apply semantics for the STG
machine. Perhaps the most useful part is that it can generate a HTML
trace of a small-step reduction. The trace shows the code, stack and
heap, so you can see how structures are shared.

It might help to read the "fast curry" paper if you want to play with MiniSTG:

   http://research.microsoft.com/en-us/um/people/simonpj/papers/eval-apply/

Cheers,
Bernie.