On 9/22/10 11:48 AM, Daniel Fischer wrote:

On Wednesday 22 September 2010 17:10:06, David Sankel wrote:

...

The following code (full code available here[1], example taken from comments here[2]),

const' = \a _ -> a

test1 c = let a = const' (nthPrime 100000) in (a c, a c)

test2 c = let a = \_ -> (nthPrime 100000) in (a c, a c)

test1, although denotationally equivalent to test2 runs about twice as fast. My questions are:

- What is the optimization that test1 is taking advantage of called?

Sharing. test1 computes nthPrime 100000 only once, test2 twice.

Actually, I'd call it partial evaluation. That is, if we expand the notation for multiple lambdas and inline const' then we get test1 c = let a = (\x -> \_ -> x) (nthPrime 100000) in (a c, a c) test2 c = let a = \_ -> (nthPrime 100000) in (a c, a c) Now, if we follow the evaluation we'll see (test1 G) -- for some G {force test1 to WHNF} (\c -> let a = (\x -> \_ -> x) (nthPrime 100000) in (a c, a c)) g {force application to WHNF} let c = G in let a = (\x -> \_ -> x) (nthPrime 100000) in (a c, a c) And here we're already in WHNF, but lets assume you're going for full NF. let c = G in let a = (\x -> \_ -> x) (nthPrime 100000) in (a c, a c) {force a to WHNF == force application to WHNF} let c = G in let a = let x = nthPrime 100000 in \_ -> x in (a c, a c) {force x to WHNF in the application of a to c} let c = G in let a = let x = X in -- for brevity \_ -> x in (a c, a c) {force the application (itself) of a to c} let c = G in let a = let x = X in \_ -> x in (X, a c) {force the application of a to c, the second one} let c = G in let a = let x = X in \_ -> x in (X, X) Now, notice that because the binding of x was floated out in front of the ignored parameter to a, we only end up computing it once and sharing that X among all the different calls. This is typically called partial evaluation because we can partially evaluate the function a, even without knowing its arguments. Partial evaluation is a general optimization technique. It is, in fact, the same technique as floating invariants out of loops in imperative languages. When GHC's optimizations are turned on, it realizes that the binding of x can be floated out of the lambda because it does not depend on the (ignored) parameter. Thus, in optimized code the two will look the same, provided the optimizer is smart enough to figure out when things can be floated out. But noone wants to be forced to guarantee that the optimizer is smart enough, which is why the Haskell specs say nothing about the exact evaluation order. -- Live well, ~wren

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

On 9/25/10 3:43 PM, Jan-Willem Maessen wrote:

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.

Exactly. Then again, call-by-need gives a form of partial evaluation, which was what I was pointing out in in the post described as:

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

...

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.

-- Live well, ~wren