This site is updated infrequently. For up-to-date information, please visit the new OCaml website at ocaml.org.

Re: [Caml-list] Re: ocaml sefault in bytecode: unanswered questions
[ Home ] [ Index: by date | by threads ]
[ Search: ]

[ Message by date: previous | next ] [ Message in thread: previous | next ] [ Thread: previous | next ]
 Date: 2009-08-09 (18:55) From: Elnatan Reisner Subject: Re: [Caml-list] Re: ocaml sefault in bytecode: unanswered questions
```Continuing this conversation about equality...

On Aug 9, 2009, at 9:20 AM, David Allsopp wrote:

> Ivan Chollet wrote:
>
>> I would have thought physical equality implies structural equality,
>> but it
>> doesn't seem like it.
>> Can you please explain to me what’s wrong there?
>
> "It does" - but only with the given caveat that comparison of cyclic
> structures may not terminate. Pervasives.compare has a similar
> restriction,
> although note that [compare q q] in your example does return 0
> (which is
> lucky or it would be a bug as the docs for Pervasives.(==) state
> that [x ==
> y] => [compare x y = 0]).

(==):

First, what David says isn't *quite* what the documentation says. The
documentation only says this is [x==y] implies [compare x y = 0]  for
non-mutable structures. And in fact, what the documentation says is
surprisingly weak: an implementation could define (==) as *always
false* for non-mutable structures and yet satisfy the documentation.
I'm not sure of the right way to reword it, but this loophole in the
specification seems undesirable.

My other issue is that the description of (==) for mutable structures
doesn't specify that it is symmetric; reading the documentation
literally only implies that e1 is a substructure of e2. Even just
adding 'and vice versa' might clean this up:
e1 == e2 is true if and only if physical modification of e1 also
affects e2 and vice versa

Okay, now for more substantive questions:

> The notes in http://caml.inria.fr/mantis/view.php?id=3322 may be of
> interest
> too...

I hadn't paid attention to the distinction drawn between 'may not
terminate' and 'does not terminate' until I read the discussion at
that link, but it's relevant to my question below...

On Aug 9, 2009, at 9:55 AM, Alain Frisch wrote:

> On 8/9/2009 2:06 PM, ivan chollet wrote:
>
>> I would have thought physical equality implies structural equality,
>> but
>> it doesn’t seem like it.
>>
>> Can you please explain to me what’s wrong there?
>
> There are two modes for the generic comparison. The total mode
> (Pervasives.compare) creates a total ordering between values (except
> for functional values and custom blocks with no comparison function)
> and uses physical equality as a shortcut to cut the recursive
> traversal of sub-values. The non-total mode (used by the operators =
> < > <= >=) has a different behavior for NaN values ([nan <= x], [x
> <= nan], and [nan = x] all return false, including when x is nan)
> and does not use the physical equality shortcut (so that [let x =
> (nan, nan) in x = x] returns false).

In terms of 'may not' versus 'does not' terminate, I just noticed that
the current documentation for (=) says 'may not terminate' while the
documentation for (>=) says 'does not terminate'. However, the example
type t = { a : t };;
let rec x = { a = x } in x = x
doesn't terminate in OCaml 3.11. This seems to be about as simple a
cyclic structure as there is, so shouldn't (=)'s documentation say
'Equality between cyclic structures does not terminate.'?

Also, the documentation for Pervasives.compare says 'may not
terminate'. Is this supposed to imply that it uses the shortcut Alain
mentions (because if it did not use physical equality as a shortcut
then it would say 'does not terminate')? Or is this shortcutting meant
to be undocumented?

And is there any reason, aside from NaN values, that (=) does *not*
use physical equality as a shortcut? The only other reason I can think
of is that, in cases where things are in fact *not* physically equal,
checking physical equality would introduce a small overhead.

In any case, if I have a data structure which I know does not contain
any NaNs (for example, maybe it doesn't contain any floats
whatsoever), is there ever a reason I should prefer (=) to (compare x
y = 0)? It sounds to me like compare is preferable because of its
shortcutting behavior.

-Elnatan
```