+++ /dev/null
-<!DOCTYPE HTML PUBLIC "-//IETF//DTD HTML//EN">
-<html>
- <head>
- <META HTTP-EQUIV="Content-Type" CONTENT="text/html; charset=ISO-8859-1">
- <title>The GHC Commentary - Cunning Prelude Code</title>
- </head>
-
- <body BGCOLOR="FFFFFF">
- <h1>The GHC Commentary - Cunning Prelude Code</h1>
- <p>
- GHC's uses a many optimsations and GHC specific techniques (unboxed
- values, RULES pragmas, and so on) to make the heavily used Prelude code
- as fast as possible.
-
- <hr>
- <h4>Par, seq, and lazy</h4>
-
- In GHC.Conc you will dinf
-<blockquote><pre>
- pseq a b = a `seq` lazy b
-</pre></blockquote>
- What's this "lazy" thing. Well, <tt>pseq</tt> is a <tt>seq</tt> for a parallel setting.
- We really mean "evaluate a, then b". But if the strictness analyser sees that pseq is strict
- in b, then b might be evaluated <em>before</em> a, which is all wrong.
-<p>
-Solution: wrap the 'b' in a call to <tt>GHC.Base.lazy</tt>. This function is just the identity function,
-except that it's put into the built-in environment in MkId.lhs. That is, the MkId.lhs defn over-rides the
-inlining and strictness information that comes in from GHC.Base.hi. And that makes <tt>lazy</tt> look
-lazy, and have no inlining. So the strictness analyser gets no traction.
-<p>
-In the worker/wrapper phase, after strictness analysis, <tt>lazy</tt> is "manually" inlined (see WorkWrap.lhs),
-so we get all the efficiency back.
-<p>
-This supersedes an earlier scheme involving an even grosser hack in which par# and seq# returned an
-Int#. Now there is no seq# operator at all.
-
-
- <hr>
- <h4>fold/build</h4>
- <p>
- There is a lot of magic in <a
- href="http://cvs.haskell.org/cgi-bin/cvsweb.cgi/fptools/ghc/lib/std/PrelBase.lhs"><code>PrelBase.lhs</code></a> -
- among other things, the <a
- href="http://haskell.cs.yale.edu/ghc/docs/latest/set/rewrite-rules.html">RULES
- pragmas</a> implementing the <a
- href="http://research.microsoft.com/Users/simonpj/Papers/deforestation-short-cut.ps.Z">fold/build</a>
- optimisation. The code for <code>map</code> is
- a good example for how it all works. In the prelude code for version
- 5.03 it reads as follows:
- <blockquote><pre>
-map :: (a -> b) -> [a] -> [b]
-map _ [] = []
-map f (x:xs) = f x : map f xs
-
--- Note eta expanded
-mapFB :: (elt -> lst -> lst) -> (a -> elt) -> a -> lst -> lst
-{-# INLINE [0] mapFB #-}
-mapFB c f x ys = c (f x) ys
-
-{-# RULES
-"map" [~1] forall f xs. map f xs = build (\c n -> foldr (mapFB c f) n xs)
-"mapList" [1] forall f. foldr (mapFB (:) f) [] = map f
-"mapFB" forall c f g. mapFB (mapFB c f) g = mapFB c (f.g)
- #-}</pre>
- </blockquote>
- <p>
- Up to (but not including) phase 1, we use the <code>"map"</code> rule to
- rewrite all saturated applications of <code>map</code> with its
- build/fold form, hoping for fusion to happen. In phase 1 and 0, we
- switch off that rule, inline build, and switch on the
- <code>"mapList"</code> rule, which rewrites the foldr/mapFB thing back
- into plain map.
- <p>
- It's important that these two rules aren't both active at once
- (along with build's unfolding) else we'd get an infinite loop
- in the rules. Hence the activation control using explicit phase numbers.
- <p>
- The "mapFB" rule optimises compositions of map.
- <p>
- The mechanism as described above is new in 5.03 since January 2002,
- where the <code>[~</code><i>N</i><code>]</code> syntax for phase number
- annotations at rules was introduced. Before that the whole arrangement
- was more complicated, as the corresponding prelude code for version
- 4.08.1 shows:
- <blockquote><pre>
-map :: (a -> b) -> [a] -> [b]
-map = mapList
-
--- Note eta expanded
-mapFB :: (elt -> lst -> lst) -> (a -> elt) -> a -> lst -> lst
-mapFB c f x ys = c (f x) ys
-
-mapList :: (a -> b) -> [a] -> [b]
-mapList _ [] = []
-mapList f (x:xs) = f x : mapList f xs
-
-{-# RULES
-"map" forall f xs. map f xs = build (\c n -> foldr (mapFB c f) n xs)
-"mapFB" forall c f g. mapFB (mapFB c f) g = mapFB c (f.g)
-"mapList" forall f. foldr (mapFB (:) f) [] = mapList f
- #-}</pre>
- </blockquote>
- <p>
- This code is structured as it is, because the "map" rule first
- <em>breaks</em> the map <em>open,</em> which exposes it to the various
- foldr/build rules, and if no foldr/build rule matches, the "mapList"
- rule <em>closes</em> it again in a later phase of optimisation - after
- build was inlined. As a consequence, the whole thing depends a bit on
- the timing of the various optimsations (the map might be closed again
- before any of the foldr/build rules fires). To make the timing
- deterministic, <code>build</code> gets a <code>{-# INLINE 2 build
- #-}</code> pragma, which delays <code>build</code>'s inlining, and thus,
- the closing of the map. [NB: Phase numbering was forward at that time.]
-
- <p><small>
-<!-- hhmts start -->
-Last modified: Mon Feb 11 20:00:49 EST 2002
-<!-- hhmts end -->
- </small>
- </body>
-</html>
projects / ghc-hetmet.git / blobdiff