Working Review of "Practical ML Programming with SML#" (Ohori, Ueno), CHAPTER 4

This chapter is short, and contains a little exercise in defining recursive datatypes. First, we see how the list datatype is defined. Then, we see how JSON can be expressed in the form of a recursive datatype. Finally, we are asked to implement a tree datatype, with several utility functions in the same module.

The Exercises

An interesting thing about the exercises in this chapter is that they build on the information presented in the previous ones. The reader is exepected to have remembered how to break up modules into implementation (.sml) and interface (.smi) files, and how to generate Makefiles for a given target interface file (reminder: smlsharp -MMm target.smi > Makefile).

I ran into one snag here regarding the module system, the solution to which can be found in the very next chapter (5). To demonstrate, let me first show you how I’d implement Tree.sml in Standard ML.

First, the signature:

signature Tree =
sig
  type 'a tree;
  val empty: 'a tree;
  val mkNode: 'a -> 'a tree -> 'a tree -> 'a tree;
  val height : 'a tree -> int ;
  val size : 'a tree  -> int;
  val sum : int tree -> int;
  val copyTree : 'a tree -> 'a tree;
  val traverse : 'a tree -> 'a list;
  val mkTree : int -> int tree;
end

And now, a structure fulfilling the above signature:

structure TreeA : Tree = struct
  datatype 'a tree = Empty | Node of 'a * ('a tree) * ('a tree);

  val empty = Empty;

  fun mkNode (v: 'a) (l: 'a tree) (r: 'a tree) : 'a tree =
      Node (v, l, r);

  fun height (t: 'a tree) : int =  (...)

  fun size (t: 'a tree) : int = (...)

  (...)
end

The important thing to note here is that the type 'a tree is an opaque type, and its constructors Empty and Node (a, l, r) are not exposed to users of the module.

Based on what I’d read thus far in the book, I assumed that the interface file functionality would allow for something similar. But when I tried specifiying the interface as follows:

(* File: Tree.smi *)
structure Tree = struct
  type 'a tree;
  val empty: 'a tree;
  val mkNode: 'a -> 'a tree -> 'a tree -> 'a tree;
  val height : 'a tree -> int ;
  (...)

I’d get the following error:

Tree.smi:3.17(39)-5.8(124) Error: syntax error: deleting  STRUCT TYPE TYVAR
Tree.smi:13.0(330)-13.0(330) Error: syntax error found at END
make: *** [Makefile:8: Tree.o] Error 1

I think the error is a bit misleading, as to me its is more of a semantic error than a syntax error per se. To get over the hump, I initially resigned myself to duplicating the full datatype declaration both in the interface file and the implemenation file:

(* Tree.smi *)
structure Tree = struct
  datatype 'a tree = Empty | Node of 'a * ('a tree) * ('a tree);
  (...)

(* Tree.sml *)
structure Tree = struct
 datatype 'a tree = Empty | Node of 'a * ('a tree) * ('a tree);
 (...)

Apparently, declaring it this way is a common pattern in SML#, and it means that the implementation of the interface must internally declare its datatype in the exact same way, verbatim. This ensures that the datatypes defined in implementation modules correspond to the same internal type. There is more on this in the sml# documentation.

Not fully satisifed beacuse opaque types remained out of reach, I peeked into chapter 5, titled “Modules and Separate Compilation”, and found out I should put this in the interface file:

structure Tree = struct
  type 'a tree (= boxed);
  val empty: 'a tree;
  val mkNode: 'a -> 'a tree -> 'a tree -> 'a tree;
  (...)

Now, we know how to define both opaque and transparent datatypes in interface files. Onto the next chapter!