From mboxrd@z Thu Jan  1 00:00:00 1970
Received: from mail4-relais-sop.national.inria.fr (mail4-relais-sop.national.inria.fr [192.134.164.105])
	by walapai.inria.fr (8.13.6/8.13.6) with ESMTP id p0ACE4Pn012724
	for <caml-list@sympa-roc.inria.fr>; Mon, 10 Jan 2011 13:14:05 +0100
X-IronPort-Anti-Spam-Filtered: true
X-IronPort-Anti-Spam-Result: Aq8BAE+HKk2A1gkBe2dsb2JhbACWMI4jAQEWIgUfu1iCdYJXBA
X-IronPort-AV: E=Sophos;i="4.60,299,1291590000"; 
   d="scan'208";a="84742043"
Received: from courier.cs.helsinki.fi (HELO mail.cs.helsinki.fi) ([128.214.9.1])
  by mail4-smtp-sop.national.inria.fr with ESMTP/TLS/DHE-RSA-AES256-SHA; 10 Jan 2011 13:13:27 +0100
Received: from melkinpaasi.cs.helsinki.fi (melkinpaasi.cs.helsinki.fi [128.214.9.14])
  (AUTH: PLAIN cs-relay, TLS: TLSv1/SSLv3,256bits,AES256-SHA)
  by mail.cs.helsinki.fi with esmtp; Mon, 10 Jan 2011 14:13:26 +0200
  id 00093F1F.4D2AF7E6.000019B4
Received: by melkinpaasi.cs.helsinki.fi (Postfix, from userid 37211)
	id F25658506D; Mon, 10 Jan 2011 14:13:25 +0200 (EET)
Date: Mon, 10 Jan 2011 14:13:25 +0200
From: Lauri Alanko <la@iki.fi>
To: caml-list@inria.fr
Message-ID: <20110110121325.GH323@melkinpaasi.cs.helsinki.fi>
Mime-Version: 1.0
Content-Type: text/plain; charset=us-ascii
Content-Transfer-Encoding: 7bit
Content-Disposition: inline
User-Agent: Mutt/1.5.20 (2009-06-14)
Subject: [Caml-list] Identity crisis

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