Photos from OCaml Users Meeting, Grenoble, 2009

We had a very successful OCaml User Meeting this week, with 45 people coming from around Europe to Grenoble.



Xavier Leroy on progress made over 2008

Sylvain Le Gall OCamlCore.org and OCaml as fast as C

Maxence Guesdon Chamo and Cameleon

Florent Ouchet VHDL symbolic simulation

David Teller Batteries Included

Christophe Troestler pa_do (delimited overloading) syntax

Richard Jones (me) OCaml Windows cross-compiler

Christophe Raffalli Parsing with dypgen

Xavier Leroy on the right:



Dinner the evening before:

ocsigen (OCaml web framework) benchmarked

This benchmark compares the OCaml web framework ocsigen against Ruby on Rails and lighttpd+C with some excellent results for the OCaml framework:

	Reqs/sec	Mem usage
Rails with mongrel, 1 process	260	49MB
Rails with mongrel via nginx (rev proxy), 1 proc	220	~51MB
Rails with mongrel, 4 processes via nginx	430	~200MB
OCaml ocsigen (1 process)	5800	4.5MB
lighttpd with FastCGI app in C, 20 procs	9300	4.5MB

OCaml is not just an order of magnitude faster and an order of magnitude more memory efficient, but it also provides complete compile-time safety, catching multiple errors at compile time which would otherwise only show up after extensive testing.

More discussion on this reddit thread.

There's a Fedora ocsigen package waiting for review here.

Fedora Rawhide has OCaml 3.11.0

Fedora Rawhide [the experimental/development version of Fedora] has been completely rebuilt with OCaml 3.11.0, and all library and application problems that were found have been patched.

List of packages: http://cocan.org/fedora#Package_status

Mailing list announcement

Slashdot groupthink

This may be the first time a comment of mine has been modded down to -1 on Slashdot. I'm questioning whether the inefficiency of glib outweighs the speed advantage of C. Very few of the replies get it. Perhaps this proves the people only read the first sentence of any posting ... tl;dr.

Fedora 10 & OCaml

You can join in the general Fedora 10 fun here, but a quick note that Fedora 10 comes with stable OCaml 3.10.2 and 68 OCaml packages, making us the fastest, best supported functional language in Fedora.

OCaml Users Meeting, Feb 2009, Grenoble

Sylvain is already organizing the next OCaml Users Meeting 4th Feb 2009 in Grenoble, France.

The last meeting (rubbish photo I took below) was a great success, and since so much has happened in the community this year, I expect this one will be even bigger and better.



Update: Sylvain's announcement and the official photo

malloc failures

I can't put a comment on Debarshi's post, so I'll answer here. Debarshi complains about this comment by the "inimitable" Jeff Johnson:

You have to look at the usage case, malloc returning NULL is a "can't happen" condition where an exit call is arguably justified.

Returning an error from library to application when malloc returns NULL assumes:

1) error return paths exist [...]
2) applications are prepared to do something meaningful with the error

Another problem is that only about 1 in 10 memory allocations in a typical C program are mallocs. The rest are stack-allocated variables, and those aren't usually checked at all. If any of your 9 out of 10 stack allocations fail, your whole program fails hard.

This is the correct way to deal with those 1 in 10 memory allocations that you can check — provide a custom abort function that the main program can override in the very rare case that they can do anything useful other than exit:

void (*custom_abort) () = abort;

void
lib_set_custom_abort (void (*new_abort) ())
{
  custom_abort = new_abort;
}

void *
lib_malloc (int n)
{
  void *data = malloc (n);
  if (data == NULL) custom_abort ();
  return data;
}

Note that the main program can use longjmp (or exceptions in some cases) to "return" back to a safe point in the program, such as a transaction checkpoint. If the main program uses pool allocators — about the only safe and sensible way to deal with C's programming model — then the program has a chance of recovering.

Really the answer is to use a sensible programming language though. Programming languages invented before C had safer, faster memory allocation, dealt with 10 out of 10 memory allocation errors, and provided a mechanism to recover correctly. Those languages are now 30 years more advanced. In 2008 we're having these silly arguments about how to deal with malloc failures. That's a failure of ourselves as programmers.

What can OCaml do that you can't do in other programming languages?

Depressingly predictable comments on the Haskell story in Slashdot yesterday such as:

"I have *never* seen it being used since. To my mind they both belong in the category 'interesting, but pointless'."

and

"The point is that there's nothing those languages can do that can't be done, often more easily, with the current crop of popular languages. Elegance cannot beat convenience in the workplace, or in most at any rate."

and so on.

Here are some useful things you can do in OCaml which you cannot do in the "current crop of popular languages".

1. Change the language to suit your task.

In our case the task was to parse binary formats.

If you have a few hours to spare, try writing a C program to parse tcpdump files. Don't forget that the endianness in these files is variable so you'll need lots of if (..) { field1 = htonl (field1); ... }. OK so that's a bit hard. Let's say you want to parse a 6 bit length field 'n' followed by an n+1 bit data field (as a 1-64 bit int). Go and write it in C now.

Using our bitstring extension to OCaml, parsing binary structures is really effortless:

let bits = Bitstring.bitstring_of_file "input.data" in
bitmatch bits with
| { n : 6;
    data : n+1 } -> data

This is the complete tcpdump parser, just 113 lines of code.

And it's fast too. The resulting code compiles down to machine code and inlines direct calls to C functions at every opportunity, so in practice you can parse data at speeds approaching C.

Another task we had was to check that hundreds of SQL statements in a modest sized web application actually matched with fields in the database, in other words that they didn't reference non-existent fields or treat a string field as an integer and so forth. Doing this by testing is almost impossible because many SQL statements are only used on rare error paths. We could contemplate doing it manually once but not routinely.

So instead we extended the OCaml language to do the checking for us every time we compiled the code. The resulting PG'OCaml project gives you compiled-time checked type-safe access to your database. It's used by mod_caml and ocsigen, or you can just use it in standalone programs. I won't go into detail because Dario Teixeira wrote a great introduction and tutorial to PG'OCaml.

Martin Jambon, author of Micmatch which adds regular expressions directly into the language, has an excellent tutorial. Browse the list of syntax extensions here.

2. Get the compiler to check for errors in your logic

Why can't your compiler check for errors like when you use a read-only database connection in a SQL INSERT statement, or you are supposed to call library function set_word_size because you try to call get_word?

In OCaml, using phantom types [tutorial] you can do exactly this.

3. Drop down to imperative code when you need speed like C

Scripting languages are expressive but slow ... and getting slower. But there's no need to compromise expressiveness to get real speed. Static typed languages with type inference (which excludes C, C++, Java, C# and most others, but includes SML, OCaml and F#) give you the expressiveness to write compact code but without compromising on speed.

OCaml programs are more than 10 - 15 times faster and less memory intensive than Python programs.

More about speed and optimizing OCaml programs. Comparison of a raytracer written in C++ and OCaml.

4. Large well-established standard libraries

OCaml comes with hundreds of packages for many tasks now.

If that's not enough you can directly call out to Perl, Java, Python and .Net [on Windows] libraries. Or you can call C functions directly.

You can compile the same code on Unix, Mac OS X and Windows.

So enough of this "elegance can't beat convenience" stuff please.

Tip: Read all lines from a file (the most common OCaml newbie question?)

Is this the most common OCaml beginners question? It comes up every few weeks on the OCaml beginners list, and I have tried to answer it before.

It seems that everyone who learns OCaml comes away with the impression that functional programming is the New Cool Thing, and imperative programming is Bad and Must Be Avoided.

I'm going to say it now: programming fashions are stupid and counterproductive. The only things that matter are that your program is short, easy to write, easy to maintain and works correctly. How you achieve this has nothing to do with programming fads.

Reading all lines from a file is an imperative problem, and the shortest solution (easy to write, easy to maintain and correct¹) uses a while loop, in OCaml or any other language:

let lines = ref [] in
let chan = open_in filename in
try
  while true; do
    lines := input_line chan :: !lines
  done; []
with End_of_file ->
  close_in chan;
  List.rev !lines

Actually, no, I'm lying. The best solution is this:

Std.input_list chan

which is supplied by extlib. Don't bother to duplicate functions which are already provided in commonly available libraries.

---

¹This is only strictly speaking correct if you handle clean-up if input_line throws some read error (exception). In the common case where you just exit the program, leaving the channel open is perfectly acceptable.

Writing printf-like functions

Here's a quick and useful tip: failwith is the standard function to raise a general error, but it's a little bit clumsy to use because it only takes a fixed string.

if temp >= 100 then
  failwith "we've reached boiling point"

If you want to have the message contain useful debugging information, you need to use sprintf to generate the fixed string, like:

if temp >= 100 then
  failwith (sprintf "%d degC: boiling point reached" temp)

(I'm assuming here that you have open Printf at the top of your file, something which you should almost always do so you don't need to write Printf.sprintf all the time,).

With this simple tip we can turn failwith into a function that automatically takes a printf-like format string, and we can learn a little bit about the arcana of polymorphic types too.

First of all, here is the code:

let failwith format = ksprintf failwith format

You can see in the toplevel that it works:

# let failwith format = ksprintf failwith format ;;
val failwith : ('a, unit, string, 'b) format4 -> 'a = <fun>
# failwith "hello, %s" "world" ;;
Exception: Failure "hello, world".
# failwith "error code %d" 3 ;;
Exception: Failure "error code 3".

ksprintf is the key function here. Like sprintf it takes a format string and a variable number of parameters, and makes a fixed result string. Unlike sprintf it doesn't return the string, but passes it to the function which is its first parameter — in this case, the standard failwith function. So ksprintf is useful because it can turn almost any fixed string function into a printf-like function.

Now how about the lesson on type arcana? Well if you know anything about currying you might think that you could write the new failwith function even shorter, like this:

let failwith = ksprintf failwith

If you try this, you'll find the new function works some of the time, but fails to type-check at other times. In fact, the first time you use it, it seems to "remember" the type of all the arguments, and then refuses to work if any of those types change:

# failwith "hello, %s" "world" ;;
Exception: Failure "hello, world".
# failwith "error code %d" 3 ;;
This expression has type (int -> 'a, 'b, 'c, 'd, 'd, 'a) format6
but is here used with type
  (string -> 'e, unit, string, 'e) format4 =
    (string -> 'e, unit, string, string, string, 'e) format6

If we take a close look at the inferred types of the wrong definition, we can see why:

# let failwith = ksprintf failwith ;;
val failwith : ('_a, unit, string, '_b) format4 -> '_a = <fun>

'_a (with an underscore) is not a polymorphic type, but a single type that the compiler just hasn't been able to infer fully yet. As soon as you give it more information (eg. calling the function), the compiler infers that type into some concrete type (like string -> ... above) and won't let you change it later.

A more advanced question is to work out why type inference fails to infer the more general polymorphic type. I suspect this FAQ may have the answer.

Sharing a global variable between C and OCaml

I was asked today if it is possible to share a global variable between C and OCaml. This was my first response:

OCaml cannot just directly access C globals. At best you'd need to have a function that returns the address of the C global, _and_ the C global would need to be in a form that OCaml code could understand although that is pretty easy to arrange.

In a followup, I gave some example code:

------------------------------------------------------------ test_c.c
/* Variable shared between C and OCaml. */

#include <caml/mlvalues.h>
                                                                                
/* On the OCaml side, this will be made to look like a structure
 * containing a single int (well, provided you don't look *too*
 * closely at it). 
 */
value shared_var = Val_int (0); 

value
get_struct_addr (value unitv)
{
  /* Return the address of the 'structure'. */
  return ((value) &shared_var);
}

/* Increment the shared variable. */
value
increment_it (value unitv)
{
  int i = Int_val (shared_var);
  i++;
  shared_var = Val_int (i);
  return (Val_unit);
}
----------------------------------------------------------------------

------------------------------------------------------------ test.ml
(* Variable shared between C and OCaml. *)

type var = {
  shared_var : int;
}

external get_struct_addr : unit -> var = "get_struct_addr" "noalloc"
external increment_it : unit -> unit = "increment_it" "noalloc"

let var = get_struct_addr () ;;

while true do
  Printf.printf "value of the variable now is %d\n%!" var.shared_var;
  increment_it ();
  (* OCaml isn't expecting that increment_it modifies a variable, so
   * there is no guarantee that we will see the changed value next
   * time around.
   *)
  Unix.sleep 1;
done
----------------------------------------------------------------------

$ gcc -I /usr/lib/ocaml -c test_c.c
$ ocamlopt -c test.ml
$ ocamlopt unix.cmxa test_c.o test.cmx -o test
$ ./test
value of the variable now is 0
value of the variable now is 1
value of the variable now is 2
value of the variable now is 3
value of the variable now is 4
[etc.]

Before you use this code, be aware that it's a real hack.

Tip: Calling C functions directly with "noalloc"

In OCaml you can call a C function by writing:

external call_1 : float -> float = "call_1"

then just using call_1. However these calls are not direct. They go via an OCaml runtime function called caml_c_call. This is a tiny bit of assembler, so the overhead isn't large, but it does use a computed jump which on many processors is quite slow.

Luckily this indirection is only needed in order to set up the garbage collector. If your C function won't perform any OCaml allocations, then you don't need this, and you can tell OCaml to jump directly to your C function like this:

external call_2 : float -> float = "call_2" "noalloc"

Let's compare the generated assembly code for the calls in both cases:

Normal                                    "noalloc"       

pushl   %eax                              pushl   %eax
movl    $call_1, %eax                     call    call_2
call    caml_c_call                       addl    $4, %esp
addl    $4, %esp
   ...
caml_c_call:
movl    (%esp), %edx
movl    %edx, G(caml_last_return_address)
leal    4(%esp), %edx
movl    %edx, G(caml_bottom_of_stack)
jmp     *%eax

As you can see, the "noalloc" version is much shorter.

Just draw something on the f-ing screen

I don't believe that computers have got better over the past 40 years.

Case in point: I've spent at least 2 hours trying to debug a Gtk program which is supposed to plot some dots on the screen. Like this sort of thing in barely remembered ZX Spectrum BASIC:

10 FOR F = 0 TO 2*PI STEP 0.1
20 PLOT SIN(F)*200+100, COS(F)*200+100
30 NEXT F

The Gtk program is 20 times longer than this. And refuses to draw anything except a black window.

Computers have got worse in many ways since my first computer.

Update

My angry late-night programming rant makes it to reddit.

---

Ob-awesome Wikipedia page of the week: List of 8 bit computer hardware palettes.

3 things that will confuse you when reading functional programs

Here are 3 things that will confuse you when you read a program written in a functional language. They're just small stylistic differences compared to more mainstream languages, and once you understand them you'll be able to read the code much more easily.

1. Function calls

Calls to functions are written differently, without any brackets or commas.

In C you would write:

printf ("hello %s\n", name);

but in OCaml the same function call would be written like this:

printf "hello %s\n" name;

What's the difference? In functional languages you don't put brackets around the arguments, and you just put spaces between the function name and the arguments.

Why is it confusing? It doesn't look like a function call (unless you're used to this style). Functions are very common in functional programming, not surprising really, and they are often given short names, so you'll see plenty of code like this:

f (g a b) c

Just take it one step at a time and remember that g a b is a function call (in C it would be written as g (a, b)), and that f (...) c is a function call with two parameters (in C it would be written as f (g (a, b), c).)

Why is it done like this? This syntax is better because it's shorter. Functions and function calls are very common in functional programming languages, so we need to use the shortest possible syntax, which is this one.

2. Bindings are not variables

let x = foo

x is not a variable. It's just a name which refers to foo, and there is no way to change its value. The technical term is a let-binding.

You can create another name x with a different value, but that doesn't change the original x or foo:

let x = foo in
let x = bar in
...

One consequence of this is that the following code doesn't do what you think it does:

let quit = false in
while not quit do
  let line = read_line () in
  if line = "q" then let quit = true in ();
  print_endline line
done

In fact this loop never exits. Why? Because the inner quit is just a different label from the outer one. In this case you would get a compiler warning because the inner quit label is never used.

What's the difference? Let bindings make labels, not variables.

Why is it confusing? Variables do exist in some functional languages, particularly ones based on ML like OCaml, but they aren't used very much. Most code you look at will use only let bindings, and you shouldn't confuse those with variables.

Why is it done like this? This encourages the use of immutable data structures, which is a giant topic in itself. In brief, immutable data structures make programming errors less likely because they remove the "who owns that data" problem that imperative languages have. (It's fair to say that immutable data structures also have disadvantages, which is why OCaml lets you drop down to mutable data when you need it).

3. Function types use lots of '->' (arrows)

To write the type of a function, you use an arrow notation. The parameters and the return type are separated by arrows like this:

val average : float -> float -> float

This means that there is a function called average which takes two parameters, both floating point numbers, and returns a floating pointer number.

Here are some more examples:

val print_string : string -> unit

(Takes one parameter, a string, and returns nothing -- unit is like void in C).

val int_of_string : string -> int

(Takes one parameter, a string, and returns an int).

val open_out_gen : open_flag list -> int -> string -> out_channel

(Takes three parameters: a list of flags, an integer and a string. Returns an output channel).

What's the difference? This syntax is common in functional programming, and almost completely unknown outside of it.

Why is it confusing? The parameters and the return type aren't separated from each other.

Why is it done like this? The reason is to do with a mathematical concept called currying. The practical reason is that functional languages let you generate new functions by partially applying some arguments. Thus:

       add : int -> int -> int
  (add 42) : int -> int
(add 42 2) : int

The first is the general adding function. The second is a partially applied function which adds 42 to any int. The third is the number 44.

virt-mem 0.2.9

I'm pleased to announce the latest alpha release of the virt-mem tools, version 0.2.9.

These are tools for system administrators which let you find things like kernel messages, process lists and network information of your guests.

For example:

  virt-uname
    'uname' command, shows OS version, architecture, etc.
  virt-dmesg
    'dmesg' command, shows kernel messages
  virt-ps
    'ps' command, shows process list

Nothing needs to be installed in the guest for this to work, and the tools are specifically designed to allow easy scripting and integration with databases and monitoring systems.

Source is available from the web page here:

http://et.redhat.com/~rjones/virt-mem/

The latest version (0.2.9) reworks the internals substantially so that we have direct access to basically any kernel structure, and this will allow us to quickly add the remaining features that people have asked for (memory usage information, lists of network interfaces and so on).

As usual, patches, feedback, suggestions etc. are very welcome!

Binaries are available for Fedora through this link:
https://bugzilla.redhat.com/show_bug.cgi?id=450713

virt-ps and the Red Hat Summit

Tomorrow (Wednesday) through to Friday is the Red Hat Summit in Boston. If you're coming, please make sure to see my talk with Dan Berrange on the "Virtualization Toolbox", or all the little, useful tools we've been writing to help you manage your virt systems. That talk is tomorrow, Wednesday 18th June, some time after 11am.

As I mentioned previously on this blog I'm working on deep inspection of the internals of running virtual machines, and dressing this up as familiar, easy to use command line tools, such as virt-df and virt-dmesg. I'll be talking a lot more about those tomorrow, so I don't want to spoil the surprises.

The real question is whether I'll get virt-ps (process listings) working today. Getting the process listing out of a stuck virtual machine is immensely useful to find out what's going on with the machine. For example, did it blow up because there are too many Apache processes? Or is some other daemon causing trouble? I had an initial implementation of this working, but it was rather slow and unsatisfactory because of the all the guessing and heuristics it had to do. In the meantime, I discovered that getting the Linux kernel version is quite easy, and once you know the kernel version you immediately reduce the amount of heuristics you need by a large factor. So the new implementation should be much faster.

Faster, but it doesn't work at the moment. Today is the final push on this - can I get virt-ps working in time for the demo tomorrow?

virt-df, virt-mem and bitmatch

One of the "self-evident truths" about virtualization is that in order to monitor aspects of the virtual machine such as free disk space / free memory / running processes / etc, you need to run some software inside the virtual machine. That's how the expensive proprietary virt systems such as VMWare work. The alternative to running monitoring software in the virtual machine would be to try to look at the disk image and memory image of the virtual machine and try to make sense of it, and that is usually regarded as an intractable, unimplementable nightmare.

That's not a truth any more.

A few months ago I proved with virt-df that it's perfectly possible to parse the disk image of a virtual machine to find out how much free disk space is left. And although in theory this could get inconsistent results, in practice it works well. Virt-df supports Linux, Windows NTFS, and complex partitioning schemes such as LVM as well as simple DOS-style partitions.

Now I'm proving with the virt-mem toolkit that we can snoop on the live memory image of running virtual machines and pull out such interesting details as the process list, the network configuration, the kernel messages (dmesg), and the kernel version strings.

So how is this possible?

Of course I'm writing these tools in OCaml, which allows me to express complicated ideas in a very few lines of code, yet is as fast as optimized C code. But OCaml alone isn't sufficient because all of the disk and memory images that we're parsing are made from binary structures and the base language doesn't handle binary structures very well. OCaml though does allow programmers to change and extend the base language using LISP-style macros -- these are language extensions that become one with the original language, but enable you to extend it in arbitrary and unexpected ways.

I have already extended OCaml by adding the entire, complete PostgreSQL SQL syntax through a macro, so this should be easy.

The key to being able to parse hundreds of different variations of the Linux task_struct (process table entry) so we can print process lists, was to look at a successful functional language which already supports bitstrings directly. Erlang is used in the telecom industry to parse binary network protocols and has a rich syntax for parsing and assembling bitstrings. I copied Erlang's syntax and using macros added it directly to OCaml. The result is the OCaml bitmatch project, hosted on Googlecode and with lots of examples and documentation.

Bitmatch is now a very advanced and powerful system for dealing with binary structures (more powerful than what the Erlang architype offered). As an example, how much code would you expect to write in order to take an ext3 partition, find the superblock and print out the number of free blocks from the superblock? (A poor man's 'df' command) You'll need to parse the Linux kernel header file <ext3_fs_sb.h> to get the fields, their offsets, sizes, endianness, etc. Then you'll need to load the superblock from disk and parse it using bit operators.

The answer in bitmatch is just 9 lines of code:

  (* bitmatch-import-c ext3.c > ext3.bmpp *)
  open bitmatch "ext3.bmpp"

  let () =
    let fd = Unix.openfile "/dev/sda1" [Unix.O_RDONLY] 0 in
    let bits = Bitmatch.bitstring_of_file_descr_max fd 4096 in

    bitmatch bits with
    | { :ext3_super_block } ->
        printf "free blocks = %ld\n" s_free_blocks_count
    | { _ } ->
        printf "/dev/sda1 is not an ext3 filesystem\n"

Phantom types

In libvirt we have a concept of a connection to the hypervisor, and every libvirt operation happens across this connection. Connections are normally read/write, which means that you can carry out any operation, even destructive ones like shutting down a virtual machine. But since programs normally need to have root (or "elevated") privileges to do these destructive operations, we also introduced the concept of a read-only connection which can just be used for non-destructive things such as listing out virtual machines or monitoring CPU loads.

Read-only operations	Read/write operations
get hypervisor type get version get hostname get URI get num CPUs list VMs list networks get VM CPU stats	suspend VM resume VM shutdown VM destroy VM coredump VM create VM change CPU pinning

The question is, what happens if a program tries to call a destructive operation using just a read-only connection? The answer, naturally, is that libvirt throws a runtime error if you try this.

Wouldn't it be nicer if the compiler could find these sorts of errors? That way you could be sure that your compiled program was completely correct, and there wasn't some sort of dark corner of untested code which might fail in rare circumstances. For the OCaml bindings to libvirt that was exactly the sort of guarantee I wanted to make, and to do it I used a language feature which is often thought of as being confusing or highly expert (but in fact is neither of those) ... phantom types.

Before we can understand phantom types, we need to set up a little bit of background: firstly asking what sort of errors is it conceivable for the compiler to find, and secondly understanding a bit more about polymorphic types and variants (which are the toolbox we use to construct phantom types).

Compile time or run time?

To ask if phantom types are useful we need to know first if they are applicable to our problem. Phantom types find only compile time errors. Let's understand what a compile time error could be in libvirt:

let conn = Libvirt.Connect.connect_readonly ()
let dom = Libvirt.Domain.lookup_by_name conn "test"
 ...
Libvirt.Domain.destroy dom   (* fail! *)

Clearly here the dom ("domain" = virtual machine) is derived from a read-only connection (conn), so the call to destroy must fail. It is also clear that the compiler can trivially know that conn / dom are read-only, because of the special connect_readonly call.

Contrast that with the following code:

printf "Connect read-only?" ;;
let readonly_flag = read_line () = "y"
let conn = Libvirt.Connect.open readonly_flag
(* etc. *)

Now the compiler cannot possibly predict what the user will type in at runtime, so this is not a situation where the compiler or phantom types can help. (The Libvirt.Connect.open call is one I just made up, it's not a real call precisely because of this problem).

So libvirt has two separate calls to create connections, connect_readonly which makes read-only connections and connect which makes read/write connections. The connections returned have different but compatible types, and because of this "compatibility" the connections can still be passed to the common non-destructive functions. Even more amazingly, the extra "is read/write" flag which is attached to the connection simply disappears at runtime, which means there is zero loss of efficiency when using phantom types (I'll explain a bit more about that below).

It's important to keep a very clear distinction in your head about what happens at compile time versus what happens at run time.

Mysterious polymorphic types

You may be familiar with polymorphic types such as 'a list, lists of any type, where 'a (pronounced alpha) stands for all types. Here's another example of a polymorphic type, a structure which contains a "free" field that can store any particular type:

type 'a t = { data : 'a }

We can make a structure containing string data for example. Notice its type:

# { data = "hello" } ;;
- : string t = {data = "hello"}

What is perhaps not so well known is that you can add extra polymorphism to any type you like, even when it doesn't seem to need it.

This just makes t an alias for the floating point type:

type t = float

But the following (legal) definition is much more mysterious:

type 'a t = float

What does it do, and how can you create anything of this type? The answer is that any float has this type, as you can prove very easily in the OCaml toplevel:

# (3.0 : unit t);;
- : unit t = 3.
# (10.4 : string t);;
- : string t = 10.4

Because the 'a isn't needed, it can be set to any type (unit and string in the examples above).

This isn't yet the "phantom" type though. It's tempting to think we could write a function which only works on string t (I'll call them "stringies"):

# let add_stringies (a : string t) (b : string t) = (a +. b : string t) ;;
val add_stringies : string t -> string t -> string t = <fun>

But in fact this function does not work!

# add_stringies (3.0 : unit t) 5.0 ;;
- : string t = 8.

This is because unit t and string t can be freely unified with each other because the compiler knows that both are really just floats:

# ((3.0 : unit t) : string t) ;;
- : string t = 3.

To prevent this "rogue" unification and allow us to write a function like add_stringies correctly, we have to hide the real type of t inside a module, like this:

module T : sig
  type 'a t
  val add_stringies : string t -> string t -> string t
end = struct
  type 'a t = float
  let add_stringies a b = a +. b
end

Module T is completely useless by the way, it's just setting the stage for ...

Phantom types

OCaml might have saved NASA from losing a $125 million space probe if only they'd had the following Length module which prevents programmers from mixing imperial and metric measurements:

module Length : sig
  type 'a t
  val meters : float -> [`Meters] t
  val feet : float -> [`Feet] t
  val (+.) : 'a t -> 'a t -> 'a t
  val to_float : 'a t -> float
end = struct
  type 'a t = float
  external meters : float -> [`Meters] t = "%identity"
  external feet : float -> [`Feet] t = "%identity"
  let (+.) = (+.)
  external to_float : 'a t -> float = "%identity"
end

open Length
open Printf

let () =
  let m1 = meters 10. in
  let m2 = meters 20. in
  printf "10m + 20m = %g\n" (to_float (m1 +. m2));
  let f1 = feet 40. in
  let f2 = feet 50. in
  printf "40ft + 50ft = %g\n" (to_float (f1 +. f2));
  (*printf "10m + 50ft = %g\n" (to_float (m1 +. f2)) (* error *) *)

(Try compiling and running this, then try uncommenting the very last line and compiling it again).

Just for readability, we're using polymorphic variant types instead of the basic types (unit and string from the previous section). This allows us to substitute meaningful type names like [`Meters] t which I hope is obvious as to what it contains. It also means the error messages from the compiler will be easy to read - that's important because we are expecting to get a compiler error each time the programmer makes a mistake.

Now look at the functions we have:

Two functions (meters and feet) convert floating point numbers into meters or feet respectively. But the implementation of these functions is completely efficient. They're just the identity operation (which the compiler turns into a null operation). At compile time, the values have this extra type information. But at run time the overhead evaporates completely. At run time, these are just floats.

The addition function is constrained: 'a t -> 'a t -> 'a t. This means you can use it on two meter measurements, or two feet measurements, but you cannot mix meters and feet. Furthermore the return type is the same as the input types, so this safety cascades through all code.

Finally we need a way to extract and print the results. I've included a rather naive to_float function, but for better safety we'd probably want to define special print functions which ensure that the output indicates the correct type back to the user.

Let's go back to our read-only/-write connections from the beginning. Remember that simple non-destructive status functions are safe for anyone to call, but destructive functions must only be used when you have a read/write connection. To express this we will use a slightly different feature of polymorphic variants, that is being able to express open types using [>...]. A read-only connection will have type [`Readonly] t and a read/write connection will have type [`Readonly|`Readwrite] t which means that it's compatible with the read-only type but has the extra read/write ability.

Status functions have type : [>`Readonly] t -> ... because they work with "read-only or greater".

Here is our module:

module Connection : sig
  type 'a t
  val connect_readonly : unit -> [`Readonly] t
  val connect : unit -> [`Readonly|`Readwrite] t
  val status : [>`Readonly] t -> int
  val destroy : [>`Readwrite] t -> unit
end = struct
  type 'a t = int
  let count = ref 0
  let connect_readonly () = incr count; !count
  let connect () = incr count; !count
  let status c = c
  let destroy c = ()
end

open Connection
open Printf

let () =
  let conn = connect_readonly () in
  printf "status = %d\n" (status conn);
  (*destroy conn; (* error *) *)
  let conn = connect () in
  printf "status = %d\n" (status conn);
  destroy conn

Again, after compiling this, try uncommenting the rogue call to destroy and notice that the error is caught by the compiler.

Here's another example, again it comes from actual deployed code. A "memory map" is a view into the memory of a virtual machine. When we first load a memory map we don't know anything about the endianness or word size of the virtual machine. We have to inspect the memory map first to determine endianness (little or big endian) and word size (32 or 64 bit pointers). Once we've determined both, we offer additional operations which work on the integers and pointers contained in the memory map.

So there are four "subtypes" (states?) of memory map, summarized in the diagram on the left.

Can we use phantom types to ensure that the transitions happen before specific calls are allowed? Yes we can!

We start by defining our phantom type. This is how it appears in the module signature (the mli file). The specifics of the implementation (from the ml file) aren't important here. Note that because there are two degrees of freedom (word size and endianness), there are two phantom types attached to t:

type ('a,'b) t

The basic of_file function makes a memory map from a file descriptor and base address. It returns a memory map with no word size or endianness, which is pretty clearly expressed in the return type:

val of_file : Unix.file_descr -> addr -> ([`NoWordsize], [`NoEndian]) t

Some functions work with any memory map, whether or not word size and endianness have been set. For example, the find function searches for strings in the memory map:

val find : ('a, 'b) t -> ?start:addr -> string -> addr option

A related function is find_align which finds strings that are aligned to the word size. This function cares that word size has been set, but not endianness, and its type is therefore:

val find_align : ([`Wordsize], 'b) t -> ?start:addr -> string -> addr option

The find_pointer function looks for pointers appearing in the memory map. Pointers have both endianness and word size implicitly, so this function can only be used when both have been set on the memory map. Its type is:

val find_pointer : ([`Wordsize], [`Endian]) t -> ?start:addr -> addr ->
  addr option

Finally of course we need a way to supply the word size and endianness to the memory map. Detecting these is a difficult and drawn-out process, so our main code will set each one individually by calling the following two functions:

val set_wordsize : ([`NoWordsize], 'b) t -> wordsize ->
  ([`Wordsize], 'b) t
val set_endian : ('a, [`NoEndian]) t -> endian ->
  ('a, [`Endian]) t

The compiler guarantees here are quite strict. Although the programmer can call the functions in either order, they must call each function only once. And of course the programmer won't be allowed to call functions like find_pointer until they have called both set_wordsize and set_endian exactly once (although the order they call the functions doesn't matter).

Personally I think this is a pretty awesome language feature. I'm not sure if any other non-functional languages can make these sorts of guarantees at compile time. (Perhaps Eiffel?)

One interesting thing is that the implementation of the memory map still has runtime checks in those functions (such as find_pointer) which need it. But you can be sure that the runtime checks will never fail. An improvement to the code would be to write it so it doesn't need any runtime checks at all.

Runtime and phantom types

My final example with phantom types will be to explain how to add runtime checks back in. Some situations simply cannot be checked at compile time, yet don't represent errors. For example in mlvirsh users can open read-only or read/write connections to the hypervisor. We deal with this by adding a limited amount of dynamic typing back into the system:

type conn_t =
  | No_connection
  | RO of Libvirt.ro Libvirt.Connect.t
  | RW of Libvirt.rw Libvirt.Connect.t

Of course we need to also add runtime checks into the program.

I will argue that this is an acceptable trade-off and still much better than languages which only do dynamic typing. We get the benefits of static types / early compiler errors when it's possible to check for them, but we can slip back to dynamic typing in the situations where it's necessary. Out of the entire suite of virt tools, just one (mlvirsh) needs runtime types.

Extending immutable data structures (part 2)

[This is part 2 of my series about extending immutable data structures in OCaml. You may want to go back and read part 1 first]

Previously I took this definition of an XML document tree from xml-light and asked how we could annotate nodes with extra data.

type xml = 
        | Element of (string * (string * string) list * xml list)
        | PCData of string

If you "think outside the box", or in this case literally outside the structure, you might see that you can add annotations using a hash table. The idea is that we'll hash the addresses of nodes to the annotated data.

Let's have a concrete example to make this all a bit clearer. Start with this simple document tree:

<a href="http://camltastic.blogspot.com/">Camltastic!</a>

which is written in OCaml as:

let str = PCData "Camltastic!"
let doc = Element ("a",
        ["href", "http://camltastic.blogspot.com/"],
        [str])

There are two nodes here (str and doc) and both have type xml.

A simple, and wrong, way to use a hash table to annotate these nodes is like this:

let h = Hashtbl.create 13
let add_annot node data = Hashtbl.add h node data
let get_annot node =
  try Some (Hashtbl.find h node)
  with Not_found -> None

It seems to work:

# add_annot doc "doc is annotated with this string" ;;
- : unit = ()
# get_annot doc ;;
- : string option = Some "doc is annotated with this string"
# get_annot str ;;
- : string option = None

But there are some subtle and not-so-subtle problems with this approach.

The first problem is that Hashtbl, by default, uses structural equality to hash nodes. If you had a document like <a>Link</a><a>Link</a> then there is no way to attach different data to the two links, because both links appear to be equal (they are equal, structurally). Attaching data to one link attaches the data to both.

The two other problems with this are garbage collection and copying. Garbage collection is defeated because the hash table maintains a permanent pointer to any annotated nodes. What we would like to happen is that if a node becomes garbage, the collector frees the node and any annotations on the node. In fact this never happens: the permanent pointer held by the hash table prevents any node from becoming garbage. The copying problem is that when the main program copies a node, the annotations aren't copied across.

Enter the Weak Hash Table

OCaml has a rarely-used but rather elegant module in the standard library called Weak. This module implements weak pointers. A weak pointer is like an ordinary pointer, but it doesn't "count" towards garbage collection. In other words if a value on the heap is only pointed at by weak pointers, then the garbage collector may free that value as if nothing was pointing to it.

A weak hash table uses weak pointers to avoid the garbage collection problem above. Instead of storing a permanent pointer to the keys or values, a weak hash table stores only a weak pointer, allowing the garbage collector to free nodes as normal.

It probably isn't immediately obvious, but there are 3 variants of the weak hash table, to do with whether the key, the value or both are weak. (The fourth "variant", where both key and value are strong, is just an ordinary Hashtbl). Thus the OCaml standard library "weak hash table" has only weak values. The Hweak library has weak keys and values. And the WeakMetadata library (weakMetadata.ml, weakMetadata.mli) is a version of Hweak modified by me which has only weak keys.

Which sort of weak hash table do we need? If you look at the Hashtbl implementation above you'll see that the key corresponds to the xml node and the value corresponds to the metadata attached to nodes. We assume that the main program holds onto a pointer to the xml tree until it is no longer needed, whereupon it should be collected. So we definitely need weak keys. How about the values (annotations)? The main program probably isn't holding any references to the annotations - it expects to annotate a node and then forget about the annotation until it is needed later. So values should not be weak (otherwise our annotation library will be rather "forgetful"). You'll therefore need to use my modified WeakMetadata library to get around the garbage collection problem.

Using WeakMetadata you can annotate immutable data structures, as this test program shows. Although we have solved the garbage collection problem, the other two problems I mentioned remain. Namely, it's still using structural equality, and if the main program copies a node, then the annotations don't get copied too.

However there are some rather more insidious problems that remain with this whole approach, which are down to how weak pointers are actually implemented inside the OCaml garbage collector. I wrote about them in this posting on the OCaml mailing list which also includes some analysis of the performance and memory usage of annotating XML document nodes.

Part 3 (next week) will look at what I hope is the "final word" on safely extending data structures.

Extending immutable data structures (part 1)

Functional languages are famous because they let the programmer build complicated data structures effortlessly. It's very compelling to describe the type of any XML document in just three lines of code:

type xml = 
        | Element of (string * (string * string) list * xml list)
        | PCData of string

And I won't recur (pun, intended) on the subject of how easy it is to write code to process these data structures.

However there is one thing which is difficult to do, and that is to meaningfully extend or annotate such data.

Let's say as a practical example I want to write a CSS renderer for XML documents. A first step to doing this is to annotate each node in the XML document with the list of styles that apply to it. (Styles are inherited, so natural recursive algorithms work quite well for this). The second step is to take what CSS calls "replaced elements" (elements like <IMG> that have an intrinsic size not known to CSS itself) and compute their sizes.

The xml type defined above is not extensible at all. In order to allow it to store styles and sizes for replaced elements we'd need to change the type definition to something like this:

type xml = 
        | Element of (string * (string * string) list * xml list
            * style list * size option)
        | PCData of string

Unfortunately this is no use to us because all our existing code that worked on the old xml type no longer works on this new type. That is no mere theoretical concern either, because the old xml type at the top wasn't just chosen at random. It is in fact the type used by Xml-Light, a useful, simplified XML parser and printer, and we cannot change this type without stopping using this library.

PXP (another XML library -- OCaml has several) has a polymorphic XML type, allowing you to attach precisely one arbitrary datum to each node. In terms of the xml type defined above, it looks similar to this:

type 'a xml = 
        | Element of ('a, ...

This is half-way useful, because one can now use the library functions (they assume polymorphism, so work fine), but has some serious shortcomings of its own. One is that you can't easily build up independent modules. If there is a PXP module which uses the 'a for its own purpose then one cannot extend the XML document any further. If you avoid that, you can attach multiple data by using a tuple, but each module that wants to attach data had better know about all the other modules in advance and agree on a single tuple type.

For the CSS styles / sizes example, we could also imagine adding a 'b styles with 'b instantiated as size when that is needed. You'd end up with document types like this:

unit xml          # The basic document
unit styles xml   # After annotating with styles (pass 1)
size styles xml   # After annotating with sizes (pass 2)

But you can't write a function that just operates on "an XML document annotated with sizes", unless it "knows" about all the other annotations and the order in which they were applied. (Is the type size styles xml or styles size xml if we happened to swap the two passes around?)

In part 2 (next week) I'll look at some radically different ways to annotate and extend immutable data structures.