GHC's uses a many optimsations and GHC specific techniques (unboxed values, RULES pragmas, and so on) to make the heavily used Prelude code as fast as possible.
What's this "lazy" thing. Well, pseq is a seq for a parallel setting. We really mean "evaluate a, then b". But if the strictness analyser sees that pseq is strict in b, then b might be evaluated before a, which is all wrong.pseq a b = a `seq` lazy b
Solution: wrap the 'b' in a call to GHC.Base.lazy. This function is just the identity function, except that it's put into the built-in environment in MkId.lhs. That is, the MkId.lhs defn over-rides the inlining and strictness information that comes in from GHC.Base.hi. And that makes lazy look lazy, and have no inlining. So the strictness analyser gets no traction.
In the worker/wrapper phase, after strictness analysis, lazy is "manually" inlined (see WorkWrap.lhs), so we get all the efficiency back.
This supersedes an earlier scheme involving an even grosser hack in which par# and seq# returned an Int#. Now there is no seq# operator at all.
There is a lot of magic in PrelBase.lhs -
among other things, the RULES
pragmas implementing the fold/build
optimisation. The code for map is
a good example for how it all works. In the prelude code for version
5.03 it reads as follows:
map :: (a -> b) -> [a] -> [b]
map _ [] = []
map f (x:xs) = f x : map f xs
-- Note eta expanded
mapFB :: (elt -> lst -> lst) -> (a -> elt) -> a -> lst -> lst
{-# INLINE [0] mapFB #-}
mapFB c f x ys = c (f x) ys
{-# RULES
"map" [~1] forall f xs. map f xs = build (\c n -> foldr (mapFB c f) n xs)
"mapList" [1] forall f. foldr (mapFB (:) f) [] = map f
"mapFB" forall c f g. mapFB (mapFB c f) g = mapFB c (f.g)
#-}
Up to (but not including) phase 1, we use the "map" rule to
rewrite all saturated applications of map with its
build/fold form, hoping for fusion to happen. In phase 1 and 0, we
switch off that rule, inline build, and switch on the
"mapList" rule, which rewrites the foldr/mapFB thing back
into plain map.
It's important that these two rules aren't both active at once (along with build's unfolding) else we'd get an infinite loop in the rules. Hence the activation control using explicit phase numbers.
The "mapFB" rule optimises compositions of map.
The mechanism as described above is new in 5.03 since January 2002,
where the [~N] syntax for phase number
annotations at rules was introduced. Before that the whole arrangement
was more complicated, as the corresponding prelude code for version
4.08.1 shows:
map :: (a -> b) -> [a] -> [b]
map = mapList
-- Note eta expanded
mapFB :: (elt -> lst -> lst) -> (a -> elt) -> a -> lst -> lst
mapFB c f x ys = c (f x) ys
mapList :: (a -> b) -> [a] -> [b]
mapList _ [] = []
mapList f (x:xs) = f x : mapList f xs
{-# RULES
"map" forall f xs. map f xs = build (\c n -> foldr (mapFB c f) n xs)
"mapFB" forall c f g. mapFB (mapFB c f) g = mapFB c (f.g)
"mapList" forall f. foldr (mapFB (:) f) [] = mapList f
#-}
This code is structured as it is, because the "map" rule first
breaks the map open, which exposes it to the various
foldr/build rules, and if no foldr/build rule matches, the "mapList"
rule closes it again in a later phase of optimisation - after
build was inlined. As a consequence, the whole thing depends a bit on
the timing of the various optimsations (the map might be closed again
before any of the foldr/build rules fires). To make the timing
deterministic, build gets a {-# INLINE 2 build
#-} pragma, which delays build's inlining, and thus,
the closing of the map. [NB: Phase numbering was forward at that time.]
Last modified: Mon Feb 11 20:00:49 EST 2002