Antoine Kalmbach's blog

The expression problem as a litmus test

The expression problem is a famous problem in programming languages.

“The Expression Problem is a new name for an old problem. The goal is to define a datatype by cases, where one can add new cases to the datatype and new functions over the datatype, without recompiling existing code, and while retaining static type safety (e.g., no casts).”

Using interfaces (like in Java) as the datatype example, the problem simply asks whether it is possible to derive the interface and add new methods to the interface, without having to recompile existing code or to resort to using casts.

Obviously, in a OOP language it’s easy to derive interfaces, but the problem uncovers the rigidity of the type system: you can’t modify (i.e. extend) the interface, because you have to modify all the classes classes that implement the interface.

Conversely, in functional programming languages, adding new methods operating on the interface is easy. Consider the canonical OCaml example:

type shape = Circle of float | Rectangle of float * float

let area shp = match shp with
    Circle radius -> 3.14159 *. radius *. radius
  | Rectangle (width, height) -> width *. height
  
let vertices shp = match shp with 
    Circle _ -> infinity
  | Rectangle (_, _) -> 4

So in FP, you could create a function called volume that computes the volume for the existing types, and you needn’t touch the above code. However, as soon as you do that, you realize you’ve made a silly mistake: our shapes are flat so their volume is zero. Quickly, you realize you need a three-dimensional Cube shape.

let volume shp = match shp with
    Circle _ -> 0.
  | Rectangle _ -> 0.
  | Cube s   -> a *. a *. a        (* Cube isn't defined *)

Oops!

Here’s the onion: to get the Cube working, you’ll have to modify the existing code in two places: the definition of shape and both methods area and vertices.

In OOP, this isn’t the case, since you can just derive the new IShape interface and be done with it, but the problem arises when you’re adding the volume function, because you need to modify IShape, and thus every class that derives it.

In FP, adding new functions over the datatypes is easy, but adding new cases to the datatype is tricky, because you have to modify existing functions. In OOP, adding new functions over the datatype is hard, because you need to modify each implementation; adding new cases to the datatype is easy, since all you need to do is derive the interface. FP has invented a multitude of ways to deal with this problem, ranging from type classes, traits to protocols; OOP usually solves with either patterns or open classes. Ruby’s refinements can be used for this purpose as well.

Polymorphic variants

That’s a quick introduction to the problem. I think the expression problem is a perfect litmus test of sorts for programming languages, that is, the measure of the expressive power of the language is the quality of the solutions the language presents to the expression problem.

The expression problem is theoretically solvable in any language, but to varying degrees of elegance. In Java one must resort to using the visitor pattern, and in my mind this is the most inelegant way of going about it. I would rate the solutions on a spectrum: with the most basic solution being the visitor pattern, at the other end we have something like polymorphic variants and type classes. Multimethods and protocols are somewhere in between.

When you compare polymorphic variants of OCaml with Haskell’s type classes, there’s a marked difference in brevity. Polymorphic variants are succincter than type classes but cannot provide the same level of type safety.

type shape = [ `Circle of float | `Rectangle of float * float ]

let area shp = match shp with
    `Circle radius -> radius *. radius *. 3.14159
  | `Rectangle (w, h) -> w *. h

let vertices shp = match shp with
    `Circle radius -> infinity
  | `Rectangle (w, h) -> 4.

Not too different from the above declaration, the type is surrounded with brackets and the types are preceded with backticks. Recreating the volume function is easy.

let volume shp = match shp with
    `Circle _ -> 0.
  | `Rectangle _ -> 0.
  | `Cube a -> a *. a *. a

So now I’ve extended the shape type with another type Cube, and I haven’t touched vertices and area functions. The volume function can be done even more succinctly:

let short_volume shp = match shp with
    (* no volume in two dimensions! *)
    #shape -> 0.
  | `Cube a -> a *. a *. a

It is also possible to constrain the polymorphic variants:

let flatten shp = match shp with
    #shape as x -> x
  | `Cube a -> `Rectangle a

The type of this function is [ < `Circle of float | `Cube of float | `Rectangle of float * float ] -> [> shape]. The [< A | B] means a closed type: it can be only A or B, but nothing else, and [> Foo] means “Foo or something else”. So the flatten function accepts Circle, Rectangle or Cube and returns a shape (or possibly something else). Trying to run flatten (`Sphere 4) produces a type error:

# flatten (`Sphere 3);;
Characters 8-19:
  flatten (`Sphere 3);;
          ^^^^^^^^^^^
Error: This expression has type [> `Sphere of int ]
       but an expression was expected of type
         [< `Circle of float
          | `Cube of float * float
          | `Rectangle of float * float ]
       The second variant type does not allow tag(s) `Sphere

However, the following code compiles:

type polytope = [ shape | `Cube | `Octahedron ]

let frobnicate pt =
  let flattened = flatten pt in
  match flattened with
    #shape -> "Already flaaat!"
  | `Octagon -> "Eight coorneeeeerss"

The compiles, although we didn’t tell the compiler that flatten does not return Octagon. There are two ways to fix this: either explicitly annotate pt to be of type polytope, which produces this error:

Error: This expression has type polytope
       but an expression was expected of type
         [< `Circle of float | `Cube of float | `Rectangle of float * float ]
       The second variant type does not allow tag(s) `Octahedron

It is possible to further constrain the type with type annotations. We can make sure that the flatten function returns only flat shapes:

let safe_flatten shp : [< shape] = match shp with
    #shape as x -> x
  | `Cube a -> `Rectangle a
  | `Sphere r -> `Circle r

This produces the error:

Error: This pattern matches values of type [? `Octagon ]
       but a pattern was expected which matches values of type shape
       The second variant type does not allow tag(s) `Octagon

Not a silver bullet

Unfortunately, polymorphic variants are problematic. The problem with polymorphic variants is you quickly reach an absurd level of complexity and are forced to use annotations or subtyping to ensure maximal type safety. So although polymorphic variants are nice, and they do let us solve the expression problem, they’re an unsteady compromise between type safety and brevity. You can certainly make elegant abstractions with them but they get unwieldy quickly. They aren’t as efficient compared to regular variants either.

So what are the options? In OCaml 4.02, you can use extensible variant types:

type boring_shape = ..
type boring_shape += Circle of float | Square of float
                                                   
let boring_area shp = match shp with
    Circle r -> r *. r *. 3.14159
  | Square a -> a *. a
  | _ -> 0.

type boring_shape += Rectangle of float * float
let radical_area shp = match shp with
    Circle _ as c -> boring_area c
  | Square _ as s -> boring_area s
  | Rectangle (w, h) -> w *. h
  | _ -> 0.

An extensible variant is defined using .., and extension is done with the += operator. The caveat is that you must handle the default _ case in pattern matching. Extensible variants are another neat trick for solving the expression problem.

A measure of expressive power

The expression problem is a great litmus test that measures the expressive power of a programming language. The actual measurement of the test can be either the brevity of the code or its type safety. The solutions range from the clumsy Visitor Pattern in Java to polymorphic and extensible variants in OCaml and to type classes in Haskell. Clojure and Elixir have protocols that are both quite nice but not so type-safe since both are dynamically typed languages. What is more, since the expression problem is also about type safety, then strictly speaking the problem isn’t valid in a dynamic language. Any Lisper knows that Lisps are super expressive anyway.

Previous: Before we begin Next: Are my services talking to each other?