Extensible Open Datatypes in OCaml

Synopsis

This page gives details of an extension to the OCaml compiler that adds extensible open datatypes.  One open type already exists within OCaml: the exn type used for exceptions. This patch extends this mechanism to allow the programmer to create their own open types. This has previously been proposed for functional languages a number of times, for instance as part of a solution to the expression problem (Loh et al. "Open Data Types and Open Functions").

Although open types are in some ways similar to polymorphic variants,
they are more similar to ordinary variants:
  • Constructors for open types can be used anywhere that an ordinary variant constructor can be used.
  • Constructors for open types have a single type, which can make them less prone to errors than polymorphic variants
  • Constructors for open types are associated with modules, so they can be hidden by signatures.
  • Open types can be Generalized Algebraic Data Types.
More details and examples can be found below.

Installation


The most recent version of this extension, built against OCaml 4.00.1:

      4.00.1+open_types

This can be installed by following the normal installation instructions for OCaml.

The extension is also now available using the OPAM package manager:

    $ opam switch 4.00.1+open-types
    $ eval `opam config -env`

The latest development version of this extension can also be found on GitHub.

Open Datatypes

This patch allows "open" abstract data types to be created which can then be extended with new constructors at other points in the program.
For example:

type foo = ..

type foo += A

type foo += B of int

let is_a x =
  match x with
    A -> true
  | _ -> false

Like normal constructors, these type extensions are associated with a module. They can be hidden or even made private using a signature. Like exceptions, type extensions can also be given an alias.

module M = struct
  type foo += C of int
end


let c = M.C 10

type foo += D = M.C

let c2 = D 20

module type P = sig
  type foo += private C of int
end


module M_P = (M : P)

let c3 = M_P.C 30 (* ERROR: Cannot create a value using a private constructor *)


Whether a type is "open" can also be hidden using a signature.

module N = struct
  type bar = ..
  type bar += Bar
end


type N.bar += Bar2

module type C = sig
  type bar
  type bar += Bar
end


module N_C = (N : C)

type N_C.bar += Bar3 (* ERROR: Cannot extend a type that isn't "open" *)

Open Polymorphic Types and Open GADTs

Open types can also be polymorphic.

type 'a pfoo = ..

type 'a pfoo += PFoo of int

Constraints and variance specifications are also supported.

type +'a vfoo = ..

type 'a vfoo +=
  Good of (int -> 'a)

Bad of ('a -> int) (* ERROR: Parameter variances are not satisfied *)

type 'a cfoo = .. constraint 'a = [> `Var ]

type 'a cfoo += CFoo of 'a

let cf = CFoo 9 (* ERROR: Constraints not met *)


As this patch is based on version 4.00 of OCaml, it also supported open GADTs. These can be created with the GADT syntax:

type 'a gfoo = ..

type 'a gfoo += GFoo : int -> int gfoo

let get_num (type a) (gf: a gfoo) (i: a) =
  match gf with
    GFoo j -> Some (i + j)
  | _ -> None

Example

A good use for open datatypes is to support nominative dynamic types for user-defined types.

For example we can use open types to create classes that allow down-casting:

type 'a class_name = ..

exception Bad_cast

class type castable =
object
  method cast: 'a.'a class_name -> 'a
end

(* Lets create a castable class with a name*)

class type foo_t =
object
  inherit castable
  method foo: string
end

type 'a class_name += Foo: foo_t class_name

class foo: foo_t =
object(self)
  method cast: type a. a class_name -> a =
    function
       Foo -> (self : #foo_t :> foo_t)
      | _ -> ((raise Bad_cast) : a)
  method foo = "foo"
end

(* Now we can create a subclass of foo *)

class type bar_t =
object
  inherit foo
  method bar: string
end

type 'a class_name += Bar: bar_t class_name

class bar: bar_t =
object(self)
  inherit foo as super
  method cast: type a. a class_name -> a =
    function
        Bar -> (self : #bar_t :> bar_t)
      | other -> super#cast other
  method bar = "bar"
end

(* Now lets create a mutable list of castable objects *)

let clist :castable list ref = ref []

let push_castable (c: #castable) =
  clist := (c :> castable) :: !clist

let pop_castable () =
  match !clist with
      c :: rest ->
        clist := rest;
        c
    | [] -> raise Not_found;;

(* We can add foos and bars to this list, and retrieve them *)

push_castable (new foo);;
push_castable (new bar);;
push_castable (new foo);;

let c1: castable = pop_castable ()
let c2: castable = pop_castable ()
let c3: castable = pop_castable ()

(* We can also downcast these values back to foos and bars *)

let f1: foo = c1#cast Foo
let f2: foo = c2#cast Foo
let f3: foo = c3#cast Foo

let b2: bar = c2#cast Bar


Contact


lpw25  at  cl.cam.ac.uk