For programming in small, I will use plain old algebraic data types. For public libraries and large programs designed for change, I will use the dependency inversion principle and make sure that my high-level policy code (e.g., drawing facilities) doesn’t depend on the low-level implementation details.
Large vs. Small
First of all, let’s define what is programming in large and what is in small. The truth is that there is no definite answer, you have to develop some taste to understand where you should just stick with plain ADT (PADT) or where to unpack the heavy artillery of GADT and final tagless styles. There is, however, a rule of thumb that I have developed and which might be useful to you as well.
ADT is the detail of implementation
ADT shall never go into the public interface. Both PADT and GADT are details of implementation and should be hidden inside the module and never reach the mli file, at least the mli of a publically available code (i.e., a library that you plan to distribute and for which you install cmi/mli files). Exposing your data definitions is much like showing your public member values in C++ or Java.
The less the extent of an ADT in your codebase the easier it will be to maintain it. Indeed, notice even how hard and ugly it is to work in OCaml with ADT defined in other modules. So even the language resists this. And if the language resists then don’t force it.
With that said, 90% of your code should be small code with data types defined for the extent of a compilation unit, which, in general, should be less than 300-500 lines of code (ideally start with 100) and have a couple of internal modules. Basically, a compilation unit should have a size that easily fits into short-term memory.
Since programming in small is a more or less clear concept, let’s move forward.
Programming In Large
So you’re designing a large project, possibly with a public API, that will help lots of developers with different backgrounds and skills. And as always it should be delivered next week, well at least the minimal viable product. The upper management is stressing you but you still don’t want to mess things up and be cursed by the generations of software developers that will use your product.
One of the killer features of OCaml, and the main reason why I have switched to it a long time ago and use it since then, is that it ideally fits the above-described use case. It fully supports the programming in large style (like Java and Ada) but enables at the same easy prototyping and delivering MVPs the next day your manager asks (like Python). And if you have young students in your team, their enthusiasm will not leave the boundaries of the module abstraction. And if you are the manager you have excellent language (the language of mli files) that you can use to convey your design ideas to other team members and even to non-technical personnel.
So let’s do some prototyping and design, using the language of signatures. First of all, we shall decide which type should be designed for change and which should be regular data types. E.g., we probably don’t want to have a string data type with pluggable implementation. But we definitely know that our figures will change and more will be added, possibly by 3rd-party developers.
We finally decide that Point and Canvas will be the regular types (for Canvas we might regret our design decision). For prototyping, we will write the module type of our project. At the same time, we should also write documentation for each module and its items (functions, types, classes, etc). Writing documentation is an important design procedure. If you can’t describe in plain English what a module is doing then probably it is a wrong abstraction. But now, for the sake of brevity and lack of time we will skip this important step and unroll the whole design right away.
module type Project = sig
module Point : sig
type t
val create : int -> int -> t
val x : t -> int
val y : t -> int
val show : t -> string
end
module Canvas : sig
type t
val empty : t
val text : t -> Point.t -> string -> unit
end
module Widget : sig
type t
val create : ('a -> Canvas.t -> unit) -> 'a -> t
val draw : t -> Canvas.t -> unit
end
module type Figure = sig
type t
val widget : t -> Widget.t
end
module Rectangle : sig
include Figure
val create : Point.t -> Point.t -> t
end
module Circle : sig
include Figure
val create : Point.t -> int -> t
end
end
Let’s discuss it a bit. The Canvas and Point types are pretty obvious, in fact this design just assumes that they are already provided by the third-party libraries, so that we can focus on our figures.
Now the Widget types. Following the dependency inversion principle, we decided to make our rendering layer independent of the particular implementation of the things that will populate it. Therefore we created an abstraction of a drawable entity with a rather weak definition of the abstraction, i.e., a drawable is anything that implements ('a -> Canvas.t -> unit) method. We will later muse on how we will extend this abstraction without breaking good relationships with colleagues.
Another point of view on Widget is that it defines a Drawable type class and that Widget.create is defining an instance of that class, so we could even choose a different naming for that, e.g.,
module Draw : sig
type t
val instance : ('a -> Canvas.t -> unit) -> 'a -> t
val render : t -> Canvas.t -> unit
end
The particular choice depends on the mindset of your team, but I bet that the Widget abstraction would fit better more people.
But let’s go back to our figures. So far we only decided that a figure is any type t that defines val widget : t -> Widget.t. We can view this from the type classes standpoint as that the figure class is an instance of the widget class. Or we can invoke Curry-Howard isomorphism and notice that val widget : t -> Widget.t is a theorem that states that every figure is a widget.
The rest should be trivial with these signatures, so let’s move forward and develop MVP,
module Prototype : Project = struct
module Point = struct
type t = {x : int; y : int}
let create x y = {x; y}
let x {x} = x
let y {y} = y
let show {x; y} = "(" ^ string_of_int x ^ ", " ^ string_of_int y ^ ")"
end
module Canvas = struct
type t = unit
let empty = ()
let text _canvas _position = print_endline
end
module Widget = struct
type t = Widget : {
draw : 'obj -> Canvas.t -> unit;
self : 'obj;
} -> t
let create draw self = Widget {self; draw}
let draw (Widget {draw; self}) canvas = draw self canvas
end
module type Figure = sig
type t
val widget : t -> Widget.t
end
module Rectangle = struct
type t = {ll : Point.t; ur : Point.t}
let create ll ur = {ll; ur}
let widget = Widget.create @@ fun {ll} canvas ->
Canvas.text canvas ll "rectangle"
end
module Circle = struct
type t = {p : Point.t; r : int}
let create p r = {p; r}
let widget = Widget.create @@ fun {p} canvas ->
Canvas.text canvas p "circle"
end
end
Et voila, we can show it to our boss and have some coffee. But let’s look into the implementation details to learn some new tricks. We decided to encode widget as an existential data type, no surprises here as abstract types have existential type and our widget is an abstract type. What is existential you might ask (even after reading the paper), well in OCaml it is a GADT that captures one or more type variables, e.g., here we have 'obj type variable that is not bound (quantified) on the type level, but is left hidden inside the type. You can think of existential as closures on the type level.
This approach enables us to have widgets of any types and, moreover, develop widgets totally independently and even load them as plugins without having to recompile our main project.
Of course, using GADT as encoding for abstract type is not the only choice. It even has its drawbacks, like we can’t serialize/deserialize them directly (though probably we shouldn’t) it has some small overhead.
There are other options that are feasible. For example, for a widget type, it is quite logical to stick with the featherweight design pattern and represent it as an integer, and store the table of methods in the external hash table.
We might also need more than one method to implement the widget class, which we can pack as modules and store in the existential or in an external hash table. Using module types enables us gradual upgrade of our interfaces and build hierarchies of widgets if we need.
When we will develop more abstract types (type classes), like the Geometry class that will calculate area and bounding rectangles for our figures, we might notice some commonalities in the implementation. We might even choose to implement dynamic typing so that we can have the common representation for all abstract types and even type casting operators, e.g., this is where we might end up several years later.
module Widget : sig
type 'cls t
module type S = sig
type t
...
end
type 'a widget = (module S with type t = 'a)
val create : 'a widget -> 'a -> 'a cls t
val forget : 'a t -> unit t
val refine : 'a Class.t -> unit t -> 'a cls t option
val figure : 'a t -> 'a
end
We’re now using a module type to define the abstraction of widget, we probably even have a full hierarchy of module types to give the widget implementors more freedom and to preserve backward compatibility and good relationships. We also keep the original type in the widget so that we can recover it back using the figure function. yes, we resisted this design decision, because it is in fact downcasting, but our clients insisted on it. And yes, we implemented dynamic types, so that we can upcast all widgets to the base class unit Widget.t using forget, but we can still recover the original type (downcast) with refine, which is, obviously, a non-total function.
In BAP, we ended up having all these features as we represent complex data types (machine instructions and expressions). We represent instructions as lightweight integers with all related information stored in the knowledge base. We use dynamic typing together with final tagless style to build our programs and ensure their well-formedness, and we use our typeclass approach a lot, to enable serialization, inspection, and ordering (we use domains for all our data type). You can read more about our knowledge base and even peek into the implementation of it. And we have a large library of signatures that define our abstract types, such as semantics, values, and programs. In the end, our design allows us to extend our abstractions without breaking backward compatibility and to add new operations or new representations without even having to rebuild the library or the main executable. But this is a completely different story that doesn’t really fit into this posting.
Conclusions
We can easily see that our design makes it easy to add new behaviors and even extend the existing one. It also provisions for DRY as we can write generic algorithms for widgets that are totally independent of the underlying implementation. We have a place to grow and an option to completely overhaul our inner representation without breaking any existing code. For example, we can switch from a fat GADT representation of a widget to a featherweight pattern and nobody will notice anything, except (hopefully) improved performance. With that said, I have to conclude as it already took too much time. I am ready for the questions if you have any.