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 defintion 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 defintion 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