%
-% $Id: glasgow_exts.vsgml,v 1.7 1999/03/26 19:50:31 sof Exp $
+% $Id: glasgow_exts.vsgml,v 1.12 1999/07/14 11:33:10 simonmar Exp $
%
% GHC Language Extensions.
%
<tag>Local universal quantification:</tag>
-GHC's type system supports explicit unversal quantification in
+GHC's type system supports explicit universal quantification in
constructor fields and function arguments. This is useful for things
like defining @runST@ from the state-thread world. See Section <ref
name="Local universal quantification" id="universal-quantification">.
file. The pragmas GHC supports are described in Section <ref
name="Pragmas" id="pragmas">.
+<tag>Rewrite rules:</tag>
+
+The programmer can specify rewrite rules as part of the source program
+(in a pragma). GHC applies these rewrite rules wherever it can.
+Details in Section <ref name="Rewrite Rules"
+id="rewrite-rules">.
+
</descrip>
Before you get too carried away working at the lowest level (e.g.,
through a native-code generator):
<tscreen><verb>
+import Addr
+import CString
+
oldGetEnv name
- = _casm_ ``%r = getenv((char *) %0);'' name >>= \ litstring@(A# str#) ->
+ = _casm_ ``%r = getenv((char *) %0);'' name >>= \ litstring ->
return (
- if (litstring == ``NULL'') then
+ if (litstring == nullAddr) then
Left ("Fail:oldGetEnv:"++name)
else
- Right (unpackCString# str#)
+ Right (unpackCString litstring)
)
</verb></tscreen>
from the <tt>MonadT</tt> data structure, rather than using pattern
matching.
+You cannot pattern-match against an argument that is polymorphic.
+For example:
+<tscreen><verb>
+ newtype TIM s a = TIM (ST s (Maybe a))
+
+ runTIM :: (forall s. TIM s a) -> Maybe a
+ runTIM (TIM m) = runST m
+</verb></tscreen>
+
+Here the pattern-match fails, because you can't pattern-match against
+an argument of type <tt>(forall s. TIM s a)</tt>. Instead you
+must bind the variable and pattern match in the right hand side:
+<tscreen><verb>
+ runTIM :: (forall s. TIM s a) -> Maybe a
+ runTIM tm = case tm of { TIM m -> runST m }
+</verb></tscreen>
+The <tt>tm</tt> on the right hand side is (invisibly) instantiated, like
+any polymorphic value at its occurrence site, and now you can pattern-match
+against it.
+
<sect2>The partial-application restriction
<p>
<label id="sec:assertions">
<p>
-If you want to use assertions in your standard Haskell code, you
-could define something like the following:
+If you want to make use of assertions in your standard Haskell code, you
+could define a function like the following:
<tscreen><verb>
assert :: Bool -> a -> a
</verb></tscreen>
which works, but gives you back a less than useful error message --
-an assertion failed, but which?
+an assertion failed, but which and where?
One way out is to define an extended <tt/assert/ function which also
takes a descriptive string to include in the error message and
assertion was made,
<tscreen><verb>
-assert pred val ==> assertError "Main.hs,15" pred val
+assert pred val ==> assertError "Main.hs|15" pred val
</verb></tscreen>
-The rewrite is only performed by the compiler when applications of
-<tt>Exception.assert</tt> are spotted, so you can still define and use
-your own versions of <tt/assert/, should you so wish. If not, import
-<tt/Exception/ to use <tt/assert/ in your code.
+The rewrite is only performed by the compiler when it spots
+applications of <tt>Exception.assert</tt>, so you can still define and
+use your own versions of <tt/assert/, should you so wish. If not,
+import <tt/Exception/ to make use <tt/assert/ in your code.
+
+To have the compiler ignore uses of assert, use the compiler option
+@-fignore-asserts@. <nidx>-fignore-asserts option</nidx> That is,
+expressions of the form @assert pred e@ will be rewritten to @e@.
Assertion failures can be caught, see the documentation for the
Hugs/GHC Exception library for information of how.
its error messages to refer to the line/file named in the @LINE@
pragma.
+<sect2>RULES pragma
+<p>
+The RULES pragma lets you specify rewrite rules. It is described in
+Section <ref name="Rewrite Rules"
+id="rewrite-rules">.
+
+%-----------------------------------------------------------------------------
+<sect1>Rewrite rules
+<label id="rewrite-rules">
+<nidx>RULES pagma</nidx>
+<nidx>pragma, RULES</nidx>
+<nidx>rewrite rules</nidx>
+<p>
+
+The programmer can specify rewrite rules as part of the source program
+(in a pragma). GHC applies these rewrite rules wherever it can.
+
+Here is an example:
+<tscreen><verb>
+ {-# RULES
+ "map/map" forall f,g,xs. map f (map g) xs = map (f.g) xs
+ #-}
+</verb></tscreen>
+
+<sect2>Syntax
+<p>
+
+From a syntactic point of view:
+<itemize>
+<item> Each rule has a name, enclosed in double quotes.
+<item> There may be zero or more rules in a @RULES@ pragma.
+<item> Layout applies in a @RULES@ pragma. Currently no new indentation level
+is set, so you must lay out your rules starting in the same column as the
+enclosing definitions.
+<item> Each variable mentioned in a rule must either be in scope (e.g. @map@),
+or bound by the @forall@ (e.g. @f@, @g@, @xs@). The variables bound by
+the @forall@ are called the <em>pattern</em> variables.
+<item> A pattern variable may optionally have a type signature.
+If its type is polymorphic, it <em>must</em> have a type signature.
+For example, here is the @foldr/build@ rule:
+<tscreen><verb>
+ "fold/build" forall k,z,g::forall b. (a->b->b) -> b -> b .
+ foldr k z (build g) = g k z
+</verb></tscreen>
+
+
+<item> The left hand side of a rule must consist of a top-level variable applied
+to arbitrary expressions. For example, this is <em>not</em> OK:
+<tscreen><verb>
+ "wrong1" forall e1,e2. case True of { True -> e1; False -> e2 } = e1
+ "wrong2" forall f. f True = True
+</verb></tscreen>
+In @"wrong1"@, the LHS is not an application; in @"wrong1"@, the LHS has a pattern variable
+in the head.
+<item> A rule does not need to be in the same module as (any of) the
+variables it mentions, though of course they need to be in scope.
+<item> Rules are automatically exported from a module, just as instance declarations are.
+</itemize>
+
+<sect2>Semantics
+<p>
+
+From a semantic point of view:
+<itemize>
+<item> Rules are only applied if you use the @-O@ flag.
+
+<item> Rules are regarded as left-to-right rewrite rules.
+When GHC finds an expression that is a substitution instance of the LHS
+of a rule, it replaces the expression by the (appropriately-substituted) RHS.
+By "a substitution instance" we mean that the LHS can be made equal to the
+expression by substituting for the pattern variables.
+
+<item> The LHS and RHS of a rule are typechecked, and must have the
+same type.
+
+<item> GHC makes absolutely no attempt to verify that the LHS and RHS
+of a rule have the same meaning. That is undecideable in general, and
+infeasible in most interesting cases. The responsibility is entirely the programmer's!
+
+<item> GHC makes no attempt to make sure that the rules are confluent or
+terminating. For example:
+<tscreen><verb>
+ "loop" forall x,y. f x y = f y x
+</verb></tscreen>
+This rule will cause the compiler to go into an infinite loop.
+
+<item> GHC currently uses a very simple, syntactic, matching algorithm
+for matching a rule LHS with an expression. It seeks a substitution
+which makes the LHS and expression syntactically equal modulo: alpha
+conversion, and (I think) eta conversion. But not beta conversion (that's
+called higher-order matching).
+
+<item> GHC keeps trying to apply the rules as it optimises the program.
+For example, consider:
+<tscreen><verb>
+ let s = map f
+ t = map g
+ in
+ s (t xs)
+</verb></tscreen>
+The expression @s (t xs)@ does not match the rule @"map/map"@, but GHC
+will substitute for @s@ and @t@, giving an expression which does match.
+If @s@ or @t@ was (a) used more than once, and (b) large or a redex, then it would
+not be substituted, and the rule would not fire.
+
+<item> In the earlier phases of compilation, GHC inlines <em>nothing
+that appears on the LHS of a rule</em>, because once you have substituted
+for something you can't match against it (given the simple minded
+matching). So if you write the rule
+<tscreen><verb>
+ "map/map" forall f,g. map f . map g = map (f.g)
+</verb></tscreen>
+this <em>won't</em> match the expression @map f (map g xs)@.
+It will only match something written with explicit use of ".".
+Well, not quite. It <em>will</em> match the expression
+<tscreen><verb>
+ wibble f g xs
+</verb></tscreen>
+where @wibble@ is defined:
+<tscreen><verb>
+ wibble f g = map f . map g
+</verb></tscreen>
+because @wibble@ will be inlined (it's small).
+
+Later on in compilation, GHC starts inlining even things on the
+LHS of rules, but still leaves the rules enabled. This inlining
+policy is controlled by the per-simplification-pass flag @-finline-phase@n.
+</itemize>
+
+
+<sect2>Controlling what's going on
+<p>
+
+<itemize>
+<item> Use @-fddump-rules@ to see what transformation rules GHC is using.
+<item> Use @-fddump-simpl-stats@ to see what rules are being fired.
+<item> The defintion of (say) @build@ in @PrelBase.lhs@ looks llike this:
+<tscreen><verb>
+ build :: forall a. (forall b. (a -> b -> b) -> b -> b) -> [a]
+ {-# INLINE build #-}
+ build g = g (:) []
+</verb></tscreen>
+Notice the @INLINE@! That prevents @(:)@ from being inlined when compiling
+@PrelBase@, so that an importing module will ``see'' the @(:)@, and can
+match it on the LHS of a rule. @INLINE@ prevents any inlining happening
+in the RHS of the @INLINE@ thing. I regret the delicacy of this.
+
+<item> In @ghc/lib/std/PrelBase.lhs@ look at the rules for @map@ to
+see how to write rules that will do fusion and yet give an efficient
+program even if fusion doesn't happen. More rules in @PrelList.lhs@.
+</itemize>
projects / ghc-hetmet.git / blobdiff