doc/guide/src/MatchCompile.adoc

   1 MatchCompile
   2 ============
   3
   4 <:MatchCompile:> is a translation pass, agnostic in the
   5 <:IntermediateLanguage:>s between which it translates.
   6
   7 == Description ==
   8
   9 <:MatchCompilation:Match compilation> converts a case expression with
  10 nested patterns into a case expression with flat patterns.
  11
  12 == Implementation ==
  13
  14 * <!ViewGitFile(mlton,master,mlton/match-compile/match-compile.sig)>
  15 * <!ViewGitFile(mlton,master,mlton/match-compile/match-compile.fun)>
  16
  17 == Details and Notes ==
  18
  19 [source,sml]
  20 ----
  21 val matchCompile:
  22    {caseType: Type.t, (* type of entire expression *)
  23     cases: (NestedPat.t * ((Var.t -> Var.t) -> Exp.t)) vector,
  24     conTycon: Con.t -> Tycon.t,
  25     region: Region.t,
  26     test: Var.t,
  27     testType: Type.t,
  28     tyconCons: Tycon.t -> {con: Con.t, hasArg: bool} vector}
  29    -> Exp.t * (unit -> ((Layout.t * {isOnlyExns: bool}) vector) vector)
  30 ----
  31
  32 `matchCompile` is complicated by the desire for modularity between the
  33 match compiler and its caller.  Its caller is responsible for building
  34 the right hand side of a rule `p => e`.  On the other hand, the match
  35 compiler is responsible for destructing the test and binding new
  36 variables to the components.  In order to connect the new variables
  37 created by the match compiler with the variables in the pattern `p`,
  38 the match compiler passes an environment back to its caller that maps
  39 each variable in `p` to the corresponding variable introduced by the
  40 match compiler.
  41
  42 The match compiler builds a tree of n-way case expressions by working
  43 from outside to inside and left to right in the patterns.  For example,
  44 [source,sml]
  45 ----
  46 case x of
  47   (_, C1 a) => e1
  48 | (C2 b, C3 c) => e2
  49 ----
  50 is translated to
  51 [source,sml]
  52 ----
  53 let
  54    fun f1 a = e1
  55    fun f2 (b, c) = e2
  56 in
  57   case x of
  58      (x1, x2) =>
  59        (case x1 of
  60           C2 b' => (case x2 of
  61                       C1 a' => f1 a'
  62                     | C3 c' => f2(b',c')
  63                     | _ => raise Match)
  64         | _ => (case x2 of
  65                   C1 a_ => f1 a_
  66                 | _ => raise Match))
  67 end
  68 ----
  69
  70 Here you can see the necessity of abstracting out the ride hand sides
  71 of the cases in order to avoid code duplication.  Right hand sides are
  72 always abstracted.  The simplifier cleans things up.  You can also see
  73 the new (primed) variables introduced by the match compiler and how
  74 the renaming works.  Finally, you can see how the match compiler
  75 introduces the necessary default clauses in order to make a match
  76 exhaustive, i.e. cover all the cases.
  77
  78 The match compiler uses `numCons` and `tyconCons` to determine
  79 the exhaustivity of matches against constructors.