O'Caml

From GPWiki

Objective CAML (Homepage) is one branch of the ML family of languages. Its most distinguishing features (when compared to other ML-style languages) are transparent functors and support for subtyping, inheritance (by delegation), and data hiding through subtyping. Despite the OO extension, the standard library is implemented in traditional ML style, using structures and functors. Out of the larger family of functional programming languages, O'Caml is perhaps the most widely used one; a popular myth for why this might be the case can be summarised as "come for the OO, stay for the functional programming".

Executive Summary

• Availability: Free for commercial and non-commercial use, source code changes to shipped libraries/compilers/RTS must be shared (partially GPL v2, other parts QPL)
• Platforms: UNIX, Win32, Mac
• Performance: On-par with other compiled/gc'd languages, C interface for high-performance subroutines
• Paradigm: Combined Imperative + Functional + OO
• Memory Management: Automatic (Mark&Sweep garbage collection)
• Syntax Family: ML
• Evaluation: strict (pass-by-value), lazy evaluation as module. Has short-circuit primitives.
• Type system: Hindley-Milner parametrically polymorphic type system with type inference, extended with subtyping; type constructors may have co-/contravariant parameters (explicit annotation). O'Caml is statically type-safe (no type errors are possible at run-time, except with dynamic module loading)
• Preprocessing: camlp4 AST-based turing-complete preprocessor
• Built-in facilities: Threads, Serialisation (pickling), dynamic module loading (with bytecode interpretation only), Mark&Sweep garbage collection
• Use: Interactive top-level, optimising native code compiler (IA32, PowerPC, AMD64, Alpha, Sparc, Mips, IA64, HPPA, StrongArm), Bytecode compiler, profiler, debugger
• Manufacturer: INRIA (French national research institute)

There is also .NET platform language called F#, developed by Microsoft Research, that was designed to be very similar to O'Caml. F# comes with samples for GUI and DirectX programming.

Functional programming basics

By integrating OO features, O'Caml effectively supports imperative and functional programming with and without object-orientation, making it a comparatively powerful multi-paradigm language. Since object orientation and imperative programming are explained elsewhere, let us examine functional programming in a little more detail.

The most fundamental differences between functional programming and imperative programming (as practiced today) are: (1) Functions are Values (2) There are no references (pointers) (3) Types describe sets of values

(note that not all of these ideas hold straightforwardly for O'Caml, as discussed later).

The idea that functions are values may seem not totally new to e.g. C programmers, who might be familiar with the libc qsort function, which takes, as parameter, a comparison function pointer. Functional programming drives this idea to its logical conclusion, except that it does away of the complication of distinguishing between functions and function pointers. One particular, slightly academic example can be found in the following code fragment:

let inc = (+) 1;; inc 5;;

In the first line, we take the function (+), which adds two numbers, "partially apply" it to 1, and call the result "inc". "Partially apply" here means that we pass the function one of its parameters, but not the other. O'Caml fills in the left-most parameter slot, which leaves one parameter slot open. Thus, if "(+)" took two numbers, "(+) 1" now only takes one number. The function "inc" then is the addition to one, a.k.a. the increment.

Further details can be obtained from various O'Caml tutorials and books. This idea is particularly useful when passing functions as parameters. Functions which take functions as parameters are very common in functional programming languages; one very popular example is 'map', which allows iterations or recursions to be avoided:

List.map ((+) 1) [1;2;3;4;5;6;7;8;9];;

will compute for us the result of applying ((+) 1), i.e. the increment, to all elements of the list of integers from 1 to 9 (lists are a built-in datastructure in O'Caml and slightly easier to use than arrays). The advantage is obvious: Instead of making up an iterator variable and finding a proper condition to insure that we iterate precisely over all elements of the list, we simply leave all these worries to "List.map" and only tell it what we want done with all the elements of the list.

For a game programming example, consider a space shooter game. Assume that the player's secondary weapon can have a variety of effects: It can damage an enemy fighter, slow it down, jam its weapons systems, push it away, or transform it into a turnip, or it can pick at random one of these effects. The usual way to encode this in an imperative style would be to have a record containing a magical number for the intended effect, plus another number for severity (amount of damage). This approach would mean that we need to carry a log of magical numbers around and must make global changes whenever we want to add a new effect-- clearly not an elegant solution. The object-oriented solution would be much more straightforward, but still requires us to create a new class for each effect we are interested in. With a functional language, we simply encode our effect as a locally defined function (perhaps even an anonymous function), which makes it trivial to add a new effect.

To understand that functional languages do not (normally) use references and what this means, consider the difference between saying

int a = 5; int b = a;

and

Object o1 = getMeAnObject(); Object o2 = o1;

in any given C-style OO language. In the first example, the value "5" is copied to "b". Now, no matter which operations you perform on the value stored in "b", the value "a" will be unaffected. This is called value semantics. However, in the second example, if you modify the object named by o1 or by o2 in any way, it will also affect the other (this is referring to object changes, not to changing the reference stored in either variable). That is called reference semantics. Functional programming (conceptually) only uses value semantics: This means that if you do any kind of operation, your effects will be purely local-- you cannot accidently change the value of something else at the other end of the program. Another way to think about this is that everything you get is a copy; except that the compiler makes sure to copy only as little as neccessary.

To understand types as sets of values, consider an example: In a given game, players can be part of the Alliance, part of the Empire, or part of the Confederation. To encode this, we define what amounts to an 'enum' in other languages:

type allegiance = ALLIANCE | EMPIRE | CONFED;;

Now, 'ALLIANCE', 'EMPIRE' and 'CONFED' are all values of type 'allegiance'-- more precisely, they are the only values of this type. While this is all fine, consider the following example from a strategic wargame (made up, of course):

type munit = MINE | PLATOON int | TRANSPORT (munit list);;

This describes the type 'munit', and its three possible values: Each munit is either a mine, a 'PLATOON' parameterised by an integer (which could be e.g. the number of soldiers in the platoon), or a 'TRANSPORT', which is parameterised by a 'munit list'. An 'munit list' is a list of 'munit's; one example of a value of this type would be

TRANSPORT [MINE ; MINE ; PLATOON 5 ];;

which would be a transport containing a mine, another mine, and a platoon of five soldiers.

Of course, this is only a very rough sketch of those ideas; tutorials to functional programming languages explain these ideas better and in more detail.

O'Caml features

O'Caml has the following features:

• Functions as first-class values
• Dynamic dispatch
• Inheritance
• F-bounded polymorphism with co- and contravariant type parameters (in layman's terms: A VERY powerful type system which finds many program errors even before you run your code)
• Type inference (meaning: For most things, you don't need to tell O'Caml what its type is-- O'Caml can figure that out by itself, at compile-time-- so you get all the error checking with only a small amount of the notational overhead)
• Automatic Garbage Collection
• Built-in serialisation/deserialisation facilities ("pickling", in Modula-3 terms-- very useful for savegames)
• An interactive top-level system (allows you to test your programs interactively)
• An optimising compiler (Despite having an interactive top-level, O'Caml is a compiled language, and correspondingly fast)
• Existing library bindings for e.g. SDL and OpenGL
• Functors for more flexible module design (modules and objects are separate concepts in O'Caml)
• Support for imperative programming: side-effects (updates/assignments) and loops