[Caml-list] equality over functional value

[Caml-list] equality over functional value

[Georges Brun-Cottan]

Hi, 

A friend of mine is just starting with ocaml. He was puzzled by the
following result:

# let a i = i;;
val a : 'a -> 'a = <fun>
# let b i = i;;
val b : 'a -> 'a = <fun>
# a=b;;
Uncaught exception: Invalid_argument "equal: functional value".
# a=a;;
- : bool = true
# 

That is 'a=a' does not return the expected exception.  Actually it
first hit this "curiosity" when creating a polymorphic 'sort' function
on lists - and by applying it to a [sort;sort..] list. It worked.

Is this a bug? 

It might means that some errors can came up detected later than any
Camel rider would have expected...


[Francais]

Bonjour, 

Un ami débute en ocaml. Il fut intrigué par le résultat suivant:

# let a i = i;;
val a : 'a -> 'a = <fun>
# let b i = i;;
val b : 'a -> 'a = <fun>
# a=b;;
Uncaught exception: Invalid_argument "equal: functional value".
# a=a;;
- : bool = true
# 

a=a ne retourne pas l'exception attendue. 

Est-ce un bogue? 

Je suis un peu inquiet à l'idée que certaines erreurs de programmation
grossière peuvent être ainsi être détectés trop tardivement.

-- Georges
-------------------
To unsubscribe, mail caml-list-request@inria.fr.  Archives: http://caml.inria.fr

Re: [Caml-list] equality over functional value

[Alain Frisch]

While we are about it, what is the reason for disallowing structural
comparison over functional values  (that is, comparing for instance the
code address, then the environment) ?  I agree that this semantics may be
somewhat puzzling, but it is useful when storing closures in complex data
structures.

-- 
  Alain Frisch

-------------------
To unsubscribe, mail caml-list-request@inria.fr.  Archives: http://caml.inria.fr

Re: [Caml-list] equality over functional value

[Marcin 'Qrczak' Kowalczyk]

Fri, 20 Apr 2001 23:23:26 +0200 (MET DST), Alain Frisch <frisch@clipper.ens.fr> pisze:

> While we are about it, what is the reason for disallowing structural
> comparison over functional values  (that is, comparing for instance the
> code address, then the environment) ?

It would say that (fun x -> x+1) is not equal to (fun x -> x+1).
Or maybe that it is, depending on how smart the compiler is.

And it's impossible to say whether (fun () -> 1+2) is equal to
(fun () -> 2+1).

Embedding pointer equality of immutable values into value equality
doesn't have a sane meaning.

-- 
 __("<  Marcin Kowalczyk * qrczak@knm.org.pl http://qrczak.ids.net.pl/
 \__/
  ^^                      SYGNATURA ZASTĘPCZA
QRCZAK

-------------------
To unsubscribe, mail caml-list-request@inria.fr.  Archives: http://caml.inria.fr

Re: [Caml-list] equality over functional value

[David Monniaux]

On Fri, 20 Apr 2001, Georges Brun-Cottan wrote:

> That is 'a=a' does not return the expected exception.  Actually it

I bet that the comparison function tests the equality of pointers
(a==a) before attempting anything else, including checking that the values
are not closures.


David Monniaux            http://www.di.ens.fr/~monniaux
Laboratoire d'informatique de l'École Normale Supérieure,
Paris, France
-------------------
To unsubscribe, mail caml-list-request@inria.fr.  Archives: http://caml.inria.fr

Re: [Caml-list] equality over functional value

[Jean-Christophe Filliatre]

Georges Brun-Cottan writes:
 > 
 > Hi, 
 > 
 > A friend of mine is just starting with ocaml. He was puzzled by the
 > following result:
 > 
 > # let a i = i;;
 > val a : 'a -> 'a = <fun>
 > # let b i = i;;
 > val b : 'a -> 'a = <fun>
 > # a=b;;
 > Uncaught exception: Invalid_argument "equal: functional value".
 > # a=a;;
 > - : bool = true
 > # 
 > 
 > That is 'a=a' does not return the expected exception.  Actually it
 > first hit this "curiosity" when creating a polymorphic 'sort' function
 > on lists - and by applying it to a [sort;sort..] list. It worked.
 > 
 > Is this a bug? 

I  don't  think this  behavior  is intentional,  but  it  has an  easy
explanation: for better efficiency, the structural comparison function
(in  byterun/compare.c)  first   tries  physical  equality,  and  then
structural equality if  there is no physical equality.  So in the case
of a=a, the answer is true because of physical equality.

Hope this helps,
-- 
Jean-Christophe FILLIATRE
  mailto:Jean-Christophe.Filliatre@lri.fr
  http://www.lri.fr/~filliatr
-------------------
To unsubscribe, mail caml-list-request@inria.fr.  Archives: http://caml.inria.fr

Re: [Caml-list] equality over functional value

[Xavier Leroy]

> Hi, 
> 
> A friend of mine is just starting with ocaml. He was puzzled by the
> following result:
> 
> # let a i = i;;
> val a : 'a -> 'a = <fun>
> # let b i = i;;
> val b : 'a -> 'a = <fun>
> # a=b;;
> Uncaught exception: Invalid_argument "equal: functional value".
> # a=a;;
> - : bool = true
> # 
> 
> That is 'a=a' does not return the expected exception.  Actually it
> first hit this "curiosity" when creating a polymorphic 'sort' function
> on lists - and by applying it to a [sort;sort..] list. It worked.
> 
> Is this a bug? 

It's a questionable behavior.  As Alain Frisch said, polymorphic
structural equality is implemented by first testing physical (pointer)
equality.  Besides speed, this has the advantage that x == y implies x = y.

However, this causes a = a where a is a function to return true
instead of raising an exception as you expect.

(Another weird consequence of this implementation of physical equality
is that
             (nan, nan) = (nan, nan)
returns true, which is incorrect according to the IEEE specs: the NaN
float is not equal to itself!)

The special case (first test pointer equality) in structural equality
could be eliminated, although I don't know how big a performance
impact this would have.

More generally, equality between functions can be interpreted in
several ways:

1- Extensional, pessimistic: f = g iff for all x, f x = g x,
and since this is undecidable, equality always raises an exception
when passed function values.

2- Extensional, approximated: same definition as above, but we return
"true" in some cases where the two functions are guaranteed to be
extensionally equal, e.g. f and g point to the same closure, or even f
and g have the same code pointer and contain equal values in their
environments.  Otherwise, we raise an exception.

3- By representation: two functions are equal iff their closures are
structurally equal, i.e. they have the same code pointer and contain
equal values in their environment.

Interpretation 3- is useless I think, because it depends very much on
the compiler's closure representation strategy.  In other terms, while
a "true" result guarantees that the two functions are extensionally
equal, a "false" result does not mean anything.

The current interpretation 2- is semantically more sound: if it
returns "true", then the two functions are extensionally equal;
and it never returns "false", so it never claims that two functions
are extensionally different!  Still, it is rather unintuitive.
Also, the current implementation exposes too much the order of the tests,
i.e. "(0, f) = (1, g)" returns "false", but
"(f, 0) = (g, 1)" raises an exception.

Interpretation 1- is easiest to explain, although it entails a bit of
a performance penalty as I said above.

Food for thoughts...

- Xavier Leroy
-------------------
To unsubscribe, mail caml-list-request@inria.fr.  Archives: http://caml.inria.fr

Re: [Caml-list] equality over functional value

[Alain Frisch]

On Mon, 23 Apr 2001, Xavier Leroy wrote:

> More generally, equality between functions can be interpreted in
> several ways:
>...
> 3- By representation: two functions are equal iff their closures are
> structurally equal, i.e. they have the same code pointer and contain
> equal values in their environment.
> 
> Interpretation 3- is useless I think, because it depends very much on
> the compiler's closure representation strategy.  In other terms, while
> a "true" result guarantees that the two functions are extensionally
> equal, a "false" result does not mean anything.

For equality testing, this comparison doesn't make much sense. But it may
be useful because it defines a total (quasi-)ordering on functional values
whose associated equivalence is: 

- coarser than physical equality 

- finer than observational equivalence

It is probably bad style to rely heavily on such an ordering, but it is
sometimes annoying not to be able to use generic comparison function when
you have functional types somewhere in your complex data structures.
Even if you associate a "stamp" to functional values, you can't use
generic comparisons.


Having said that, being able to define custom operation for Caml values
seems much more important and general to me. The interface may be
something like:

type 'a t
type 'a operations = { compare: 'a -> 'a -> int ; hash : 'a -> int ; ... }
val wrap : 'a operations -> 'a -> 'a t
val extract : 'a t -> 'a


-- 
  Alain Frisch

-------------------
To unsubscribe, mail caml-list-request@inria.fr.  Archives: http://caml.inria.fr

Re: [Caml-list] equality over functional value

[Fabrice Le Fessant]

Personally, I think functions comparisons should always have the same
behavior. So, we have two options:

- Always raise an exception, even for f = f. This would have a cost
  for all programs, since the runtime would have to check the type of
  the value before testing for pointer equality.

- Never raise an exception. Function comparison would be closure
  comparison. Most people will never use any such comparison, and I
  don't know any already-written program whose behavior would be
  broken by this change. Even if the semantics is not clearly defined,
  it is not the first time (cf labels), and it can be seen as an
  implementation compromise...

So, I personnaly vote for the second one.


- Fabrice

-------------------
To unsubscribe, mail caml-list-request@inria.fr.  Archives: http://caml.inria.fr