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
  15     <h4>Type Checking Environment</h4>
  16     <p>
  17       During type checking, GHC maintains a <em>type environment</em> whose
  18       details are fixed in <a
  19       href="http://cvs.haskell.org/cgi-bin/cvsweb.cgi/fptools/ghc/compiler/typecheck/TcEnv.lhs"><code>TcEnv.lhs</code>.</a>
  20       Among other things, the environment contains all imported and local
  21       instances as well as a list of <em>global</em> entities (imported and
  22       local types and classes together with imported identifiers) and
  23       <em>local</em> entities (locally defined identifiers).  This environment
  24       is threaded through the type checking monad.
  25
  26     <h4>Expressions</h4>
  27     <p>
  28       Expressions are type checked by <a
  29       href="http://cvs.haskell.org/cgi-bin/cvsweb.cgi/fptools/ghc/compiler/typecheck/TcExpr.lhs"><code>TcExpr.lhs</code>.</a>
  30     <p>
  31       Usage occurences of identifiers are processed by the function
  32       <code>tcId</code> whose main purpose is to <a href="#inst">instantiate
  33       overloaded identifiers.</a> It essentially calls
  34       <code>TcInst.instOverloadedFun</code> once for each universally
  35       quantified set of type constraints.  It should be noted that overloaded
  36       identifiers are replaced by new names that are first defined in the LIE
  37       (Local Instance Environment?) and later promoted into top-level
  38       bindings.
  39
  40     <h4><a name="inst">Handling of Dictionaries and Method Instances</a></h4>
  41     <p>
  42       GHC implements overloading using so-called <em>dictionaries.</em> A
  43       dictionary is a tuple of functions -- one function for each method in
  44       the class of which the dictionary implements an instance.  During type
  45       checking, GHC replaces each type constraint of a function with one
  46       additional argument.  At runtime, the extended function gets passed a
  47       matching class dictionary by way of these additional arguments.
  48       Whenever the function needs to call a method of such a class, it simply
  49       extracts it from the dictionary.
  50     <p>
  51       This sounds simple enough; however, the actual implementation is a bit
  52       more tricky as it wants to keep track of all the instances at which
  53       overloaded functions are used in a module.  This information is useful
  54       to optimise the code.  The implementation is the module <a
  55       href="http://cvs.haskell.org/cgi-bin/cvsweb.cgi/fptools/ghc/compiler/typecheck/Inst.lhs"><code>Inst.lhs</code>.</a>
  56     <p>
  57       The function <code>instOverloadedFun</code> is invoked for each
  58       overloaded usage occurence of an identifier, where overloaded means that
  59       the type of the idendifier contains a non-trivial type constraint.  It
  60       proceeds in two steps: (1) Allocation of a method instance
  61       (<code>newMethodWithGivenTy</code>) and (2) instantiation of functional
  62       dependencies.  The former implies allocating a new unique identifier,
  63       which replaces the original (overloaded) identifier at the currently
  64       type-checked usage occurrence.
  65     <p>
  66       The new identifier (after being threaded through the LIE) eventually
  67       will be bound by a top-level binding whose rhs contains a partial
  68       application of the original overloaded identifier.  This papp applies
  69       the overloaded function to the dictionaries needed for the current
  70       instance.  In GHC lingo, this is called a <em>method.</em>  Before
  71       becoming a top-level binding, the method is first represented as a value
  72       of type <code>Inst.Inst</code>, which makes it easy to fold multiple
  73       instances of the same identifier at the same types into one global
  74       definition.  (And probably other things, too, which I haven't
  75       investigated yet.)
  76
  77     <p>
  78       <strong>Note:</strong> As of 13 January 2001 (wrt. to the code in the
  79       CVS HEAD), the above mechanism interferes badly with RULES pragmas
  80       defined over overloaded functions.  During instantiation, a new name is
  81       created for an overloaded function partially applied to the dictionaries
  82       needed in a usage position of that function.  As the rewrite rule,
  83       however, mentions the original overloaded name, it won't fire anymore
  84       -- unless later phases remove the intermediate definition again.  The
  85       latest CVS version of GHC has an option
  86       <code>-fno-method-sharing</code>, which avoids sharing instantiation
  87       stubs.  This is usually/often/sometimes sufficient to make the rules
  88       fire again.
  89
  90     <p><small>
  91 <!-- hhmts start -->
  92 Last modified: Wed Aug  8 19:24:09 EST 2001
  93 <!-- hhmts end -->
  94     </small>
  95   </body>
  96 </html>