equality of Big_ints

equality of Big_ints

[Ian Zimmerman]

Is Big_int.eq_big_int the same as polymorphic equality on Big_int.big_int?
In other words, can the same big_int have distinct representations?

I looked at Valerie Menissier-Morain's paper but it seems to refer to
the "old" CAML, so I am afraid to draw any conclusions.

-- 
"It's not true or not."  A reality show producer (real quote)

Re: [Caml-list] equality of Big_ints

[skaller]

On Mon, 2005-10-10 at 00:12 -0400, Ian Zimmerman wrote:
> Is Big_int.eq_big_int the same as polymorphic equality on Big_int.big_int?

No. Polymorphic equality does not work for Big_int.

Example:

let x = Big_int.big_int_of_int 42;;
let y = Big_int.big_int_of_int 42;;

if x = y then print_endline "Equal" else print_endline "Not equal";;

Compile and execute:

skaller@rosella:/work/felix/flx$ ocamlopt nums.cmxa x.ml -o bite
skaller@rosella:/work/felix/flx$ ./bite
Fatal error: exception Invalid_argument("equal: abstract value")

Examining 'custom.h' this just looks like a bug:

struct custom_operations {
  char *identifier;
  void (*finalize)(value v);
  int (*compare)(value v1, value v2);
  long (*hash)(value v);
  void (*serialize)(value v,
                    /*out*/ unsigned long * wsize_32 /*size in bytes*/,
                    /*out*/ unsigned long * wsize_64 /*size in bytes*/);
  unsigned long (*deserialize)(void * dst);
};

So custom blocks can support finalisers, comparators, hashing
and serialisation. Big_int CAN be serialised .. looks like 
the the comparator simply wasn't installed.

For 'nat' I see this:

static struct custom_operations nat_operations = {
  "_nat",
  custom_finalize_default,
  custom_compare_default,
  custom_hash_default,
  serialize_nat,
  deserialize_nat
};

[Nat is the underlying C type used in Big_int]

So, a custom serialiser/deserialiser has been provided,
but the default comparator is left in place (which throws
an exception I guess).

The reason may be because the equality of integers
isn't the same as algebraic equality of the data structures:
for example using signed magnitude minus 0 is not algebraically
equal to plus 0 -- and polymorphic comparison compares the
(ocaml) representations. So even if Nat custom block could
provide a custom comparator that worked correctly, the Big_int
built on it would only work if the representation was canonical,
and the invariant could be expensive to maintain. But it does
not seem like this is so in this case...

For Rationals, however, it could be very much the case that
maintaining the usual invariant (no common divisors of the
numerator and denominator) would be expensive to maintain.

So perhaps this is another case where polymorphic compare
was a 'good idea at the time' but actually fails with abstract
types. It really only works with sums, products, and some primitives,
and fails with functions and general abstract types. The problem
is Ocaml (rather than C) abstractions have no way to provide
the run time with custom operations -- the type information
is lost.

-- 
John Skaller <skaller at users dot sf dot net>
Felix, successor to C++: http://felix.sf.net

Re: [Caml-list] equality of Big_ints

[Alain Frisch]

skaller wrote:
> The reason may be because the equality of integers
> isn't the same as algebraic equality of the data structures:

Indeed, but this is not about maintaining an invariant. Because of the
representation of Big_int.big_int as a pair (sign,absolute value), the
polymorphic comparison would give (-1) < (-2) if the custom comparison
were used for Nat.nat.

-- Alain

Re: [Caml-list] equality of Big_ints

[Thomas Fischbacher]

On Mon, 10 Oct 2005, skaller wrote:

> On Mon, 2005-10-10 at 00:12 -0400, Ian Zimmerman wrote:
> > Is Big_int.eq_big_int the same as polymorphic equality on Big_int.big_int?
> 
> No. Polymorphic equality does not work for Big_int.

Equality is not really polymorphic anyway.

-- 
regards,               tf@cip.physik.uni-muenchen.de              (o_
 Thomas Fischbacher -  http://www.cip.physik.uni-muenchen.de/~tf  //\
(lambda (n) ((lambda (p q r) (p p q r)) (lambda (g x y)           V_/_
(if (= x 0) y (g g (- x 1) (* x y)))) n 1))                  (Debian GNU)

Re: [Caml-list] equality of Big_ints

[skaller]

On Mon, 2005-10-10 at 09:36 +0200, Alain Frisch wrote:
> skaller wrote:
> > The reason may be because the equality of integers
> > isn't the same as algebraic equality of the data structures:
> 
> Indeed, but this is not about maintaining an invariant. Because of the
> representation of Big_int.big_int as a pair (sign,absolute value), the
> polymorphic comparison would give (-1) < (-2) if the custom comparison
> were used for Nat.nat.

Yes. There are really two separate issues here I think.

First, comparison is required for total ordering 
or perhaps just equality is required for use in some data 
structures (Hashtbl only needs equality and hash, a polymorphic
set would need the total order, but there isn't one ..) 

In this case, only a bijection  between abstract values 
and representation is required,
which can obtained by a suitable representation invariant.
So here -1 < -2 may be counterintuitive, but irrelevant.

Second, comparison is required for user ordering of values.
Of course here -1 < -2 would be a disaster.

This is the same issue with floating comparison vs
polymorphic comparison of floats.

Of course the client can provide an ordering for (most)
functorised data structures -- the problem is if the data
type is complicated, it can be very hard to construct
the ordering, which is where the polymorphic comparison
proves useful.

An interesting tradeoff.

-- 
John Skaller <skaller at users dot sf dot net>
Felix, successor to C++: http://felix.sf.net