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)
in a ghci session (with :set +s):
*Primes> test1 1 (9592,9592) (0.89 secs, 106657468 bytes) *Primes> test2 1 (9592,9592) (1.80 secs, 213077068 bytes)
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. Note that when compiled with optimisations, test1 and test2 give exactly the same core.
- Is said optimization required to conform to the Haskell98 standard? If so, where is it stated?
No, it's not required. Unconditional sharing may be bad, so it would be unwise to demand sharing.
- Could someone explain or point to a precise explanation of this optimization? If I'm doing an operational reduction by hand on paper, how would I take account for this optimization?
More or less test1 c = let v = nthPrime 100000 a = const' v in (a c, a c) You (the compiler) give(s) a name to a value, when the value is referred to via that name, it's not recalculated (it's calculated on first demand).
Thanks,
David
[1] http://hpaste.org/40033/operational_semantics [2] http://conal.net/blog/posts/lazier-functional-programming-part-2/