TFs: FIX #2203 (second half)
[ghc-hetmet.git] / 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