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