A Hundred Lines of Caml

Elementary functions

Using the interactive system, let us define the square function and the recursive factorial function. Then, let us apply these functions to sample values:

        Objective Caml version 3.07+2

let square x = x * x;;
val square : int -> int = <fun>
let rec fact x =
  if x <= 1 then 1 else x * fact (x - 1);;
val fact : int -> int = <fun>
fact 5;;
- : int = 120
square 120;;
- : int = 14400

Automatic memory management

All allocation and deallocation operations are fully automatic. For example, let us consider simply linked lists.

Lists are predefined in Caml. The empty list is written []. The constructor that allows prepending an element to a list is written :: (in infix form).

let l = 1 :: 2 :: 3 :: [];;
val l : int list = [1; 2; 3]
[1; 2; 3];;
- : int list = [1; 2; 3]
5 :: l;;
- : int list = [5; 1; 2; 3]

Polymorphism: sorting lists

Insertion sort is defined using two recursive functions.

let rec sort = function
  | [] -> []
  | x :: l -> insert x (sort l)

and insert elem = function
  | [] -> [elem]
  | x :: l -> 
      if elem < x then elem :: x :: l else x :: insert elem l;;
val sort : 'a list -> 'a list = <fun>
val insert : 'a -> 'a list -> 'a list = <fun>

Note that the type of the list elements remains unspecified: it is represented by a type variable 'a. Thus, sort can be applied both to a list of integers and to a list of strings.

sort [2; 1; 0];;
- : int list = [0; 1; 2]
sort ["yes"; "ok"; "sure"; "ya"; "yep"];;
- : string list = ["ok"; "sure"; "ya"; "yep"; "yes"]

Imperative features

Let us encode polynomials as arrays of integer coefficients. Then, to add two polynomials, we first allocate the result array, then fill its slots using two successive for loops.

let add_polynom p1 p2 =
  let n1 = Array.length p1
  and n2 = Array.length p2 in
  let result = Array.create (max n1 n2) 0 in
  for i = 0 to n1 - 1 do result.(i) <- p1.(i) done;
  for i = 0 to n2 - 1 do result.(i) <- result.(i) + p2.(i) done;
  result;;
val add_polynom : int array -> int array -> int array
add_polynom [| 1; 2 |] [| 1; 2; 3 |];;
- : int array = [|2; 4; 3|]

Caml offers updatable memory cells, called references: ref init returns a new cell with initial contents init, !cell returns the current contents of cell, and cell := v writes the value v into cell.

We may redefine fact using a reference cell and a for loop:

let fact n =
  let result = ref 1 in
  for i = 2 to n do
    result := i * !result
   done;
   !result;;
val fact : int -> int = <fun>
fact 5;;
- : int = 120

Higher-order functions

There is no restriction on functions, which may thus be passed as arguments to other functions. Let us define a function sigma that returns the sum of the results of applying a given function f to each element of a list:

let rec sigma f = function
    | [] -> 0
    | x :: l -> f x + sigma f l;;
val sigma : ('a -> int) -> 'a list -> int = <fun>

Anonymous functions may be defined using the function construct:

sigma (function x -> x * x) [1; 2; 3];;
- : int = 14

Polymorphism and higher-order functions allow defining function composition in its most general form:

let compose f g = function x -> f (g x);;
val compose : ('a -> 'b) -> ('c -> 'a) -> 'c -> 'b = <fun>
let square_o_fact = compose square fact;;
val square_o_fact : int -> int = <fun>
square_o_fact 5;;
- : int = 14400

The power of functions

The power of functions cannot be better illustrated than by the power function:

let rec power f n = 
    if n = 0 then function x -> x 
    else compose f (power f (n - 1));;
val power : ('a -> 'a) -> int -> 'a -> 'a = <fun>

The n^th derivative of a function can be computed as in mathematics by raising the derivative function to the n^th power:

let derivative dx f = function x -> (f (x +. dx) -. f x) /. dx;;
val derivative : float -> (float -> float) -> float -> float
let sin''' = power (derivative 1e-5) 3 sin;;
val sin''' : float -> float = <fun>
let pi = 4.0 *. atan 1.0 in sin''' pi;;
- : float = 0.999998972517346263

Symbolic computation

Let us consider simple symbolic expressions made up of integers, variables, let bindings, and binary operators. Such expressions can be defined as a new data type, as follows:

type expression =
  | Num of int
  | Var of string
  | Let of string * expression * expression
  | Binop of string * expression * expression;;

Evaluation of these expressions involves an environment that maps identifiers to values, represented as a list of pairs.

let rec eval env = function
  | Num i -> i
  | Var x -> List.assoc x env
  | Let (x, e1, in_e2) ->
     let val_x = eval env e1 in
     eval ((x, val_x) :: env) in_e2
  | Binop (op, e1, e2) ->
     let v1 = eval env e1 in
     let v2 = eval env e2 in
     eval_op op v1 v2

and eval_op op v1 v2 =
  match op with
  | "+" -> v1 + v2
  | "-" -> v1 - v2
  | "*" -> v1 * v2
  | "/" -> v1 / v2
  | _ -> failwith ("Unknown operator: " ^ op);;
val eval : (string * int) list -> expression -> int = <fun>
val eval_op : string -> int -> int -> int = <fun>

As an example, we evaluate the phrase let x = 1 in x + x:

eval [] (Let ("x", Num 1, Binop ("+", Var "x", Var "x")));;
- : int = 2

Pattern matching eases the definition of functions operating on symbolic data, by giving function definitions and type declarations similar shapes. Indeed, note the close resemblance between the definition of the eval function and that of the expression type.

Elementary debugging

To conclude, here is the simplest way of spying over functions:

let rec fib x = if x <= 1 then 1 else fib (x - 1) + fib (x - 2);;
val fib : int -> int = <fun>
#trace fib;;
fib is now traced.
fib 3;;
fib <-- 3
fib <-- 1
fib --> 1
fib <-- 2
fib <-- 0
fib --> 1
fib <-- 1
fib --> 1
fib --> 2
fib --> 3
- : int = 3