Test Trac #9036
[ghc.git] / docs / comm / the-beast / data-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 - Data types and data constructors</title>
6 </head>
7
8 <body BGCOLOR="FFFFFF">
9 <h1>The GHC Commentary - Data types and data constructors</h1>
10 <p>
11
12 This chapter was thoroughly changed Feb 2003.
13
14 <h2>Data types</h2>
15
16 Consider the following data type declaration:
17
18 <pre>
19 data T a = MkT !(a,a) !(T a) | Nil
20
21 f x = case x of
22 MkT p q -> MkT p (q+1)
23 Nil -> Nil
24 </pre>
25 The user's source program mentions only the constructors <tt>MkT</tt>
26 and <tt>Nil</tt>. However, these constructors actually <em>do</em> something
27 in addition to building a data value. For a start, <tt>MkT</tt> evaluates
28 its arguments. Secondly, with the flag <tt>-funbox-strict-fields</tt> GHC
29 will flatten (or unbox) the strict fields. So we may imagine that there's the
30 <em>source</em> constructor <tt>MkT</tt> and the <em>representation</em> constructor
31 <tt>MkT</tt>, and things start to get pretty confusing.
32 <p>
33 GHC now generates three unique <tt>Name</tt>s for each data constructor:
34 <pre>
35 ---- OccName ------
36 String Name space Used for
37 ---------------------------------------------------------------------------
38 The "source data con" MkT DataName The DataCon itself
39 The "worker data con" MkT VarName Its worker Id
40 aka "representation data con"
41 The "wrapper data con" $WMkT VarName Its wrapper Id (optional)
42 </pre>
43 Recall that each occurrence name (OccName) is a pair of a string and a
44 name space (see <a href="names.html">The truth about names</a>), and
45 two OccNames are considered the same only if both components match.
46 That is what distinguishes the name of the name of the DataCon from
47 the name of its worker Id. To keep things unambiguous, in what
48 follows we'll write "MkT{d}" for the source data con, and "MkT{v}" for
49 the worker Id. (Indeed, when you dump stuff with "-ddumpXXX", if you
50 also add "-dppr-debug" you'll get stuff like "Foo {- d rMv -}". The
51 "d" part is the name space; the "rMv" is the unique key.)
52 <p>
53 Each of these three names gets a distinct unique key in GHC's name cache.
54
55 <h2>The life cycle of a data type</h2>
56
57 Suppose the Haskell source looks like this:
58 <pre>
59 data T a = MkT !(a,a) !Int | Nil
60
61 f x = case x of
62 Nil -> Nil
63 MkT p q -> MkT p (q+1)
64 </pre>
65 When the parser reads it in, it decides which name space each lexeme comes
66 from, thus:
67 <pre>
68 data T a = MkT{d} !(a,a) !Int | Nil{d}
69
70 f x = case x of
71 Nil{d} -> Nil{d}
72 MkT{d} p q -> MkT{d} p (q+1)
73 </pre>
74 Notice that in the Haskell source <em>all data contructors are named via the "source data con" MkT{d}</em>,
75 whether in pattern matching or in expressions.
76 <p>
77 In the translated source produced by the type checker (-ddump-tc), the program looks like this:
78 <pre>
79 f x = case x of
80 Nil{d} -> Nil{v}
81 MkT{d} p q -> $WMkT p (q+1)
82
83 </pre>
84 Notice that the type checker replaces the occurrence of MkT by the <em>wrapper</em>, but
85 the occurrence of Nil by the <em>worker</em>. Reason: Nil doesn't have a wrapper because there is
86 nothing to do in the wrapper (this is the vastly common case).
87 <p>
88 Though they are not printed out by "-ddump-tc", behind the scenes, there are
89 also the following: the data type declaration and the wrapper function for MkT.
90 <pre>
91 data T a = MkT{d} a a Int# | Nil{d}
92
93 $WMkT :: (a,a) -> T a -> T a
94 $WMkT p t = case p of
95 (a,b) -> seq t (MkT{v} a b t)
96 </pre>
97 Here, the <em>wrapper</em> <tt>$WMkT</tt> evaluates and takes apart the argument <tt>p</tt>,
98 evaluates the argument <tt>t</tt>, and builds a three-field data value
99 with the <em>worker</em> constructor <tt>MkT{v}</tt>. (There are more notes below
100 about the unboxing of strict fields.) The worker $WMkT is called an <em>implicit binding</em>,
101 because it's introduced implicitly by the data type declaration (record selectors
102 are also implicit bindings, for example). Implicit bindings are injected into the code
103 just before emitting code or External Core.
104 <p>
105 After desugaring into Core (-ddump-ds), the definition of <tt>f</tt> looks like this:
106 <pre>
107 f x = case x of
108 Nil{d} -> Nil{v}
109 MkT{d} a b r -> let { p = (a,b); q = I# r } in
110 $WMkT p (q+1)
111 </pre>
112 Notice the way that pattern matching has been desugared to take account of the fact
113 that the "real" data constructor MkT has three fields.
114 <p>
115 By the time the simplifier has had a go at it, <tt>f</tt> will be transformed to:
116 <pre>
117 f x = case x of
118 Nil{d} -> Nil{v}
119 MkT{d} a b r -> MkT{v} a b (r +# 1#)
120 </pre>
121 Which is highly cool.
122
123
124 <h2> The constructor wrapper functions </h2>
125
126 The wrapper functions are automatically generated by GHC, and are
127 really emitted into the result code (albeit only after CorePre; see
128 <tt>CorePrep.mkImplicitBinds</tt>).
129 The wrapper functions are inlined very
130 vigorously, so you will not see many occurrences of the wrapper
131 functions in an optimised program, but you may see some. For example,
132 if your Haskell source has
133 <pre>
134 map MkT xs
135 </pre>
136 then <tt>$WMkT</tt> will not be inlined (because it is not applied to anything).
137 That is why we generate real top-level bindings for the wrapper functions,
138 and generate code for them.
139
140
141 <h2> The constructor worker functions </h2>
142
143 Saturated applications of the constructor worker function MkT{v} are
144 treated specially by the code generator; they really do allocation.
145 However, we do want a single, shared, top-level definition for
146 top-level nullary constructors (like True and False). Furthermore,
147 what if the code generator encounters a non-saturated application of a
148 worker? E.g. <tt>(map Just xs)</tt>. We could declare that to be an
149 error (CorePrep should saturate them). But instead we currently
150 generate a top-level definition for each constructor worker, whether
151 nullary or not. It takes the form:
152 <pre>
153 MkT{v} = \ p q r -> MkT{v} p q r
154 </pre>
155 This is a real hack. The occurrence on the RHS is saturated, so the code generator (both the
156 one that generates abstract C and the byte-code generator) treats it as a special case and
157 allocates a MkT; it does not make a recursive call! So now there's a top-level curried
158 version of the worker which is available to anyone who wants it.
159 <p>
160 This strange definition is not emitted into External Core. Indeed, you might argue that
161 we should instead pass the list of <tt>TyCon</tt>s to the code generator and have it
162 generate magic bindings directly. As it stands, it's a real hack: see the code in
163 CorePrep.mkImplicitBinds.
164
165
166 <h2> External Core </h2>
167
168 When emitting External Core, we should see this for our running example:
169
170 <pre>
171 data T a = MkT a a Int# | Nil{d}
172
173 $WMkT :: (a,a) -> T a -> T a
174 $WMkT p t = case p of
175 (a,b) -> seq t (MkT a b t)
176
177 f x = case x of
178 Nil -> Nil
179 MkT a b r -> MkT a b (r +# 1#)
180 </pre>
181 Notice that it makes perfect sense as a program all by itself. Constructors
182 look like constructors (albeit not identical to the original Haskell ones).
183 <p>
184 When reading in External Core, the parser is careful to read it back in just
185 as it was before it was spat out, namely:
186 <pre>
187 data T a = MkT{d} a a Int# | Nil{d}
188
189 $WMkT :: (a,a) -> T a -> T a
190 $WMkT p t = case p of
191 (a,b) -> seq t (MkT{v} a b t)
192
193 f x = case x of
194 Nil{d} -> Nil{v}
195 MkT{d} a b r -> MkT{v} a b (r +# 1#)
196 </pre>
197
198
199 <h2> Unboxing strict fields </h2>
200
201 If GHC unboxes strict fields (as in the first argument of <tt>MkT</tt> above),
202 it also transforms
203 source-language case expressions. Suppose you write this in your Haskell source:
204 <pre>
205 case e of
206 MkT p t -> ..p..t..
207 </pre>
208 GHC will desugar this to the following Core code:
209 <pre>
210 case e of
211 MkT a b t -> let p = (a,b) in ..p..t..
212 </pre>
213 The local let-binding reboxes the pair because it may be mentioned in
214 the case alternative. This may well be a bad idea, which is why
215 <tt>-funbox-strict-fields</tt> is an experimental feature.
216 <p>
217 It's essential that when importing a type <tt>T</tt> defined in some
218 external module <tt>M</tt>, GHC knows what representation was used for
219 that type, and that in turn depends on whether module <tt>M</tt> was
220 compiled with <tt>-funbox-strict-fields</tt>. So when writing an
221 interface file, GHC therefore records with each data type whether its
222 strict fields (if any) should be unboxed.
223
224 <h2> Labels and info tables </h2>
225
226 <em>Quick rough notes: SLPJ March 2003</em>.
227 <p>
228 Every data constructor <tt>C</tt>has two info tables:
229 <ul>
230 <li> The static info table (label <tt>C_static_info</tt>), used for statically-allocated constructors.
231
232 <li> The dynamic info table (label <tt>C_con_info</tt>), used for dynamically-allocated constructors.
233 </ul>
234 Statically-allocated constructors are not moved by the garbage collector, and therefore have a different closure
235 type from dynamically-allocated constructors; hence they need
236 a distinct info table.
237 Both info tables share the same entry code, but since the entry code is phyiscally juxtaposed with the
238 info table, it must be duplicated (<tt>C_static_entry</tt> and <tt>C_con_entry</tt> respectively).
239
240 </body>
241 </html>
242