doc/guide/src/Elaborate.adoc

   1 Elaborate
   2 =========
   3
   4 <:Elaborate:> is a translation pass from the <:AST:>
   5 <:IntermediateLanguage:> to the <:CoreML:> <:IntermediateLanguage:>.
   6
   7 == Description ==
   8
   9 This pass performs type inference and type checking according to the
  10 <:DefinitionOfStandardML:Definition>.  It also defunctorizes the
  11 program, eliminating all module-level constructs.
  12
  13 == Implementation ==
  14
  15 * <!ViewGitFile(mlton,master,mlton/elaborate/elaborate.sig)>
  16 * <!ViewGitFile(mlton,master,mlton/elaborate/elaborate.fun)>
  17 * <!ViewGitFile(mlton,master,mlton/elaborate/elaborate-env.sig)>
  18 * <!ViewGitFile(mlton,master,mlton/elaborate/elaborate-env.fun)>
  19 * <!ViewGitFile(mlton,master,mlton/elaborate/elaborate-modules.sig)>
  20 * <!ViewGitFile(mlton,master,mlton/elaborate/elaborate-modules.fun)>
  21 * <!ViewGitFile(mlton,master,mlton/elaborate/elaborate-core.sig)>
  22 * <!ViewGitFile(mlton,master,mlton/elaborate/elaborate-core.fun)>
  23 * <!ViewGitDir(mlton,master,mlton/elaborate)>
  24
  25 == Details and Notes ==
  26
  27 At the modules level, the <:Elaborate:> pass:
  28
  29 * elaborates signatures with interfaces (see
  30 <!ViewGitFile(mlton,master,mlton/elaborate/interface.sig)> and
  31 <!ViewGitFile(mlton,master,mlton/elaborate/interface.fun)>)
  32 +
  33 The main trick is to use disjoint sets to efficiently handle sharing
  34 of tycons and of structures and then to copy signatures as dags rather
  35 than as trees.
  36
  37 * checks functors at the point of definition, using functor summaries
  38 to speed up checking of functor applications.
  39 +
  40 When a functor is first type checked, we keep track of the dummy
  41 argument structure and the dummy result structure, as well as all the
  42 tycons that were created while elaborating the body.  Then, if we
  43 later need to type check an application of the functor (as opposed to
  44 defunctorize an application), we pair up tycons in the dummy argument
  45 structure with the actual argument structure and then replace the
  46 dummy tycons with the actual tycons in the dummy result structure,
  47 yielding the actual result structure.  We also generate new tycons for
  48 all the tycons that we created while originally elaborating the body.
  49
  50 * handles opaque signature constraints.
  51 +
  52 This is implemented by building a dummy structure realized from the
  53 signature, just as we would for a functor argument when type checking
  54 a functor.  The dummy structure contains exactly the type information
  55 that is in the signature, which is what opacity requires.  We then
  56 replace the variables (and constructors) in the dummy structure with
  57 the corresponding variables (and constructors) from the actual
  58 structure so that the translation to <:CoreML:> uses the right stuff.
  59 For each tycon in the dummy structure, we keep track of the
  60 corresponding type structure in the actual structure.  This is used
  61 when producing the <:CoreML:> types (see `expandOpaque` in
  62 <!ViewGitFile(mlton,master,mlton/elaborate/type-env.sig)> and
  63 <!ViewGitFile(mlton,master,mlton/elaborate/type-env.fun)>).
  64 +
  65 Then, within each `structure` or `functor` body, for each declaration
  66 (`<dec>` in the <:StandardML:Standard ML> grammar), the <:Elaborate:>
  67 pass does three steps:
  68 +
  69 --
  70 1. <:ScopeInference:>
  71 2. {empty}
  72 ** <:PrecedenceParse:>
  73 ** `_{ex,im}port` expansion
  74 ** profiling insertion
  75 ** unification
  76 3. Overloaded {constant, function, record pattern} resolution
  77 --
  78
  79 === Defunctorization ===
  80
  81 The <:Elaborate:> pass performs a number of duties historically
  82 assigned to the <:Defunctorize:> pass.
  83
  84 As part of the <:Elaborate:> pass, all module level constructs
  85 (`open`, `signature`, `structure`, `functor`, long identifiers) are
  86 removed.  This works because the <:Elaborate:> pass assigns a unique
  87 name to every type and variable in the program.  This also allows the
  88 <:Elaborate:> pass to eliminate `local` declarations, which are purely
  89 for namespace management.
  90
  91
  92 == Examples ==
  93
  94 Here are a number of examples of elaboration.
  95
  96 * All variables bound in `val` declarations are renamed.
  97 +
  98 [source,sml]
  99 ----
 100 val x = 13
 101 val y = x
 102 ----
 103 +
 104 ----
 105 val x_0 = 13
 106 val y_0 = x_0
 107 ----
 108
 109 * All variables in `fun` declarations are renamed.
 110 +
 111 [source,sml]
 112 ----
 113 fun f x = g x
 114 and g y = f y
 115 ----
 116 +
 117 ----
 118 fun f_0 x_0 = g_0 x_0
 119 and g_0 y_0 = f_0 y_0
 120 ----
 121
 122 * Type abbreviations are removed, and the abbreviation is expanded
 123 wherever it is used.
 124 +
 125 [source,sml]
 126 ----
 127 type 'a u = int * 'a
 128 type 'b t = 'b u * real
 129 fun f (x : bool t) = x
 130 ----
 131 +
 132 ----
 133 fun f_0 (x_0 : (int * bool) * real) = x_0
 134 ----
 135
 136 * Exception declarations create a new constructor and rename the type.
 137 +
 138 [source,sml]
 139 ----
 140 type t = int
 141 exception E of t * real
 142 ----
 143 +
 144 ----
 145 exception E_0 of int * real
 146 ----
 147
 148 * The type and value constructors in datatype declarations are renamed.
 149 +
 150 [source,sml]
 151 ----
 152 datatype t = A of int | B of real * t
 153 ----
 154 +
 155 ----
 156 datatype t_0 = A_0 of int | B_0 of real * t_0
 157 ----
 158
 159 * Local declarations are moved to the top-level.  The environment
 160 keeps track of the variables in scope.
 161 +
 162 [source,sml]
 163 ----
 164 val x = 13
 165 local val x = 14
 166 in val y = x
 167 end
 168 val z = x
 169 ----
 170 +
 171 ----
 172 val x_0 = 13
 173 val x_1 = 14
 174 val y_0 = x_1
 175 val z_0 = x_0
 176 ----
 177
 178 * Structure declarations are eliminated, with all declarations moved
 179 to the top level.  Long identifiers are renamed.
 180 +
 181 [source,sml]
 182 ----
 183 structure S =
 184    struct
 185       type t = int
 186       val x : t = 13
 187    end
 188 val y : S.t = S.x
 189 ----
 190 +
 191 ----
 192 val x_0 : int = 13
 193 val y_0 : int = x_0
 194 ----
 195
 196 * Open declarations are eliminated.
 197 +
 198 [source,sml]
 199 ----
 200 val x = 13
 201 val y = 14
 202 structure S =
 203    struct
 204      val x = 15
 205    end
 206 open S
 207 val z = x + y
 208 ----
 209 +
 210 ----
 211 val x_0 = 13
 212 val y_0 = 14
 213 val x_1 = 15
 214 val z_0 = x_1 + y_0
 215 ----
 216
 217 * Functor declarations are eliminated, and the body of a functor is
 218 duplicated wherever the functor is applied.
 219 +
 220 [source,sml]
 221 ----
 222 functor F(val x : int) =
 223    struct
 224      val y = x
 225    end
 226 structure F1 = F(val x = 13)
 227 structure F2 = F(val x = 14)
 228 val z = F1.y + F2.y
 229 ----
 230 +
 231 ----
 232 val x_0 = 13
 233 val y_0 = x_0
 234 val x_1 = 14
 235 val y_1 = x_1
 236 val z_0 = y_0 + y_1
 237 ----
 238
 239 * Signature constraints are eliminated.  Note that signatures do
 240 affect how subsequent variables are renamed.
 241 +
 242 [source,sml]
 243 ----
 244 val y = 13
 245 structure S : sig
 246                  val x : int
 247               end =
 248    struct
 249       val x = 14
 250       val y = x
 251    end
 252 open S
 253 val z = x + y
 254 ----
 255 +
 256 ----
 257 val y_0 = 13
 258 val x_0 = 14
 259 val y_1 = x_0
 260 val z_0 = x_0 + y_0
 261 ----