docs/comm/the-beast/types.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 - Hybrid Types</title>
   6   </head>
   7
   8   <body BGCOLOR="FFFFFF">
   9     <h1>The GHC Commentary - Hybrid Types</h1>
  10     <p>
  11       GHC essentially supports two type systems: (1) the <em>source type
  12         system</em> (which is a heavily extended version of the type system of
  13       Haskell 98) and (2) the <em>Core type system,</em> which is the type system
  14       used by the intermediate language (see also <a
  15       href="desugar.html">Sugar Free: From Haskell To Core</a>).
  16     </p>
  17     <p>
  18       During parsing and renaming, type information is represented in a form
  19       that is very close to Haskell's concrete syntax; it is defined by
  20       <code>HsTypes.HsType</code>.  In addition, type, class, and instance
  21       declarations are maintained in their source form as defined in the
  22       module <code>HsDecl</code>.  The situation changes during type checking,
  23       where types are translated into a second representation, which is
  24       defined in the module <code>types/TypeRep.lhs</code>, as type
  25       <code>Type</code>.  This second representation is peculiar in that it is
  26       a hybrid between the source representation of types and the Core
  27       representation of types.  Using functions, such as
  28       <code>Type.coreView</code> and <code>Type.deepCoreView</code>, a value
  29       of type <code>Type</code> exhibits its Core representation.  On the
  30       other hand, pretty printing a <code>Type</code> with
  31       <code>TypeRep.pprType</code> yields the type's source representation.
  32     </p>
  33     <p>
  34       In fact, the <a href="typecheck.html">type checker</a> maintains type
  35       environments based on <code>Type</code>, but needs to perform type
  36       checking on source-level types.  As a result, we have functions
  37       <code>Type.tcEqType</code> and <code>Type.tcCmpType</code>, which
  38       compare types based on their source representation, as well as the
  39       function <code>coreEqType</code>, which compares them based on their
  40       core representation.  The latter is needed during type checking of Core
  41       (as performed by the functions in the module
  42       <code>coreSyn/CoreLint.lhs</code>).
  43     </p>
  44
  45     <h2>Type Synonyms</h2>
  46     <p>
  47       Type synonyms in Haskell are essentially a form of macro definitions on
  48       the type level.  For example, when the type checker compares two type
  49       terms, synonyms are always compared in their expanded form.  However, to
  50       produce good error messages, we like to avoid expanding type synonyms
  51       during pretty printing.  Hence, <code>Type</code> has a variant
  52       <code>NoteTy TyNote Type</code>, where
  53     </p>
  54     <blockquote>
  55       <pre>
  56 data TyNote
  57   = FTVNote TyVarSet    -- The free type variables of the noted expression
  58
  59   | SynNote Type        -- Used for type synonyms
  60                         -- The Type is always a TyConApp, and is the un-expanded form.
  61                         -- The type to which the note is attached is the expanded form.</pre>
  62     </blockquote>
  63     <p>
  64       In other words, a <code>NoteTy</code> represents the expanded form of a
  65       type synonym together with a note stating its source form.
  66     </p>
  67
  68     <h3>Creating Representation Types of Synonyms</h3>
  69     <p>
  70       During translation from <code>HsType</code> to <code>Type</code> the
  71       function <code>Type.mkSynTy</code> is used to construct representations
  72       of applications of type synonyms.  It creates a <code>NoteTy</code> node
  73       if the synonym is applied to a sufficient number of arguments;
  74       otherwise, it builds a simple <code>TyConApp</code> and leaves it to
  75       <code>TcMType.checkValidType</code> to pick up invalid unsaturated
  76       synonym applications.  While creating a <code>NoteTy</code>,
  77       <code>mkSynTy</code> also expands the synonym by substituting the type
  78       arguments for the parameters of the synonym definition, using
  79       <code>Type.substTyWith</code>.
  80     </p>
  81     <p>
  82       The function <code>mkSynTy</code> is used indirectly via
  83       <code>mkGenTyConApp</code>, <code>mkAppTy</code>, and
  84       <code>mkAppTy</code>, which construct type representations involving
  85       type applications.  The function <code>mkSynTy</code> is also used
  86       directly during type checking interface files; this is for tedious
  87       reasons to do with forall hoisting - see the comment at
  88       <code>TcIface.mkIfTcApp</code>.
  89     </p>
  90
  91     <h2>Newtypes</h2>
  92     <p>
  93       Data types declared by a <code>newtype</code> declarations constitute new
  94       type constructors---i.e., they are not just type macros, but introduce
  95       new type names.  However, provided that a newtype is not recursive, we
  96       still want to implement it by its representation type.  GHC realises this
  97       by providing two flavours of type equality: (1) <code>tcEqType</code> is
  98       source-level type equality, which compares newtypes and
  99       <code>PredType</code>s by name, and (2) <code>coreEqType</code> compares
 100       them structurally (by using <code>deepCoreView</code> to expand the
 101       representation before comparing).  The function
 102       <code>deepCoreView</code> (via <code>coreView</code>) invokes
 103       <code>expandNewTcApp</code> for every type constructor application
 104       (<code>TyConApp</code>) to determine whether we are looking at a newtype
 105       application that needs to be expanded to its representation type.
 106     </p>
 107
 108     <h2>Predicates</h2>
 109     <p>
 110       The dictionary translation of type classes, translates each predicate in
 111       a type context of a type signature into an additional argument, which
 112       carries a dictionary with the functions overloaded by the corresponding
 113       class.  The <code>Type</code> data type has a special variant
 114       <code>PredTy PredType</code> for predicates, where
 115     </p>
 116     <blockquote>
 117       <pre>
 118 data PredType
 119   = ClassP Class [Type]         -- Class predicate
 120   | IParam (IPName Name) Type   -- Implicit parameter</pre>
 121     </blockquote>
 122     <p>
 123       These types need to be handled as source type during type checking, but
 124       turn into their representations when inspected through
 125       <code>coreView</code>.  The representation is determined by
 126       <code>Type.predTypeRep</code>.
 127     </p>
 128
 129     <h2>Representation of Type Constructors</h2>
 130     <p>
 131       Type constructor applications are represented in <code>Type</code> by
 132       the variant <code>TyConApp :: TyCon -> [Type] -> Type</code>.  The first
 133       argument to <code>TyConApp</code>, namely <code>TyCon.TyCon</code>,
 134       distinguishes between function type constructors (variant
 135       <code>FunTyCon</code>) and algebraic type constructors (variant
 136       <code>AlgTyCon</code>), which arise from data and newtype declarations.
 137       The variant <code>AlgTyCon</code> contains all the information available
 138       from the data/newtype declaration as well as derived information, such
 139       as the <code>Unique</code> and argument variance information.  This
 140       includes a field <code>algTcRhs :: AlgTyConRhs</code>, where
 141       <code>AlgTyConRhs</code> distinguishes three kinds of algebraic data
 142       type declarations: (1) declarations that have been exported abstractly,
 143       (2) <code>data</code> declarations, and (3) <code>newtype</code>
 144       declarations.  The last two both include their original right hand side;
 145       in addition, the third variant also caches the "ultimate" representation
 146       type, which is the right hand side after expanding all type synonyms and
 147       non-recursive newtypes.
 148     </p>
 149     <p>
 150       Both data and newtype declarations refer to their data constructors
 151       represented as <code>DataCon.DataCon</code>, which include all details
 152       of their signature (as derived from the original declaration) as well
 153       information for code generation, such as their tag value.
 154     </p>
 155
 156     <h2>Representation of Classes and Instances</h2>
 157     <p>
 158       Class declarations turn into values of type <code>Class.Class</code>.
 159       They represent methods as the <code>Id</code>s of the dictionary
 160       selector functions.  Similar selector functions are available for
 161       superclass dictionaries.
 162     </p>
 163     <p>
 164       Instance declarations turn into values of type
 165       <code>InstEnv.Instance</code>, which in interface files are represented
 166       as <code>IfaceSyn.IfaceInst</code>.  Moreover, the type
 167       <code>InstEnv.InstEnv</code>, which is a synonym for <code>UniqFM
 168       ClsInstEnv</code>, provides a mapping of classes to their
 169       instances---<code>ClsInstEnv</code> is essentially a list of instance
 170       declarations.
 171     </p>
 172
 173     <p><small>
 174 <!-- hhmts start -->
 175 Last modified: Sun Jun 19 13:07:22 EST 2005
 176 <!-- hhmts end -->
 177     </small></p>
 178   </body>
 179 </html>