doc/guide/localhost/UniversalType

   1 <!DOCTYPE html>
   2 <html lang="en">
   3 <head>
   4 <meta http-equiv="Content-Type" content="text/html; charset=UTF-8">
   5 <meta name="generator" content="AsciiDoc 8.6.9">
   6 <title>UniversalType</title>
   7 <link rel="stylesheet" href="./asciidoc.css" type="text/css">
   8 <link rel="stylesheet" href="./pygments.css" type="text/css">
   9
  10
  11 <script type="text/javascript" src="./asciidoc.js"></script>
  12 <script type="text/javascript">
  13 /*<![CDATA[*/
  14 asciidoc.install();
  15 /*]]>*/
  16 </script>
  17 <link rel="stylesheet" href="./mlton.css" type="text/css">
  18 </head>
  19 <body class="article">
  20 <div id="banner">
  21 <div id="banner-home">
  22 <a href="./Home">MLton 20180207</a>
  23 </div>
  24 </div>
  25 <div id="header">
  26 <h1>UniversalType</h1>
  27 </div>
  28 <div id="content">
  29 <div id="preamble">
  30 <div class="sectionbody">
  31 <div class="paragraph"><p>A universal type is a type into which all other types can be embedded.
  32 Here&#8217;s a <a href="StandardML">Standard ML</a> signature for a universal type.</p></div>
  33 <div class="listingblock">
  34 <div class="content"><div class="highlight"><pre><span class="k">signature</span><span class="w"> </span><span class="n">UNIVERSAL_TYPE</span><span class="w"> </span><span class="p">=</span><span class="w"></span>
  35 <span class="w">   </span><span class="k">sig</span><span class="w"></span>
  36 <span class="w">      </span><span class="k">type</span><span class="w"> </span><span class="n">t</span><span class="w"></span>
  37
  38 <span class="w">      </span><span class="k">val</span><span class="w"> </span><span class="n">embed</span><span class="p">:</span><span class="w"> </span><span class="n">unit</span><span class="w"> </span><span class="p">-&gt;</span><span class="w"> </span><span class="p">(</span><span class="n">&#39;a</span><span class="w"> </span><span class="p">-&gt;</span><span class="w"> </span><span class="n">t</span><span class="p">)</span><span class="w"> </span><span class="n">*</span><span class="w"> </span><span class="p">(</span><span class="n">t</span><span class="w"> </span><span class="p">-&gt;</span><span class="w"> </span><span class="n">&#39;a</span><span class="w"> </span><span class="n">option</span><span class="p">)</span><span class="w"></span>
  39 <span class="w">   </span><span class="k">end</span><span class="w"></span>
  40 </pre></div></div></div>
  41 <div class="paragraph"><p>The idea is that <span class="monospaced">type t</span> is the universal type and that each call to
  42 <span class="monospaced">embed</span> returns a new pair of functions <span class="monospaced">(inject, project)</span>, where
  43 <span class="monospaced">inject</span> embeds a value into the universal type and <span class="monospaced">project</span> extracts
  44 the value from the universal type.  A pair <span class="monospaced">(inject, project)</span>
  45 returned by <span class="monospaced">embed</span> works together in that <span class="monospaced">project u</span> will return
  46 <span class="monospaced">SOME v</span> if and only if <span class="monospaced">u</span> was created by <span class="monospaced">inject v</span>.  If <span class="monospaced">u</span> was
  47 created by a different function <span class="monospaced">inject'</span>, then <span class="monospaced">project</span> returns
  48 <span class="monospaced">NONE</span>.</p></div>
  49 <div class="paragraph"><p>Here&#8217;s an example embedding integers and reals into a universal type.</p></div>
  50 <div class="listingblock">
  51 <div class="content"><div class="highlight"><pre><span class="k">functor</span><span class="w"> </span><span class="n">Test</span><span class="w"> </span><span class="p">(</span><span class="n">U</span><span class="p">:</span><span class="w"> </span><span class="n">UNIVERSAL_TYPE</span><span class="p">):</span><span class="w"> </span><span class="k">sig</span><span class="w"> </span><span class="k">end</span><span class="w"> </span><span class="p">=</span><span class="w"></span>
  52 <span class="w">   </span><span class="k">struct</span><span class="w"></span>
  53 <span class="w">      </span><span class="k">val</span><span class="w"> </span><span class="p">(</span><span class="n">intIn</span><span class="p">:</span><span class="w"> </span><span class="n">int</span><span class="w"> </span><span class="p">-&gt;</span><span class="w"> </span><span class="n">U</span><span class="p">.</span><span class="n">t</span><span class="p">,</span><span class="w"> </span><span class="n">intOut</span><span class="p">)</span><span class="w"> </span><span class="p">=</span><span class="w"> </span><span class="n">U</span><span class="p">.</span><span class="n">embed</span><span class="w"> </span><span class="p">()</span><span class="w"></span>
  54 <span class="w">      </span><span class="k">val</span><span class="w"> </span><span class="n">r</span><span class="p">:</span><span class="w"> </span><span class="n">U</span><span class="p">.</span><span class="n">t</span><span class="w"> </span><span class="n">ref</span><span class="w"> </span><span class="p">=</span><span class="w"> </span><span class="n">ref</span><span class="w"> </span><span class="p">(</span><span class="n">intIn</span><span class="w"> </span><span class="mi">13</span><span class="p">)</span><span class="w"></span>
  55 <span class="w">      </span><span class="k">val</span><span class="w"> </span><span class="n">s1</span><span class="w"> </span><span class="p">=</span><span class="w"></span>
  56 <span class="w">         </span><span class="k">case</span><span class="w"> </span><span class="n">intOut</span><span class="w"> </span><span class="p">(</span><span class="n">!r</span><span class="p">)</span><span class="w"> </span><span class="k">of</span><span class="w"></span>
  57 <span class="w">            </span><span class="n">NONE</span><span class="w"> </span><span class="p">=&gt;</span><span class="w"> </span><span class="s">&quot;NONE&quot;</span><span class="w"></span>
  58 <span class="w">          </span><span class="p">|</span><span class="w"> </span><span class="n">SOME</span><span class="w"> </span><span class="n">i</span><span class="w"> </span><span class="p">=&gt;</span><span class="w"> </span><span class="n">Int</span><span class="p">.</span><span class="n">toString</span><span class="w"> </span><span class="n">i</span><span class="w"></span>
  59 <span class="w">      </span><span class="k">val</span><span class="w"> </span><span class="p">(</span><span class="n">realIn</span><span class="p">:</span><span class="w"> </span><span class="n">real</span><span class="w"> </span><span class="p">-&gt;</span><span class="w"> </span><span class="n">U</span><span class="p">.</span><span class="n">t</span><span class="p">,</span><span class="w"> </span><span class="n">realOut</span><span class="p">)</span><span class="w"> </span><span class="p">=</span><span class="w"> </span><span class="n">U</span><span class="p">.</span><span class="n">embed</span><span class="w"> </span><span class="p">()</span><span class="w"></span>
  60 <span class="w">      </span><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">r</span><span class="w"> </span><span class="n">:=</span><span class="w"> </span><span class="n">realIn</span><span class="w"> </span><span class="mf">13.0</span><span class="w"></span>
  61 <span class="w">      </span><span class="k">val</span><span class="w"> </span><span class="n">s2</span><span class="w"> </span><span class="p">=</span><span class="w"></span>
  62 <span class="w">         </span><span class="k">case</span><span class="w"> </span><span class="n">intOut</span><span class="w"> </span><span class="p">(</span><span class="n">!r</span><span class="p">)</span><span class="w"> </span><span class="k">of</span><span class="w"></span>
  63 <span class="w">            </span><span class="n">NONE</span><span class="w"> </span><span class="p">=&gt;</span><span class="w"> </span><span class="s">&quot;NONE&quot;</span><span class="w"></span>
  64 <span class="w">          </span><span class="p">|</span><span class="w"> </span><span class="n">SOME</span><span class="w"> </span><span class="n">i</span><span class="w"> </span><span class="p">=&gt;</span><span class="w"> </span><span class="n">Int</span><span class="p">.</span><span class="n">toString</span><span class="w"> </span><span class="n">i</span><span class="w"></span>
  65 <span class="w">      </span><span class="k">val</span><span class="w"> </span><span class="n">s3</span><span class="w"> </span><span class="p">=</span><span class="w"></span>
  66 <span class="w">         </span><span class="k">case</span><span class="w"> </span><span class="n">realOut</span><span class="w"> </span><span class="p">(</span><span class="n">!r</span><span class="p">)</span><span class="w"> </span><span class="k">of</span><span class="w"></span>
  67 <span class="w">            </span><span class="n">NONE</span><span class="w"> </span><span class="p">=&gt;</span><span class="w"> </span><span class="s">&quot;NONE&quot;</span><span class="w"></span>
  68 <span class="w">          </span><span class="p">|</span><span class="w"> </span><span class="n">SOME</span><span class="w"> </span><span class="n">x</span><span class="w"> </span><span class="p">=&gt;</span><span class="w"> </span><span class="n">Real</span><span class="p">.</span><span class="n">toString</span><span class="w"> </span><span class="n">x</span><span class="w"></span>
  69 <span class="w">      </span><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">print</span><span class="w"> </span><span class="p">(</span><span class="n">concat</span><span class="w"> </span><span class="p">[</span><span class="n">s1</span><span class="p">,</span><span class="w"> </span><span class="s">&quot; &quot;</span><span class="p">,</span><span class="w"> </span><span class="n">s2</span><span class="p">,</span><span class="w"> </span><span class="s">&quot; &quot;</span><span class="p">,</span><span class="w"> </span><span class="n">s3</span><span class="p">,</span><span class="w"> </span><span class="s">&quot;</span><span class="se">\n</span><span class="s">&quot;</span><span class="p">])</span><span class="w"></span>
  70 <span class="w">   </span><span class="k">end</span><span class="w"></span>
  71 </pre></div></div></div>
  72 <div class="paragraph"><p>Applying <span class="monospaced">Test</span> to an appropriate implementation will print</p></div>
  73 <div class="listingblock">
  74 <div class="content monospaced">
  75 <pre>13 NONE 13.0</pre>
  76 </div></div>
  77 <div class="paragraph"><p>Note that two different calls to embed on the same type return
  78 different embeddings.</p></div>
  79 <div class="paragraph"><p>Standard ML does not have explicit support for universal types;
  80 however, there are at least two ways to implement them.</p></div>
  81 </div>
  82 </div>
  83 <div class="sect1">
  84 <h2 id="_implementation_using_exceptions">Implementation Using Exceptions</h2>
  85 <div class="sectionbody">
  86 <div class="paragraph"><p>While the intended use of SML exceptions is for exception handling, an
  87 accidental feature of their design is that the <span class="monospaced">exn</span> type is a
  88 universal type.  The implementation relies on being able to declare
  89 exceptions locally to a function and on the fact that exceptions are
  90 <a href="GenerativeException">generative</a>.</p></div>
  91 <div class="listingblock">
  92 <div class="content"><div class="highlight"><pre><span class="k">structure</span><span class="w"> </span><span class="n">U</span><span class="p">:&gt;</span><span class="w"> </span><span class="n">UNIVERSAL_TYPE</span><span class="w"> </span><span class="p">=</span><span class="w"></span>
  93 <span class="w">   </span><span class="k">struct</span><span class="w"></span>
  94 <span class="w">      </span><span class="k">type</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">exn</span><span class="w"></span>
  95
  96 <span class="w">      </span><span class="k">fun</span><span class="w"> </span><span class="n">&#39;a</span><span class="w"> </span><span class="n">embed</span><span class="w"> </span><span class="p">()</span><span class="w"> </span><span class="p">=</span><span class="w"></span>
  97 <span class="w">         </span><span class="k">let</span><span class="w"></span>
  98 <span class="w">            </span><span class="k">exception</span><span class="w"> </span><span class="n">E</span><span class="w"> </span><span class="k">of</span><span class="w"> </span><span class="n">&#39;a</span><span class="w"></span>
  99 <span class="w">            </span><span class="k">fun</span><span class="w"> </span><span class="n">project</span><span class="w"> </span><span class="p">(</span><span class="n">e</span><span class="p">:</span><span class="w"> </span><span class="n">t</span><span class="p">):</span><span class="w"> </span><span class="n">&#39;a</span><span class="w"> </span><span class="n">option</span><span class="w"> </span><span class="p">=</span><span class="w"></span>
 100 <span class="w">               </span><span class="k">case</span><span class="w"> </span><span class="n">e</span><span class="w"> </span><span class="k">of</span><span class="w"></span>
 101 <span class="w">                  </span><span class="n">E</span><span class="w"> </span><span class="n">a</span><span class="w"> </span><span class="p">=&gt;</span><span class="w"> </span><span class="n">SOME</span><span class="w"> </span><span class="n">a</span><span class="w"></span>
 102 <span class="w">                </span><span class="p">|</span><span class="w"> </span><span class="p">_</span><span class="w"> </span><span class="p">=&gt;</span><span class="w"> </span><span class="n">NONE</span><span class="w"></span>
 103 <span class="w">         </span><span class="k">in</span><span class="w"></span>
 104 <span class="w">            </span><span class="p">(</span><span class="n">E</span><span class="p">,</span><span class="w"> </span><span class="n">project</span><span class="p">)</span><span class="w"></span>
 105 <span class="w">         </span><span class="k">end</span><span class="w"></span>
 106 <span class="w">   </span><span class="k">end</span><span class="w"></span>
 107 </pre></div></div></div>
 108 </div>
 109 </div>
 110 <div class="sect1">
 111 <h2 id="_implementation_using_functions_and_references">Implementation Using Functions and References</h2>
 112 <div class="sectionbody">
 113 <div class="listingblock">
 114 <div class="content"><div class="highlight"><pre><span class="k">structure</span><span class="w"> </span><span class="n">U</span><span class="p">:&gt;</span><span class="w"> </span><span class="n">UNIVERSAL_TYPE</span><span class="w"> </span><span class="p">=</span><span class="w"></span>
 115 <span class="w">   </span><span class="k">struct</span><span class="w"></span>
 116 <span class="w">      </span><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">T</span><span class="w"> </span><span class="k">of</span><span class="w"> </span><span class="p">{</span><span class="n">clear</span><span class="p">:</span><span class="w"> </span><span class="n">unit</span><span class="w"> </span><span class="p">-&gt;</span><span class="w"> </span><span class="n">unit</span><span class="p">,</span><span class="w"></span>
 117 <span class="w">                         </span><span class="n">store</span><span class="p">:</span><span class="w"> </span><span class="n">unit</span><span class="w"> </span><span class="p">-&gt;</span><span class="w"> </span><span class="n">unit</span><span class="p">}</span><span class="w"></span>
 118
 119 <span class="w">      </span><span class="k">fun</span><span class="w"> </span><span class="n">&#39;a</span><span class="w"> </span><span class="n">embed</span><span class="w"> </span><span class="p">()</span><span class="w"> </span><span class="p">=</span><span class="w"></span>
 120 <span class="w">         </span><span class="k">let</span><span class="w"></span>
 121 <span class="w">            </span><span class="k">val</span><span class="w"> </span><span class="n">r</span><span class="p">:</span><span class="w"> </span><span class="n">&#39;a</span><span class="w"> </span><span class="n">option</span><span class="w"> </span><span class="n">ref</span><span class="w"> </span><span class="p">=</span><span class="w"> </span><span class="n">ref</span><span class="w"> </span><span class="n">NONE</span><span class="w"></span>
 122 <span class="w">            </span><span class="k">fun</span><span class="w"> </span><span class="n">inject</span><span class="w"> </span><span class="p">(</span><span class="n">a</span><span class="p">:</span><span class="w"> </span><span class="n">&#39;a</span><span class="p">):</span><span class="w"> </span><span class="n">t</span><span class="w"> </span><span class="p">=</span><span class="w"></span>
 123 <span class="w">               </span><span class="n">T</span><span class="w"> </span><span class="p">{</span><span class="n">clear</span><span class="w"> </span><span class="p">=</span><span class="w"> </span><span class="k">fn</span><span class="w"> </span><span class="p">()</span><span class="w"> </span><span class="p">=&gt;</span><span class="w"> </span><span class="n">r</span><span class="w"> </span><span class="n">:=</span><span class="w"> </span><span class="n">NONE</span><span class="p">,</span><span class="w"></span>
 124 <span class="w">                  </span><span class="n">store</span><span class="w"> </span><span class="p">=</span><span class="w"> </span><span class="k">fn</span><span class="w"> </span><span class="p">()</span><span class="w"> </span><span class="p">=&gt;</span><span class="w"> </span><span class="n">r</span><span class="w"> </span><span class="n">:=</span><span class="w"> </span><span class="n">SOME</span><span class="w"> </span><span class="n">a</span><span class="p">}</span><span class="w"></span>
 125 <span class="w">            </span><span class="k">fun</span><span class="w"> </span><span class="n">project</span><span class="w"> </span><span class="p">(</span><span class="n">T</span><span class="w"> </span><span class="p">{</span><span class="n">clear</span><span class="p">,</span><span class="w"> </span><span class="n">store</span><span class="p">}):</span><span class="w"> </span><span class="n">&#39;a</span><span class="w"> </span><span class="n">option</span><span class="w"> </span><span class="p">=</span><span class="w"></span>
 126 <span class="w">               </span><span class="k">let</span><span class="w"></span>
 127 <span class="w">                  </span><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">store</span><span class="w"> </span><span class="p">()</span><span class="w"></span>
 128 <span class="w">                  </span><span class="k">val</span><span class="w"> </span><span class="n">res</span><span class="w"> </span><span class="p">=</span><span class="w"> </span><span class="n">!r</span><span class="w"></span>
 129 <span class="w">                  </span><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">clear</span><span class="w"> </span><span class="p">()</span><span class="w"></span>
 130 <span class="w">               </span><span class="k">in</span><span class="w"></span>
 131 <span class="w">                  </span><span class="n">res</span><span class="w"></span>
 132 <span class="w">               </span><span class="k">end</span><span class="w"></span>
 133 <span class="w">         </span><span class="k">in</span><span class="w"></span>
 134 <span class="w">            </span><span class="p">(</span><span class="n">inject</span><span class="p">,</span><span class="w"> </span><span class="n">project</span><span class="p">)</span><span class="w"></span>
 135 <span class="w">         </span><span class="k">end</span><span class="w"></span>
 136 <span class="w">   </span><span class="k">end</span><span class="w"></span>
 137 </pre></div></div></div>
 138 <div class="paragraph"><p>Note that due to the use of a shared ref cell, the above
 139 implementation is not thread safe.</p></div>
 140 <div class="paragraph"><p>One could try to simplify the above implementation by eliminating the
 141 <span class="monospaced">clear</span> function, making <span class="monospaced">type t = unit -&gt; unit</span>.</p></div>
 142 <div class="listingblock">
 143 <div class="content"><div class="highlight"><pre><span class="k">structure</span><span class="w"> </span><span class="n">U</span><span class="p">:&gt;</span><span class="w"> </span><span class="n">UNIVERSAL_TYPE</span><span class="w"> </span><span class="p">=</span><span class="w"></span>
 144 <span class="w">   </span><span class="k">struct</span><span class="w"></span>
 145 <span class="w">      </span><span class="k">type</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">unit</span><span class="w"> </span><span class="p">-&gt;</span><span class="w"> </span><span class="n">unit</span><span class="w"></span>
 146
 147 <span class="w">      </span><span class="k">fun</span><span class="w"> </span><span class="n">&#39;a</span><span class="w"> </span><span class="n">embed</span><span class="w"> </span><span class="p">()</span><span class="w"> </span><span class="p">=</span><span class="w"></span>
 148 <span class="w">         </span><span class="k">let</span><span class="w"></span>
 149 <span class="w">            </span><span class="k">val</span><span class="w"> </span><span class="n">r</span><span class="p">:</span><span class="w"> </span><span class="n">&#39;a</span><span class="w"> </span><span class="n">option</span><span class="w"> </span><span class="n">ref</span><span class="w"> </span><span class="p">=</span><span class="w"> </span><span class="n">ref</span><span class="w"> </span><span class="n">NONE</span><span class="w"></span>
 150 <span class="w">            </span><span class="k">fun</span><span class="w"> </span><span class="n">inject</span><span class="w"> </span><span class="p">(</span><span class="n">a</span><span class="p">:</span><span class="w"> </span><span class="n">&#39;a</span><span class="p">):</span><span class="w"> </span><span class="n">t</span><span class="w"> </span><span class="p">=</span><span class="w"> </span><span class="k">fn</span><span class="w"> </span><span class="p">()</span><span class="w"> </span><span class="p">=&gt;</span><span class="w"> </span><span class="n">r</span><span class="w"> </span><span class="n">:=</span><span class="w"> </span><span class="n">SOME</span><span class="w"> </span><span class="n">a</span><span class="w"></span>
 151 <span class="w">            </span><span class="k">fun</span><span class="w"> </span><span class="n">project</span><span class="w"> </span><span class="p">(</span><span class="n">f</span><span class="p">:</span><span class="w"> </span><span class="n">t</span><span class="p">):</span><span class="w"> </span><span class="n">&#39;a</span><span class="w"> </span><span class="n">option</span><span class="w"> </span><span class="p">=</span><span class="w"> </span><span class="p">(</span><span class="n">r</span><span class="w"> </span><span class="n">:=</span><span class="w"> </span><span class="n">NONE</span><span class="p">;</span><span class="w"> </span><span class="n">f</span><span class="w"> </span><span class="p">();</span><span class="w"> </span><span class="n">!r</span><span class="p">)</span><span class="w"></span>
 152 <span class="w">         </span><span class="k">in</span><span class="w"></span>
 153 <span class="w">            </span><span class="p">(</span><span class="n">inject</span><span class="p">,</span><span class="w"> </span><span class="n">project</span><span class="p">)</span><span class="w"></span>
 154 <span class="w">         </span><span class="k">end</span><span class="w"></span>
 155 <span class="w">   </span><span class="k">end</span><span class="w"></span>
 156 </pre></div></div></div>
 157 <div class="paragraph"><p>While correct, this approach keeps the contents of the ref cell alive
 158 longer than necessary, which could cause a space leak.  The problem is
 159 in <span class="monospaced">project</span>, where the call to <span class="monospaced">f</span> stores some value in some ref cell
 160 <span class="monospaced">r'</span>.  Perhaps <span class="monospaced">r'</span> is the same ref cell as <span class="monospaced">r</span>, but perhaps not.  If
 161 we do not clear <span class="monospaced">r'</span> before returning from <span class="monospaced">project</span>, then <span class="monospaced">r'</span> will
 162 keep the value alive, even though it is useless.</p></div>
 163 </div>
 164 </div>
 165 <div class="sect1">
 166 <h2 id="_also_see">Also see</h2>
 167 <div class="sectionbody">
 168 <div class="ulist"><ul>
 169 <li>
 170 <p>
 171 <a href="PropertyList">PropertyList</a>: Lisp-style property lists implemented with a universal type
 172 </p>
 173 </li>
 174 </ul></div>
 175 </div>
 176 </div>
 177 </div>
 178 <div id="footnotes"><hr></div>
 179 <div id="footer">
 180 <div id="footer-text">
 181 </div>
 182 <div id="footer-badges">
 183 </div>
 184 </div>
 185 </body>
 186 </html>