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
17 There is a lot of magic in <a
18 href="http://cvs.haskell.org/cgi-bin/cvsweb.cgi/fptools/ghc/lib/std/PrelBase.lhs"><code>PrelBase.lhs</code></a> -
19 among other things, the <a
20 href="http://haskell.cs.yale.edu/ghc/docs/latest/set/rewrite-rules.html">RULES
21 pragmas</a> implementing the <a
22 href="http://research.microsoft.com/Users/simonpj/Papers/deforestation-short-cut.ps.Z">fold/build</a>
23 optimisation. The code for <code>map</code> is
24 a good example for how it all works. In the prelude code for version
25 5.03 it reads as follows:
27 map :: (a -> b) -> [a] -> [b]
29 map f (x:xs) = f x : map f xs
32 mapFB :: (elt -> lst -> lst) -> (a -> elt) -> a -> lst -> lst
33 {-# INLINE [0] mapFB #-}
34 mapFB c f x ys = c (f x) ys
37 "map" [~1] forall f xs. map f xs = build (\c n -> foldr (mapFB c f) n xs)
38 "mapList" [1] forall f. foldr (mapFB (:) f) [] = map f
39 "mapFB" forall c f g. mapFB (mapFB c f) g = mapFB c (f.g)
43 Up to (but not including) phase 1, we use the <code>"map"</code> rule to
44 rewrite all saturated applications of <code>map</code> with its
45 build/fold form, hoping for fusion to happen. In phase 1 and 0, we
46 switch off that rule, inline build, and switch on the
47 <code>"mapList"</code> rule, which rewrites the foldr/mapFB thing back
50 It's important that these two rules aren't both active at once
51 (along with build's unfolding) else we'd get an infinite loop
52 in the rules. Hence the activation control using explicit phase numbers.
54 The "mapFB" rule optimises compositions of map.
56 The mechanism as described above is new in 5.03 since January 2002,
57 where the <code>[~</code><i>N</i><code>]</code> syntax for phase number
58 annotations at rules was introduced. Before that the whole arrangement
59 was more complicated, as the corresponding prelude code for version
62 map :: (a -> b) -> [a] -> [b]
66 mapFB :: (elt -> lst -> lst) -> (a -> elt) -> a -> lst -> lst
67 mapFB c f x ys = c (f x) ys
69 mapList :: (a -> b) -> [a] -> [b]
71 mapList f (x:xs) = f x : mapList f xs
74 "map" forall f xs. map f xs = build (\c n -> foldr (mapFB c f) n xs)
75 "mapFB" forall c f g. mapFB (mapFB c f) g = mapFB c (f.g)
76 "mapList" forall f. foldr (mapFB (:) f) [] = mapList f
80 This code is structured as it is, because the "map" rule first
81 <em>breaks</em> the map <em>open,</em> which exposes it to the various
82 foldr/build rules, and if no foldr/build rule matches, the "mapList"
83 rule <em>closes</em> it again in a later phase of optimisation - after
84 build was inlined. As a consequence, the whole thing depends a bit on
85 the timing of the various optimsations (the map might be closed again
86 before any of the foldr/build rules fires). To make the timing
87 deterministic, <code>build</code> gets a <code>{-# INLINE 2 build
88 #-}</code> pragma, which delays <code>build</code>'s inlining, and thus,
89 the closing of the map. [NB: Phase numbering was forward at that time.]
93 Last modified: Mon Feb 11 20:00:49 EST 2002