<!DOCTYPE html>
<html lang="en">
<head>
<meta charset="UTF-8">
<meta http-equiv="X-UA-Compatible" content="IE=edge">
<meta name="viewport" content="width=device-width, initial-scale=1.0">
<meta name="generator" content="Asciidoctor 2.0.26">
<title>UniversalType</title>
<link rel="stylesheet" href="https://fonts.googleapis.com/css?family=Open+Sans:300,300italic,400,400italic,600,600italic%7CNoto+Serif:400,400italic,700,700italic%7CDroid+Sans+Mono:400,700">
<link rel="stylesheet" href="./asciidoctor.css">
<link rel="stylesheet" href="./mlton.css">

</head>
<body class="article">
<div id="mlton-header">
<div id="mlton-header-text">
<h2>
<a href="./Home">
MLton
20241230+git20251029+dfsg-5
</a>
</h2>
</div>
</div>
<div id="header">
<h1>UniversalType</h1>
</div>
<div id="content">
<div id="preamble">
<div class="sectionbody">
<div class="paragraph">
<p>A universal type is a type into which all other types can be embedded.
Here&#8217;s a <a href="StandardML">Standard ML</a> signature for a universal type.</p>
</div>
<div class="listingblock">
<div class="content">
<pre class="rouge highlight"><code data-lang="sml">signature UNIVERSAL_TYPE =
   sig
      type t

      val embed: unit -&gt; ('a -&gt; t) * (t -&gt; 'a option)
   end</code></pre>
</div>
</div>
<div class="paragraph">
<p>The idea is that <code>type t</code> is the universal type and that each call to
<code>embed</code> returns a new pair of functions <code>(inject, project)</code>, where
<code>inject</code> embeds a value into the universal type and <code>project</code> extracts
the value from the universal type.  A pair <code>(inject, project)</code>
returned by <code>embed</code> works together in that <code>project u</code> will return
<code>SOME v</code> if and only if <code>u</code> was created by <code>inject v</code>.  If <code>u</code> was
created by a different function <code>inject'</code>, then <code>project</code> returns
<code>NONE</code>.</p>
</div>
<div class="paragraph">
<p>Here&#8217;s an example embedding integers and reals into a universal type.</p>
</div>
<div class="listingblock">
<div class="content">
<pre class="rouge highlight"><code data-lang="sml">functor Test (U: UNIVERSAL_TYPE): sig end =
   struct
      val (intIn: int -&gt; U.t, intOut) = U.embed ()
      val r: U.t ref = ref (intIn 13)
      val s1 =
         case intOut (!r) of
            NONE =&gt; "NONE"
          | SOME i =&gt; Int.toString i
      val (realIn: real -&gt; U.t, realOut) = U.embed ()
      val () = r := realIn 13.0
      val s2 =
         case intOut (!r) of
            NONE =&gt; "NONE"
          | SOME i =&gt; Int.toString i
      val s3 =
         case realOut (!r) of
            NONE =&gt; "NONE"
          | SOME x =&gt; Real.toString x
      val () = print (concat [s1, " ", s2, " ", s3, "\n"])
   end</code></pre>
</div>
</div>
<div class="paragraph">
<p>Applying <code>Test</code> to an appropriate implementation will print</p>
</div>
<div class="listingblock">
<div class="content">
<pre>13 NONE 13.0</pre>
</div>
</div>
<div class="paragraph">
<p>Note that two different calls to embed on the same type return
different embeddings.</p>
</div>
<div class="paragraph">
<p>Standard ML does not have explicit support for universal types;
however, there are at least two ways to implement them.</p>
</div>
</div>
</div>
<div class="sect1">
<h2 id="_implementation_using_exceptions">Implementation Using Exceptions</h2>
<div class="sectionbody">
<div class="paragraph">
<p>While the intended use of SML exceptions is for exception handling, an
accidental feature of their design is that the <code>exn</code> type is a
universal type.  The implementation relies on being able to declare
exceptions locally to a function and on the fact that exceptions are
<a href="GenerativeException">generative</a>.</p>
</div>
<div class="listingblock">
<div class="content">
<pre class="rouge highlight"><code data-lang="sml">structure U:&gt; UNIVERSAL_TYPE =
   struct
      type t = exn

      fun 'a embed () =
         let
            exception E of 'a
            fun project (e: t): 'a option =
               case e of
                  E a =&gt; SOME a
                | _ =&gt; NONE
         in
            (E, project)
         end
   end</code></pre>
</div>
</div>
</div>
</div>
<div class="sect1">
<h2 id="_implementation_using_functions_and_references">Implementation Using Functions and References</h2>
<div class="sectionbody">
<div class="listingblock">
<div class="content">
<pre class="rouge highlight"><code data-lang="sml">structure U:&gt; UNIVERSAL_TYPE =
   struct
      datatype t = T of {clear: unit -&gt; unit,
                         store: unit -&gt; unit}

      fun 'a embed () =
         let
            val r: 'a option ref = ref NONE
            fun inject (a: 'a): t =
               T {clear = fn () =&gt; r := NONE,
                  store = fn () =&gt; r := SOME a}
            fun project (T {clear, store}): 'a option =
               let
                  val () = store ()
                  val res = !r
                  val () = clear ()
               in
                  res
               end
         in
            (inject, project)
         end
   end</code></pre>
</div>
</div>
<div class="paragraph">
<p>Note that due to the use of a shared ref cell, the above
implementation is not thread safe.</p>
</div>
<div class="paragraph">
<p>One could try to simplify the above implementation by eliminating the
<code>clear</code> function, making <code>type t = unit -&gt; unit</code>.</p>
</div>
<div class="listingblock">
<div class="content">
<pre class="rouge highlight"><code data-lang="sml">structure U:&gt; UNIVERSAL_TYPE =
   struct
      type t = unit -&gt; unit

      fun 'a embed () =
         let
            val r: 'a option ref = ref NONE
            fun inject (a: 'a): t = fn () =&gt; r := SOME a
            fun project (f: t): 'a option = (r := NONE; f (); !r)
         in
            (inject, project)
         end
   end</code></pre>
</div>
</div>
<div class="paragraph">
<p>While correct, this approach keeps the contents of the ref cell alive
longer than necessary, which could cause a space leak.  The problem is
in <code>project</code>, where the call to <code>f</code> stores some value in some ref cell
<code>r'</code>.  Perhaps <code>r'</code> is the same ref cell as <code>r</code>, but perhaps not.  If
we do not clear <code>r'</code> before returning from <code>project</code>, then <code>r'</code> will
keep the value alive, even though it is useless.</p>
</div>
</div>
</div>
<div class="sect1">
<h2 id="_also_see">Also see</h2>
<div class="sectionbody">
<div class="ulist">
<ul>
<li>
<p><a href="PropertyList">PropertyList</a>: Lisp-style property lists implemented with a universal type</p>
</li>
</ul>
</div>
</div>
</div>
</div>
</body>
</html>