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>