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
(* ... *)
end
module MyType : MY_TYPE = struct
type t = int
let empty = 0
let do_something n = n + 88
end
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.