The OCaml programming language

Why OCaml?

• OCaml occupies a sweet-spot in programming language design
  • expressiveness
  • practicality
  • efficiency

Expressiveness

• OCaml has a powerful (ML-based) type system
• functional languages tend to be more expressive than average
• check out this plot of language expressiveness
  • http://redmonk.com/dberkholz/2013/03/25/programming-languages-ranked-by-expressiveness/

Practicality: multi-paradigmatic

• Not very comfortable with purely functional languages such as Haskell?
  • Don't panic!
  • You can fall back to imperative and/or object-oriented programming!
• Mix all these styles as you see fit.
• Gain the pros of each!

Efficiency: it's pretty fast

• static type checking means it doesn't need to happen at run-time
• easily interface with C code
• optimized native machine code
  • OCaml's compiler uses static program analysis techniques to optimize value boxing and closure allocation
• Xavier Leroy: "OCaml delivers at least 50% of performance of a decent C compiler"

Who uses OCaml?

• Jane Street Capital
• Citrix Systems
• Facebook
• Etc.

What has been made with OCaml?

• MirageOS
• Hack
• Flow
• Frama-C
• Coq

Features: strong static type system with type inference

• strong means types are checked to make sure they are used properly
• static means types are checked at compile-time
  • the type checker helps you find bugs before run-time
• the type checker makes refactoring code easier
• if OCaml code compiles, it will probably work the very first time
• type annotations are not required due to type inference

Strongly and statically typed

Let's download a url:

match download url with
| Success data -> process data
| Failure error_msg -> print_error error_msg

But the user might cancel the download! Luckily, the static type checker will catch this at compile-time:

Warning: this pattern-matching is not exhaustive.
Here is an example of a value that is not matched:
Cancelled

Okay, let's handle that:

match download url with
| Success data -> process data
| Failure error_msg -> print_error error_msg
| Cancelled -> stop_download ()

Type inference

let x = (1, 0.1, ["foo"], fun f x -> f x)
- : int * float * bytes list * (('a -> 'b) -> 'a -> 'b) = (1, 0.1, ["foo"], <fun>)

Notice the type polymorphism in the last tuple entry (it's just function application)! Polymorphic classes, class types, and objects:

let print_object_id obj = print_string obj#id
val print_object_id : < id : string; .. > -> unit =

Polymorphic variants:

let rec eval = function
| `Int n -> n
| `Add e1 e2 -> eval e1 + eval e2
| `Sub e1 e2 -> eval e1 - eval e2
([< `Add of 'a * 'a | `Int of int | `Sub of 'a * 'a ] as 'a) -> int = <fun>

Features: algebraic data types

We've already seen tuples, lists, and variants. There are also records. Say I want a polynomial type with integer coefficients. OCaml makes this easy.

type t = {
  n_vars : int;
  mon_map : int IntArrayMap.t
}

In words, a polynomial type is a number of variables n_vars and a map mon_map from int arrays to ints.

Options

A useful kind of algebraic data type is an option, defined with constructors:

type 'a option = None | Some of 'a

This is a good alternative to error handling. Just patten match on options to handle computations that might fail.

let scale_polynomial ?scalar poly =
  match scalar with
  | None -> poly
  | Some scalar -> multiply_each_coefficient_by scalar

Features: immutability by default

This is the way functional languages such as Haskell are, but OCaml supports mutability as well. Recall our polynomial type

type t = {
  n_vars : int;
  mon_map : int IntArrayMap.t
}

Say we had a polynomial

let poly = { n_vars = 2; mon_map = some_map }

We cannot change the record field values of poly (which can be dangerous!). If we want mutable record fields, we have to change the type explicitly:

type t = {
  mutable n_vars : int;
  mutable mon_map : int IntArrayMap.t
}

In general, we can specify and use mutable values like so:

let counter = ref 0 in
while (!counter < 42) do
  counter := succ !counter
done

This behaves like you would expect in any imperative language.

To summarize:

• ref declares a variable to be mutable and global
• we access a ref with !
• we mutate a ref with :=
• mutation acts by side effect, which means it is a function that returns the unit type
• so it is easy to know exactly when you are being naughty and using mutabality and imperative programming!

Features: Module system and functors

What are modules?

• abstract concept of modular programming
• decompose program into separate modules, each with their own purpose
• all ocaml programs are modules (.ml files)
• we can provide module specifications (.mli files) that provide abstraction
• parameterized modules are called functors

Example module specification

module type Stack_no_pop_t = sig
  type 'a t
  exception Empty
  val create : unit -> 'a t
  val push : 'a -> 'a t -> unit
end

If we had a module Stack (which would be written module Stack = struct let ... end), we could obtain a module that's like Stack, but hides pop:

module Stack_only_push = (Stack : Stack_no_pop_t)

Functors

• say we want a module in which we can find the greatest element of a list of elements of a given ordered type Here is the ordered type specification:

  module type Ordered_t = sig
    type t
    val compare : t -> t -> int
  end
  

  Then our functor could be

  module GreatestElem (Order : Ordered_t) = struct
    type elt = Order.t
    let greatest_elem xs = List.fold_left (fun curr next ->
      if Order.compare next curr = 1 then next else curr)
      (List.hd xs) xs
  end
  

Notes about functors and modules

• they are applicative, i.e. the same functor gives equal abstract types on equal inputs
• they are a powerful tool for generic programming
  • e.g. ocamlgraph defines graphs as functors
  • this is powerful because you can have graphs where the nodes and vertices can be all kinds of rich types (edges could be matrices and nodes vectors)
• OCaml also support first-class modules
  • these are modules that are actually values, and can be passed around like any other kind of data

One more note about functors (math)

• You may hear Haskellers/OCamlers talk about category theory and how functors are an important part of it
• There isn't really a deep connection between the functors of category theory and functors of OCaml/Haskell
• You don't need to know any category theory to understand OCaml or Haskell functors.
• OCaml functors are different from Haskell functors
  • Haskell's are more directly related to category theory (they are endofunctors on the category Hask of types and functions)

Features: Objects and classes

• Warning: forget everything you know about objects, classes, and types if you're coming from mainsteam OO languages such as Java or C++
• if you do, here are some things that might surprise you:
  • the type of an object isn't necessarily the class of an object
  • a class can inherit from another without being a subclass
  • a class can be a subclass without inheriting
  • we can make objects without classes

Objects: quick intro

• A stack object (how surprising!)

  let stack = object
    val mutable v = [1;2]
  
    method pop = match v with
    | x :: xs -> 
      v <- xs;
      Some x
    | [] -> None
  
    method push x = 
      v <- x :: v
  end
  

• now we can...

  stack#push 42
  stach#pop
  

Objects: are they really that great?

• Don't use them unless you really need to.
  • Then why are you telling us about them?
    • Because they can be useful.
• Why aren't they useful?
  • First-class modules can include types, which objects and classes cannot
  • In general, modules, functors, and types are more expressive

Objects: when to use them

• When you want to be contrarian. (Seriously, using objects is not very common OCaml practice.)
• More seriously: for open recursion through self
  • Use them when the problem could really benefit from open recursion
• Methods in an object can refer to other methods in the object prior to run-time

Classes: quick intro

class ['a] stack (init : 'a list) = object
  val mutable v = init

  method pop = match v with
  | x :: xs -> 
    v <- xs;
    Some x
  | [] -> None

  method push x = 
    v <- x :: v
end

• now...

  let s = new stack [1;2] in
  s#push 42
  

Classes: when to use them?

• Only use classes when inheritance is a big deal

• Simple example:

  class string_stack init = object
    inherit [string] stack init
  
    method print_angrily =
      List.iter (fun s -> print_endline (s^"!!!!!!!")) v
  end
  

• Example: Camlp4 defines classes that work on contentless abstract syntax trees. You can inherit AST traversal objects to implement the behavior you want, leaving the tedious traversal details to the class you inherited from.