Objective Caml

What is Objective Caml?

There are many valid answers to this question. To most programmers, the most important point is: what does it have to offer? So, if we look at it in this way, it is:

Is it "object oriented"?

Some people like to stick labels onto programming languages, that is, classify them as, for example, "imperative" or "object-oriented" or "logic-based". Actually, this is somewhat misleading, as these terms rather describe different strategies to approach a problem, and the structure of real-world problems is often such that they can be decomposed into sub-problems that may suggest very different strategies. So, even though C is not considered to be an object-oriented language, there are many places in a complex piece of software such as the Linux kernel that are designed in an object-oriented way, such as the virtual file system interface specification. Likewise, C++ is not usually considered to be a "functional" language, but there are libraries, such as the Boost Lambda Library which greatly simplify using functional techniques with C++. On the other hand, one of the most flexible object systems around is part of the functional language (Common) LISP: CLOS.

So, this classification issue is mostly about what approaches and techniques a given language emphasizes. Seen that way, OCaml may be regarded as belonging to one family of functional languages, the so-called "statically typed strict functional languages", while also featuring the usual basic object-oriented concepts: there are syntactic structures that deal with objects, classes, inheritance, methods, and so on.

In what follows, we will not put too much emphasis on the object-oriented side of OCaml. The major reason is that this is pretty much standard, so everyone having learned OO before should find it easy to adopt the particular OCaml syntax for method invocation and such. Those who did not have any previous exposure to object-oriented programming on the other hand cannot be expected to master it in a few lessons, so there would be little point in trying to teach that. Actually, if OCaml were just another object oriented language which we fancy for the sole reason that it gives us funky blue objects rather than the boring green objects from C++, we never would have chosen it in the first place! There is more to this particular language, and this is precisely the reason why we consider it a good choice for our project. So, let us rather spend our time talking about some powerful techniques that are not widely discussed with other, more mainstream languages, but very natural with OCaml.

A brief history of OCaml

For many of today's programming languages, there was a solitary large problem that helped bringing them into existence by pointing at some important ideas: C was born because a sufficiently abstract language was needed to port an operating system between different machine architectures (cf. The Development of the C Language). Perl was written because Larry Wall had to struggle with scripting tasks that became too complex to be done with the prehistoric "Unix swiss army knife" awk. The same is true for the ancestor of OCaml, which is the ML language, and it is presumably quite useful to know a bit about this history to understand how some of the fundamental concepts that may seem somewhat strange during first contact with ML were "discovered".

On Theorems and Proofs

Humans do formal reasoning, humans make mistakes, hence humans make mistakes at formal reasoning. Still, with formal reasoning being formal, it should be possible to have some kind of machine that checks a properly written down formal proof for its correctness. Let us call a program that can do this a "proof checker". Now, using a proof checker certainly is a lot of work, as first of all, a proof has to be brought into a machine-readable form, so we have to be far more elaborate than in a mathematical textbook, where we may just say "proof by induction" when the reader will be able to work out the details of his own. As many proofs are repetitive in the sense that there are re-occurring patterns of reasoning, it would be nice to have something more like an "automatic proof assistant", which allows construction of parts of a proof by just specifying some general method and works out the details of its own. Of course, even more convenient would be a theorem proving program, but combinatorical explosion perhaps prevents this fro working effectively. There is no substitute for human intuition in proving theorems.

When working with theorems and partial proofs, we need some kind of "language" to assemble larger proof strategies from smaller ones, and talk about terms and theorems. This language should be both very flexible and very abstract, as we will have to express very abstract ideas in it. A fundamental point which is perfectly natural for mathematicians is that a theorem is something very holy: having a theorem means that I can handle some situations by applying that theorem instead of having to go through a whole sequence of maybe even prohibitively complicated reasoning. Therefore, it is very natural to try to lift this concept of a theorem directly onto the machine. So, the machine should have some knowledge that any term that has theorem status is true, without having to go through all the atomic steps of a proof that demonstrate this.

Note carefully that a simple-minded object oriented approach cannot do this: the object oriented point of view presumably should be that a theorem is an entity (hence, object) for which it makes sense to ask whether it is true - which therefore should have an "am_I_true" method. According to the object-oriented philosophy, I could always subclass a "theorem" with a class that provides a specialized "am_I_true" method, and hence have objects which are theorems (trough "is-a" inheritance), but not necessarily true - an unsatisfactory state of affairs (vulgo: complete rubbish).

Hence, we need something else. The main objects of our studies are theorems, terms, and proof strategies. Evidently, these will furthermore also involve natural numbers, boolean values, and maybe some other fundamental data types, as well as tuples, sets, and similar "containers". Let us consider a simple example and try to interpret the monotonicity of addition as a proof strategy. It says that, given two theorems of the form "a<b" and "c<d", we have a new theorem "a+b < c+d", so this is a function mapping a pair of theorems to a new theorem. Now, if we attach types to our values, the system can watch that this function cannot be applied to get a theorem from just a pair of terms: we have to feed it with theorems to get a new theorem.

Simple proof strategies, their types, and examples
Monotonicity of addition (theorem, theorem) -> theorem (a<b , c<d) -> a+c < b+d
Proof by induction
-> theorem
 For_all(k): (Sum(n=0..k;n) = k(k+1)/2
     => Sum(n=0..k+1;n) = (k+1)((k+1)+1)/2))
-> For_all(k): Sum(n=0..k;n) = k(k+1)/2
A is A term -> theorem a -> a=a

So, if we take care that the only way to obtain a theorem is via a valid proof strategy, or from axioms, then we just know by the fact that some value has the type theorem that it has to represent something true. It may happen that a function claiming to produce a theorem fails to do so, because it does not terminate. But if we get something, and it's a theorem, it must be true.

This is the essential idea behind Milner's LCF - see the paper A Metalanguage for interactive proof in LCF for further reading.

Actually, if one looks at one of the real ML-based proof assistants, all this is a somewhat gross over-simplification. Things are actually quite a bit more involved, but the broad idea is right. In a certain sense, one could say that the type system fulfils the old philosopher's dream of creating a language in which it is not possible to lie. For those who want to know more about proof assistants, it may be interesting to have a look at The HOL Light manual (which, by the way, also contains a brief introduction to CAML, which is a very very close relative of OCaml).

Types are very important with OCaml, and you will experience this of your own very soon. But other languages do have types as well, so in which way does this differ from the type systems of C, or Python? Giving a good answer would take quite some time, so I will instead just provide some food for thought: First, how would one define something like tuples in C? How could one make sure that a tuple of one kind then cannot be passed into a function expecting a tuple of a different kind? And when does the type checking happen? Is it possible to pass a value of the wrong type into a function which will eventually only find out about this much later, during a lengthy computation?

Now, this may all sound very interesting, but raises the question: why does it matter to us in engineering, with primarily numerical applications in mind? I will elaborate on this in more detail, but for now, the brief answer is: mathematical proof strategies are among the most abstract things one can imagine. During their work n formal proof systems, people found out that the "Meta Language" with which they manipulated the "object language" entities - theorems - actually is a very convenient and useful tool to handle far more real world problems than they were interested in initially. Actually, for a system that makes it easy and convenient to work with entities even as abstract as mathematical theorems, it should be a piece of cake to deal with the algorithmically nontrivial parts of many problems. In particular, it should especially make it easy to write software in a much more abstract and generic way: instead of solving just one specific problem - say, generating a stiffness matrix for the Laplacian on a mesh with first order elements, it will become feasible to attack the much more general problem of discretizing any first or second order differential operator on a mesh of any dimension, with any element order.

Of course, one may say that from the machine perspective, there is nothing that can be done in OCaml which cannot be done in C. After all, one uses just a C compiler to build the OCaml compiler from its sources, so one may regard OCaml as being nothing else but a collection of conventions that allow one to use a different notation for programs. So, technically speaking, it is not impossible to write highly abstract software in C, or even FORTRAN. However, programming is a human activity, so the only relevant question is: what can be achieved with reasonable human effort? So, if one insists that everything can be done in C, that's certainly true, but by the same token, one could claim that there is no need for theorems in mathematics, as one may always analyze any given mathematical problem by just applying a long sequence of axioms, definitions, and deductions.

But back to OCaml history: ML was developed in Edinburgh, evolved over the years, and got more people interested in that approach, especially concerning applications to the field of reasoning about programs, like compiler writers do. Hence, ML was adopted by the french INRIA institute, who actually wanted to use it for real applications, and so then evolved it further into the dialect OCaml, which is still developed and maintained by INRIA today. By now there are a few major noteworthy applications written in OCaml that nicely demonstrate its potential in the battlefield, among them the HeVeA LaTeX/HTML translator, the unison file synchronizer, the FFTW Fourier Transform library, and some more. For further examples, see e.g. INRIA's applications page.

Let us conclude this excursion with a reference to http://delysid.org/programming.html, which contains a very good brief history of a number of interesting programming languages, including the ML family.

The Language

As alluded to earlier, the type system of OCaml will be quite interesting, as it is very different from the type system of other languages. For now, we will limit ourselves to the discussion of the "Core Language", which is, up to syntactic nuances, the part of the language that is shared between all ML dialects, such as OCaml and SML.

Fundamental data types

By "fundamental" data types, we mean built-in data types known to the system right from the beginning. However, it is easy to extend OCaml with new data types that behave in any relevant aspect like these fundamental ones. Every piece of data will have some memory representation, and we will consider a data type as being "fundamental", or rather "atomic", if it is not possible to change the value of an entity through any assignment operation. This may sound very strange at first, especially from the perspective of a C programmer where something like this effectively does not exist, but will become relevant later when we talk in more detail about assignments.

Fundamental data types of OCaml
intMachine integers17Range: -2^30..2^30-1 (on 32 bit machines)
boolBoolean valuestrue
floatIEEE 754 Double-precision floatingpoint values-2.38e9
char8-bit Characters'a'
unitType with just a single value()May also be regarded as the unique 0-tuple.

Even with those few types, there would be a lot to say about special quirks of OCaml. For example, while -1 is a valid literal for an integer number, +1 is not. Quite in general, we will not go into such language details in this course, whose main objective is to present the structure of the language, and show how one should approach and analyze the real problems, not the artificial ones introduced by the language. Now, take your C++ bible and check which exercise questions deal with real world issues and which deal with mundane quirks of the language.

Some "containers"

From simple, atomic data, we build more complex values by sticking them into containers. For now, we will limit ourselves to just four: strings, tuples, arrays, and lists. There are of course more, such as records (quite similar to C structures), and some very ML-specific ones, which we will discuss later on in this course. For now, we want to have something that helps us to get going with the language.


Strings behave like fixed-size vectors of 8-bit characters. One of the somewhat unfortunate limitations of OCaml is that on 32-bit systems, the maximal length of a string is slightly less than 16 MB, but in practice there usually are ways to work around this if it becomes an issue. Nevertheless, it should not be like that. The notation is as usual, with "hello" being a five-character string. Escape sequences like \n, \t, \xf2 and such work as expected, but instead of octal triplets, OCaml uses decimal triplets, so \n is not \012 but \010. The name of the type is string.


Tuples are fixed-length ordered sequences of values, which may be of different type. It is not possible to assign to a tuple, but we will have to say more about the fine points of this statement later. For now, it is better if we do not think too much at all about modifying values. The notation is like (17,true,"hello"), that is, a tuple is a comma-separated sequence of values enclosed in round parentheses. Some language lawyers may say that in OCaml, these parentheses are optional in many situations, but as they are mandatory in any other relative of OCaml, it will simplify communication with other programmers to always place them. The type of this particular tuple would be int * bool * string, and other tuple types are constructed likewise. The type of the tuple (1,(true,2.3),'x') would be int * (bool * float) * char. The unit value () may be regarded as being the empty tuple, and one-tuples do not exist: (x) is just the same as x.

How can one extract data from the various slots of a tuple? Here, OCaml uses an approach that may appear somewhat strange at first, but actually turns out to be quite convenient in many situations: structural matching. We will just give an example (which, actually, no advanced OCaml programmer would write that way) to demonstrate how this looks like and define a function that maps a triple to its middle component:

Structural Matching - mapping a triple to its middle component

let tuple_2_of_3 = fun (a,b,c) -> b;;

For now, the reader should just try to generalize this example and define similar accessor functions whenever he needs one. We will later on learn how to write this in a more elegant way.


Arrays behave like fixed-length vectors of values of homogeneous type. It is possible to assign to array entries, and the time for array lookup and assignment will not depend on the index (up to caching effects, of course). On 32 bit systems, the memory representation of an OCaml array cannot be longer than about 16 MB, and as every array entry occupies either four bytes or eight (only for float arrays), such machines have an array length limitation of about 4 million entries (2 million for float arrays). This certainly is not very well suited for large numerical data, but there is a specialized kind of arrays for that. These generic arrays can hold just about anything, such as tuples which are pairs of integers and strings. The notation is like [|1;2;5|], and array elements can be accessed with the special syntax a.(5). However, lisp hackers may believe to have good reasons to use a function here and prefer to write Array.get a 5. Note that array index counting starts at 0, as in C (which, by the way, is the only reasonable convention, since array indices starting at 1 would require crazy correction factors when one maps indices from two-dimensional arrays to linear indices). The type of the array [|1;2;3|] is int array, the type of the array [|(1,true);(2,false)|] is (int * bool) array.


OCaml lists are variable-length singly linked lists of homogeneous values. While access to the n-th element requires the more time the larger n, as pointer sequences have to be chased, it is very easy (small constant time effort) to compute a new list from a given list by appending or removing an entry at the list's head. Note that an array would have to be copied for this. It is possible (and not infrequently seen) that multiple lists share a common tail. Just like tuples, lists are non-modifiable, and one normally uses funny syntactic constructs to get data from a list. The notation is like [1;2;3], and this particular list would have the type int list.

For the time being, we will use the comparison x = [] when we have to find out whether a list is empty, and the functions List.hd and List.tl to get the head element, respective tail, of a list. When x is a list, and we want another list that is just x, extended with a new head h, we just write h::x for this new list. Note that computing such a new and extended list does not change the list x!

Running the interpreter

OCaml provides both a compiler and an interpreter. For now, we will limit ourselves to playing around with the interpreter at its interactive command prompt. But first of all, we will build ourselves a custom interpreter that already comes with all the useful libraries which we are going to use pre-loaded. So, we first create an ocaml-tutorial directory and make that special extended interpreter in there:

Setting up the scene

~$ mkdir ocaml-tutorial
~$ cd ocaml-tutorial/
~/ocaml-tutorial$ ocamlmktop -o ext-ocaml unix.cma nums.cma str.cma graphics.cma
~/ocaml-tutorial$ ls -la
total 1120
drwxr-xr-x   2 tf tf    4096 2005-12-08 15:25 .
drwxr-xr-x  20 tf tf    4096 2005-12-08 15:24 ..
-rwxr-xr-x   1 tf tf 1134018 2005-12-08 15:25 ext-ocaml
~/ocaml-tutorial$ ./ext-ocaml
        Objective Caml version 3.08.3

# ^D

Like any nicely behaving Unix program with a toplevel, sending an End-Of-File (Control-D) at the prompt will quit the interpreter. A running computation can be interrupted with Control-C. Some people may find it useful to start our OCaml interpreter from within an (x)emacs shell by entering M-x shell in (x)emacs. The advantage of this is that one can use all of emacs' buffer editing facilities on the history transcript of an interactive session. (Note: if a "ls" in an emacs shell produces trash, try telling the shell to "unalias ls".) There is a normally even better way to use Emacs to interoperate with OCaml, the so-called "Caml mode". We will look into this later.

Now, at the top level, OCaml just behaves like a "pocket calculator on steroids" that not only knows about numbers, but just as well about many other kinds of data. One should know:

So, let us just give a few definitions and play with them:

Playing with the interpreter

~/ocaml-tutorial$ ./ext-ocaml 
        Objective Caml version 3.08.3

# 2*3;;
- : int = 6

# 1+2+3+4+5+6+7+8+9+10;;
- : int = 55

# let lightspeed = 299792458.0;;
val lightspeed : float = 299792458.

# let light_time_to_sun = 149.6e9 /. lightspeed;;
val light_time_to_sun : float = 499.011886416435459

# light_time_to_sun /. 60.0;;
- : float = 8.31686477360725718

# let pi = 3.1415926535897932384626;;
val pi : float = 3.14159265358979312

val sphere_surface : float -> float = <fun>

# sphere_surface(10.0);;
- : float = 314.159265358979326

# let my_abs_float = fun x -> if x < 0.0 then -. x else x;;
val my_abs_float : float -> float = <fun>

# my_abs_float(-2.3);;
- : float = 2.3

# let tuple_3_of_4 = fun (x1,x2,x3,x4) -> x3;;
val tuple_3_of_4 : 'a * 'b * 'c * 'd -> 'c = <fun>

# let some_quadruple = ("foo",("bar",27),[1;2;3],false);;
val some_quadruple : string * (string * int) * int list * bool =
  ("foo", ("bar", 27), [1; 2; 3], false)

# tuple_3_of_4(some_quadruple);;
- : int list = [1; 2; 3]


Paying close attention to those examples, we see a few noteworthy things: first of all, there are different arithmetic infix operators for integer and floatingpoint operations: integer addition is "+" and floatingpoint addition is "+.". Likewise for the other operators, i.e. "/" vs. "/." and "*" vs. "*.". The same holds for unary minus, as we see in the "... then -. x ..." piece. This may seem strange and does require some getting used to, and indeed, other relatives of OCaml use different approaches here. Why is this necessary? Actually, this has to do with type inference: if we define a function such as "sphere_surface", the system can "magically determine" that this is mapping float to float. Why so? As the argument x is used in a floatingpoint multiplication, it must be float, and likewise reasoning tells us that the result also is float. Now, here one may say that this could also be derived from the fact that a number explicitly known to be a floatingpoint value appears in the product, namely "pi". But then, there are situations like this one:

Why different arithmetic operators for int and float?

# let square_int = fun x -> x*x;;
val square_int : int -> int = <fun>

# let square_float = fun x -> x*.x;;
val square_float : float -> float = <fun>

Evidently, OCaml does not do any implicit conversion between integers and floats, as C or C++ would do. This might be considered to be a good thing, as implicit conversion, especially in conjunction with the extreme richness of integer types in C, turned out to be one frequent source of security bugs in many programs, see e.g. this linux kernel bug. However, this means that we will require additional functions that convert between integers and floats. These are float_of_int and int_of_float.

If one looks very close, one may wonder why there does not seem to be a "<." float comparison function then, as we use the comparison "x<0". This is a slightly hairy issue, and turns out to be one of the dark corners of OCaml. For us, it is sufficient to know that OCaml extends the natural order given on the fundamental data types via lexicographical ordering to containers as well.

A Beginner's Survival Guide To OCaml

Newcomers to OCaml frequently are quite annoyed at first that the system often complains about type mismatch in the code they write. This is usually followed by a phase where one masters the type system and is quite delighted to discover that actually, once the program does typecheck, it will usually also just run as expected. The next step then is that one sets out to test drive the system, to discover its limits, to attack much more complex problems than one would look into when armed only with C. This eventually leads to getting more and more frequently into situations where the type system no longer is that useful - as more and more of the problems occur not at the language, but at the conceptual level. In the end, programmers always spend a considerable amount of time in a confused state of mind, but OCaml programmers usually tend to be confused about much more sophisticated issues than C programmers. Now that we have seen some of the background and original motivation behind ML, and already played around a little bit with the interpreter, some members of the audience may be keen to get something done with it. For this, we need a collection of useful first facts that get us going.

Some language facts

Some useful functions

This table of selected pre-defined functions should be useful to get a first impression of what's there and to allow one to play with the system. Usual guesses about this selection are typically right. (I.e. if there is sin, there also should be cos, tanh, acos, and such.)

absint -> intAbsolute valueabs (-5) => 5
abs_floatfloat -> floatAbsolute valueabs_float (-3.0) => 3.0
sinfloat -> floatSinesin 3.1415 => 9.265...e-5
notbool -> boolNegationnot false => true
floorfloat -> floatRound down to next integerfloor 5.2 => 5.0
modffloat -> (float * float)Floatingpoint fractional and integer partmodf 2.71828 => (0.71828, 2.)
float_of_intint -> floatConversionfloat_of_int 5 => 5.0
int_of_floatfloat -> intConversion (same as 'truncate')int_of_float 5.2 => 5
string_of_boolbool -> stringName of boolean valuestring_of_bool true => "true"
string_of_intint -> stringInteger formattingstring_of_int 42 => "42"
int_of_stringstring -> intInteger parsingint_of_string "1337" => 1337
print_stringstring -> unitPrints a stringprint_string "Hello" => () (and prints "Hello")
read_lineunit -> stringReads in a lineread_line () => [input from stdin, without terminating \n]
read_intunit -> intReads in an integerread_int () => [input from stdin]
read_floatunit -> floatReads in a floatread_float () => [input from stdin]
flush_allunit -> unitFlush all output channelsflush_all () => () (and flushes buffers)
String.lengthstring -> intString lengthString.length "hello" => 5

Some important binary infix Operators

Likewise, here is a table of selected binary operators:

+, -, *, /Integer sum, difference, ...2+3 => 5
+., -., *., /.Float sum, difference, ...2.0+.3.0 => 5.0
=Comparison ("equal")(1,"abc")=(1,"abc") => true
<>Comparison ("inequal")(1,"abc")<>(1,"abc") => false
==Comparison ("same")(1,2)==(1,2) => false (not the same "object" in the computer's memory!)
!=Comparison ("not the same")(1,2)!=(1,2) => true
<, >, <=, >=Comparison (two values of the same type only!)(5,"aa")<(5,"aaa") => true
&&Boolean "and" (uses short-circuit evaluation!)(1<>1) && (1/0>100) => false (!!!)
||Boolean "or" (uses short-circuit evaluation!)2>3 || 7>6 => true
lorBit-wise logical "or"129 lor 3 => 131
lslBit-wise logical shift left1 lsl 6 => 64
modInteger modulus13 mod 10 => 3
**Floatingpoint exponentiation2.0 ** 0.25 => 1.189...
::List extension1::[2;3] => [1;2;3] (actually, this is an "infix constructor")

Further tricks

There are a few things which we will only be able to fully understand later on, but which will simplify our life greatly if we have access to them right from the start.


The module Printf contains functions for formatted output to stdout, to other streams, and to strings that behave quite similar to C's printf, fprintf and sprintf functions, but the syntax is a bit strange. (OCaml has a somewhat special notion of "formatting strings and arguments".)


let x = 1.2 in Printf.sprintf "x^x = %f for x = %f\n" (x**x) x;;
 => "x^x = 1.244565 for x = 1.200000\n"

let user="root" in Printf.printf "Hello, %s!\n%!" user;;
 => () (and prints "Hello, root!<newline>")

Note: the OCaml-special format directive '%!' is a convenient shorthand: it causes the output buffer to be flushed after printing.

Tracing function calls

The execution of toplevel functions can be monitored with "#trace this_function;;". To turn off the tracing of a function, use "#untrace this_function;;" or "#untrace_all;;"

How to deal with "impossible" or erroneous situations

There is a very special function named 'failwith' that takes as argument a string and claims to return something that is of any type, so one can use this e.g. in a situation similar in structure to this:

let make_table_row x =
  if x < 0.0
   then failwith "make_table_row argument must be positive!"
   else [|x;sqrt(x);x**3.0|]

A first look at the compiler

Let us create a file named "hello.ml", which just looks as follows:

A very simple example

Printf.printf "Hello out there\n%!";;

let rec fibonacci n = if n < 3 then 1 else fibonacci (n-1) + fibonacci (n-2);;

Printf.printf "Please enter an integer number: %!";;

let n = read_int ()
in Printf.printf "The %d'th Fibonacci number is %d\n%!" n (fibonacci n);;

We can now either run this directly in the interpreter, either by running it as a script, or loading it at the interpreter prompt. We can also compile it to a standalone application, using the OCaml compiler:

Running interpreted and compiled code

~/ocaml-tutorial$ ocaml hello.ml
Hello out there
Please enter an integer number: 20
The 20'th Fibonacci number is 6765

~/ocaml-tutorial$ ocaml
        Objective Caml version 3.08.3

# #use "hello.ml";;
Hello out there
- : unit = ()
val fibonacci : int -> int = <fun>
Please enter an integer number: - : unit = ()
The 20'th Fibonacci number is 6765
- : unit = ()
# (* Note that here, we get the toplevel's output about
 successful evaluations mixed up with the actual output
 of our code. *)


~/ocaml-tutorial$ ocamlopt -o hello hello.ml
~/ocaml-tutorial$ ./hello
Hello out there
Please enter an integer number: 20
The 20'th Fibonacci number is 6765
~/ocaml-tutorial$ ls -la hello
-rwxr-xr-x  1 tf tf 160207 Dec  8 21:28 hello
~/ocaml-tutorial$ file hello
~/ocaml-tutorial$ ldd hello
	libm.so.6 => /lib/libm.so.6 (0x20028000)
	libdl.so.2 => /lib/libdl.so.2 (0x2004a000)
	libc.so.6 => /lib/libc.so.6 (0x2004d000)
	/lib/ld-linux.so.2 => /lib/ld-linux.so.2 (0x20000000)

~/ocaml-tutorial$ # Speed Comparison:

~/ocaml-tutorial$ time sh -c "echo 34 | ./hello"
Hello out there
Please enter an integer number: The 34'th Fibonacci number is 5702887

real	0m0.082s
user	0m0.070s
sys	0m0.000s
~/ocaml-tutorial$ time sh -c "echo 34 | ocaml ./hello.ml"
Hello out there

real	0m0.569s
user	0m0.540s
sys	0m0.010s

$ # Compiled code is about seven times as
  # fast as interpreted code. The same in python:

~/ocaml-tutorial$ cat fib.py
def fibonacci(n):
  if n<3:
    return 1
  else: return (fibonacci(n-1) + fibonacci(n-2))

print fibonacci(34)

~/ocaml-tutorial$ time python fib.py

real	0m8.045s
user	0m8.010s
sys	0m0.000s

$ # For this example, the ocaml interpreter is about 14 times faster
  # than the python interpreter.

~/ocaml-tutorial$ cat fib.c

#include <stdio.h>

int fibonacci(int n)
  return n<3?1:fibonacci(n-1)+fibonacci(n-2);

int main(void)
  return 0;

~/ocaml-tutorial$ gcc -O3 -o fib fib.c
~/ocaml-tutorial$ time ./fib

real	0m0.110s
user	0m0.090s
sys	0m0.000s

$ # This is roughly the same amount of time
  # (slightly more) as used by our compiled ocaml code.

A word of warning is in order here: one must not take microbenchmarks like those too seriously. However, this at least demonstrates that the claim that OCaml can play in the same league as C is not unjustified.

How to write small programs in OCaml

So far, we have heard a lot about data types, values, containers, expressions, functions, and definitions. But how do we actually write programs? That is, how do we assign to variables, execute statements one after another, and such? The answer is: normally we don't. There are some languages, like in particular Haskell, where strictly speaking, all of this is even impossible, but which nevertheless allow one to write large and beautiful programs. The darcs version control system is an application written completely in Haskell. OCaml is less radical here, but still, it is generally considered much better to avoid a programming style that works with lots of assignments and side effects if possible. At least, if we define a variable with let, it is not possible to over-write the value of that variable in OCaml: Variables are NOT "containers" where values are being stored, but just "names" for values!. True, it is possible to tell the toplevel to replace a definition by another one, but this is not intended to be used in the sense of changing the values of variables, and actually should only be used interactively when "sketching" new code.

That may sound pretty weird: we cannot assign to variables. But actually, this is a very, very good thing. If we look at the C programming language, where I just assume that most people in the audience have some proficiency with, then it is customary there to specify everything down to the level of what value goes where when. Those who can read assembly language will agree that most C statements can be transliterated very easily almost 1:1 to matching assembly code - at least for many processors not from the x86 line; for x86, things unfortunately are a bit odd and ugly. So, C makes it comparatively easy to write a simple C compiler. However, this level of detail also makes it difficult to write a sophisticated optimizing C compiler! Why so? Because a compiler has to reason about what a piece of code does, and this is easier if the code just says what should be done, rather than how precisely the programmer thinks this should be done on a register machine. Let us look at the following C program:

On spurious dependencies in C code

#include <stdio.h>

int main(void)
  int dummy;

  int x=10,y=20,a=30,b=40;

  printf("(x,y)=(%d,%d) - (a,b)=(%d,%d)\n",x,y,a,b);



  return 0;

This just exchanges the elements of two pairs of integer values. Note that on a modern superscalar microprocessor, which has more than one integer unit, one can imagine that both exchanges can easily be performed in parallel - at least, in principle. However, this is obscured by the re-use of the buffer variable "dummy". So, in order to compile this to efficient machine code, the compiler has to derive that the double use of the dummy variable to exchange the elements of the first pair, and of the second pair, does not lead to a conflict, and both exchanges can be done in a different way that uses two dummy variables (or none, if there is a primitive register exchange machine operation). Guess how modern C compilers do that: they first re-write the C source into an intermediate functional form, called SSA (static single assignment), where every variable is just defined once, and never changed, and then turn this into machine code. So, C is either close to machine language, or fast, but usually not both at the same time!

So, even from the perspective of a compiler, having code written in a form where assignments just do not occur is a great benefit. From the perspective of the programmer, what matters most is if we can express concisely what must be done, rather than how we think it should be decomposed into elementary machine steps (where we may guess very wrong). So, we should rather try to analyze our problems in terms of a convenient mathematical decomposition of problems into smaller problems, rather than a convenient machine-centric decomposition. Of course, there are limitations to how far we can take this shift of focus in reality. But it's presumably a step in the right direction, as it is better for everyone that has to read the code: both humans and compilers.

The basic small-scale building blocks of our code will be functions. On larger scales, there may be objects, classes, modules, and such, and some functions may turn out to become object methods. But the fundamental idea is to primarily think in terms of mappings. It is quite amazing how far we can go by just thinking about mappings, and ignoring all the details concerning input, output, and user interaction. Virtually all algorithmic problems can be formulated very well entirely in terms of functions. So, let us for now stick with extending our super-calculator that not only knows about numbers with new functions that make it smarter and smarter, and which we will use from the interactive toplevel. In later lectures, we will start worrying about input and output.

Some examples

Let us look at some very simple examples to show how one analyzes the mathematical side of a problem in such a way that this leads to an OCaml function.

Euclid's algorithm for greatest common divisors

Given two natural numbers a and b, there will be a largest integer dividing both of them, the greatest common divisor, gcd. Evidently, this cannot be larger than either of a and b. Now, if b divides a, the gcd will just be b. Otherwise, this division of a by b will produce a rest, which is strictly smaller than b. Now, the greatest common divisor must also divide this rest, so it must be the greatest common divisor of b and this rest. Note that after this first step, which leads us to the computation of gcd(b,rest), the second argument is smaller than the first one. So, if we just ensure that argument order is such that with every recursive call, the first argument gets smaller, we have a method that must eventually produce the correct result. Hence:

Euclid's gcd algorithm in OCaml

let rec gcd(a,b) =
  if b=1 then 1 else
  let rest = a mod b
      (* If we did not know mod,
	 we may have used "let rest = a-(a/b)*b" *)
  if rest = 0 then b else gcd(b,rest);;

# val gcd : int * int -> int = <fun>

# gcd(2,3);;
- : int = 1

# gcd(12,8);;
- : int = 4

# gcd(8,12);;
- : int = 4

# gcd(60,42);;
- : int = 6

Horner's method to evaluate polynomials

Given a polynomial in one variable, such as 5*x^4-2*x^3+8*x^2+6*x-3, an efficient way to compute its value for a given value of x is to re-write it in the form (((5*x-2)*x+8)*x+6)*x-3. That is, we perform a sequence of steps on a single value, which we keep in mind, where every step consists of multiplying with x, and adding another coefficient. One very nice way to represent a vector of coefficients in OCaml is to use a float array, so let us use that. We then furthermore have to know in every step at which position in the polynomial we are. So, we actually do not remember just a number, but a pair of a number and a position. We start out with the leading coefficient and the position of the sub-leading coefficient.

Horner's method in OCaml

let horner (poly_coeffs,x) =
  let nr_coeffs=Array.length poly_coeffs in
  let rec multiply_add (value_now,position) =
    if position = nr_coeffs
    then value_now
    else multiply_add (value_now*.x+.poly_coeffs.(position),position+1)
  if nr_coeffs=0 then 0.0 (* Note that we have to handle this special case *)
    multiply_add (poly_coeffs.(0),1)

# horner ([|1.0;0.0;0.0;0.0;4.0|],10.0);; (* x^4+4 at x=10 *)
- : float = 10004.

# horner ([|3.0;9.0;9.0;3.0|],9.0);; 
  (* 3x^3 + 9x^2 + 9x + 3 = 3(x+1)^3 for x=9 *)
- : float = 3000.

# (* Note that we also can do something very nice with OCaml: *)
  let vivify_polynomial poly_coeffs = fun x -> horner(poly_coeffs,x);;
val vivify_polynomial : float array -> (float -> float) = <fun>

# (* This maps a vector of coefficients to a polynomial *function*! *)
  let poly_x3_plus_3x = vivify_polynomial [|1.0;0.0;3.0;0.0|];;
val poly_x3_plus_3x : float -> float = <fun>

# (* This function then can be used like every other function *)
  poly_x3_plus_3x 10.0;;
- : float = 1030.

# (* All this will become very important later on *)

Getting Help

How to get help with OCaml problems? First of all, there is the OCaml documentation. This is available e.g. via the info system. In Emacs, Control-h i will bring up the info pages. Internally, we've made this available as well via http://alpha.sesnet.soton.ac.uk/docs/ocaml/. Later on, especially section IV on libraries will become an important source for us.

Furthermore, there is the "Developing Applications With Objective Caml" free online book, which is also available at http://alpha.sesnet.soton.ac.uk/docs/ocaml-book/.

And, of course, you can always ask the instructor. Please just do so when questions come up. I want to learn where beginners have problems. Note: if you want to learn OCaml, you are supposed to do these exercises!


All of the following exercises are of the "how can I do this-and-that in OCaml" type, rather than the "what is the OCaml notation for this and that" type. One certainly has to know a bit about the language, but becoming a language lawyer without any real programming experience is utterly pointless. The list seems to be quite long, however, some exercises are very easy.

  1. Define an OCaml function that computes the least common multiple of two positive integer numbers. Extra style points for doing this in such a way that the correct answer is found for the least common multiple of 3000000 and 7000000.

  2. Define a factorial function.

  3. Define a function that maps the pair of integers (n,m) to the binomial coefficient "n over m". Can you do this with the smallest possible number of multiplications and divisions?

  4. Define binomial coefficients for non-integer n.

  5. OCaml comes with a square root function. Define your own, using Heron's method. (Reminder: given an estimate x for the square root of n, another estimate which is at least as good is given by taking the average of x and n/x. Stop when the relative difference between x and n/x is smaller than 1 in 10^8.) Note: never ever, no matter what programming language, define functions which have exactly the same name as built-in functions!

  6. In the above discussion of Horner's method, we used a float array to represent coefficients. One may also represent coefficients as a float list. The advantage of using a list is that one can "shorten" the list in every step by passing just its tail to the recursive call, and hence go without determining the length beforehand, and also without remembering the coefficient position. Write an implementation of Horner's method using lists to represent coefficients that heeds these considerations. (Unrelated side note: The disadvantage of using a list here is that in every step, the machine has to chase a pointer.)

  7. For a given continuous function f that is negative at a and positive at b, there must be a zero in between. Write a function that takes a triplet (f,a,b) of type ((float -> float),float,float) and uses successive interval bisection to numerically determine the location of the zero. Generalize in such a way that this works whenever f a and f b have different sign.

  8. The hyperbolic tangent satisfies the addition theorem tanh(a+b)=(tanh(a)+tanh(b))/(1+tanh(a)*tanh(b)). Define an OCaml function that checks this addition theorem by mapping (a,b) to the pair of values on the the left hand side and right hand side of that equation. (What is the type of that function?) Furthermore, assuming that for values of absolute magnitude smaller than 10^(-8), tanh x always can be approximated by x, use the addition theorem to define your own variant of a tanh function. Use the tracing features to monitor the computations done by your hyperbolic tangent. How much does your variant deviate from the built-in tanh function, typically?

    Note: spend some thought on the problem first!

  9. Define your own exponential function using your factorial function and the vivify_polynomial function from the Horner example.

  10. The exponential function satisfies an addition theorem exp(a+b)=exp(a)*exp(b). Furthermore, for numbers of absolute magnitude smaller than 10^(-8), exp(x) can be approximated as 1+x. Use this to define your own exponential function.

  11. Normally, you can only use values defined previously in a definition. The "let rec" construct allows us to make recursive definitions. Sometimes, this is not good enough and we want to define multiple functions at the same time, which can recurse into one another. This is done with "let rec ... and". (This is a special case of "let ... and" which also may be nice to know about, but which we will not discuss here.) Mutual recursion works as follows:

    How to define mutually recursive functions
    let rec humpty = fun x -> if x=0 then [] else "humpty"::(dumpty (x-1))
    and dumpty = fun x -> if x=0 then [] else "dumpty"::(humpty (x-1));;
    (* This is equivalent to: *)
    let rec humpty x = if x=0 then [] else "humpty"::(dumpty (x-1))
    and dumpty x = if x=0 then [] else "dumpty"::(humpty (x-1));;
    #   val humpty : int -> string list = <fun>
    val dumpty : int -> string list = <fun>
    # dumpty 3;;
    - : string list = ["dumpty"; "humpty"; "dumpty"]
    # dumpty 4;;
    - : string list = ["dumpty"; "humpty"; "dumpty"; "humpty"]
    # humpty 4;;
    - : string list = ["humpty"; "dumpty"; "humpty"; "dumpty"]
    (* Note that someone might have the clever idea to do it that way,
       but unfortunately, OCaml's "let rec" is slightly flawed,
       so it will not allow this: *)
    let rec (humpty,dumpty) = 
      ((fun x -> if x=0 then [] else "humpty"::(dumpty (x-1))),

    For x of absolute value smaller than 10^(-8), sin(x) can be approximated by x, and cos(x) can be approximated by 1. Use the addition theorems sin(x+y)=sin(x)cos(y)+sin(y)cos(x) and cos(x+y)=cos(x)cos(y)-sin(x)sin(y) to define your own variants of sin and cos. Test them for very small arguments first. Is this a good method to compute sine and cosine functions? If not, where is the problem, and how might this be improved?

  12. We are slowly developing a feeling for what it means to write programs by extending "the OCaml programmable calculator" with new definitions. Let us now see how to do a problem in OCaml which is more like a typical beginner's example for C programmers: Write a small game that determines a random number between 1 and 100 and lets the user repeatedly guess that number until he gets it right. When he did not guess right, the program should tell him whether he guessed too high or too low.


Dr. Thomas Fischbacher
Last modified: Sat May 13 18:26:55 BST 2006