Bindings, Expressions and Patterns in OCaml
It is very interesting how programs in OCaml are expressively constructed from few bindings, expressions and matching patterns. Bindings let's us assign a name to an expression or a function. These bindings can be used in other expressions to build compound expressions. Expressions can include other expressions. This recursive syntax allows to flexibly create our programs. Let's take a look.
Three types of bindings are good to start our work - variable bindings, function bindings and recursive function bindings:
(* variable binding *) let x = e (* function binding *) let f x1...xn = e (* recursive function binding *) let rec f x1...xn = e
In the first above code,
e is the expression that is evaluated to a value
v which is then bound to the variable
x. For both types of function bindings, there is no expression evaluation. Instead,
e provides the structure of a computation that uses parameters
x1...xn. This expression later can be evaluated using arguments that are passed during function application expression (discussed below).
Five expression types will give us a good start - arithmatic and logical operations, if..then..else, let, match..with and function application:
(* arithmatic and logical operations *) e1 op e2 (* if..then..else *) if e1 then e2 else e3 (* let *) let x = e1 in e2 (* match *) match e with p1 -> e1 | p2 -> e2 |... | pn -> en (* function application *) e0 e1...en
In the above snippet, arithmatic and logical expressions takes the form
e1 op e2 where
e2 are sub-expressions and
op is some operator. For example 2 + 3, (5 mod 2) + (3 / 2). For if..then..else, e1 must evaluate to
bool and e2,e3 can be of any type as long as both are of same types. Let expression is similar to let binding.
e1 is evaluated to
v that is then bound to variable
x. This variable is then used in
e2 which if evaluates to a value
v2 will be the result of entire let expression. Match is the most interesting, where we see patterns p1…pn on the left side of arrows while expressions e1…en on the right side. Here, expression
e is evaluated to value
v which is then matched with one of the patters (see below for discussion). Once a match is found, the corresponding expression is evaluated to a value
vn which becomes the value of the entire match expression. Finally, in the function application expression, e0 is evaluated to a value which should be a function binding in the scope. Then, e1..en are all evaluated to values v1..vn, which after type checked with the function binding, are bound to the functions’ parameters x1..xn and added to the environment of function body expression. Then function body is evaluated to a value,
v which becomes the value of function application.
In the match expression above, let's see what type of patterns p1..pn can match to.
(* anything *) _ (* either p1 or p2 *) p1 | p2 (* all lowercase letters *) 'a'..'z' (* all uppercase letters *) 'A'..'Z' (* empty list *)  (* non-empty list *) h::t (* one element list *) [h] (* list containing at least 2 elements *) a::b::t (* matching more than 1 thing *) a, b
These are just a few that will get us going but there potentially are many others.
(* ex1: absolute value of a number *) (* a function binding with if..then expression body*) let abs x = if x < 0 then -1*x else x (* ex2: test if first number in a pair is odd *) (* a function binding with pattern matching pair *) let first_odd x = match x with (a,_) -> a mod 2 <> 0 (* ex3: sum of square of odd numbers in a list *) (* a recursive function binding with 2 local function bindings, a list match expression and final expression containing function application expression and if..then expression *) let rec sum_square_odd l = let square x = x*x in (* local function binding *) let isodd x = x mod 2 <> 0 in (* another local function binding *) match l with  -> 0 (* if list is empty then evaluate to 0 *) | h::t -> if isodd h (* if list is non-empty then check if head is odd *) then square h + sum_square_odd t (* recursively call sum_square_odd on tail *) else sum_square_odd t
In example 1, a function is defined using if..then expression. In example 2, a function is defined using a match expression where the argument is matched with a tuple containing 2 elements. Since only first element is of interest to us, first value is bound to
a while the second is matched with
_ since we don't need it in our expression later (remember
_ matches anything, which has an interesting consequence of getting a polymorphic function - the 2nd element can be of any type!). In the final example, we mix more elements together that evaluates sum of squares of elements in a list only if the elements are odd integers. It uses 2 local function bindings,
isodd, meaning these are only available to
let expressions inside our function but not anywhere else in our program. The argument is then matched with a list. If the list is empty, it evaluates to 0. If the list is non-empty, 2 bindings are created -
h bound to the first element of the list,
t bound to the remaining list.
h is then tested using function application expression to check if it is odd, it is squared and added to result of recursively calling our function on tail
t otherwise it is omitted in the next recursive call. Pretty neat!