full laziness

[guest]

GHC 6.4.1 isn't fully lazy as the following code snippet demonstrates.

> 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

Hugs calculates the memoized version of fib much faster.

Test> :set +s Test> map fib [0 .. 30] [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] (21162936 reductions, 29882544 cells, 30 garbage collections) Test> map fib' [0 .. 30] [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] (18924 reductions, 25176 cells)

By contrast, GHCi gives:

*Test> :set +s *Test> map fib [0 .. 30] [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] (5.71 secs, 423333160 bytes) *Test> map fib' [0 .. 30] [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] (19.75 secs, 2430652680 bytes)

The memoized version is actually slower. The flags

-no-full-laziness and -ffull-laziness seem to have no influence on the performance.

> 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

[simonmar]

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.

Full-laziness is an optimisation that is performed when -O is on (and hence never when using GHCi). Even so, it isn't applied consistently, so you shouldn't rely on GHC performing full-laziness.

[simonpj]

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.

For those who care, it was in preInlineUnconditionally.

Still, it's a nice test, and I'll add it to the test suite

Simon