Commit | Line | Data |
---|---|---|
7f918cf1 CE |
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. |