* [Caml-list] Stability of order between polymorphic variants
@ 2013-09-05 0:17 Daniel Bünzli
2013-09-05 2:06 ` Anthony Tavener
` (2 more replies)
0 siblings, 3 replies; 10+ messages in thread
From: Daniel Bünzli @ 2013-09-05 0:17 UTC (permalink / raw)
To: caml list
Hello,
I have this type
type weight = [ `W100 | `W200 | `W300 | `W400 | `W500 | `W600 | `W700 | `W800 | `W900 ]
In the current compiler it has the property that `Wx00 < `Wy00 if x < y.
The question is, is the order between polymorphic variants an invariant provided by the compiler or is it subject to change ?
Best,
Daniel
^ permalink raw reply [flat|nested] 10+ messages in thread* Re: [Caml-list] Stability of order between polymorphic variants
2013-09-05 0:17 [Caml-list] Stability of order between polymorphic variants Daniel Bünzli
@ 2013-09-05 2:06 ` Anthony Tavener
2013-09-05 2:11 ` Anthony Tavener
2013-09-05 8:24 ` Jacques Garrigue
2013-09-05 9:26 ` Jeremy Yallop
2 siblings, 1 reply; 10+ messages in thread
From: Anthony Tavener @ 2013-09-05 2:06 UTC (permalink / raw)
To: Daniel Bünzli; +Cc: caml list
[-- Attachment #1: Type: text/plain, Size: 1260 bytes --]
I haven't looked at how the compare happens for polyvariants, but I assume
it's going to treat them as integers. And the integer value of the
polymorphic variants is a simple hashing-type function (byterun/hash.c:
caml_hash_variant). A multiplication by 223 is involved for each character
of the variant name, so with a long enough name, compared to the integer
size, you'll get wraparound. The short names you have there are okay.
I'd be uncomfortable relying on this ordering, but I can imagine it would
make some things a lot simpler...
On Wed, Sep 4, 2013 at 6:17 PM, Daniel Bünzli
<daniel.buenzli@erratique.ch>wrote:
> Hello,
>
> I have this type
>
> type weight = [ `W100 | `W200 | `W300 | `W400 | `W500 | `W600 | `W700 |
> `W800 | `W900 ]
>
> In the current compiler it has the property that `Wx00 < `Wy00 if x < y.
>
> The question is, is the order between polymorphic variants an invariant
> provided by the compiler or is it subject to change ?
>
> Best,
>
> Daniel
>
>
>
> --
> Caml-list mailing list. Subscription management and archives:
> https://sympa.inria.fr/sympa/arc/caml-list
> Beginner's list: http://groups.yahoo.com/group/ocaml_beginners
> Bug reports: http://caml.inria.fr/bin/caml-bugs
>
[-- Attachment #2: Type: text/html, Size: 1925 bytes --]
^ permalink raw reply [flat|nested] 10+ messages in thread
* Re: [Caml-list] Stability of order between polymorphic variants
2013-09-05 2:06 ` Anthony Tavener
@ 2013-09-05 2:11 ` Anthony Tavener
2013-09-05 2:18 ` Francois Berenger
0 siblings, 1 reply; 10+ messages in thread
From: Anthony Tavener @ 2013-09-05 2:11 UTC (permalink / raw)
To: Daniel Bünzli; +Cc: caml list
[-- Attachment #1: Type: text/plain, Size: 1456 bytes --]
Addendum: On a 32b arch, those names will wrap.
On Wed, Sep 4, 2013 at 8:06 PM, Anthony Tavener
<anthony.tavener@gmail.com>wrote:
> I haven't looked at how the compare happens for polyvariants, but I assume
> it's going to treat them as integers. And the integer value of the
> polymorphic variants is a simple hashing-type function (byterun/hash.c:
> caml_hash_variant). A multiplication by 223 is involved for each character
> of the variant name, so with a long enough name, compared to the integer
> size, you'll get wraparound. The short names you have there are okay.
>
> I'd be uncomfortable relying on this ordering, but I can imagine it would
> make some things a lot simpler...
>
>
>
> On Wed, Sep 4, 2013 at 6:17 PM, Daniel Bünzli <daniel.buenzli@erratique.ch
> > wrote:
>
>> Hello,
>>
>> I have this type
>>
>> type weight = [ `W100 | `W200 | `W300 | `W400 | `W500 | `W600 | `W700 |
>> `W800 | `W900 ]
>>
>> In the current compiler it has the property that `Wx00 < `Wy00 if x < y.
>>
>> The question is, is the order between polymorphic variants an invariant
>> provided by the compiler or is it subject to change ?
>>
>> Best,
>>
>> Daniel
>>
>>
>>
>> --
>> Caml-list mailing list. Subscription management and archives:
>> https://sympa.inria.fr/sympa/arc/caml-list
>> Beginner's list: http://groups.yahoo.com/group/ocaml_beginners
>> Bug reports: http://caml.inria.fr/bin/caml-bugs
>>
>
>
[-- Attachment #2: Type: text/html, Size: 2401 bytes --]
^ permalink raw reply [flat|nested] 10+ messages in thread
* Re: [Caml-list] Stability of order between polymorphic variants
2013-09-05 2:11 ` Anthony Tavener
@ 2013-09-05 2:18 ` Francois Berenger
2013-09-05 2:31 ` Anthony Tavener
0 siblings, 1 reply; 10+ messages in thread
From: Francois Berenger @ 2013-09-05 2:18 UTC (permalink / raw)
To: caml-list
On 09/05/2013 11:11 AM, Anthony Tavener wrote:
> Addendum: On a 32b arch, those names will wrap.
Why not write a to_int for your type
and then a specialized comparator using it?
> On Wed, Sep 4, 2013 at 8:06 PM, Anthony Tavener
> <anthony.tavener@gmail.com <mailto:anthony.tavener@gmail.com>> wrote:
>
> I haven't looked at how the compare happens for polyvariants, but I
> assume it's going to treat them as integers. And the integer value
> of the polymorphic variants is a simple hashing-type function
> (byterun/hash.c: caml_hash_variant). A multiplication by 223 is
> involved for each character of the variant name, so with a long
> enough name, compared to the integer size, you'll get wraparound.
> The short names you have there are okay.
>
> I'd be uncomfortable relying on this ordering, but I can imagine it
> would make some things a lot simpler...
>
>
>
> On Wed, Sep 4, 2013 at 6:17 PM, Daniel Bünzli
> <daniel.buenzli@erratique.ch <mailto:daniel.buenzli@erratique.ch>>
> wrote:
>
> Hello,
>
> I have this type
>
> type weight = [ `W100 | `W200 | `W300 | `W400 | `W500 | `W600
> | `W700 | `W800 | `W900 ]
>
> In the current compiler it has the property that `Wx00 < `Wy00
> if x < y.
>
> The question is, is the order between polymorphic variants an
> invariant provided by the compiler or is it subject to change ?
>
> Best,
>
> Daniel
>
>
>
> --
> Caml-list mailing list. Subscription management and archives:
> https://sympa.inria.fr/sympa/arc/caml-list
> Beginner's list: http://groups.yahoo.com/group/ocaml_beginners
> Bug reports: http://caml.inria.fr/bin/caml-bugs
>
>
>
^ permalink raw reply [flat|nested] 10+ messages in thread
* Re: [Caml-list] Stability of order between polymorphic variants
2013-09-05 2:18 ` Francois Berenger
@ 2013-09-05 2:31 ` Anthony Tavener
2013-09-05 7:47 ` Stéphane Glondu
0 siblings, 1 reply; 10+ messages in thread
From: Anthony Tavener @ 2013-09-05 2:31 UTC (permalink / raw)
To: Francois Berenger; +Cc: caml-list
[-- Attachment #1: Type: text/plain, Size: 743 bytes --]
On Wed, Sep 4, 2013 at 8:18 PM, Francois Berenger <berenger@riken.jp> wrote:
> On 09/05/2013 11:11 AM, Anthony Tavener wrote:
>
>> Addendum: On a 32b arch, those names will wrap.
>>
>
> Why not write a to_int for your type
> and then a specialized comparator using it?
>
A sane suggestion. :) Daniel might not want to write an explicit mapping to
int if these
weight types grow in number?
And I need to correct my addendum. I now realize the multiplier of 223
would still fit a
4-character name in 30bits, given that the first char must be a capital
letter. So I'm
guessing you're already aware of all this, Daniel, and just wanted to know
if there is
likelihood of the calculation changing. That I know nothing about. Sorry
for the noise!
[-- Attachment #2: Type: text/html, Size: 1323 bytes --]
^ permalink raw reply [flat|nested] 10+ messages in thread
* Re: [Caml-list] Stability of order between polymorphic variants
2013-09-05 0:17 [Caml-list] Stability of order between polymorphic variants Daniel Bünzli
2013-09-05 2:06 ` Anthony Tavener
@ 2013-09-05 8:24 ` Jacques Garrigue
2013-09-05 8:39 ` Mark Shinwell
2013-09-05 9:26 ` Jeremy Yallop
2 siblings, 1 reply; 10+ messages in thread
From: Jacques Garrigue @ 2013-09-05 8:24 UTC (permalink / raw)
To: Daniel Bünzli; +Cc: caml list
On 2013/09/05, at 9:17, Daniel Bünzli <daniel.buenzli@erratique.ch> wrote:
> Hello,
>
> I have this type
>
> type weight = [ `W100 | `W200 | `W300 | `W400 | `W500 | `W600 | `W700 | `W800 | `W900 ]
>
> In the current compiler it has the property that `Wx00 < `Wy00 if x < y.
>
> The question is, is the order between polymorphic variants an invariant provided by the compiler or is it subject to change ?
>
> Best,
>
> Daniel
As was pointed by some, the hashing function ensures that all constructor names up to 4 characters may not conflict, on all architectures.
It also preserves the order in that case.
Since there is no reason to change this hashing function, I suppose you can rely on that.
Jacques Garrigue
^ permalink raw reply [flat|nested] 10+ messages in thread
* Re: [Caml-list] Stability of order between polymorphic variants
2013-09-05 8:24 ` Jacques Garrigue
@ 2013-09-05 8:39 ` Mark Shinwell
0 siblings, 0 replies; 10+ messages in thread
From: Mark Shinwell @ 2013-09-05 8:39 UTC (permalink / raw)
To: Jacques Garrigue; +Cc: Daniel Bünzli, caml list
On 5 September 2013 09:24, Jacques Garrigue
<garrigue@math.nagoya-u.ac.jp> wrote:
> As was pointed by some, the hashing function ensures that all constructor names up to 4 characters may not conflict, on all architectures.
> It also preserves the order in that case.
> Since there is no reason to change this hashing function, I suppose you can rely on that.
This seems quite fragile. If you're going to rely on that,
I'd suggest having a unit test.
Mark
^ permalink raw reply [flat|nested] 10+ messages in thread
* Re: [Caml-list] Stability of order between polymorphic variants
2013-09-05 0:17 [Caml-list] Stability of order between polymorphic variants Daniel Bünzli
2013-09-05 2:06 ` Anthony Tavener
2013-09-05 8:24 ` Jacques Garrigue
@ 2013-09-05 9:26 ` Jeremy Yallop
2013-09-05 14:46 ` Goswin von Brederlow
2 siblings, 1 reply; 10+ messages in thread
From: Jeremy Yallop @ 2013-09-05 9:26 UTC (permalink / raw)
To: Daniel Bünzli; +Cc: caml list
On 5 September 2013 01:17, Daniel Bünzli <daniel.buenzli@erratique.ch> wrote:
> The question is, is the order between polymorphic variants an invariant provided by the compiler or is it subject to change ?
The order is fairly unlikely to change. It's based on a hash function
that's used during type checking to determine whether tags can occur
in the same type:
# [`premiums; `squigglier];;
Characters 12-23:
[`premiums; `squigglier];;
^^^^^^^^^^^
Error: Variant tags `premiums and `squigglier have the same hash value.
Change one of them.
Changing the hash function could cause some existing programs to be rejected.
^ permalink raw reply [flat|nested] 10+ messages in thread* Re: [Caml-list] Stability of order between polymorphic variants
2013-09-05 9:26 ` Jeremy Yallop
@ 2013-09-05 14:46 ` Goswin von Brederlow
0 siblings, 0 replies; 10+ messages in thread
From: Goswin von Brederlow @ 2013-09-05 14:46 UTC (permalink / raw)
To: Jeremy Yallop; +Cc: Daniel Bünzli, caml list
On Thu, Sep 05, 2013 at 10:26:42AM +0100, Jeremy Yallop wrote:
> On 5 September 2013 01:17, Daniel Bünzli <daniel.buenzli@erratique.ch> wrote:
> > The question is, is the order between polymorphic variants an invariant provided by the compiler or is it subject to change ?
>
> The order is fairly unlikely to change. It's based on a hash function
> that's used during type checking to determine whether tags can occur
> in the same type:
>
> # [`premiums; `squigglier];;
> Characters 12-23:
> [`premiums; `squigglier];;
> ^^^^^^^^^^^
> Error: Variant tags `premiums and `squigglier have the same hash value.
> Change one of them.
>
> Changing the hash function could cause some existing programs to be rejected.
Wow, those names even look sensible. Nice collision example.
MfG
Goswin
^ permalink raw reply [flat|nested] 10+ messages in thread
end of thread, other threads:[~2013-09-05 14:46 UTC | newest]
Thread overview: 10+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2013-09-05 0:17 [Caml-list] Stability of order between polymorphic variants Daniel Bünzli
2013-09-05 2:06 ` Anthony Tavener
2013-09-05 2:11 ` Anthony Tavener
2013-09-05 2:18 ` Francois Berenger
2013-09-05 2:31 ` Anthony Tavener
2013-09-05 7:47 ` Stéphane Glondu
2013-09-05 8:24 ` Jacques Garrigue
2013-09-05 8:39 ` Mark Shinwell
2013-09-05 9:26 ` Jeremy Yallop
2013-09-05 14:46 ` Goswin von Brederlow
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox