null values and sentinels

null values and sentinels

[Jerry Jackson]

Hello,

I'd like to know what the recommended solution to the following 
situation is...

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?

Thanks for any help,

Jerry Jackson

Re: null values and sentinels

[Xavier Leroy]

> 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

Re: null values and sentinels

[Anton Moscal]

On Tue, 12 Jan 1999, Jerry Jackson wrote:

> Hello,
> 
> I'd like to know what the recommended solution to the following 
> situation is...
> 
> 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.

The only known to me solution is the following:

declare

    let rec foo_nil = {xxx=1; yyy = foo_nil};

and then use foo_nil as Nil constant. The main problem is the
following: foo_nil can't be used in the matching.
 
Anton E.Moscal