doc/guide/src/AST.adoc

   1 AST
   2 ===
   3
   4 <:AST:> is the <:IntermediateLanguage:> produced by the <:FrontEnd:>
   5 and translated by <:Elaborate:> to <:CoreML:>.
   6
   7 == Description ==
   8
   9 The abstract syntax tree produced by the <:FrontEnd:>.
  10
  11 == Implementation ==
  12
  13 * <!ViewGitFile(mlton,master,mlton/ast/ast-programs.sig)>
  14 * <!ViewGitFile(mlton,master,mlton/ast/ast-programs.fun)>
  15 * <!ViewGitFile(mlton,master,mlton/ast/ast-modules.sig)>
  16 * <!ViewGitFile(mlton,master,mlton/ast/ast-modules.fun)>
  17 * <!ViewGitFile(mlton,master,mlton/ast/ast-core.sig)>
  18 * <!ViewGitFile(mlton,master,mlton/ast/ast-core.fun)>
  19 * <!ViewGitDir(mlton,master,mlton/ast)>
  20
  21 == Type Checking ==
  22
  23 The <:AST:> <:IntermediateLanguage:> has no independent type
  24 checker. Type inference is performed on an AST program as part of
  25 <:Elaborate:>.
  26
  27 == Details and Notes ==
  28
  29 === Source locations ===
  30
  31 MLton makes use of a relatively clean method for annotating the
  32 abstract syntax tree with source location information.  Every source
  33 program phrase is "wrapped" with the `WRAPPED` interface:
  34
  35 [source,sml]
  36 ----
  37 sys::[./bin/InclGitFile.py mlton master mlton/control/wrapped.sig 8:19]
  38 ----
  39
  40 The key idea is that `node'` is the type of an unannotated syntax
  41 phrase and `obj` is the type of its annotated counterpart. In the
  42 implementation, every `node'` is annotated with a `Region.t`
  43 (<!ViewGitFile(mlton,master,mlton/control/region.sig)>,
  44 <!ViewGitFile(mlton,master,mlton/control/region.sml)>), which describes the
  45 syntax phrase's left source position and right source position, where
  46 `SourcePos.t` (<!ViewGitFile(mlton,master,mlton/control/source-pos.sig)>,
  47 <!ViewGitFile(mlton,master,mlton/control/source-pos.sml)>) denotes a
  48 particular file, line, and column.  A typical use of the `WRAPPED`
  49 interface is illustrated by the following code:
  50
  51 [source,sml]
  52 ----
  53 sys::[./bin/InclGitFile.py mlton master mlton/ast/ast-core.sig 46:65]
  54 ----
  55
  56 Thus, AST nodes are cleanly separated from source locations.  By way
  57 of contrast, consider the approach taken by <:SMLNJ:SML/NJ> (and also
  58 by the <:CKitLibrary:CKit Library>).  Each datatype denoting a syntax
  59 phrase dedicates a special constructor for annotating source
  60 locations:
  61 [source,sml]
  62 -----
  63 datatype pat = WildPat                             (* empty pattern *)
  64              | AppPat of {constr:pat,argument:pat} (* application *)
  65              | MarkPat of pat * region             (* mark a pattern *)
  66 ----
  67
  68 The main drawback of this approach is that static type checking is not
  69 sufficient to guarantee that the AST emitted from the front-end is
  70 properly annotated.