[Caml-list] Strange physical equality behavior

[Caml-list] Strange physical equality behavior

[Oleg Trott]

        Objective Caml version 3.07+2

# sin == sin;;
- : bool = false
# let f = sin;;
val f : float -> float = <fun>
# f == f;;
- : bool = true

I don't like the fact that (sin == sin) returns false.

-- 
Oleg Trott <oleg_trott@columbia.edu>

-------------------
To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr
Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners

Re: [Caml-list] Strange physical equality behavior

[Jacques Garrigue]

From: Oleg Trott <oleg_trott@columbia.edu>

>         Objective Caml version 3.07+2
> 
> # sin == sin;;
> - : bool = false
> # let f = sin;;
> val f : float -> float = <fun>
> # f == f;;
> - : bool = true
> 
> I don't like the fact that (sin == sin) returns false.

This is coherent with the specification of (==), which says that
it is fully specified only for mutable structures.
(** [e1 == e2] tests for physical equality of [e1] and [e2].
   On integers and characters, physical equality is identical to structural
   equality. On mutable structures, [e1 == e2] is true if and only if
   physical modification of [e1] also affects [e2].
   On non-mutable structures, the behavior of [(==)] is
   implementation-dependent; however, it is guaranteed that
   [e1 == e2] implies [e1 = e2]. *)
And note that:
  # sin = sin;;
  Exception: Invalid_argument "equal: functional value".
so returning false in this case is valid.

This is for the defensive part.

Now the real explanation: primitives (appearing as "external" in the
.mli) are not closures by themselves. A closure is built as needed.
As a result, two different occurences of "sin" will create different
closures.
If this is a problem for you, you should just be careful of wrapping
all your primitives. This is just what "let f = sin" does.
(Note however that the specification doesn't say what should be (==)
for closures either. It just happens to be reflexive in the current
implementation.)

Jacques Garrigue

-------------------
To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr
Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners

Re: [Caml-list] Strange physical equality behavior

[Oleg Trott]

On Sunday 09 November 2003 08:33 pm, Jacques Garrigue wrote:
> From: Oleg Trott <oleg_trott@columbia.edu>
>
> >         Objective Caml version 3.07+2
> >
> > # sin == sin;;
> > - : bool = false
> > # let f = sin;;
> > val f : float -> float = <fun>
> > # f == f;;
> > - : bool = true
> >
> > I don't like the fact that (sin == sin) returns false.
>
> This is coherent with the specification of (==), which says that
> it is fully specified only for mutable structures.
> (** [e1 == e2] tests for physical equality of [e1] and [e2].
>    On integers and characters, physical equality is identical to structural
>    equality. On mutable structures, [e1 == e2] is true if and only if
>    physical modification of [e1] also affects [e2].
>    On non-mutable structures, the behavior of [(==)] is
>    implementation-dependent; however, it is guaranteed that
>    [e1 == e2] implies [e1 = e2]. *)

<snip>

So returning "true" for "sin == sin" and "sin = sin" wouldn't break the above 
guarantee.

Here are my reasons for wanting such behavior (not just for "sin" of course, 
but also "(+)" , etc., and especially for "compare"):

As was discussed lately [1], the functorial interfaces (as used in the 
standard library) are somewhat clumsy. One solution could be to pass the 
necessary ordering and hashing functions as optional parameters to "emtpy" or 
"create". However, in this case, functions would need to be compared at 
runtime

compare_functions f g = try f = g with _ -> false

So e.g. "compare == compare" returning true would be a lot more convenient

[1] http://groups.google.com/groups?selm=fa.cvslsk1.37iiq9%40ifi.uio.no


-- 
Oleg Trott <oleg_trott@columbia.edu>

-------------------
To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr
Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners

Re: [Caml-list] Strange physical equality behavior

[Jacques Garrigue]

From: Oleg Trott <oleg_trott@columbia.edu>

> So returning "true" for "sin == sin" and "sin = sin" wouldn't break
> the above guarantee.

Of course.
And returning true for "sin = (fun x -> cos (x -. acos (-1.) /. 2))"
wouldn't break it either.
The specification is just designed to avoid having to do that: to
allow the compiler to choose the most efficient runtime
representation. It might actually just return "false" when you compare
any two functions, but even this would require some more computation.

> Here are my reasons for wanting such behavior (not just for "sin" of course, 
> but also "(+)" , etc., and especially for "compare"):
> 
> As was discussed lately [1], the functorial interfaces (as used in the 
> standard library) are somewhat clumsy. One solution could be to pass the 
> necessary ordering and hashing functions as optional parameters to "emtpy" or 
> "create". However, in this case, functions would need to be compared at 
> runtime
> 
> compare_functions f g = try f = g with _ -> false
> 
> So e.g. "compare == compare" returning true would be a lot more convenient

The problem is that compare has several implementations, depending on
the type of its argument, to be more efficient. One may imagine tricks
to make sure that any one of these implementations is shared between
all its occurences (but even this may be complicated while keeping
inlining). But generic compare cannot be equal to float compare, while
they are just separated by their types.

The functorial approach offers a much cleaner solution.
Alternatively, you can think of a system of registered comparison
functions:
  type 'a comparison = {id: int; compare: 'a -> 'a -> int}
  let count = ref 0
  let make_compare f = incr count; {id = !count; compare = f}
  let same f1 f2 = (f1.id = f2.id)
If comparison is kept abstract, you can then safely check for
equality.
A lighter way would be to combine this registration with the "empty"
function: two sets can be combined if they were created from the same
empty set.

The last solution is not to bother about that: I'm yet to see code
mixing two sets of the same type but with different comparison
functions. Sounds silly.

Jacques Garrigue

-------------------
To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr
Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners

Re: [Caml-list] Strange physical equality behavior

[Michal Moskal]

On Mon, Nov 10, 2003 at 05:29:24PM +0900, Jacques Garrigue wrote:
> The last solution is not to bother about that: I'm yet to see code
> mixing two sets of the same type but with different comparison
> functions. Sounds silly.

For me it doesn't. You cannot prevent user from shooting his foot in
this case. For example consider:

  let cmp x y = Random.int ()

This is very good comparision functions, and can also be used with
functiorial interface. You may say it is silly, but random functions 
(that are not total orderings) can be created by accident (for example
by comparing some mutable member or what's not).

-- 
: Michal Moskal :: http://www.kernel.pl/~malekith : GCS {C,UL}++++$ a? !tv
: PLD Linux ::::::::: Wroclaw University, CS Dept : {E-,w}-- {b++,e}>+++ h

-------------------
To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr
Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners

Re: [Caml-list] Strange physical equality behavior

[Jacques Garrigue]

From: Michal Moskal <malekith@pld-linux.org>
> On Mon, Nov 10, 2003 at 05:29:24PM +0900, Jacques Garrigue wrote:
> > The last solution is not to bother about that: I'm yet to see code
> > mixing two sets of the same type but with different comparison
> > functions. Sounds silly.
> 
> For me it doesn't. You cannot prevent user from shooting his foot in
> this case. For example consider:
> 
>   let cmp x y = Random.int ()
> 
> This is very good comparision functions, and can also be used with
> functiorial interface. You may say it is silly, but random functions 
> (that are not total orderings) can be created by accident (for example
> by comparing some mutable member or what's not).

Looks like you are supporting my point.
I was just saying that I'm yet to see somebody trying to take the
union of two sets defined with different (supposedly correct)
comparison functions.
And you point out a much more probable danger, which cannot be
prevented neither by the type system or dynamic checks.
So using the type system (or dynamic checks) to prevent an unprobable
risk, while there are much more probable ones, seems an overkill.

But I won't go more in that direction: as a type freak, preventing any
risk is good.

     Jacques Garrigue

-------------------
To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr
Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners

Re: [Caml-list] Strange physical equality behavior

[Oleg Trott]

On Sunday 09 November 2003 08:33 pm, Jacques Garrigue wrote:
>  On mutable structures, [e1 == e2] is true if and only if
>    physical modification of [e1] also affects [e2].

By the way, either "mutable structures" or "physical modification" need to be 
clarified, because if (int ref list) is "mutable" then the above is wrong:

 let a = [ref 0];;
 let b = ref 0 :: a;;
 incr (List.hd a);; (*  physical  ? *)
 a == b;;
 b;;

> On non-mutable structures, the behavior of [(==)] is
> implementation-dependent; however, it is guaranteed that
> [e1 == e2] implies [e1 = e2].

This doesn't work for "nan" though, as was recently discussed. [1] 

> The functorial approach offers a much cleaner solution.

I'm not convinced.

With non-functorial sets:

type t = Leaf of string | Node of t Set.t

How would you do this with functorial sets? Perhaps like this:

http://groups.google.com/groups?selm=fa.dlqsupe.1c6ajga%40ifi.uio.no

    module A : sig
                 type t = Leaf of string | Node of ASet.t
                 val compare: t -> t -> int
               end
             = struct
                 type t = Leaf of string | Node of ASet.t
                 let compare t1 t2 =
                   match (t1, t2) with
                     (Leaf s1, Leaf s2) -> Pervasives.compare s1 s2
                   | (Leaf _, Node _) -> 1
                   | (Node _, Leaf _) -> -1
                   | (Node n1, Node n2) -> ASet.compare n1 n2
               end
    and ASet : Set.S with type elt = A.t
             = Set.Make(A)

(BTW, that example doesn't yet work in 3.07-2 default toplevel. And couldn't 
one write "let compare = Pervasives.compare" above? )

> I'm yet to see code mixing two sets of the same type but with different 
> comparison functions.

Exactly! That's why *statically* assuring ordering function consistency is not 
all that important [2]. Which is why x==x would be a bigger help than 
recursive modules.

[1] I can understand false "nan = nan", because "nan" is a kind of exception, 
but false "x == x" feels very non-mathematical to me.

[2] I am a static typing fan, but this seems excessive.

Regards,
Oleg

P.S. I've already participated in this discussion longer than my tolerance for 
language-lawyerism or passion about this issue allow me, so I'll probably end 
it here.
-- 
Oleg Trott <oleg_trott@columbia.edu>

-------------------
To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr
Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners

Re: [Caml-list] Strange physical equality behavior

[David Brown]

On Tue, Nov 11, 2003 at 01:48:22AM -0500, Oleg Trott wrote:
> On Sunday 09 November 2003 08:33 pm, Jacques Garrigue wrote:
> >  On mutable structures, [e1 == e2] is true if and only if
> >    physical modification of [e1] also affects [e2].
> 
> By the way, either "mutable structures" or "physical modification" need to be 
> clarified, because if (int ref list) is "mutable" then the above is wrong:

If you take structure to mean a single data type, rather than a more
complicated data structure, then it is true.

Dave

-------------------
To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr
Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners

Re: [Caml-list] Strange physical equality behavior

[brogoff]

On Tue, 11 Nov 2003, Oleg Trott wrote:
> On Sunday 09 November 2003 08:33 pm, Jacques Garrigue wrote:
> > The functorial approach offers a much cleaner solution.
>
> I'm not convinced.
>
> With non-functorial sets:
>
> type t = Leaf of string | Node of t Set.t
>
> How would you do this with functorial sets? Perhaps like this:
>
> http://groups.google.com/groups?selm=fa.dlqsupe.1c6ajga%40ifi.uio.no
>
>     module A : sig
>                  type t = Leaf of string | Node of ASet.t
>                  val compare: t -> t -> int
>                end
>              = struct
>                  type t = Leaf of string | Node of ASet.t
>                  let compare t1 t2 =
>                    match (t1, t2) with
>                      (Leaf s1, Leaf s2) -> Pervasives.compare s1 s2
>                    | (Leaf _, Node _) -> 1
>                    | (Node _, Leaf _) -> -1
>                    | (Node n1, Node n2) -> ASet.compare n1 n2
>                end
>     and ASet : Set.S with type elt = A.t
>              = Set.Make(A)
>
> (BTW, that example doesn't yet work in 3.07-2 default toplevel. And couldn't
> one write "let compare = Pervasives.compare" above? )

 module rec A : (* a forgotten "rec" inserted *)
    sig
      type t = Leaf of string | Node of ASet.t
      val compare: t -> t -> int
    end
    = struct
      type t = Leaf of string | Node of ASet.t
      let compare t1 t2 =
        match (t1, t2) with
          (Leaf s1, Leaf s2) -> Pervasives.compare s1 s2
        | (Leaf _, Node _) -> 1
        | (Node _, Leaf _) -> -1
        | (Node n1, Node n2) -> ASet.compare n1 n2
    end
and ASet : Set.S with type elt = A.t
      = Set.Make(A)

It's a simple syntax error. And, if we use Pervasives.compare, we don't know
for sure how the Leaf <-> Node comparison will work, do we? What if it's
dependent on the order of occurrence of those constructors in the type
definition?

Functors can be heavy, but I prefer that approach too. Having a bit of
recursiveness in the module language makes them much nicer. Now if we can
just get generics...

-- Brian


-------------------
To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr
Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners

Re: [Caml-list] Strange physical equality behavior

[William Lovas]

On Tue, Nov 11, 2003 at 08:46:56AM -0800, David Brown wrote:
> On Tue, Nov 11, 2003 at 01:48:22AM -0500, Oleg Trott wrote:
> > On Sunday 09 November 2003 08:33 pm, Jacques Garrigue wrote:
> > >  On mutable structures, [e1 == e2] is true if and only if
> > >    physical modification of [e1] also affects [e2].
> > 
> > By the way, either "mutable structures" or "physical modification" need
> > to be clarified, because if (int ref list) is "mutable" then the above
> > is wrong:
> 
> If you take structure to mean a single data type, rather than a more
> complicated data structure, then it is true.

Well, what do you mean by "a single data type", then?  Surely a record is a
single data type, but ...

    type r = { mutable a: int; mutable r: r }

    let rec r1 = { a = 5; r = r2 }
        and r2 = { a = 7; r = r1 }

Surely you wouldn't argue that this is an immutable data structure, either
-- it contains nothing *but* mutable fields!  And yet,

    r1.a <- 6

also "affects" r2, but r1 != r2.  (Admittedly, though, the ambiguity may
lie in the usage of the word "affects".)

*shrug* Maybe it's a bit contrived, but i would err on the side of caution
and say that the documentation should be made clearer.

William

-------------------
To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr
Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners