ca56d6b6a8a72a0f3002e9ffafde9403404928fa
[ghc.git] / docs / comm / the-beast / basicTypes.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 Basics</title>
6 </head>
7
8 <body BGCOLOR="FFFFFF">
9 <h1>The GHC Commentary - The Basics</h1>
10 <p>
11 The directory <a
12 href="http://cvs.haskell.org/cgi-bin/cvsweb.cgi/fptools/ghc/compiler/basicTypes/"><code>fptools/ghc/compiler/basicTypes/</code></a>
13 contains modules that define some of the essential types definition for
14 the compiler - such as, identifiers, variables, modules, and unique
15 names. Some of those are discussed in the following. See elsewhere for more
16 detailed information on:
17 <ul>
18 <li> <a href="vars.html"><code>Var</code>s, <code>Id</code>s, and <code>TyVar</code>s</a>
19 <li> <a href="renamer.html"><code>OccName</code>s, <code>RdrName</code>s, and <code>Names</code>s</a>
20 </ul>
21
22 <h2>Elementary Types</h2>
23
24 <h4><code>Id</code>s</h4>
25 <p>
26 An <code>Id</code> (defined in <a
27 href="http://cvs.haskell.org/cgi-bin/cvsweb.cgi/fptools/ghc/compiler/basicTypes/Id.lhs"><code>Id.lhs</code></a>
28 essentially records information about value and data constructor
29 identifiers -- to be precise, in the case of data constructors, two
30 <code>Id</code>s are used to represent the worker and wrapper functions
31 for the data constructor, respectively. The information maintained in
32 the <code>Id</code> abstraction includes among other items strictness,
33 occurrence, specialisation, and unfolding information.
34 <p>
35 Due to the way <code>Id</code>s are used for data constructors,
36 all <code>Id</code>s are represented as variables, which contain a
37 <code>varInfo</code> field of abstract type <code><a
38 href="http://cvs.haskell.org/cgi-bin/cvsweb.cgi/fptools/ghc/compiler/basicTypes/IdInfo.lhs">IdInfo</a>.IdInfo</code>.
39 This is where the information about <code>Id</code>s is really stored.
40 The following is a (currently, partial) list of the various items in an
41 <code>IdInfo</code>:
42 <p>
43 <dl>
44 <dt><a name="occInfo">Occurence information</a>
45 <dd>The <code>OccInfo</code> data type is defined in the module <a
46 href="http://cvs.haskell.org/cgi-bin/cvsweb.cgi/fptools/ghc/compiler/basicTypes/BasicTypes.lhs"><code>BasicTypes.lhs</code></a>.
47 Apart from the trivial <code>NoOccInfo</code>, it distinguishes
48 between variables that do not occur at all (<code>IAmDead</code>),
49 occur just once (<code>OneOcc</code>), or a <a
50 href="simplifier.html#loopBreaker">loop breakers</a>
51 (<code>IAmALoopBreaker</code>).
52 </dl>
53
54 <h2>Sets, Finite Maps, and Environments</h2>
55 <p>
56 Sets of variables, or more generally names, which are needed throughout
57 the compiler, are provided by the modules <a
58 href="http://cvs.haskell.org/cgi-bin/cvsweb.cgi/fptools/ghc/compiler/basicTypes/VarSet.lhs"><code>VarSet.lhs</code></a>
59 and <a
60 href="http://cvs.haskell.org/cgi-bin/cvsweb.cgi/fptools/ghc/compiler/basicTypes/NameSet.lhs"><code>NameSet.lhs</code></a>,
61 respectively. Moreover, frequently maps from variables (or names) to
62 other data is needed. For example, a substitution is represented by a
63 finite map from variable names to expressions. Jobs like this are
64 solved by means of variable and name environments implemented by the
65 modules <a
66 href="http://cvs.haskell.org/cgi-bin/cvsweb.cgi/fptools/ghc/compiler/basicTypes/VarEnv.lhs"><code>VarEnv.lhs</code></a>
67 and <a
68 href="http://cvs.haskell.org/cgi-bin/cvsweb.cgi/fptools/ghc/compiler/basicTypes/NameEnv.lhs"><code>NameEnv.lhs</code></a>.
69
70 <h4>The Module <code>VarSet</code></h4>
71 <p>
72 The Module <code>VarSet</code> provides the types <code>VarSet</code>,
73 <code>IdSet</code>, and <code>TyVarSet</code>, which are synonyms in the
74 current implementation, as <code>Var</code>, <code>Id</code>, and
75 <code>TyVar</code> are synonyms. The module provides all the operations
76 that one would expect including the creating of sets from individual
77 variables and lists of variables, union and intersection operations,
78 element checks, deletion, filter, fold, and map functions.
79 <p>
80 The implementation is based on <a
81 href="http://cvs.haskell.org/cgi-bin/cvsweb.cgi/fptools/ghc/compiler/utils/UniqSet.lhs"><code>UniqSet</code></a>s,
82 which in turn are simply <a href="http://cvs.haskell.org/cgi-bin/cvsweb.cgi/fptools/ghc/compiler/utils/UniqFM.lhs"><code>UniqFM</code></a>s
83 (i.e., finite maps with uniques as keys) that map each unique to the
84 variable that it represents.
85
86 <h4>The Module <code>NameSet</code></h4>
87 <p>
88 The Module <code>NameSet</code> provides the same functionality as
89 <code>VarSet</code> only for <a
90 href="http://cvs.haskell.org/cgi-bin/cvsweb.cgi/fptools/ghc/compiler/basicTypes/Name.lhs"><code>Name</code></a>s.
91 As for the difference between <code>Name</code>s and <code>Var</code>s,
92 a <code>Var</code> is built from a <code>Name</code> plus additional
93 information (mostly importantly type information).
94
95 <h4>The Module <code>VarEnv</code></h4>
96 <p>
97 The module <code>VarEnv</code> provides the types <code>VarEnv</code>,
98 <code>IdEnv</code>, and <code>TyVarEnv</code>, which are again
99 synonyms. The provided base functionality is similar to
100 <code>VarSet</code> with the main difference that a type <code>VarEnv
101 T</code> associates a value of type <code>T</code> with each variable in
102 the environment, thus effectively implementing a finite map from
103 variables to values of type <code>T</code>.
104 <p>
105 The implementation of <code>VarEnv</code> is also by <a
106 href="http://cvs.haskell.org/cgi-bin/cvsweb.cgi/fptools/ghc/compiler/utils/UniqFM.lhs"><code>UniqFM</code></a>,
107 which entails the slightly surprising implication that it is
108 <em>not</em> possible to retrieve the domain of a variable environment.
109 In other words, there is no function corresponding to
110 <code>VarSet.varSetElems :: VarSet -> [Var]</code> in
111 <code>VarEnv</code>. This is because the <code>UniqFM</code> used to
112 implement <code>VarEnv</code> stores only the unique corresponding to a
113 variable in the environment, but not the entire variable (and there is
114 no mapping from uniques to variables).
115 <p>
116 In addition to plain variable environments, the module also contains
117 special substitution environments - the type <code>SubstEnv</code> -
118 that associates variables with a special purpose type
119 <code>SubstResult</code>.
120
121 <h4>The Module <code>NameEnv</code></h4>
122 <p>
123 The type <code>NameEnv.NameEnv</code> is like <code>VarEnv</code> only
124 for <code>Name</code>s.
125
126 <p><hr><small>
127 <!-- hhmts start -->
128 Last modified: Tue Jan 8 18:29:52 EST 2002
129 <!-- hhmts end -->
130 </small>
131 </body>
132 </html>