Representation of different polymorphic variants guaranteed to be different?

Representation of different polymorphic variants guaranteed to be different?

[Bruno Daniel]

Dear OCaml developers,

I'm trying to understand the representation of polymorphic variants in OCaml
and I'm a bit worried about possible problems. Section 18.3.6 of the
OCaml 3.11 reference manual reads:

"[...] The variant value `VConstr is represented by hash_variant("VConstr").
The variant value `VConstr(v) is represented by a block of size 2 and tag 0,
with field number 0 containing hash_variant("VConstr") and field number 1
containing v."

I take it from the source code of caml_hash_variant in
ocaml-3.11.1_src/asmrun/hash.c and hash_variant in
ocaml-3.11.1_src/typing/btype.ml that hash_variant returns an OCaml 31-bit
integer value, i.e. there is only room for at most 2147483648 different
polymorphic variants, but even with identifiers composed of only 7 characters
chosen from 26 letters one could easily construct  8031810176 different
polymorphic variant constructors.

How is it ensured that I get a <> b for a and b created as polymorphic
variants from two different identifiers? Will pattern matching give wrong
results if I accidentally choose two different identifiers translated to the
same internal representation?

The same applies to method names according to section 18.3.5:
"Since public method tags are hashed in the same way as variant tags, and
methods are functions taking self as first argument, if you want to do the method
call foo#bar from the C side, you should call:
callback(caml_get_public_method(foo, hash_variant("bar")), foo);".

I apologize if these questions have been answered before. I couldn't find any
discussion about them in the archives. Thank you very much for your help.

Best regards
  Bruno Daniel

Re: [Caml-list] Representation of different polymorphic variants guaranteed to be different?

[Eric Cooper]

On Wed, Jul 08, 2009 at 08:35:27PM +0200, Bruno Daniel wrote:
> How is it ensured that I get a <> b for a and b created as
> polymorphic variants from two different identifiers? Will pattern
> matching give wrong results if I accidentally choose two different
> identifiers translated to the same internal representation?

See this thread:
    http://caml.inria.fr/pub/ml-archives/caml-list/2005/03/544288096a47d82ec870d01c8396f5fe.fr.html 

Short answer: collisions could theoretically occur, but are detected
at link time.

-- 
Eric Cooper             e c c @ c m u . e d u

Re: [Caml-list] Representation of different polymorphic variants guaranteed to be different?

[Elnatan Reisner]

On Wed, 2009-07-08 at 14:54 -0400, Eric Cooper wrote:
> On Wed, Jul 08, 2009 at 08:35:27PM +0200, Bruno Daniel wrote:
> > How is it ensured that I get a <> b for a and b created as
> > polymorphic variants from two different identifiers? Will pattern
> > matching give wrong results if I accidentally choose two different
> > identifiers translated to the same internal representation?
> 
> See this thread:
>     http://caml.inria.fr/pub/ml-archives/caml-list/2005/03/544288096a47d82ec870d01c8396f5fe.fr.html 
> 
> Short answer: collisions could theoretically occur, but are detected
> at link time.

That thread actually concludes that the check is at compile-time:
http://caml.inria.fr/pub/ml-archives/caml-
list/2005/03/7965b012288982e74718b2ae769dc189.fr.html

Re: [Caml-list] Representation of different polymorphic variants guaranteed to be different?

[Bruno Daniel]

Dear Eric Cooper,

thank you very much for your answer. I tried it out and I found that it really
works, even with the variants defined in different ml-files linked together:

--- module1.ml ---
let a1 = if !Sys.interactive then `a else `zyctRecABC;;
--- module2.ml ---
let a2 = `ABC;;

let _ = a2 = Module1.a1;;
------------------

or

--- module2.ml ---
let a2 = `ABC;;

let h1 = Hashtb.create 100;;

let _ =
  Hashtbl.replace h1 a2 0;
  Hashtbl.replace h1 Module1.a1 1;;
------------------

In both cases I get the following error message when compiling the second module:
"Error: Variant tags `ABC and `zyctRecABC have the same hash value.
Change one of them."

But it's clear from this discussion that I'll never be allowed to use
Obj.magic on variant types. The following goes through unchecked:

--- module2.ml ---
let a2 = `ABC;;

let h1 : (int, int) Hashtbl.t = Hashtbl.create 100;;

let _ =
  Hashtbl.replace h1 (Obj.magic a2) 0;
  Hashtbl.replace h1 (Obj.magic Module1.a1) 1;;
------------------

Best regards
  Bruno Daniel

Eric Cooper wrote:
> On Wed, Jul 08, 2009 at 08:35:27PM +0200, Bruno Daniel wrote:
>> How is it ensured that I get a <> b for a and b created as
>> polymorphic variants from two different identifiers? Will pattern
>> matching give wrong results if I accidentally choose two different
>> identifiers translated to the same internal representation?
> 
> See this thread:
>     http://caml.inria.fr/pub/ml-archives/caml-list/2005/03/544288096a47d82ec870d01c8396f5fe.fr.html 
> 
> Short answer: collisions could theoretically occur, but are detected
> at link time.
> 
> -- 
> Eric Cooper             e c c @ c m u . e d u
> 
> _______________________________________________
> Caml-list mailing list. Subscription management:
> http://yquem.inria.fr/cgi-bin/mailman/listinfo/caml-list
> Archives: http://caml.inria.fr
> Beginner's list: http://groups.yahoo.com/group/ocaml_beginners
> Bug reports: http://caml.inria.fr/bin/caml-bugs

Re: [Caml-list] Representation of different polymorphic variants guaranteed to be different?

[Frédéric van der Plancke]

Eric Cooper wrote:
> On Wed, Jul 08, 2009 at 08:35:27PM +0200, Bruno Daniel wrote:
>   
>> How is it ensured that I get a <> b for a and b created as
>> polymorphic variants from two different identifiers? Will pattern
>> matching give wrong results if I accidentally choose two different
>> identifiers translated to the same internal representation?
>>     
>
> See this thread:
>     http://caml.inria.fr/pub/ml-archives/caml-list/2005/03/544288096a47d82ec870d01c8396f5fe.fr.html 
>
> Short answer: collisions could theoretically occur, but are detected
> at link time.
>
>   
Actually at compile time, as stated by Jacques Garrigue* *in the last 
message of said thread:

"By the way, the check is not at link time, as was stated in another
message, but at compile time. It is the typing of variants itself that
guarantees that no such conflict will go undetected. So you will be
warned early enough."

Example:

# type a = [ `ABC | `zyctRecABC ];;
Variant tags `ABC and `zyctRecABC have same hash value. Change one of them.


Frédéric.