A universal type is a type into which all other types can be embedded. Here’s a Standard ML signature for a universal type.

signature UNIVERSAL_TYPE =
   sig
      type t

      val embed: unit -> ('a -> t) * (t -> 'a option)
   end

The idea is that type t is the universal type and that each call to embed returns a new pair of functions (inject, project), where inject embeds a value into the universal type and project extracts the value from the universal type. A pair (inject, project) returned by embed works together in that project u will return SOME v if and only if u was created by inject v. If u was created by a different function inject', then project returns NONE.

Here’s an example embedding integers and reals into a universal type.

functor Test (U: UNIVERSAL_TYPE): sig end =
   struct
      val (intIn: int -> U.t, intOut) = U.embed ()
      val r: U.t ref = ref (intIn 13)
      val s1 =
         case intOut (!r) of
            NONE => "NONE"
          | SOME i => Int.toString i
      val (realIn: real -> U.t, realOut) = U.embed ()
      val () = r := realIn 13.0
      val s2 =
         case intOut (!r) of
            NONE => "NONE"
          | SOME i => Int.toString i
      val s3 =
         case realOut (!r) of
            NONE => "NONE"
          | SOME x => Real.toString x
      val () = print (concat [s1, " ", s2, " ", s3, "\n"])
   end

Applying Test to an appropriate implementation will print

13 NONE 13.0

Note that two different calls to embed on the same type return different embeddings.

Standard ML does not have explicit support for universal types; however, there are at least two ways to implement them.

Implementation Using Exceptions

While the intended use of SML exceptions is for exception handling, an accidental feature of their design is that the exn 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 generative.

structure U:> 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 => SOME a
                | _ => NONE
         in
            (E, project)
         end
   end

Implementation Using Functions and References

structure U:> UNIVERSAL_TYPE =
   struct
      datatype t = T of {clear: unit -> unit,
                         store: unit -> unit}

      fun 'a embed () =
         let
            val r: 'a option ref = ref NONE
            fun inject (a: 'a): t =
               T {clear = fn () => r := NONE,
                  store = fn () => 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

Note that due to the use of a shared ref cell, the above implementation is not thread safe.

One could try to simplify the above implementation by eliminating the clear function, making type t = unit -> unit.

structure U:> UNIVERSAL_TYPE =
   struct
      type t = unit -> unit

      fun 'a embed () =
         let
            val r: 'a option ref = ref NONE
            fun inject (a: 'a): t = fn () => r := SOME a
            fun project (f: t): 'a option = (r := NONE; f (); !r)
         in
            (inject, project)
         end
   end

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 project, where the call to f stores some value in some ref cell r'. Perhaps r' is the same ref cell as r, but perhaps not. If we do not clear r' before returning from project, then r' will keep the value alive, even though it is useless.

Also see

  • PropertyList: Lisp-style property lists implemented with a universal type