figure 4. connection types.

The compiler gives the following error:

type connection_state =
| Connecting
| Connected
| Disconnected

type connection_info = {
state: connection_state;
server: inet_addr;
last_ping_time: time option;
last_ping_id: int option;
session_id: string option;
when_initiated: time option;
when_disconnected: time option;
}

File “ destutter.ml”, line 2, characters 2-125: Warning 8: this pattern-matching is not exhaustive. Here is an example of a value that is not matched: _ ::[]

 

The missing case, _ ::[], is a list with a single element.

You can fix the code (and satisfy the compiler) by adding a handler for the missing case:

 

Not, have associated data, and that data varies between the cases. This type actually contains both sums and products, with the And and Or branches containing tuples. Types consisting of layered combinations of products and sums are a common and powerful idiom in OCaml.

One notable bit of syntax is the type variable ’a. A type variable can be instantiated with any type, and this is what allows the code to be generic over the set of base predicates. This is similar to how generic types are handled in Java or C#. Thus, Java’s <A>List would be rendered as ’a list in OCaml.

The function eval takes two arguments: expr, the expression to be evaluated; and eval _ base, a function for evaluating base predicates. The code is generic in the sense that eval could be used for expressions over any type of base predicate, but eval _ base must be provided in order to evaluate the truth or falsehood of those base predicates. The function eval’ is defined as shorthand for invoking recursive calls to eval with eval _ base as an argument. Finally, the match statement is used for doing a case analysis of the possible structures of the expression, calling out to eval _ base when evaluating a base predicate, and otherwise acting as a straightforward recursion over the structure of the datatypes.

Figure 2 shows how the same code might be rendered in Java. The verbosity is immediately striking. Adding a single case such as And takes two (short)

lines in OCaml and eight in Java—and the Java code is actually pretty minimal as these things go. If you wanted to allow the creation of other algorithms around this expression type that are not baked into the class definition, then you probably want to use the visitor pattern, which will inflate the line count considerably.

Another facet of the language that demands some further explanation is the ability of the type system to catch bugs. People who are not familiar with OCaml and related languages (and some who are) often make the mistake of underestimating the power of the type system. It is easy to conclude that all the type system does for you is ensure you passed in your parameters correctly (for example, that you provided a float where you were supposed to provide a float).

But there is more to it than that. Even naive use of the type system is eerily good at catching bugs. Consider the Python code for destuttering a list (that is, removing sequential duplicates) as shown in Figure 3. It uses OCaml’s pat-tern-matching syntax to get access to the elements of the list. Here :: is the list constructor, and [] indicates an empty list. Thus, the [] case matches the empty list, and the x::y::rest case matches lists that have at least two elements, x and y. The variable rest refers to the (potentially empty) remainder of the list.

Like the Python example, this code fails to contemplate what happens when you get to the end of the list and have only one element left. In this case, however, you find out about the problem not at runtime but at compile time.

let rec destutter l = match l with | [] -> [] |x::[] ->x::[] | x :: y :: rest ->

if x = y then destutter (y :: rest) else x :: destutter (y :: rest)

 

The error here is a trivial one that would be found easily by testing. But the type system does just as well in exposing errors that are hard to test, either because they show up only in odd corner cases that are easy to miss in testing, or because they show up in complex systems that are difficult to mock up and exercise exhaustively.

Straight out of the box, OCaml is pretty good at catching bugs, but it can do even more if you design your types carefully. Consider as an example the following types for representing the state of a network connection as illustrated in Figure 4.

figure 5. connection types revisited.

type connecting = { when_initiated: time; }
type connected = { last_ping : (time int) option;
session_id : string; }
type disconnected = { when_disconnected: time; }

type connection_state =
| Connecting of connecting
| Connected of connected
| Disconnected of disconnected

type connection_info = {
state: connection_state;
server: inet_addr;