From ade3217b2f77547417798e7a6f8ca6b69d67adc7 Mon Sep 17 00:00:00 2001 From: simonpj Date: Tue, 18 May 1999 15:41:32 +0000 Subject: [PATCH] [project @ 1999-05-18 15:41:31 by simonpj] Documentation for rewrite rules. Some stuff in (a) glasgow exts (b) debugging Doubtless incomplete, and since I can't build the docs on (my) NT box, I don't even know if my changes are syntactically correct! --- ghc/docs/users_guide/debugging.vsgml | 55 ++++++----- ghc/docs/users_guide/glasgow_exts.vsgml | 159 ++++++++++++++++++++++++++++++- 2 files changed, 189 insertions(+), 25 deletions(-) diff --git a/ghc/docs/users_guide/debugging.vsgml b/ghc/docs/users_guide/debugging.vsgml index 78842c7..6d14eb3 100644 --- a/ghc/docs/users_guide/debugging.vsgml +++ b/ghc/docs/users_guide/debugging.vsgml @@ -101,23 +101,26 @@ happening. Make a debugging dump after pass @@ (may be common enough to need a short form...). Some of the most useful ones are: - -@-ddump-rdr@ | reader output (earliest stuff in the compiler) @@ -@-ddump-rn@ | renamer output @@ -@-ddump-tc@ | typechecker output @@ -@-ddump-deriv@ | derived instances @@ -@-ddump-ds@ | desugarer output @@ -@-ddump-simpl@ | simplifer output (Core-to-Core passes) @@ -@-ddump-stranal@ | strictness analyser output @@ -@-ddump-usagesp@ | UsageSP inference pre-inf and output @@ -@-ddump-occur-anal@ | `occurrence analysis' output @@ -@-ddump-spec@ | dump specialisation info @@ -@-ddump-stg@ | output of STG-to-STG passes @@ -@-ddump-absC@ | unflattened Abstract~C @@ -@-ddump-flatC@ | flattened Abstract~C @@ -@-ddump-realC@ | same as what goes to the C compiler @@ -@-ddump-asm@ | assembly language from the native-code generator @@ - + +@-ddump-rdr@: reader output (earliest stuff in the compiler) +@-ddump-rn@: renamer output +@-ddump-tc@: typechecker output +@-ddump-deriv@: derived instances +@-ddump-ds@: desugarer output +@-ddump-spec@: output of specialisation pass +@-ddump-rules@: dumps all rewrite rules (including those generated by the specialisation pass) +@-ddump-simpl@: simplifer output (Core-to-Core passes) +@-ddump-usagesp@: UsageSP inference pre-inf and output +@-ddump-cpranal@: CPR analyser output +@-ddump-stranal@: strictness analyser output +@-ddump-workwrap@: worker/wrapper split output +@-ddump-occur-anal@: `occurrence analysis' output +@-ddump-stg@: output of STG-to-STG passes +@-ddump-absC@: unflattened Abstract~C +@-ddump-flatC@: flattened Abstract~C +@-ddump-realC@: same as what goes to the C compiler +@-ddump-asm@: assembly language from the native-code generator + -ddump-rdr option% -ddump-rn option% @@ -125,6 +128,9 @@ need a short form...). Some of the most useful ones are: -ddump-deriv option% -ddump-ds option% -ddump-simpl option% +-ddump-cpranal option% +-ddump-workwrap option% +-ddump-rules option% -ddump-usagesp option% -ddump-stranal option% -ddump-occur-anal option% @@ -154,18 +160,21 @@ Show the output of each @-dppr-{user,debug,all@}: +@-dppr-{user,debug@}: -dppr-user option -dppr-debug option --dppr-all option Debugging output is in one of several ``styles.'' Take the printing of types, for example. In the ``user'' style, the compiler's internal ideas about types are presented in Haskell source-level syntax, insofar as possible. In the ``debug'' style (which is the default for -debugging output), the types are printed in the most-often-desired -form, with explicit foralls, etc. In the ``show all'' style, very -verbose information about the types (e.g., the Uniques on the -individual type variables) is displayed. +debugging output), the types are printed in with +explicit foralls, and variables have their unique-id attached (so you +can check for things that look the same but aren't). + +@-ddump-simpl-stats@: +-ddump-simpl-stats option +Dump statistics about how many of each kind +of transformation too place. If you add @-dppr-debug@ you get more detailed information. @-ddump-raw-asm@: -ddump-raw-asm option diff --git a/ghc/docs/users_guide/glasgow_exts.vsgml b/ghc/docs/users_guide/glasgow_exts.vsgml index e54d9f8..4f52a48 100644 --- a/ghc/docs/users_guide/glasgow_exts.vsgml +++ b/ghc/docs/users_guide/glasgow_exts.vsgml @@ -1,5 +1,5 @@ % -% $Id: glasgow_exts.vsgml,v 1.10 1999/05/04 08:31:52 sof Exp $ +% $Id: glasgow_exts.vsgml,v 1.11 1999/05/18 15:41:32 simonpj Exp $ % % GHC Language Extensions. % @@ -36,7 +36,7 @@ classes" id="multi-param-type-classes">. Local universal quantification: -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 . @@ -66,6 +66,13 @@ Pragmas are special instructions to the compiler placed in the source file. The pragmas GHC supports are described in Section . +Rewrite rules: + +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 . + Before you get too carried away working at the lowest level (e.g., @@ -1986,3 +1993,151 @@ and this line corresponds to line 42 in the original. GHC will adjust its error messages to refer to the line/file named in the @LINE@ pragma. +RULES pragma +

+The RULES pragma lets you specify rewrite rules. It is described in +Section . + +%----------------------------------------------------------------------------- +Rewrite rules +

+ +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: + + {-# RULES + "map/map" forall f,g,xs. map f (map g) xs = map (f.g) xs + #-} + + +Syntax + +From a syntactic point of view: + + Each rule has a name, enclosed in double quotes. + There may be zero or more rules in a @RULES@ pragma. + 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. + 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 pattern variables. + A pattern variable may optionally have a type signature. +If its type is polymorphic, it must have a type signature. +For example, here is the @foldr/build@ rule: + + "fold/build" forall k,z,g::forall b. (a->b->b) -> b -> b . + foldr k z (build g) = g k z + + + + The left hand side of a rule must consist of a top-level variable applied +to arbitrary expressions. For example, this is not OK: + + "wrong1" forall e1,e2. case True of { True -> e1; False -> e2 } = e1 + "wrong2" forall f. f True = True + +In @"wrong1"@, the LHS is not an application; in @"wrong1"@, the LHS has a pattern variable +in the head. + 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. + Rules are automatically exported from a module, just as instance declarations are. + + +Semantics + +From a semantic point of view: + + Rules are only applied if you use the @-O@ flag. + + 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. + + The LHS and RHS of a rule are typechecked, and must have the +same type. + + 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! + + GHC makes no attempt to make sure that the rules are confluent or +terminating. For example: + + "loop" forall x,y. f x y = f y x + +This rule will cause the compiler to go into an infinite loop. + + 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). + + GHC keeps trying to apply the rules as it optimises the program. +For example, consider: + + let s = map f + t = map g + in + s (t xs) + +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. + + In the earlier phases of compilation, GHC inlines nothing +that appears on the LHS of a rule, because once you have substituted +for something you can't match against it (given the simple minded +matching). So if you write the rule + + "map/map" forall f,g. map f . map g = map (f.g) + +this won't match the expression @map f (map g xs)@. +It will only match something written with explicit use of ".". +Well, not quite. It will match the expression + + wibble f g xs + +where @wibble@ is defined: + + wibble f g = map f . map g + +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. + + + +Controlling what's going on + + + Use @-fddump-rules@ to see what transformation rules GHC is using. + Use @-fddump-simpl-stats@ to see what rules are being fired. + The defintion of (say) @build@ in @PrelBase.lhs@ looks llike this: + + build :: forall a. (forall b. (a -> b -> b) -> b -> b) -> [a] + {-# INLINE build #-} + build g = g (:) [] + +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. + + 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@. + -- 1.7.10.4