Test Trac #9036
[ghc.git] / 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>