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.

Bindings

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).

Expressions

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 e1 and 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.

Pattern Matching

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.

Some examples

(* 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, square and 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!