ghc/docs/comm/the-beast/typecheck.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 - Checking Types</title>
   6   </head>
   7
   8   <body BGCOLOR="FFFFFF">
   9     <h1>The GHC Commentary - Checking Types</h1>
  10     <p>
  11       Probably the most important phase in the frontend is the type checker,
  12       which is located at <a
  13         href="http://cvs.haskell.org/cgi-bin/cvsweb.cgi/fptools/ghc/compiler/typecheck/"><code>fptools/ghc/compiler/typecheck/</code>.</a>
  14       GHC type checks programs in their original Haskell form before the
  15       desugarer converts them into Core code.  This complicates the type
  16       checker as it has to handle the much more verbose Haskell AST, but it
  17       improves error messages, as the those message are based on the same
  18       structure that the user sees.
  19     <p>
  20       GHC defines the abstract syntax of Haskell programs in <a
  21       href="http://cvs.haskell.org/cgi-bin/cvsweb.cgi/fptools/ghc/compiler/hsSyn/HsSyn.lhs"><code>HsSyn</code></a>
  22       using a structure that abstracts over the concrete representation of
  23       bound occurences of identifiers and patterns.  The module <a
  24       href="http://cvs.haskell.org/cgi-bin/cvsweb.cgi/fptools/ghc/compiler/typecheck/TcHsSyn.lhs"><code>TcHsSyn</code></a>
  25       instantiates this structure for the type checker using <a
  26       href="http://cvs.haskell.org/cgi-bin/cvsweb.cgi/fptools/ghc/compiler/typecheck/TcEnv.lhs"><code>TcEnv</code></a>.<code>TcId</code>
  27       to represent identifiers - in fact, a <code>TcId</code> is currently
  28       nothing but just a synonym for a <a href="vars.html">plain
  29       <code>Id</code>.</a>
  30
  31     <h4>Types Variables and Zonking</h4>
  32     <p>
  33       During type checking type variables are represented by mutable variables
  34       - cf. the <a href="vars.html#TyVar">variable story.</a>  Consequently,
  35       unification can instantiate type variables by updating those mutable
  36       variables.  This process of instantiation is (for reasons that elude
  37       me) called <a
  38       href="http://www.dictionary.com/cgi-bin/dict.pl?term=zonk&db=*">zonking</a>
  39       in GHC's sources.  The zonking routines for the various forms of Haskell
  40       constructs are responsible for most of the code in the module <a
  41       href="http://cvs.haskell.org/cgi-bin/cvsweb.cgi/fptools/ghc/compiler/typecheck/TcHsSyn.lhs"><code>TcHsSyn</code>,</a>
  42       whereas the routines that actually operate on mutable types are defined
  43       in <a
  44       href="http://cvs.haskell.org/cgi-bin/cvsweb.cgi/fptools/ghc/compiler/typecheck/TcMType.lhs"><code>TcMTypes</code></a>;
  45       this includes routines to create mutable structures and update them as
  46       well as routines that check constraints, such as that type variables in
  47       function signatures have not been instantiated during type checking.
  48       The actual type unification routine is <code>uTys</code> in the same
  49       module.
  50     <p>
  51       All type variables that may be instantiated (those in signatures
  52       may not), but haven't been instantiated during type checking, are zonked
  53       to <code>()</code>, so that after type checking all mutable variables
  54       have been eliminated.
  55
  56     <h4>Type Checking Environment</h4>
  57     <p>
  58       During type checking, GHC maintains a <em>type environment</em> whose
  59       details are fixed in <a
  60       href="http://cvs.haskell.org/cgi-bin/cvsweb.cgi/fptools/ghc/compiler/typecheck/TcEnv.lhs"><code>TcEnv.lhs</code>.</a>
  61       Among other things, the environment contains all imported and local
  62       instances as well as a list of <em>global</em> entities (imported and
  63       local types and classes together with imported identifiers) and
  64       <em>local</em> entities (locally defined identifiers).  This environment
  65       is threaded through the type checking monad.
  66
  67     <h4>Expressions</h4>
  68     <p>
  69       Expressions are type checked by <a
  70       href="http://cvs.haskell.org/cgi-bin/cvsweb.cgi/fptools/ghc/compiler/typecheck/TcExpr.lhs"><code>TcExpr.lhs</code>.</a>
  71     <p>
  72       Usage occurences of identifiers are processed by the function
  73       <code>tcId</code> whose main purpose is to <a href="#inst">instantiate
  74       overloaded identifiers.</a> It essentially calls
  75       <code>TcInst.instOverloadedFun</code> once for each universally
  76       quantified set of type constraints.  It should be noted that overloaded
  77       identifiers are replaced by new names that are first defined in the LIE
  78       (Local Instance Environment?) and later promoted into top-level
  79       bindings.
  80
  81     <h4><a name="inst">Handling of Dictionaries and Method Instances</a></h4>
  82     <p>
  83       GHC implements overloading using so-called <em>dictionaries.</em> A
  84       dictionary is a tuple of functions -- one function for each method in
  85       the class of which the dictionary implements an instance.  During type
  86       checking, GHC replaces each type constraint of a function with one
  87       additional argument.  At runtime, the extended function gets passed a
  88       matching class dictionary by way of these additional arguments.
  89       Whenever the function needs to call a method of such a class, it simply
  90       extracts it from the dictionary.
  91     <p>
  92       This sounds simple enough; however, the actual implementation is a bit
  93       more tricky as it wants to keep track of all the instances at which
  94       overloaded functions are used in a module.  This information is useful
  95       to optimise the code.  The implementation is the module <a
  96       href="http://cvs.haskell.org/cgi-bin/cvsweb.cgi/fptools/ghc/compiler/typecheck/Inst.lhs"><code>Inst.lhs</code>.</a>
  97     <p>
  98       The function <code>instOverloadedFun</code> is invoked for each
  99       overloaded usage occurence of an identifier, where overloaded means that
 100       the type of the idendifier contains a non-trivial type constraint.  It
 101       proceeds in two steps: (1) Allocation of a method instance
 102       (<code>newMethodWithGivenTy</code>) and (2) instantiation of functional
 103       dependencies.  The former implies allocating a new unique identifier,
 104       which replaces the original (overloaded) identifier at the currently
 105       type-checked usage occurrence.
 106     <p>
 107       The new identifier (after being threaded through the LIE) eventually
 108       will be bound by a top-level binding whose rhs contains a partial
 109       application of the original overloaded identifier.  This papp applies
 110       the overloaded function to the dictionaries needed for the current
 111       instance.  In GHC lingo, this is called a <em>method.</em>  Before
 112       becoming a top-level binding, the method is first represented as a value
 113       of type <code>Inst.Inst</code>, which makes it easy to fold multiple
 114       instances of the same identifier at the same types into one global
 115       definition.  (And probably other things, too, which I haven't
 116       investigated yet.)
 117
 118     <p>
 119       <strong>Note:</strong> As of 13 January 2001 (wrt. to the code in the
 120       CVS HEAD), the above mechanism interferes badly with RULES pragmas
 121       defined over overloaded functions.  During instantiation, a new name is
 122       created for an overloaded function partially applied to the dictionaries
 123       needed in a usage position of that function.  As the rewrite rule,
 124       however, mentions the original overloaded name, it won't fire anymore
 125       -- unless later phases remove the intermediate definition again.  The
 126       latest CVS version of GHC has an option
 127       <code>-fno-method-sharing</code>, which avoids sharing instantiation
 128       stubs.  This is usually/often/sometimes sufficient to make the rules
 129       fire again.
 130
 131     <p><small>
 132 <!-- hhmts start -->
 133 Last modified: Tue Nov 13 14:28:44 EST 2001
 134 <!-- hhmts end -->
 135     </small>
 136   </body>
 137 </html>