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       4.08.1 it reads as follows:
  26     <blockquote><pre>
  27 map :: (a -> b) -> [a] -> [b]
  28 map = mapList
  29
  30 -- Note eta expanded
  31 mapFB ::  (elt -> lst -> lst) -> (a -> elt) -> a -> lst -> lst
  32 mapFB c f x ys = c (f x) ys
  33
  34 mapList :: (a -> b) -> [a] -> [b]
  35 mapList _ []     = []
  36 mapList f (x:xs) = f x : mapList f xs
  37
  38 {-# RULES
  39 "map"     forall f xs.  map f xs               = build (\c n -> foldr (mapFB c f) n xs)
  40 "mapFB"   forall c f g. mapFB (mapFB c f) g    = mapFB c (f.g)
  41 "mapList" forall f.     foldr (mapFB (:) f) [] = mapList f
  42  #-}</pre>
  43     </blockquote>
  44     <p>
  45       This code is structured as it is, because the "map" rule first
  46       <em>breaks</em> the map <em>open,</em> which exposes it to the various
  47       foldr/build rules, and if no foldr/build rule matches, the "mapList"
  48       rule <em>closes</em> it again in a later phase of optimisation - after
  49       build was inlined.  As a consequence, the whole thing depends a bit on
  50       the timing of the various optimsations (the map might be closed again
  51       before any of the foldr/build rules fires).  To make the timing
  52       deterministic, <code>build</code> gets a <code>{-# INLINE 2 build
  53       #-}</code> pragma, which delays <code>build</code>'s inlining, and thus,
  54       the closing of the map.
  55
  56     <p><small>
  57 <!-- hhmts start -->
  58 Last modified: Wed Aug  8 19:31:18 EST 2001
  59 <!-- hhmts end -->
  60     </small>
  61   </body>
  62 </html>