The power of OCaml's signatures

A student in my lab is currently taking a programming languages course that teaches OCaml; he's a C guy and doesn't really like OCaml. A few weeks ago, we were talking about OCaml's module system and how we can use it to hide its underlying implementation.

module type MY_TYPE = sig
  type t
  val empty : t
  val do_something : t -> t
  (* ... *)

module MyType : MY_TYPE = struct
    type t = int
    let empty = 0
    let do_something n = n + 88

The MyType module implements the MY_TYPE signature, and if we look at a MyType.t in the OCaml REPL we see the rather unhelpful <abstr>. This student was trying to finish an assignment, and he was annoyed at this opacity which made debugging harder. I told him that in practice, it can often be extremely helpful, but had no actual example from my own experience to offer. Yesterday, I was fortunate to have such an experience.

I am currently writing a small and simple compiler for a subset of the Go language, in preparation of a compiler class this winter. As I started working on the type checker, I needed a symbol table, and thus defined the following signature (inside a .mli file):

type 'a t

val empty    : 'a t
val add      : 'a t -> Ast.symbol -> 'a -> 'a t
val mem      : 'a t -> Ast.symbol -> bool
val find_exn : 'a t -> Ast.symbol -> 'a
val print    : 'a t -> ('a -> string) -> unit

And the actual implementation used a Map, and that seemed to work fine. During the implementation of the type checker, I found that I had a small problem: in Go, two variables cannot be declared in the same lexical scope, i.e.:

// Illegal
var x int = 3
var x int = 4

// Okay
var x int = 3
    var x int = 4

To permit variable shadowing, I needed a way to determine if a symbol was declared locally or in a parent scope. I modified the signature of my symbol table with functions that you would find in any good compiler textbook:

type 'a t

val empty           : 'a t
val add             : 'a t -> Ast.symbol -> 'a -> 'a t
val mem             : 'a t -> Ast.symbol -> bool
val find_exn        : 'a t -> Ast.symbol -> 'a
val print           : 'a t -> ('a -> string) -> unit

val open_scope      : 'a t -> 'a t
val exit_scope      : 'a t -> 'a t
val defined_locally : 'a t -> Ast.symbol -> bool

I modified the implementation to use a list of Maps instead of a single one, where open_scope adds an empty Map to the list and close_scope removes the head of the list. After recompiling the program, everything worked as it did before, and I was able to detect symbols defined multiple times. This did not involve the modification of any code in the actual type checking procedures.

This is a small example of the power of abstract data types and how OCaml enforces them: by not allowing the user to peek into a abstract type and play with its underlying data structures, we can apply important changes to our core while keeping user code unaltered and unaffected.