Commit | Line | Data |
---|---|---|
7f918cf1 CE |
1 | <!DOCTYPE html>\r |
2 | <html lang="en">\r | |
3 | <head>\r | |
4 | <meta http-equiv="Content-Type" content="text/html; charset=UTF-8">\r | |
5 | <meta name="generator" content="AsciiDoc 8.6.9">\r | |
6 | <title>PolymorphicEquality</title>\r | |
7 | <link rel="stylesheet" href="./asciidoc.css" type="text/css">\r | |
8 | <link rel="stylesheet" href="./pygments.css" type="text/css">\r | |
9 | \r | |
10 | \r | |
11 | <script type="text/javascript" src="./asciidoc.js"></script>\r | |
12 | <script type="text/javascript">\r | |
13 | /*<![CDATA[*/\r | |
14 | asciidoc.install(2);\r | |
15 | /*]]>*/\r | |
16 | </script>\r | |
17 | <link rel="stylesheet" href="./mlton.css" type="text/css">\r | |
18 | </head>\r | |
19 | <body class="article">\r | |
20 | <div id="banner">\r | |
21 | <div id="banner-home">\r | |
22 | <a href="./Home">MLton 20180207</a>\r | |
23 | </div>\r | |
24 | </div>\r | |
25 | <div id="header">\r | |
26 | <h1>PolymorphicEquality</h1>\r | |
27 | <div id="toc"> | |
28 | <div id="toctitle">Table of Contents</div> | |
29 | <noscript><p><b>JavaScript must be enabled in your browser to display the table of contents.</b></p></noscript> | |
30 | </div>\r | |
31 | </div>\r | |
32 | <div id="content">\r | |
33 | <div id="preamble">\r | |
34 | <div class="sectionbody">\r | |
35 | <div class="paragraph"><p>Polymorphic equality is a built-in function in\r | |
36 | <a href="StandardML">Standard ML</a> that compares two values of the same type\r | |
37 | for equality. It is specified as</p></div>\r | |
38 | <div class="listingblock">\r | |
39 | <div class="content"><div class="highlight"><pre><span class="k">val</span><span class="w"> </span><span class="p">=</span><span class="w"> </span><span class="p">:</span><span class="w"> </span><span class="n">''a</span><span class="w"> </span><span class="n">*</span><span class="w"> </span><span class="n">''a</span><span class="w"> </span><span class="p">-></span><span class="w"> </span><span class="n">bool</span><span class="w"></span>\r | |
40 | </pre></div></div></div>\r | |
41 | <div class="paragraph"><p>The <span class="monospaced">''a</span> in the specification are\r | |
42 | <a href="EqualityTypeVariable">equality type variables</a>, and indicate that\r | |
43 | polymorphic equality can only be applied to values of an\r | |
44 | <a href="EqualityType">equality type</a>. It is not allowed in SML to rebind\r | |
45 | <span class="monospaced">=</span>, so a programmer is guaranteed that <span class="monospaced">=</span> always denotes polymorphic\r | |
46 | equality.</p></div>\r | |
47 | </div>\r | |
48 | </div>\r | |
49 | <div class="sect1">\r | |
50 | <h2 id="_equality_of_ground_types">Equality of ground types</h2>\r | |
51 | <div class="sectionbody">\r | |
52 | <div class="paragraph"><p>Ground types like <span class="monospaced">char</span>, <span class="monospaced">int</span>, and <span class="monospaced">word</span> may be compared (to values\r | |
53 | of the same type). For example, <span class="monospaced">13 = 14</span> is type correct and yields\r | |
54 | <span class="monospaced">false</span>.</p></div>\r | |
55 | </div>\r | |
56 | </div>\r | |
57 | <div class="sect1">\r | |
58 | <h2 id="_equality_of_reals">Equality of reals</h2>\r | |
59 | <div class="sectionbody">\r | |
60 | <div class="paragraph"><p>The one ground type that can not be compared is <span class="monospaced">real</span>. So,\r | |
61 | <span class="monospaced">13.0 = 14.0</span> is not type correct. One can use <span class="monospaced">Real.==</span> to compare\r | |
62 | reals for equality, but beware that this has different algebraic\r | |
63 | properties than polymorphic equality.</p></div>\r | |
64 | <div class="paragraph"><p>See <a href="http://standardml.org/Basis/real.html">http://standardml.org/Basis/real.html</a> for a discussion of why\r | |
65 | <span class="monospaced">real</span> is not an equality type.</p></div>\r | |
66 | </div>\r | |
67 | </div>\r | |
68 | <div class="sect1">\r | |
69 | <h2 id="_equality_of_functions">Equality of functions</h2>\r | |
70 | <div class="sectionbody">\r | |
71 | <div class="paragraph"><p>Comparison of functions is not allowed.</p></div>\r | |
72 | </div>\r | |
73 | </div>\r | |
74 | <div class="sect1">\r | |
75 | <h2 id="_equality_of_immutable_types">Equality of immutable types</h2>\r | |
76 | <div class="sectionbody">\r | |
77 | <div class="paragraph"><p>Polymorphic equality can be used on <a href="Immutable">immutable</a> values like\r | |
78 | tuples, records, lists, and vectors. For example,</p></div>\r | |
79 | <div class="listingblock">\r | |
80 | <div class="content monospaced">\r | |
81 | <pre>(1, 2, 3) = (4, 5, 6)</pre>\r | |
82 | </div></div>\r | |
83 | <div class="paragraph"><p>is a type-correct expression yielding <span class="monospaced">false</span>, while</p></div>\r | |
84 | <div class="listingblock">\r | |
85 | <div class="content monospaced">\r | |
86 | <pre>[1, 2, 3] = [1, 2, 3]</pre>\r | |
87 | </div></div>\r | |
88 | <div class="paragraph"><p>is type correct and yields <span class="monospaced">true</span>.</p></div>\r | |
89 | <div class="paragraph"><p>Equality on immutable values is computed by structure, which means\r | |
90 | that values are compared by recursively descending the data structure\r | |
91 | until ground types are reached, at which point the ground types are\r | |
92 | compared with primitive equality tests (like comparison of\r | |
93 | characters). So, the expression</p></div>\r | |
94 | <div class="listingblock">\r | |
95 | <div class="content monospaced">\r | |
96 | <pre>[1, 2, 3] = [1, 1 + 1, 1 + 1 + 1]</pre>\r | |
97 | </div></div>\r | |
98 | <div class="paragraph"><p>is guaranteed to yield <span class="monospaced">true</span>, even though the lists may occupy\r | |
99 | different locations in memory.</p></div>\r | |
100 | <div class="paragraph"><p>Because of structural equality, immutable values can only be compared\r | |
101 | if their components can be compared. For example, <span class="monospaced">[1, 2, 3]</span> can be\r | |
102 | compared, but <span class="monospaced">[1.0, 2.0, 3.0]</span> can not. The SML type system uses\r | |
103 | <a href="EqualityType">equality types</a> to ensure that structural equality is\r | |
104 | only applied to valid values.</p></div>\r | |
105 | </div>\r | |
106 | </div>\r | |
107 | <div class="sect1">\r | |
108 | <h2 id="_equality_of_mutable_values">Equality of mutable values</h2>\r | |
109 | <div class="sectionbody">\r | |
110 | <div class="paragraph"><p>In contrast to immutable values, polymorphic equality of\r | |
111 | <a href="Mutable">mutable</a> values (like ref cells and arrays) is performed by\r | |
112 | pointer comparison, not by structure. So, the expression</p></div>\r | |
113 | <div class="listingblock">\r | |
114 | <div class="content monospaced">\r | |
115 | <pre>ref 13 = ref 13</pre>\r | |
116 | </div></div>\r | |
117 | <div class="paragraph"><p>is guaranteed to yield <span class="monospaced">false</span>, even though the ref cells hold the\r | |
118 | same contents.</p></div>\r | |
119 | <div class="paragraph"><p>Because equality of mutable values is not structural, arrays and refs\r | |
120 | can be compared <em>even if their components are not equality types</em>.\r | |
121 | Hence, the following expression is type correct (and yields true).</p></div>\r | |
122 | <div class="listingblock">\r | |
123 | <div class="content"><div class="highlight"><pre><span class="k">let</span><span class="w"></span>\r | |
124 | <span class="w"> </span><span class="k">val</span><span class="w"> </span><span class="n">r</span><span class="w"> </span><span class="p">=</span><span class="w"> </span><span class="n">ref</span><span class="w"> </span><span class="mf">13.0</span><span class="w"></span>\r | |
125 | <span class="k">in</span><span class="w"></span>\r | |
126 | <span class="w"> </span><span class="n">r</span><span class="w"> </span><span class="p">=</span><span class="w"> </span><span class="n">r</span><span class="w"></span>\r | |
127 | <span class="k">end</span><span class="w"></span>\r | |
128 | </pre></div></div></div>\r | |
129 | </div>\r | |
130 | </div>\r | |
131 | <div class="sect1">\r | |
132 | <h2 id="_equality_of_datatypes">Equality of datatypes</h2>\r | |
133 | <div class="sectionbody">\r | |
134 | <div class="paragraph"><p>Polymorphic equality of datatypes is structural. Two values of the\r | |
135 | same datatype are equal if they are of the same <a href="Variant">variant</a> and\r | |
136 | if the <a href="Variant">variant</a>'s arguments are equal (recursively). So,\r | |
137 | with the datatype</p></div>\r | |
138 | <div class="listingblock">\r | |
139 | <div class="content"><div class="highlight"><pre><span class="k">datatype</span><span class="w"> </span><span class="n">t</span><span class="w"> </span><span class="p">=</span><span class="w"> </span><span class="n">A</span><span class="w"> </span><span class="p">|</span><span class="w"> </span><span class="n">B</span><span class="w"> </span><span class="k">of</span><span class="w"> </span><span class="n">t</span><span class="w"></span>\r | |
140 | </pre></div></div></div>\r | |
141 | <div class="paragraph"><p>then <span class="monospaced">B (B A) = B A</span> is type correct and yields <span class="monospaced">false</span>, while <span class="monospaced">A = A</span>\r | |
142 | and <span class="monospaced">B A = B A</span> yield <span class="monospaced">true</span>.</p></div>\r | |
143 | <div class="paragraph"><p>As polymorphic equality descends two values to compare them, it uses\r | |
144 | pointer equality whenever it reaches a mutable value. So, with the\r | |
145 | datatype</p></div>\r | |
146 | <div class="listingblock">\r | |
147 | <div class="content"><div class="highlight"><pre><span class="k">datatype</span><span class="w"> </span><span class="n">t</span><span class="w"> </span><span class="p">=</span><span class="w"> </span><span class="n">A</span><span class="w"> </span><span class="k">of</span><span class="w"> </span><span class="n">int</span><span class="w"> </span><span class="n">ref</span><span class="w"> </span><span class="p">|</span><span class="w"> </span><span class="p">...</span><span class="w"></span>\r | |
148 | </pre></div></div></div>\r | |
149 | <div class="paragraph"><p>then <span class="monospaced">A (ref 13) = A (ref 13)</span> is type correct and yields <span class="monospaced">false</span>,\r | |
150 | because the pointer equality on the two ref cells yields <span class="monospaced">false</span>.</p></div>\r | |
151 | <div class="paragraph"><p>One weakness of the SML type system is that datatypes do not inherit\r | |
152 | the special property of the <span class="monospaced">ref</span> and <span class="monospaced">array</span> type constructors that\r | |
153 | allows them to be compared regardless of their component type. For\r | |
154 | example, after declaring</p></div>\r | |
155 | <div class="listingblock">\r | |
156 | <div class="content"><div class="highlight"><pre><span class="k">datatype</span><span class="w"> </span><span class="n">'a</span><span class="w"> </span><span class="n">t</span><span class="w"> </span><span class="p">=</span><span class="w"> </span><span class="n">A</span><span class="w"> </span><span class="k">of</span><span class="w"> </span><span class="n">'a</span><span class="w"> </span><span class="n">ref</span><span class="w"></span>\r | |
157 | </pre></div></div></div>\r | |
158 | <div class="paragraph"><p>one might expect to be able to compare two values of type <span class="monospaced">real t</span>,\r | |
159 | because pointer comparison on a ref cell would suffice.\r | |
160 | Unfortunately, the type system can only express that a user-defined\r | |
161 | datatype <a href="AdmitsEquality">admits equality</a> or not. In this case, <span class="monospaced">t</span>\r | |
162 | admits equality, which means that <span class="monospaced">int t</span> can be compared but that\r | |
163 | <span class="monospaced">real t</span> can not. We can confirm this with the program</p></div>\r | |
164 | <div class="listingblock">\r | |
165 | <div class="content"><div class="highlight"><pre><span class="k">datatype</span><span class="w"> </span><span class="n">'a</span><span class="w"> </span><span class="n">t</span><span class="w"> </span><span class="p">=</span><span class="w"> </span><span class="n">A</span><span class="w"> </span><span class="k">of</span><span class="w"> </span><span class="n">'a</span><span class="w"> </span><span class="n">ref</span><span class="w"></span>\r | |
166 | <span class="k">fun</span><span class="w"> </span><span class="n">f</span><span class="w"> </span><span class="p">(</span><span class="n">x</span><span class="p">:</span><span class="w"> </span><span class="n">real</span><span class="w"> </span><span class="n">t</span><span class="p">,</span><span class="w"> </span><span class="n">y</span><span class="p">:</span><span class="w"> </span><span class="n">real</span><span class="w"> </span><span class="n">t</span><span class="p">)</span><span class="w"> </span><span class="p">=</span><span class="w"> </span><span class="n">x</span><span class="w"> </span><span class="p">=</span><span class="w"> </span><span class="n">y</span><span class="w"></span>\r | |
167 | </pre></div></div></div>\r | |
168 | <div class="paragraph"><p>on which MLton reports the following error.</p></div>\r | |
169 | <div class="listingblock">\r | |
170 | <div class="content monospaced">\r | |
171 | <pre>Error: z.sml 2.32-2.36.\r | |
172 | Function applied to incorrect argument.\r | |
173 | expects: [<equality>] t * [<equality>] t\r | |
174 | but got: [real] t * [real] t\r | |
175 | in: = (x, y)</pre>\r | |
176 | </div></div>\r | |
177 | </div>\r | |
178 | </div>\r | |
179 | <div class="sect1">\r | |
180 | <h2 id="_implementation">Implementation</h2>\r | |
181 | <div class="sectionbody">\r | |
182 | <div class="paragraph"><p>Polymorphic equality is implemented by recursively descending the two\r | |
183 | values being compared, stopping as soon as they are determined to be\r | |
184 | unequal, or exploring the entire values to determine that they are\r | |
185 | equal. Hence, polymorphic equality can take time proportional to the\r | |
186 | size of the smaller value.</p></div>\r | |
187 | <div class="paragraph"><p>MLton uses some optimizations to improve performance.</p></div>\r | |
188 | <div class="ulist"><ul>\r | |
189 | <li>\r | |
190 | <p>\r | |
191 | When computing structural equality, first do a pointer comparison.\r | |
192 | If the comparison yields <span class="monospaced">true</span>, then stop and return <span class="monospaced">true</span>, since\r | |
193 | the structural comparison is guaranteed to do so. If the pointer\r | |
194 | comparison fails, then recursively descend the values.\r | |
195 | </p>\r | |
196 | </li>\r | |
197 | <li>\r | |
198 | <p>\r | |
199 | If a datatype is an enum (e.g. <span class="monospaced">datatype t = A | B | C</span>), then a\r | |
200 | single comparison suffices to compare values of the datatype. No case\r | |
201 | dispatch is required to determine whether the two values are of the\r | |
202 | same <a href="Variant">variant</a>.\r | |
203 | </p>\r | |
204 | </li>\r | |
205 | <li>\r | |
206 | <p>\r | |
207 | When comparing a known constant non-value-carrying\r | |
208 | <a href="Variant">variant</a>, use a single comparison. For example, the\r | |
209 | following code will compile into a single comparison for <span class="monospaced">A = x</span>.\r | |
210 | </p>\r | |
211 | <div class="listingblock">\r | |
212 | <div class="content"><div class="highlight"><pre><span class="k">datatype</span><span class="w"> </span><span class="n">t</span><span class="w"> </span><span class="p">=</span><span class="w"> </span><span class="n">A</span><span class="w"> </span><span class="p">|</span><span class="w"> </span><span class="n">B</span><span class="w"> </span><span class="p">|</span><span class="w"> </span><span class="n">C</span><span class="w"> </span><span class="k">of</span><span class="w"> </span><span class="p">...</span><span class="w"></span>\r | |
213 | <span class="k">fun</span><span class="w"> </span><span class="n">f</span><span class="w"> </span><span class="n">x</span><span class="w"> </span><span class="p">=</span><span class="w"> </span><span class="p">...</span><span class="w"> </span><span class="k">if</span><span class="w"> </span><span class="n">A</span><span class="w"> </span><span class="p">=</span><span class="w"> </span><span class="n">x</span><span class="w"> </span><span class="k">then</span><span class="w"> </span><span class="p">...</span><span class="w"></span>\r | |
214 | </pre></div></div></div>\r | |
215 | </li>\r | |
216 | <li>\r | |
217 | <p>\r | |
218 | When comparing a small constant <span class="monospaced">IntInf.int</span> to another\r | |
219 | <span class="monospaced">IntInf.int</span>, use a single comparison against the constant. No case\r | |
220 | dispatch is required.\r | |
221 | </p>\r | |
222 | </li>\r | |
223 | </ul></div>\r | |
224 | </div>\r | |
225 | </div>\r | |
226 | <div class="sect1">\r | |
227 | <h2 id="_also_see">Also see</h2>\r | |
228 | <div class="sectionbody">\r | |
229 | <div class="ulist"><ul>\r | |
230 | <li>\r | |
231 | <p>\r | |
232 | <a href="AdmitsEquality">AdmitsEquality</a>\r | |
233 | </p>\r | |
234 | </li>\r | |
235 | <li>\r | |
236 | <p>\r | |
237 | <a href="EqualityType">EqualityType</a>\r | |
238 | </p>\r | |
239 | </li>\r | |
240 | <li>\r | |
241 | <p>\r | |
242 | <a href="EqualityTypeVariable">EqualityTypeVariable</a>\r | |
243 | </p>\r | |
244 | </li>\r | |
245 | </ul></div>\r | |
246 | </div>\r | |
247 | </div>\r | |
248 | </div>\r | |
249 | <div id="footnotes"><hr></div>\r | |
250 | <div id="footer">\r | |
251 | <div id="footer-text">\r | |
252 | </div>\r | |
253 | <div id="footer-badges">\r | |
254 | </div>\r | |
255 | </div>\r | |
256 | </body>\r | |
257 | </html>\r |