ghc/docs/comm/rts-libs/prelude.html

   1 <!DOCTYPE HTML PUBLIC "-//IETF//DTD HTML//EN">
   2 <html>
   3   <head>
   4     <META HTTP-EQUIV="Content-Type" CONTENT="text/html; charset=ISO-8859-1">
   5     <title>The GHC Commentary - Cunning Prelude Code</title>
   6   </head>
   7
   8   <body BGCOLOR="FFFFFF">
   9     <h1>The GHC Commentary - Cunning Prelude Code</h1>
  10     <p>
  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
  13       as fast as possible.
  14
  15     <h4>fold/build</h4>
  16     <p>
  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:
  26     <blockquote><pre>
  27 map :: (a -> b) -> [a] -> [b]
  28 map _ []     = []
  29 map f (x:xs) = f x : map f xs
  30
  31 -- Note eta expanded
  32 mapFB ::  (elt -> lst -> lst) -> (a -> elt) -> a -> lst -> lst
  33 {-# INLINE [0] mapFB #-}
  34 mapFB c f x ys = c (f x) ys
  35
  36 {-# RULES
  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)
  40   #-}</pre>
  41     </blockquote>
  42     <p>
  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
  48       into plain map.
  49     <p>
  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.
  53     <p>
  54       The "mapFB" rule optimises compositions of map.
  55     <p>
  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
  60       4.08.1 shows:
  61     <blockquote><pre>
  62 map :: (a -> b) -> [a] -> [b]
  63 map = mapList
  64
  65 -- Note eta expanded
  66 mapFB ::  (elt -> lst -> lst) -> (a -> elt) -> a -> lst -> lst
  67 mapFB c f x ys = c (f x) ys
  68
  69 mapList :: (a -> b) -> [a] -> [b]
  70 mapList _ []     = []
  71 mapList f (x:xs) = f x : mapList f xs
  72
  73 {-# RULES
  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
  77  #-}</pre>
  78     </blockquote>
  79     <p>
  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.]
  90
  91     <p><small>
  92 <!-- hhmts start -->
  93 Last modified: Mon Feb 11 20:00:49 EST 2002
  94 <!-- hhmts end -->
  95     </small>
  96   </body>
  97 </html>