Commit | Line | Data |
---|---|---|
7f918cf1 CE |
1 | Monomorphise |
2 | ============ | |
3 | ||
4 | <:Monomorphise:> is a translation pass from the <:XML:> | |
5 | <:IntermediateLanguage:> to the <:SXML:> <:IntermediateLanguage:>. | |
6 | ||
7 | == Description == | |
8 | ||
9 | Monomorphisation eliminates polymorphic values and datatype | |
10 | declarations by duplicating them for each type at which they are used. | |
11 | ||
12 | Consider the following <:XML:> program. | |
13 | [source,sml] | |
14 | ---- | |
15 | datatype 'a t = T of 'a | |
16 | fun 'a f (x: 'a) = T x | |
17 | val a = f 1 | |
18 | val b = f 2 | |
19 | val z = f (3, 4) | |
20 | ---- | |
21 | ||
22 | The result of monomorphising this program is the following <:SXML:> program: | |
23 | [source,sml] | |
24 | ---- | |
25 | datatype t1 = T1 of int | |
26 | datatype t2 = T2 of int * int | |
27 | fun f1 (x: int) = T1 x | |
28 | fun f2 (x: int * int) = T2 x | |
29 | val a = f1 1 | |
30 | val b = f1 2 | |
31 | val z = f2 (3, 4) | |
32 | ---- | |
33 | ||
34 | == Implementation == | |
35 | ||
36 | * <!ViewGitFile(mlton,master,mlton/xml/monomorphise.sig)> | |
37 | * <!ViewGitFile(mlton,master,mlton/xml/monomorphise.fun)> | |
38 | ||
39 | == Details and Notes == | |
40 | ||
41 | The monomorphiser works by making one pass over the entire program. | |
42 | On the way down, it creates a cache for each variable declared in a | |
43 | polymorphic declaration that maps a lists of type arguments to a new | |
44 | variable name. At a variable reference, it consults the cache (based | |
45 | on the types the variable is applied to). If there is already an | |
46 | entry in the cache, it is used. If not, a new entry is created. On | |
47 | the way up, the monomorphiser duplicates a variable declaration for | |
48 | each entry in the cache. | |
49 | ||
50 | As with variables, the monomorphiser records all of the type at which | |
51 | constructors are used. After the entire program is processed, the | |
52 | monomorphiser duplicates each datatype declaration and its associated | |
53 | constructors. | |
54 | ||
55 | The monomorphiser duplicates all of the functions declared in a | |
56 | `fun` declaration as a unit. Consider the following program | |
57 | [source,sml] | |
58 | ---- | |
59 | fun 'a f (x: 'a) = g x | |
60 | and g (y: 'a) = f y | |
61 | val a = f 13 | |
62 | val b = g 14 | |
63 | val c = f (1, 2) | |
64 | ---- | |
65 | ||
66 | and its monomorphisation | |
67 | ||
68 | [source,sml] | |
69 | ---- | |
70 | fun f1 (x: int) = g1 x | |
71 | and g1 (y: int) = f1 y | |
72 | fun f2 (x : int * int) = g2 x | |
73 | and g2 (y : int * int) = f2 y | |
74 | val a = f1 13 | |
75 | val b = g1 14 | |
76 | val c = f2 (1, 2) | |
77 | ---- | |
78 | ||
79 | == Pathological datatype declarations == | |
80 | ||
81 | SML allows a pathological polymorphic datatype declaration in which | |
82 | recursive uses of the defined type constructor are applied to | |
83 | different type arguments than the definition. This has been | |
84 | disallowed by others on type theoretic grounds. A canonical example | |
85 | is the following. | |
86 | [source,sml] | |
87 | ---- | |
88 | datatype 'a t = A of 'a | B of ('a * 'a) t | |
89 | val z : int t = B (B (A ((1, 2), (3, 4)))) | |
90 | ---- | |
91 | ||
92 | The presence of the recursion in the datatype declaration might appear | |
93 | to cause the need for the monomorphiser to create an infinite number | |
94 | of types. However, due to the absence of polymorphic recursion in | |
95 | SML, there are in fact only a finite number of instances of such types | |
96 | in any given program. The monomorphiser translates the above program | |
97 | to the following one. | |
98 | [source,sml] | |
99 | ---- | |
100 | datatype t1 = B1 of t2 | |
101 | datatype t2 = B2 of t3 | |
102 | datatype t3 = A3 of (int * int) * (int * int) | |
103 | val z : int t = B1 (B2 (A3 ((1, 2), (3, 4)))) | |
104 | ---- | |
105 | ||
106 | It is crucial that the monomorphiser be allowed to drop unused | |
107 | constructors from datatype declarations in order for the translation | |
108 | to terminate. |