GHC: Ticket #741: full laziness
http://ghc.haskell.org/trac/ghc/ticket/741
<p>
GHC 6.4.1 isn't fully lazy as the following code snippet demonstrates.
</p>
<pre class="wiki">> module Test where
> data Nat = Z | S Nat
> deriving (Show, Eq)
>
> memo f = \ n -> case n of Z -> f_Z
> S n -> f_S n
> where f_Z = f Z
> f_S = memo (\ y -> f (S y))
>
> fib :: Nat -> Integer
> fib Z = 0
> fib (S Z) = 1
> fib (S (S n)) = fib (S n) + fib n
>
> fib' :: Nat -> Integer
> fib' = memo fib
> where
> fib Z = 0
> fib (S Z) = 1
> fib (S (S n)) = fib' (S n) + fib' n
</pre><p>
Hugs calculates the memoized version of fib much faster.
</p>
<p>
Test> :set +s
Test> map fib [0 .. 30]
<a class="source" href="http://ghc.haskell.org/trac/ghc/log/ghc/?revs=0%2C1%2C2%2C3%2C5%2C8%2C13%2C21%2C34%2C55%2C89%2C144%2C233%2C377%2C610%2C987%2C1597%2C2584%2C4181%2C6765%2C10946%2C17711%2C28657%2C46368%2C75025%2C121393%2C196418%2C317811%2C514229%2C832040">[0,1,1,2,3,5,8,13,21,34,55,89,144,233,377,610,987,1597,2584,4181,6765,10946,17711,28657,46368,75025,121393,196418,317811,514229,832040]</a>
(21162936 reductions, 29882544 cells, 30 garbage collections)
Test> map fib' [0 .. 30]
<a class="source" href="http://ghc.haskell.org/trac/ghc/log/ghc/?revs=0%2C1%2C2%2C3%2C5%2C8%2C13%2C21%2C34%2C55%2C89%2C144%2C233%2C377%2C610%2C987%2C1597%2C2584%2C4181%2C6765%2C10946%2C17711%2C28657%2C46368%2C75025%2C121393%2C196418%2C317811%2C514229%2C832040">[0,1,1,2,3,5,8,13,21,34,55,89,144,233,377,610,987,1597,2584,4181,6765,10946,17711,28657,46368,75025,121393,196418,317811,514229,832040]</a>
(18924 reductions, 25176 cells)
</p>
<p>
By contrast, GHCi gives:
</p>
<p>
*Test> :set +s
*Test> map fib [0 .. 30]
<a class="source" href="http://ghc.haskell.org/trac/ghc/log/ghc/?revs=0%2C1%2C2%2C3%2C5%2C8%2C13%2C21%2C34%2C55%2C89%2C144%2C233%2C377%2C610%2C987%2C1597%2C2584%2C4181%2C6765%2C10946%2C17711%2C28657%2C46368%2C75025%2C121393%2C196418%2C317811%2C514229%2C832040">[0,1,1,2,3,5,8,13,21,34,55,89,144,233,377,610,987,1597,2584,4181,6765,10946,17711,28657,46368,75025,121393,196418,317811,514229,832040]</a>
(5.71 secs, 423333160 bytes)
*Test> map fib' [0 .. 30]
<a class="source" href="http://ghc.haskell.org/trac/ghc/log/ghc/?revs=0%2C1%2C2%2C3%2C5%2C8%2C13%2C21%2C34%2C55%2C89%2C144%2C233%2C377%2C610%2C987%2C1597%2C2584%2C4181%2C6765%2C10946%2C17711%2C28657%2C46368%2C75025%2C121393%2C196418%2C317811%2C514229%2C832040">[0,1,1,2,3,5,8,13,21,34,55,89,144,233,377,610,987,1597,2584,4181,6765,10946,17711,28657,46368,75025,121393,196418,317811,514229,832040]</a>
(19.75 secs, 2430652680 bytes)
</p>
<p>
The memoized version is actually slower. The flags
</p>
<blockquote>
<p>
-no-full-laziness and -ffull-laziness seem to have no influence on the performance.
</p>
</blockquote>
<pre class="wiki">> instance Num Nat where
> fromInteger 0 = Z
> fromInteger (n + 1) = S (fromInteger n)
> Z + n = n
> S m + n = S (m + n)
> Z * n = Z
> S m * n = (m * n) + n
> Z - n = Z
> S m - Z = S m
> S m - S n = m - n
>
> instance Enum Nat where
> succ = S
> pred Z = Z
> pred (S n) = n
> toEnum = fromInteger . toInteger
> fromEnum Z = 0
> fromEnum (S n) = fromEnum n + 1
</pre>en-usGHChttp://ghc.haskell.org/trac/ghc/chrome/site/ghc_logo.png
http://ghc.haskell.org/trac/ghc/ticket/741
Trac 1.2simonmarMon, 10 Apr 2006 09:40:02 GMTstatus changed; resolution set
http://ghc.haskell.org/trac/ghc/ticket/741#comment:1
http://ghc.haskell.org/trac/ghc/ticket/741#comment:1
<ul>
<li><strong>status</strong>
changed from <em>new</em> to <em>closed</em>
</li>
<li><strong>resolution</strong>
set to <em>fixed</em>
</li>
</ul>
<p>
GHC doesn't claim to implement full-laziness, although the documentation is a little vague on this point. I've expanded it a bit now.
</p>
<p>
Full-laziness is an optimisation that is performed when -O is on (and hence <em>never</em> when using GHCi). Even so, it isn't applied consistently, so you shouldn't rely on GHC performing full-laziness.
</p>
TicketsimonpjMon, 10 Apr 2006 16:38:08 GMT
http://ghc.haskell.org/trac/ghc/ticket/741#comment:2
http://ghc.haskell.org/trac/ghc/ticket/741#comment:2
<p>
Actually Simon's comment is wrong. this program should be fast regardless of full laziness. It's a bug in 6.4.1, but it was not present in 6.4 and has been fixed in 6.4.2 (not yet released) and the HEAD.
</p>
<p>
For those who care, it was in preInlineUnconditionally.
</p>
<p>
Still, it's a nice test, and I'll add it to the test suite
</p>
<p>
Simon
</p>
TicketsimonmarTue, 30 Sep 2008 15:39:58 GMTarchitecture changed
http://ghc.haskell.org/trac/ghc/ticket/741#comment:3
http://ghc.haskell.org/trac/ghc/ticket/741#comment:3
<ul>
<li><strong>architecture</strong>
changed from <em>Unknown</em> to <em>Unknown/Multiple</em>
</li>
</ul>
TicketsimonmarTue, 30 Sep 2008 15:51:04 GMTos changed
http://ghc.haskell.org/trac/ghc/ticket/741#comment:4
http://ghc.haskell.org/trac/ghc/ticket/741#comment:4
<ul>
<li><strong>os</strong>
changed from <em>Unknown</em> to <em>Unknown/Multiple</em>
</li>
</ul>
Ticket