OCaml: An Introduction

OCaml is "an industrial-strength functional programming language with an emphasis on expressiveness and safety." "Functional" here means two things. First: Functions are first-class so we can do higher-order programming.¹ First-class functions aren't unique to OCaml; Python has them:²

def foo(x):
    return x + 1

def bar(f, x):
    return f(x + 2)

assert(bar(foo, 0) == 3)              # function passed as an argument
assert(bar(lambda x : 3 * x, 1) == 9) # anonymous function created in-line

We would write the same program in OCaml as:³

let foo x = x + 1

let bar f x = f (x + 2)

let _ = assert (bar foo 0 = 3)
let _ = assert (bar (fun x -> 3 * x) 1 = 9)

Second: Programming is function composition. At a(n unreasonably) high level of abstraction, a program is a function that takes some inputs and produces an ouput. In imperative PLs like Python, we describe what to do with/to the inputs to produce the output; we think of a program as a sequence of imperatives to be carried out by the computer.

def sum(l):
    out = 0
    for x in l:        # for every element of l
        out = out + x  # do the "add it to out" thing
    return out

assert(sum([1, 2, 3, 4, 5]) == 15)

In purely functional PLs⁴ there is no notion of state or side-effects. Where this counts: no loops.⁵ We don't think in terms of doing things, but rather in terms of constructing things that describe the values we want. And that construction comes from building new functions from old ones (i.e., composing mathematical functions) often relying heavily on recursion.⁶

let rec sum_helper l out =
  match l with   (* this is called "pattern matching" *)
  | [] -> out
  | x :: xs -> sum_helper xs (out + x)

let sum l = sum_helper l 0

let _ = assert (sum [1; 2; 3; 4; 5] = 15)

We can also write the above program equivalently in Python:

def sum_helper(l, out):
    if l == []:  # Python has no pattern matching...bummer
        return out
    else:
        x, xs = l[0], l[1:]
        return sum_helper(xs, out + x)

def sum(l):
    return sum_helper(l, 0)

assert(sum([1, 2, 3, 4, 5]) == 15)

but for reasons we'll come to later, you shouldn't do this.⁷

Next: "safety" is to do with the fact that OCaml is strongly and statically typed. The notion of strong typing is so vague as to verge on being useless. At the risk of circularity, a language enjoys strong typing if it has type errors, i.e., it'll sometimes complain at you when it's expecting a thing of some kind and finds a thing of some other kind. In this regard, Python is strongly typed.

2 + "2"

# TypeError: unsupported operand type(s) for +: 'int' and 'str'

But Python is certainly not a language lauded for its safety.⁸ This is for a slew of reasons, but when it comes to typing it's to do with the fact that Python is dynamically typed. Semi-formally speaking, this means parameters can be bound to objects of different types throughout the execution of a program.

x = 2
x = "3"
assert (x + "4" == "34")

Practically speaking, this means that you won't discover your type errors until it's too late run-time.

And, while we're at it, another thing that makes the claim of strong typing seem disingenuous: Python has implicit type conversion, and a pervasive form of function overloading. This means some functions/language constructs are quite happy being given surprising (combinations of) values.

assert (2 + 2. == 4.)       # there's an int-float addition I guess
assert (False if "" else 2) # "" is falsey and 2 is truthy I guess

So the degree to which Python throwing type-errors is useful seemingly degrades.

Aside. Those of y'all who actually like programming and have been fed on a steady diet of Python⁹ are likely thinking: that's not so bad right? In fact, it's great. In fact, I trust you less now that you're telling me this is a bad thing. Fair, I'm also straw-man-ing somewhat. I just ask that you suspend your disbelieve. What I and many folks find is that these "conveniences" are at best unnecessary and difficult to reason about theoretically, and at worst make programs more prone to run-time errors.¹⁰

OCaml is really strongly typed.¹¹ In fact, every well-formed piece of an OCaml program has a type.¹² And everything has its type in perpetuity. No variable retyping, no implicit coercion, no sequence of operations that makes a thing sometimes this type, sometimes that type (because, again, there's no notion of "sequence of operations").

And, the kicker, these types can be determined at compile-time; OCaml is statically typed. So we catch type errors when we're programming and not after we pushed changes to production.¹³

let x = 2 in
let y = "2" in
x + y

(*
Line 3, characters 4-5:
3 | x + y
        ^
Error: The value y has type string but an expression was expected of type int
*)

Aside. This is made possible by a potentially more fundamental feature of OCaml: everything in OCaml is an expression. OCaml is like a super-powered calculator; a "standard" calculator evaluates arithmetic expressions to numerical values, whereas OCaml evaluates OCaml expressions to OCaml values.

How about "expressiveness"? There are a couple ways to read this, but we'll focus on how it pertains to types.¹⁴ Because everything has a type, and OCaml has functions like any reasonable PL, it follows that OCaml functions have types.

let is_even (x : int) : bool =  (* we can explicitly type annotate *)
  x mod 2 = 0

let _ = assert(is_even 100)
let _ = assert(not (is_even 101))

is_even is a function that takes an int and gives back a bool, and it's type is written int -> bool. is_even will always do this. It will behave this way in perpetuity.

Python has functions, and these functions have types, but with a major caveat.

def is_even(x):
    return x % 2 == 0

assert(is_even(100))
assert(not is_even(101))

The type of is_even in Python is: function. The only thing that Python can know about is_even is that it's a function. Python can't possibly know anything else because it doesn't check at compile time how the function behaves. In this sense, Python types are strictly less expressive than OCaml types (function says a whole lot less than int -> bool).

Can't stress enough, this is major theme of the course: the more expressive our types, the more we can say and verify about our programs at compile-time, the more predictable our programs are, the fewer the Heisenbugs we introduce, the happier we are, the better the world is.

Aside. I know what some of y'all are thinking at this point: I already know a strongly and statically typed language. It's Java and it's great. I have many thoughts, most of which I'll refrain from voicing. For now I'll just point out that, as you will come to notice, OCaml programs have the potential to be far less verbose than Java programs.¹⁵ This is because of OCaml's Hindley-Milner-style type inference, a feature we'll spend a lot of time on in this course. This feature gives OCaml verbosity comparable to Python and type guarantees comparable to (read: better than) Java.

And "industrial-strength"? It's got a solid toolchain, all the features you want in a PL (plus some you didn't know you wanted), and it's surprisingly fast. Of course racing PLs is a fools errand, but forced to categorize I'd say natively compiled OCaml rides with Go or Swift, competitive with (but slower than) C or Rust in rare cases (beating C on usability and Rust on compilation time).

Thus far I've been praising OCaml at the expense of the other household PLs.¹⁶ I'm well aware OCaml is not everyone's favorite PL, even after this course. Beyond the glories expounded above, there's a good reason──besides the all-too-common you'll-be-better-for-it argument──that we're using OCaml over something like Python or Java (despite these being the languages you've seen throughout the major so far).

Firstly, OCaml (and friends) has a dead-simple theoretical model (at least at its core). This is ostensibly a PL course.¹⁷ It's no coincidence that nearly all PL research is done in functional PLs. Using OCaml, the language in which we write code simultaneously acts as a case study of the concepts we learn.

Secondly, Functional PLs are well-suited for building definitional interpreters. It's been joked (by whom I can't for the life of me remember) that functional PLs are domain specific languages (DSLs) for building compilers and interpreters. In this course we're programming to learn (as opposed to learning to program) by building prototypes of the PLs we study mathematically. Trust me, it's easier to do that in OCaml than in Python or Java (or try it yourself (and prove me wrong)).

I'll say write it again: this is a PL course. Our goal is not to make you expert OCaml programmers.¹⁸ Our goal is to study PLs as mathematical objects. Through this lens, we're not interested in PL "conveniences" (i.e., IDE support, fast compiler, clean syntax, useful built-in types, nice libraries, readable error messages) but rather in general language constructs, the kinds of "killer features" that help us express ourselves in code and that generalize to new PLs we want to design.

The pitch of the course is essentially this: OCaml has three killer features, all of which have made some appearance in the above introduction.¹⁹

1. Higher-order Programming. Despite the fact that nearly all modern programming languages support higher-order functions, this has not always been the case. The evaluation model changes once you have to treat functions as objects in their own right, particularly when it comes to recursion.
2. Pattern-Matching. A surprisingly under-appreciated feature that appears in most functional FPs.²⁰ Algebraic data types (ADTs) let us express enumerations and products in a clean way that also allows for recursive data types (e.g., lists, trees). Pattern matching (and, perhaps more importantly, exhaustiveness checking) gives us a safe mechanism for working with these bespoke data types in a way that the type checker can validate (e.g., it can check that you've handled all cases of your data, no missing cases, no additional coverage analysis).
3. Parametric Polymorphism and Type Inference. These in tandem give languages like OCaml the strong type guarantees, code reuse, and simplicity/readability that the FP community has come to love. The "polymorphism" part lets us write code that is an general as possible (along the lines of Java generics) while being type safe, and the "inference" part lets us not think about being as general as possible while were programming; OCaml will infer the most general types for the programs you write (where "most general" can be taken in a well-defined mathematical sense). It strikes a delicate balance, and does so, in my humble opinion, very satisfyingly.

These features form an approximate roadmap for the course. We'll first come to understand how to use these features, how they make our lives easier when we write code, how help us write simpler and safer code. We'll then come to understand how these features work, how they're defined mathematically, and how they're implemented in definitional interpreters.

• OCaml: Learn
• The OCaml system
• OCP: Better Programming Through OCaml
• RWO: Prologue
• Why OCaml? (Yaron Minsky)