[Haskell-cafe] Eta-expansion destroys memoization?

[Anthony Cowley]

On Thu, Oct 7, 2010 at 9:33 AM, Jan-Willem Maessen
<jmaessen at alum.mit.edu> wrote:
> There's no evaluation magic here---all that's happening is GHC is
> executing the program exactly as written.  It can't float the list out
> of the function, as that can lead to unexpected space leaks (if you
> didn't intend to keep the list of fibs around forever).

To echo Jan-Willem a bit, the impact of let floating can be seen by
compiling the eta expanded version (i.e. fib x = map fib' [0..] !! x)
with different options.

$ ghc --make -O -fforce-recomp FibMemo.hs
[1 of 1] Compiling Main             ( FibMemo.hs, FibMemo.o )
Linking FibMemo ...
$ ./FibMemo
5
3
2
4
5

$ ghc --make -O -fforce-recomp FibMemo.hs -fno-full-laziness
[1 of 1] Compiling Main             ( FibMemo.hs, FibMemo.o )
Linking FibMemo ...
$ ./FibMemo
5
3
2
4
2
3
2
5

My understanding is that this is just a case where GHCi is able to
float a binding in the partial application formulation because the
dependency analysis is trivial due to there being no name for the
binding.

Looking at the core for the optimized version of the eta expanded
code, there is a a top-level function for building a list of fibonacci
numbers, a top-level value of type [Type.Integer] set to an
application of the builder function to zero, and finally the fib
function that indexes into that list.

The version with -fno-full-laziness leaves the let binding under the
lambda as expected.

So the optimizer is clever and can see through the lambda, but we make
the interpreter's job easier by not putting a lambda over its eyes to
begin with.

Anthony

On Thu, Oct 7, 2010 at 9:33 AM, Jan-Willem Maessen
<jmaessen at alum.mit.edu> wrote:
> What people seem to be missing here is that the location of the
> where-binding with respect to the lambda changes in each case.  As a
> result, I think the forgoing explanations were rather confusing;
> there's no magic going on here.
>
> On Thu, Oct 7, 2010 at 8:17 AM, Brent Yorgey <byorgey at seas.upenn.edu> wrote:
>
>> ----- Forwarded message from Yue Wang <yulewang at gmail.com> -----
>>
>> From: Yue Wang <yulewang at gmail.com>
>> Then there is a clever way to do that on haskell wiki:
>>
>> fib = ((map fib' [0 ..]) !!)
>>    where
>>      fib' 0 = 0
>>      fib' 1 = 1
>>      fib' n =trace(show(n)) fib (n - 1) + fib (n - 2)
>
> This is indeed equivalent to:
> fib =
>  let fib' 0 = 0
>       fib' 1 = 1
>       fib' n = fib (n-1) + fib (n-2)
>  in (map fib' [0..] !!)
>
> But adding the argument embeds the let inside the function call:
> fib x =
>  let fib' 0 = 0
>       fib' 1 = 1
>       fib' n = fib (n-1) + fib (n-2)
>  in (map fib' [0..] !!)
>
> Now we create a new fib' for each invocation of fib.  Not efficient at
> all!  (Much *less* efficient the the recursive fib).
>
> There's no evaluation magic here---all that's happening is GHC is
> executing the program exactly as written.  It can't float the list out
> of the function, as that can lead to unexpected space leaks (if you
> didn't intend to keep the list of fibs around forever).
>
> -Jan-Willem Maessen
> _______________________________________________
> Haskell-Cafe mailing list
> Haskell-Cafe at haskell.org
> http://www.haskell.org/mailman/listinfo/haskell-cafe
>