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     <hr>
  16     <h4>Par, seq, and lazy</h4>
  17
  18     In GHC.Conc you will dinf
  19 <blockquote><pre>
  20   pseq a b = a `seq` lazy b
  21 </pre></blockquote>
  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.
  25 <p>
  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.
  30 <p>
  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.
  33 <p>
  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.
  36
  37
  38     <hr>
  39     <h4>fold/build</h4>
  40     <p>
  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:
  50     <blockquote><pre>
  51 map :: (a -> b) -> [a] -> [b]
  52 map _ []     = []
  53 map f (x:xs) = f x : map f xs
  54
  55 -- Note eta expanded
  56 mapFB ::  (elt -> lst -> lst) -> (a -> elt) -> a -> lst -> lst
  57 {-# INLINE [0] mapFB #-}
  58 mapFB c f x ys = c (f x) ys
  59
  60 {-# RULES
  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)
  64   #-}</pre>
  65     </blockquote>
  66     <p>
  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
  72       into plain map.
  73     <p>
  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.
  77     <p>
  78       The "mapFB" rule optimises compositions of map.
  79     <p>
  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
  84       4.08.1 shows:
  85     <blockquote><pre>
  86 map :: (a -> b) -> [a] -> [b]
  87 map = mapList
  88
  89 -- Note eta expanded
  90 mapFB ::  (elt -> lst -> lst) -> (a -> elt) -> a -> lst -> lst
  91 mapFB c f x ys = c (f x) ys
  92
  93 mapList :: (a -> b) -> [a] -> [b]
  94 mapList _ []     = []
  95 mapList f (x:xs) = f x : mapList f xs
  96
  97 {-# RULES
  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
 101  #-}</pre>
 102     </blockquote>
 103     <p>
 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.]
 114
 115     <p><small>
 116 <!-- hhmts start -->
 117 Last modified: Mon Feb 11 20:00:49 EST 2002
 118 <!-- hhmts end -->
 119     </small>
 120   </body>
 121 </html>