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

[wren ng thornton]

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