On Thu, Oct 7, 2010 at 8:44 AM, Luke Palmer wrote:

On Thu, Oct 7, 2010 at 6:17 AM, Brent Yorgey wrote:

...

The source code seems to be easy to read, but I don't think I understand that. For me I think if I change the first line from fib = ((map fib' [0 ..]) !!) to fib x = ((map fib' [0 ..]) !!) x It should do the same thing since I think the previous version is just an abbreviation  for the second one.

Semantically, yes.  And it's possible that ghc -O is clever enough to notice that.  But at least under ghci's naive evaluation strategy, lambdas determine the lifetime of expressions. Any expression within a lambda will be re-evaluated each time the lambda is expanded.  Thus:

 fib = (map fib' [0..] !!)        -- fast  fib = \x -> map fib' [0..] !! x        -- slow  fib = let memo = map fib' [0..] in \x -> memo !! x -- fast

The section works because "(a %^&)"  (for some operator %^&) is short for "(%^&) a" and "(%^& a)" is short for "flip (%^&) a".  Sections don't expand into lambdas.

In other words, in the middle expression, there is a new "map fib' [0..]" for each x, whereas in the others, it is shared between invocations.

Does that make sense?

In general, f is not semantically equivalent to \x -> f x in Haskell. However, that is not what Brent said. The Report -defines- (m !!) as \x -> m !! x. GHC simply does not follow the Report here. You can witness this via: (() `undefined`) `seq` 0. By the Report this should evaluate to 0, in GHC it evaluates to undefined. As for the rest... The operational behavior of the above is implementation dependent, but GHC, and I imagine most implementations, more or less do the natural thing. The Report gives no way to control sharing behavior, but being able to control it is rather important, so predictable behavior here is desirable.

On 8 October 2010 10:54, Simon Marlow wrote:

We could make GHC respect the report, but we'd have to use

 (e op)  ==>  let z = e in \x -> z op x

to retain sharing without relying on full laziness.

This might be a good idea in fact - all other things being equal, having lambdas be more visible to the compiler is a good thing.

Of course, this change could cause a performance regression to existing code. Personally, I think that this is a report bug: there is no syntactic lambda in (`op` e) or (`op` e) so I would expect the evaluation of e to be shared. Max

On Tue, Oct 12, 2010 at 4:34 AM, Bertram Felgenhauer wrote:

Simon Marlow wrote:

...

Interesting.  You're absolutely right, GHC doesn't respect the report, on something as basic as sections!  The translation we use is

  (e op)  ==>  (op) e

once upon a time, when the translation in the report was originally written (before seq was added) this would have been exactly identical to \x -> e op x, so the definition in the report was probably used for consistency with left sections.

We could make GHC respect the report, but we'd have to use

  (e op)  ==>  let z = e in \x -> z op x

to retain sharing without relying on full laziness.

We should keep in mind that this was changed deliberately in ghc 6.6, in order to support "postfix" operators.

   http://www.haskell.org/ghc/docs/6.6/html/users_guide/release-6-6.html

The motivating example was the factorial operator which can currently be written as  (n !)  in ghc-Haskell.

From http://www.haskell.org/ghc/docs/6.6/html/users_guide/syntax-extns.html#postf... "Since this extension goes beyond Haskell 98, it should really be enabled by a flag; but in fact it is enabled all the time. (No Haskell 98 programs change their behaviour, of course.) "

Which is not true, but is probably true enough. Of course, there is now a flag http://www.haskell.org/ghc/docs/6.12.2/html/users_guide/syntax-extns.html#po... but it seems that the non-standard interpretation of (e !) is still kept even without it. Without the flag, it type checks as if you had written \x -> e ! x but it still behaves as if you had written (!) e.

On Thu, Oct 7, 2010 at 9:33 AM, Jan-Willem Maessen 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 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 wrote:

...

----- Forwarded message from Yue Wang -----

From: Yue Wang 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@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe