Re: null values and sentinels

[Xavier Leroy <Xavier.Leroy@inria.fr>]

> I'd like to create a type like:
> # type foo = {xxx: int; mutable yyy: foo};;
> so that I can add nodes by mutating the "yyy" slots.  Unfortunately,
> it seems that I must create a sentinel value of type "foo" to stand
> for a null pointer.  This works but I'd like to be able to use pattern
> matching on the value of yyy so as to get compile-time warnings if I
> forget to check for null.
> 
> So, I tried this:
> # type foo2 = {xxx: int; mutable yyy: bar} and bar = Empty | Pointer of
> foo2;;
> This works (i.e.  I can match on yyy in the way that I want), but
> it _seems_ like this will create an extra indirection object in the
> yyy slot.  Whether it does or not seems to be a compiler question to
> me...  "Pointer of foo2" could be collapsed into foo2 by the
> compiler.  Is it?  How should I approach this situation?

The representation of Caml datatypes is uniform and always involve an
indirection.  So, you'll indeed get an extra indirection with the
"foo2" approach.

You're correct that the compiler could eliminate the indirection in
your example above.  The old Caml V3.1 compiler did a lot of
optimizations along these lines, however they don't mix well with the
module system.  More recently, Jacques Garrigue and I have been
looking at similar schemes for optimizing the "'a option" type.  While
it can be done, the implementation cost is significant, and it messes
up the compiler and the runtime system a little too much to my taste.

My advice would be to go with the clearer solution "foo2", and then
benchmark carefully your program to see if the extra indirection
really hurts performance.  (Most often, it does not.)  If shaving an
indirection really matters, you'll have to switch to "foo" and
carefully rewrite your pattern-matchings.

- Xavier Leroy