docs/comm/the-beast/renamer.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 - The Glorious Renamer</title>
   6   </head>
   7
   8   <body BGCOLOR="FFFFFF">
   9     <h1>The GHC Commentary - The Glorious Renamer</h1>
  10     <p>
  11       The <em>renamer</em> sits between the parser and the typechecker.
  12       However, its operation is quite tightly interwoven with the
  13       typechecker.  This is partially due to support for Template Haskell,
  14       where spliced code has to be renamed and type checked.  In particular,
  15       top-level splices lead to multiple rounds of renaming and type
  16       checking.
  17     </p>
  18     <p>
  19       The main externally used functions of the renamer are provided by the
  20       module <code>rename/RnSource.lhs</code>.  In particular, we have
  21     </p>
  22     <blockquote>
  23       <pre>
  24 rnSrcDecls  :: HsGroup RdrName -> RnM (TcGblEnv, HsGroup Name)
  25 rnTyClDecls :: [LTyClDecl RdrName] -> RnM [LTyClDecl Name]
  26 rnSplice    :: HsSplice RdrName -> RnM (HsSplice Name, FreeVars)</pre>
  27     </blockquote>
  28     <p>
  29       All of which execute in the renamer monad <code>RnM</code>.  The first
  30       function, <code>rnSrcDecls</code> renames a binding group; the second,
  31       <code>rnTyClDecls</code> renames a list of (toplevel) type and class
  32       declarations; and the third, <code>rnSplice</code> renames a Template
  33       Haskell splice.  As the types indicate, the main task of the renamer is
  34       to convert converts all the <tt>RdrNames</tt> to <a
  35       href="names.html"><tt>Names</tt></a>, which includes a number of
  36       well-formedness checks (no duplicate declarations, all names are in
  37       scope, and so on).  In addition, the renamer performs other, not
  38       strictly name-related, well-formedness checks, which includes checking
  39       that the appropriate flags have been supplied whenever language
  40       extensions are used in the source.
  41     </p>
  42
  43     <h2>RdrNames</h2>
  44     <p>
  45       A <tt>RdrName.RdrName</tt> is pretty much just a string (for an
  46       unqualified name like "<tt>f</tt>") or a pair of strings (for a
  47       qualified name like "<tt>M.f</tt>"):
  48     </p>
  49     <blockquote>
  50       <pre>
  51 data RdrName
  52   = Unqual OccName
  53         -- Used for ordinary, unqualified occurrences
  54
  55   | Qual Module OccName
  56         -- A qualified name written by the user in
  57         --  *source* code.  The module isn't necessarily
  58         -- the module where the thing is defined;
  59         -- just the one from which it is imported
  60
  61   | Orig Module OccName
  62         -- An original name; the module is the *defining* module.
  63         -- This is used when GHC generates code that will be fed
  64         -- into the renamer (e.g. from deriving clauses), but where
  65         -- we want to say "Use Prelude.map dammit".
  66
  67   | Exact Name
  68         -- We know exactly the Name. This is used
  69         --  (a) when the parser parses built-in syntax like "[]"
  70         --      and "(,)", but wants a RdrName from it
  71         --  (b) when converting names to the RdrNames in IfaceTypes
  72         --      Here an Exact RdrName always contains an External Name
  73         --      (Internal Names are converted to simple Unquals)
  74         --  (c) by Template Haskell, when TH has generated a unique name</pre>
  75     </blockquote>
  76     <p>
  77       The OccName type is described in <a href="names.html#occname">The
  78         truth about names</a>.
  79     </p>
  80
  81     <h2>The Renamer Monad</h2>
  82     <p>
  83       Due to the tight integration of the renamer with the typechecker, both
  84       use the same monad in recent versions of GHC.  So, we have
  85     </p>
  86     <blockquote>
  87       <pre>
  88 type RnM  a = TcRn a            -- Historical
  89 type TcM  a = TcRn a            -- Historical</pre>
  90     </blockquote>
  91     <p>
  92       with the combined monad defined as
  93     </p>
  94     <blockquote>
  95       <pre>
  96 type TcRn a       = TcRnIf TcGblEnv TcLclEnv a
  97 type TcRnIf a b c = IOEnv (Env a b) c
  98
  99 data Env gbl lcl        -- Changes as we move into an expression
 100   = Env {
 101         env_top  :: HscEnv,     -- Top-level stuff that never changes
 102                                 -- Includes all info about imported things
 103
 104         env_us   :: TcRef UniqSupply,   -- Unique supply for local varibles
 105
 106         env_gbl  :: gbl,        -- Info about things defined at the top level
 107                                 -- of the module being compiled
 108
 109         env_lcl  :: lcl         -- Nested stuff; changes as we go into
 110                                 -- an expression
 111     }</pre>
 112     </blockquote>
 113     <p>
 114       the details of the global environment type <code>TcGblEnv</code> and
 115       local environment type <code>TcLclEnv</code> are also defined in the
 116       module <code>typecheck/TcRnTypes.lhs</code>.   The monad
 117       <code>IOEnv</code> is defined in <code>utils/IOEnv.hs</code> and extends
 118       the vanilla <code>IO</code> monad with an additional state parameter
 119       <code>env</code> that is treated as in a reader monad.  (Side effecting
 120       operations, such as updating the unique supply, are done with
 121       <code>TcRef</code>s, which are simply a synonym for <code>IORef</code>s.)
 122     </p>
 123
 124     <h2>Name Space Management</h2>
 125     <p>
 126       As anticipated by the variants <code>Orig</code> and <code>Exact</code>
 127       of <code>RdrName</code> some names should not change during renaming,
 128       whereas others need to be turned into unique names.  In this context,
 129       the two functions <code>RnEnv.newTopSrcBinder</code> and
 130       <code>RnEnv.newLocals</code> are important:
 131     </p>
 132     <blockquote>
 133       <pre>
 134 newTopSrcBinder :: Module -> Maybe Name -> Located RdrName -> RnM Name
 135 newLocalsRn     :: [Located RdrName] -> RnM [Name]</pre>
 136     </blockquote>
 137     <p>
 138       The two functions introduces new toplevel and new local names,
 139       respectively, where the first two arguments to
 140       <code>newTopSrcBinder</code> determine the currently compiled module and
 141       the parent construct of the newly defined name.  Both functions create
 142       new names only for <code>RdrName</code>s that are neither exact nor
 143       original.
 144     </p>
 145
 146     <h3>Introduction of Toplevel Names: Global RdrName Environment</h3>
 147     <p>
 148       A global <code>RdrName</code> environment
 149       <code>RdrName.GlobalRdrEnv</code> is a map from <code>OccName</code>s to
 150       lists of qualified names.  More precisely, the latter are
 151       <code>Name</code>s with an associated <code>Provenance</code>:
 152     </p>
 153     <blockquote>
 154       <pre>
 155 data Provenance
 156   = LocalDef            -- Defined locally
 157         Module
 158
 159   | Imported            -- Imported
 160         [ImportSpec]    -- INVARIANT: non-empty
 161         Bool            -- True iff the thing was named *explicitly*
 162                         -- in *any* of the import specs rather than being
 163                         -- imported as part of a group;
 164         -- e.g.
 165         --      import B
 166         --      import C( T(..) )
 167         -- Here, everything imported by B, and the constructors of T
 168         -- are not named explicitly; only T is named explicitly.
 169         -- This info is used when warning of unused names.</pre>
 170     </blockquote>
 171     <p>
 172       The part of the global <code>RdrName</code> environment for a module
 173       that contains the local definitions is created by the function
 174       <code>RnNames.importsFromLocalDecls</code>, which also computes a data
 175       structure recording all imported declarations in the form of a value of
 176       type <code>TcRnTypes.ImportAvails</code>.
 177     </p>
 178     <p>
 179       The function <code>importsFromLocalDecls</code>, in turn, makes use of
 180       <code>RnNames.getLocalDeclBinders :: Module -> HsGroup RdrName -> RnM
 181       [AvailInfo]</code> to extract all declared names from a binding group,
 182       where <code>HscTypes.AvailInfo</code> is essentially a collection of
 183       <code>Name</code>s; i.e., <code>getLocalDeclBinders</code>, on the fly,
 184       generates <code>Name</code>s from the <code>RdrName</code>s of all
 185       top-level binders of the module represented by the <code>HsGroup
 186       RdrName</code> argument.
 187     </p>
 188     <p>
 189       It is important to note that all this happens before the renamer
 190       actually descends into the toplevel bindings of a module.  In other
 191       words, before <code>TcRnDriver.rnTopSrcDecls</code> performs the
 192       renaming of a module by way of <code>RnSource.rnSrcDecls</code>, it uses
 193       <code>importsFromLocalDecls</code> to set up the global
 194       <code>RdrName</code> environment, which contains <code>Name</code>s for
 195       all imported <em>and</em> all locally defined toplevel binders.  Hence,
 196       when the helpers of <code>rnSrcDecls</code> come across the
 197       <em>defining</em> occurences of a toplevel <code>RdrName</code>, they
 198       don't rename it by generating a new name, but they simply look up its
 199       name in the global <code>RdrName</code> environment.
 200     </p>
 201
 202     <h2>Rebindable syntax</h2>
 203     <p>
 204       In Haskell when one writes "3" one gets "fromInteger 3", where
 205       "fromInteger" comes from the Prelude (regardless of whether the
 206       Prelude is in scope).  If you want to completely redefine numbers,
 207       that becomes inconvenient.  So GHC lets you say
 208       "-fno-implicit-prelude"; in that case, the "fromInteger" comes from
 209       whatever is in scope.  (This is documented in the User Guide.)
 210     </p>
 211     <p>
 212       This feature is implemented as follows (I always forget).
 213     <ul>
 214       <li>Names that are implicitly bound by the Prelude, are marked by the
 215         type <code>HsExpr.SyntaxExpr</code>.  Moreover, the association list
 216         <code>HsExpr.SyntaxTable</code> is set up by the renamer to map
 217         rebindable names to the value they are bound to.
 218       </li>
 219       <li>Currently, five constructs related to numerals
 220         (<code>HsExpr.NegApp</code>, <code>HsPat.NPat</code>,
 221         <code>HsPat.NPlusKPat</code>,   <code>HsLit.HsIntegral</code>, and
 222         <code>HsLit.HsFractional</code>)  and
 223         two constructs related to code>do</code> expressions
 224         (<code>HsExpr.BindStmt</code> and
 225         <code>HsExpr.ExprStmt</code>) have rebindable syntax.
 226       </li>
 227       <li> When the parser builds these constructs, it puts in the
 228         built-in Prelude Name (e.g. PrelNum.fromInteger).
 229       </li>
 230       <li> When the renamer encounters these constructs, it calls
 231       <tt>RnEnv.lookupSyntaxName</tt>.
 232         This checks for <tt>-fno-implicit-prelude</tt>; if not, it just
 233         returns the same Name; otherwise it takes the occurrence name of the
 234         Name, turns it into an unqualified RdrName, and looks it up in the
 235         environment.  The returned name is plugged back into the construct.
 236       </li>
 237       <li> The typechecker uses the Name to generate the appropriate typing
 238         constraints.
 239       </li>
 240     </ul>
 241
 242     <p><small>
 243 <!-- hhmts start -->
 244 Last modified: Wed May  4 17:16:15 EST 2005
 245 <!-- hhmts end -->
 246     </small>
 247   </body>
 248 </html>
 249