Using let module for matching

In OCaml, referring to constructors defined in other modules can be somewhat awkward. Suppose we have a module like the following.

  1. module Example = struct
  2. type t = Foo | Bar | Baz
  3. end

To write a function that pattern matches on values of type Example.t we could directly refer to the variants as follows.

  1. let f e =
  2. match e with
  3. | Example.Foo -> ...
  4. | Example.Bar -> ...
  5. | Example.Baz -> ...

That is pretty verbose. We could alleviate the problem by opening Example.

  1. open Example
  2. let f e = match e with
  3. | Foo -> ...
  4. | Bar -> ...
  5. | Baz -> ...

That is nicer to look at, but the open potentially brings a lot of things into scope (and not just for f, but for the rest of the file). Using open is generally bad style because it makes it hard for a reader to connect definitions with uses. The open would be less problematic if we could reduce its scope. We can do that by using a local module.

  1. let f e =
  2. let module M = struct
  3. open Example
  4. let res =
  5. match e with
  6. | Foo -> ...
  7. | Bar -> ...
  8. | Baz -> ...
  9. end in
  10. M.res

That's pretty verbose too. The approach we've settled on at Jane Street is to use let module to rebind the module to a short name, thereby making the code concise and avoiding the open entirely.

  1. let f e =
  2. let module E = Example in
  3. match e with
  4. | E.Foo -> ...
  5. | E.Bar -> ...
  6. | E.Baz -> ...

Extracting an exception from a module

The Unix module defines the Unix_error exception constructor.

  1. module Unix : sig
  2. exception Unix_error of error * string * string
  3. ...
  4. end

Suppose you want to create your own My_unix module that defines some Unix utility functions and exports the same Unix_error. How would you do it? You can't redeclare

Unix_error, since that would make a new constructor, which won't match Unix.Unix_error.

  1. module My_unix = struct
  2. exception Unix_error of error * string * string (* a new exception *)
  3. ... my unix functions ...
  4. end

You could include the whole Unix module, but that pollutes the namespace of My_unix unnecessarily.

  1. module My_unix = struct
  2. include Unix
  3.  
  4. ... my unix functions ...
  5. end

A trick to bring just the exception constructor you want into scope is to use a constrained include of the form include (M : sig ... end).

  1. module My_unix = struct
  2. include (Unix : sig exception Unix_error of Unix.error * string * string end)
  3.  
  4. ... my unix functions ...
  5. end

This does require duplicating the exception declaration in the signature, but the type checker will of course guarantee that the declaration you write matches the original, so there is no real chance for error.

A universal type?

Is it possible in OCaml to implement a universal type, into which any other type can be embedded? More concretely, is possible to implement the following signature?

  1. module type Univ = sig
  2. type t
  3. val embed: unit -> ('a -> t) * (t -> 'a option)
  4. end

The idea is that t is the universal type and that embed () returns a pair (inj, prj), which inject to and project from the universal type. Projection is partial (returns an option) because injection is not surjective.

Here is an example of how to use `Univ'.

  1. module Test (U : Univ) = struct
  2. let (of_int, to_int) = U.embed ()
  3. let (of_string, to_string) = U.embed ()
  4. let r : U.t ref = ref (of_int 13)
  5. let () = begin
  6. assert (to_int !r = Some 13);
  7. assert (to_string !r = None);
  8. r := of_string "foo";
  9. assert (to_int !r = None);
  10. assert (to_string !r = Some "foo");
  11. end
  12. end

Try it for yourself and see if you can implement module Univ : Univ so that Test (Univ) passes. No Obj.magic or other unsafe features allowed!

Talking at Penn

I just got back from an enjoyable visit at Penn. I gave a version of my POPL talk for an audience consisting in large part of students taking Benjamin Pierce's advanced programming class, which is being done in Haskell with a little bit of ML. I also got a chance to chat with some of the PL faculty and grad students and to hear what people are up to on the research front.

It was a fun afternoon. I hope among other things that it stirs up some more interest (and proposals) for this year's OCaml Summer Project.

I also spoke with Benjamin about the evolution of their intro programming course. A few years back they were teaching it in OCaml. Then, for all sorts of perfectly understandable reasons, they ended up moving the course to Java. This despite the fact that Benjamin's feeling was that the students ended up better prepared for thinking about Java when the intro course was focused more on OCaml.

It all makes sense, but it is still too bad to see one of the few places in the US really teaching functional programming as an early part of the curriculum give up on it. Maybe it will get resurrected at some point. That said, Benjamin also pointed out that there are advantages to teaching ML or Haskell to an advanced programming class, in that you get to hit the students with it when they're really ready to appreciate the power of the approach. It certainly seems like they put together a good set of students this year.

HOWTO: Static access control using phantom types

We thought that phantom types would be an appropriate topic for our first real post because they are a good example of a powerful and useful feature of OCaml that is little used in practice.

In this post, I'll cover a fairly simple use of phantom types: enforcing a capability-style access-control policy. In particular, I'll describe how you can create easy to use read-only handles to a mutable data structure. We'll explore this using the example of an int ref. The int ref is a toy example, but the same approach can be used for more realistic cases, such as a string library or a database interface.

We'll start by implementing an int ref module on top of OCaml's built-in ref.

  1. module Ref : sig
  2. type t
  3. val create : int -> t
  4. val set : t -> int -> unit
  5. val get : t -> int
  6. end
  7. =
  8. struct
  9. type t = int ref
  10. let create x = ref x
  11. let set t x = t := x
  12. let get t = !t
  13. end

The simplest way of getting a read-only handle is to create another module with a different, more constrained signature.

  1. module RORef : sig
  2. type t
  3. val import : Ref.t -> t
  4. val get : t-> int
  5. end
  6. =
  7. struct
  8. type t = Ref.t
  9. let import x = x
  10. let get = Ref.get
  11. end

An RORef.t is just a Ref.t underneath, but the signature hides that fact by making the RORef.t abstract. Note that there is a function for converting Ref.t's to RORef.t's (import), but not the other way around. This gives you a way to create the read-only handle, but prevents someone with such a handle from recovering the underlying read-write handle. The downside to this approach is that it is impossible to write code that is polymorphic over Ref.t's and RORef.t's, even if that code only uses the functionality common to both, i.e., if it only reads.

A better solution is to use a phantom type to encode the access control rights associated with a particular value. But what is a phantom type? The definition unfortunately makes it sound more complicated than it is. A phantom type is a type that is used as a parameter to another type (like the int in int list), but which is unused in the actual definition (as in type 'a t = int). The fact that the phantom parameter is unused gives you the freedom to use it to encode additional information about your types, which you can then convince the type checker to keep track of for you. Since the phantom type isn't really part of the definition of the type, it has no effect on code-generation and so is completely free at runtime. The way in which you convince the type-checker to track the information you're interested in is by constraining the appearance of the phantom types using a signature.

It's easier to understand once you look at an example.

  1. type readonly
  2. type readwrite
  3.  
  4. module PRef : sig
  5. type 'a t
  6. val create : int -> readwrite t
  7. val set : readwrite t -> int -> unit
  8. val get : 'a t -> int
  9. val readonly : 'a t -> readonly t
  10. end
  11. =
  12. struct
  13. type 'a t = Ref.t
  14. let create = Ref.create
  15. let set = Ref.set
  16. let get = Ref.get
  17. let readonly x = x
  18. end

In the above code, the phantom type tells you what your permissions are. A readwrite PRef.t can read and write, and a readonly PRef.t can only read. Note that the get function doesn't pay any attention to the phantom type, which is why get can be used with both readwrite and readonly PRef.t's. The only function that can modify a ref is get, and that requires a readwrite PRef.t.

Note that the types readonly and readwrite have no definitions. They look like the declaration of an abstract type, except that these definitions are not in a signature. They're actually examples of uninhabited types, i.e., types without associated values. The lack of values presents no problems here, since we're using the types only as tags.

The great thing about this approach is how seamlessly it works in practice. The user of the library can write things in a natural style, and the type system propagates the access-control constraints as you would expect. For example, the following definitions

  1. let sumrefs reflist =
  2. List.fold_left (+) 0 (List.map PRef.get reflist)
  3.  
  4. let increfs reflist =
  5. List.iter (fun r -> PRef.set r (PRef.get r + 1)) reflist

will be given the following inferred types

  1.  
  2. val sumrefs : 'a PRef.t list -> int
  3. val increfs : readwrite PRef.t list -> unit

In other words, the first function, which only reads, can operate on any kind of ref, and the second, which mutates the refs, requires a readwrite ref.

There is one problem with the access control policy we implemented above, which is that there is no clean way of guaranteeing that a given value is immutable. In particular, even if a given value is readonly, it doesn't preclude the existence of another readwrite handle to the same object somewhere else in the program. (Obviously, immutable int refs are not a particularly compelling application, but having both mutable and immutable versions makes sense for more complicated data types, such as string or arrays).

But we can get immutable values as well by making the phantom types just slightly more complicated.

  1. type readonly
  2. type readwrite
  3. type immutable
  4.  
  5. module IRef : sig
  6. type 'a t
  7. val create_immutable : int -> immutable t
  8. val create_readwrite : int -> readwrite t
  9. val readonly : 'a t -> readonly t
  10. val set : readwrite t -> int -> unit
  11. val get : 'a t -> int
  12. end
  13. =
  14. struct
  15. type 'a t = Ref.t
  16. let create_immutable = Ref.create
  17. let create_readwrite = Ref.create
  18. let readonly x = x
  19. let set = Ref.set
  20. let get = Ref.get
  21. end

Importantly, there's no way for an IRef.t to become immutable. It must be immutable from birth.

Extra credit: Making it more polymorphic

One thing that's notable about the IRef signature is that there is no way of creating an actual polymorphic IRef.t. The two creation functions both create values with specific tags, immutable or readwrite. These specialized create functions aren't strictly necessary, though. We could have instead written IRef with the following signature.

  1. sig
  2. type 'a t
  3. val create : int -> 'a t
  4. val set : readwrite t -> int -> unit
  5. val get : 'a t -> int
  6. val readonly : 'a t -> readonly t
  7. end

The user can force the creation of an immutable or readwrite Ref by adding a constraint. So, you could get the effect of

  1. let r = IRef.create_immutable 3

by instead writing

  1. let r = (IRef.create 3 : immutable IRef.t)

The advantage of the polymorphic create function is straightforward: it allows you to write functions that are more polymorphic, and therefore more flexible. For instance, you could write a single function that could create, depending on context, an array of readwrite refs, an array of readonly refs, or an array of immutable refs.

The downside is that it may require more type annotations when you do want to be explicit about the permissions, and it also allows some weird types to come up. In particular, you can create an IRef.t with any phantom parameter you want! Nothing stops you from creating a string IRef.t, even though string doesn't make any sense as an access-control tag. Interestingly, the signature doesn't actually make any reference to the immutable type, and in fact, using any phantom parameter other than readonly and readwrite makes the ref immutable. The access control restrictions still work in roughly the way you would expect, but it is still a bit harder to think about than the original signature.

We’ve got a blog!

Jane Street finally has a blog! Jane Street is one of the biggest commercial users of OCaml, and we like to think that we've picked up a few tricks over the years. In addition to putting down our random musings, we plan to use this space to share what we've learned. We hope that over time this turns into a useful resource for the larger OCaml community.

We'll get our first real post out soon.

4