One hundred lines of Caml

Elementary functions

Using the interactive system, I define the square function, and the recursive factorial function. Then I try my new functions with some examples:

>       Caml Light version 0.74

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

Automatic memory management

All allocation and deallocation operations are fully automatic. I give the example of lists.

Lists are predefined in Caml, the empty list is [], and the list constructor is denoted by :: (binary and infix).

#let l = 1 :: 2 :: 3 :: [];;
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 with two recursive routines, using pattern matching on lists.

#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;;
sort : 'a list -> 'a list = <fun>
insert : 'a -> 'a list -> 'a list = <fun>
#sort [2; 1; 0];;
- : int list = [0; 1; 2]
#sort ["yes"; "ok"; "sure"; "ya"; "yep"];;
- : string list = ["ok"; "sure"; "ya"; "yep"; "yes"]

Imperative features

Polynomes being represented as arrays, I add two polynomes by first creating the resulting polynome, and then filling its slots with two ``for'' loops.

#let add_polynom p1 p2 =
 let result = make_vect (max (vect_length p1) (vect_length p2)) 0 in
 for i = 0 to vect_length p1 - 1 do result.(i) <- p1.(i) done;
 for i = 0 to vect_length p2 - 1 do result.(i) <- result.(i) + p2.(i) done;
 result;;
add_polynom : int vect -> int vect -> unit
#add_polynom [| 1; 2 |] [| 1; 2 |];;
- : int vect = [|2; 4|]

Accumulators are defined in Caml using updatable cells, named references.

ref init returns a new cell with initial contents init,
!cell returns the actual contents of cell, and
cell := val updates cell with the value val.

I define fact with an accumulator and a ``for'' loop:

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

Functionality

No restrictions on functions, that may be higher-order. I define the sigma function that returns the sum of results of applying a given function f to each element of list:

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

Temporary functions may be defined as no-name functional values with the ``function'' construct:

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

Combined with polymorphism, higher-order functionality allows the definition of the functional composition of two functions.

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

Symbolic computation

I consider simple symbolic expressions with integers, variables, let bindings, and binary operators. These symbolic expressions are defined as a new data type, using a type definition:

#type expression =
 | Num of int
 | Var of string
 | Let of string * expression * expression
 | Binop of string * expression * expression;;
Type expression defined.

Symbolic evaluation of these expressions involves an environment which is just a list of pairs (identifier, value).

#let rec eval env = function
  | Num i -> i
  | Var x -> 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);;
eval : (string * int) list -> expression -> int = <fun>
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

In addition to data type definition, the pattern matching facility leads to an easy way of defining functions on symbolic data. For instance, from the type definition of expressions:

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

we get the skeleton of the printing procedure for expression:

let print_expression = function
 | Num int ->
 | Var string ->
 | Let (string, expression1, expression2) ->
 | Binop (string, expression1, expression2) ->

We just have to complete the pattern matching clauses to get the printing routine:

#let rec print_expression = function
 | Num int -> print_int int
 | Var string -> print_string string
 | Let (string, expression1, expression2) ->
    print_string "let "; print_string string; print_string " = ";
    print_expression expression1; print_string " in ";
    print_expression expression2
 | Binop (string, expression1, expression2) ->
    print_string "("; print_expression expression1;
    print_string (" "^string^" ");
    print_expression expression2; print_string ")";;
print_expression : expression -> unit = <fun>
#print_expression (Let ("x", Num 1, Binop ("+", Var "x", Var "x")));;
let x = 1 in (x + x)- : unit = ()

Parsing data

Caml offers a rich panel of parsing tools: it includes traditional lex and yacc interfaces, but also an original stream primitive data type, with its associated ``functional parsing'' technology.

Writing a parser is always a bit technical, you may like to omit it. However, you can find a parser for the above expression data type.

Elementary debugging

Just for completeness, let me show you the simplest way to debug programs, using the trace facility:

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

More

If you know the lambda calculus, click here to see a more significative example of symbolic data manipulation using Caml: the definition of lambda-terms with their associated lexical analyzer, parser and printer, within about fifty lines of Caml code.