On 25 September 2010 07:58, David Sankel
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.