1 <!DOCTYPE HTML PUBLIC "-//IETF//DTD HTML//EN">
4 <META HTTP-EQUIV="Content-Type" CONTENT="text/html; charset=ISO-8859-1">
5 <title>The GHC Commentary - Cunning Prelude Code</title>
8 <body BGCOLOR="FFFFFF">
9 <h1>The GHC Commentary - Cunning Prelude Code</h1>
11 GHC's uses a many optimsations and GHC specific techniques (unboxed
12 values, RULES pragmas, and so on) to make the heavily used Prelude code
16 <h4>Par, seq, and lazy</h4>
18 In GHC.Conc you will dinf
20 pseq a b = a `seq` lazy b
22 What's this "lazy" thing. Well, <tt>pseq</tt> is a <tt>seq</tt> for a parallel setting.
23 We really mean "evaluate a, then b". But if the strictness analyser sees that pseq is strict
24 in b, then b might be evaluated <em>before</em> a, which is all wrong.
26 Solution: wrap the 'b' in a call to <tt>GHC.Base.lazy</tt>. This function is just the identity function,
27 except that it's put into the built-in environment in MkId.lhs. That is, the MkId.lhs defn over-rides the
28 inlining and strictness information that comes in from GHC.Base.hi. And that makes <tt>lazy</tt> look
29 lazy, and have no inlining. So the strictness analyser gets no traction.
31 In the worker/wrapper phase, after strictness analysis, <tt>lazy</tt> is "manually" inlined (see WorkWrap.lhs),
32 so we get all the efficiency back.
34 This supersedes an earlier scheme involving an even grosser hack in which par# and seq# returned an
35 Int#. Now there is no seq# operator at all.
41 There is a lot of magic in <a
42 href="http://cvs.haskell.org/cgi-bin/cvsweb.cgi/fptools/ghc/lib/std/PrelBase.lhs"><code>PrelBase.lhs</code></a> -
43 among other things, the <a
44 href="http://haskell.cs.yale.edu/ghc/docs/latest/set/rewrite-rules.html">RULES
45 pragmas</a> implementing the <a
46 href="http://research.microsoft.com/Users/simonpj/Papers/deforestation-short-cut.ps.Z">fold/build</a>
47 optimisation. The code for <code>map</code> is
48 a good example for how it all works. In the prelude code for version
49 5.03 it reads as follows:
51 map :: (a -> b) -> [a] -> [b]
53 map f (x:xs) = f x : map f xs
56 mapFB :: (elt -> lst -> lst) -> (a -> elt) -> a -> lst -> lst
57 {-# INLINE [0] mapFB #-}
58 mapFB c f x ys = c (f x) ys
61 "map" [~1] forall f xs. map f xs = build (\c n -> foldr (mapFB c f) n xs)
62 "mapList" [1] forall f. foldr (mapFB (:) f) [] = map f
63 "mapFB" forall c f g. mapFB (mapFB c f) g = mapFB c (f.g)
67 Up to (but not including) phase 1, we use the <code>"map"</code> rule to
68 rewrite all saturated applications of <code>map</code> with its
69 build/fold form, hoping for fusion to happen. In phase 1 and 0, we
70 switch off that rule, inline build, and switch on the
71 <code>"mapList"</code> rule, which rewrites the foldr/mapFB thing back
74 It's important that these two rules aren't both active at once
75 (along with build's unfolding) else we'd get an infinite loop
76 in the rules. Hence the activation control using explicit phase numbers.
78 The "mapFB" rule optimises compositions of map.
80 The mechanism as described above is new in 5.03 since January 2002,
81 where the <code>[~</code><i>N</i><code>]</code> syntax for phase number
82 annotations at rules was introduced. Before that the whole arrangement
83 was more complicated, as the corresponding prelude code for version
86 map :: (a -> b) -> [a] -> [b]
90 mapFB :: (elt -> lst -> lst) -> (a -> elt) -> a -> lst -> lst
91 mapFB c f x ys = c (f x) ys
93 mapList :: (a -> b) -> [a] -> [b]
95 mapList f (x:xs) = f x : mapList f xs
98 "map" forall f xs. map f xs = build (\c n -> foldr (mapFB c f) n xs)
99 "mapFB" forall c f g. mapFB (mapFB c f) g = mapFB c (f.g)
100 "mapList" forall f. foldr (mapFB (:) f) [] = mapList f
104 This code is structured as it is, because the "map" rule first
105 <em>breaks</em> the map <em>open,</em> which exposes it to the various
106 foldr/build rules, and if no foldr/build rule matches, the "mapList"
107 rule <em>closes</em> it again in a later phase of optimisation - after
108 build was inlined. As a consequence, the whole thing depends a bit on
109 the timing of the various optimsations (the map might be closed again
110 before any of the foldr/build rules fires). To make the timing
111 deterministic, <code>build</code> gets a <code>{-# INLINE 2 build
112 #-}</code> pragma, which delays <code>build</code>'s inlining, and thus,
113 the closing of the map. [NB: Phase numbering was forward at that time.]
117 Last modified: Mon Feb 11 20:00:49 EST 2002