[Caml-list] Identity crisis

[Caml-list] Identity crisis

[Lauri Alanko]

As is well known, ocaml as no true equality comparison: (=) conflates
observably distinct values (mutable records that happen to have the
same contents at the time of comparison), whereas (==) introduces
distinctions that would otherwise been unobservable (between immutable
records that have the same contents but happen to have different
addresses). Also, (=) fails with an exception if it encounters
something it doesn't like (abstract values).

Moreover, since addresses are not stable (objects can be moved during
GC), there is no way efficient way to use record identities as keys in
trees or hash tables.

What all this means is that if the programmer wants to have an
efficiently implemented set of stateful mutable records, she has to
make sure that each record contains a unique id, and she has to
provide a custom hash or compare operation that uses this id, and she
also has to write wrappers if these stateful things are ever elements
of some other structures that need comparison or hashing. This is
superbly tedious.

Strangely enough, there is a class of stateful values that Does The
Right Thing straight out of the box: objects. You can use the standard
equality, hashing and comparison operations with objects, and they all
use a stable identity that isn't affected by GC.

Hence, if you want references in your data structures to be compared
by identity (and I can't see a reason why you would ever want
otherwise), you could use this as an alternative implementation of refs:

class ['a] ref (x : 'a) = object
    val mutable contents = x
    method get = contents
    method set x = contents <- x
end

let ref = new ref
let (!) r = r#get
let (:=) r = r#set

However, it seems really strange that one has to use objects (which
are usually considered a wholly optional component of the language) in
order to get correct semantics for stateful identities.

I don't really have any good suggestions. It would be nice if records
with mutable fields were compared like objects (and had stable ids
internally). But with e.g. strings there is no solution in sight since
the very same type is used both for string values and mutable string
buffers, so every comparison would be wrong in some context. Perhaps
we must simply accept that ocaml is irredeemably broken in this
regard.

And perhaps I will begin to use objects more from now on. I don't like
their complexity, but at least objects know who they are.


Lauri

Re: [Caml-list] Identity crisis

[Alain Frisch]

On 01/10/2011 01:13 PM, Lauri Alanko wrote:
> And perhaps I will begin to use objects more from now on. I don't like
> their complexity, but at least objects know who they are.

I've written a blog entry related to these questions a few days ago:

http://www.lexifi.com/blog/references-physical-equality

In particular, I show an ugly hack to tell OCaml to use physical 
equality for records (you have to manage explicitly the unique id).


-- Alain