Maximum non-constant constructors

Maximum non-constant constructors

[Tom Hawkins]

I just discovered another limitation: the maximum number of non-constant 
constructors is 246.

My modified OCaml parser generator (ocamlyacc with ints -- see previous 
post) is producing a parser that consumes 342 different tokens types.

Are there any ways to bypass this limitation?

-Tom

Re: [Caml-list] Maximum non-constant constructors

[Alain Frisch]

Tom Hawkins wrote:
> I just discovered another limitation: the maximum number of non-constant 
> constructors is 246.
> 
> My modified OCaml parser generator (ocamlyacc with ints -- see previous 
> post) is producing a parser that consumes 342 different tokens types.
> 
> Are there any ways to bypass this limitation?

Polymorphic variants.

-- Alain

Re: [Caml-list] Maximum non-constant constructors

[Tom Hawkins]

Alain Frisch wrote:
> Tom Hawkins wrote:
> 
>> I just discovered another limitation: the maximum number of 
>> non-constant constructors is 246.
>>
>> My modified OCaml parser generator (ocamlyacc with ints -- see 
>> previous post) is producing a parser that consumes 342 different 
>> tokens types.
>>
>> Are there any ways to bypass this limitation?
> 
> 
> Polymorphic variants.

Good idea, but ocamlyacc does not accept `Some_token as valid syntax.

I'm starting to think I should invest some time developing a new parser 
generator for OCaml.

-Tom

> 
> -- Alain
> 
> _______________________________________________
> 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] Maximum non-constant constructors

[Richard Jones]

On Wed, Mar 16, 2005 at 09:42:35PM +0100, Alain Frisch wrote:
> Polymorphic variants.

Has anyone ever seen (in real life) a collision in the hash function
which encodes polymorphic variants?  Just wondering ...  It seems like
it could occur.

Rich.

-- 
Richard Jones, CTO Merjis Ltd.
Merjis - web marketing and technology - http://merjis.com
Team Notepad - intranets and extranets for business - http://team-notepad.com

Re: [Caml-list] Maximum non-constant constructors

[Jean-Christophe Filliatre]

Richard Jones writes:
 > 
 > Has anyone ever seen (in real life) a collision in the hash function
 > which encodes polymorphic variants?  Just wondering ...  It seems like
 > it could occur.

Yes it could occur, but there is a check a link time for such collisions.

-- 
Jean-Christophe

(http://www.lri.fr/~filliatr)

Re: [Caml-list] Maximum non-constant constructors

[Eric Cooper]

On Thu, Mar 17, 2005 at 01:36:35PM +0100, Jean-Christophe Filliatre wrote:
> 
> Richard Jones writes:
>  > 
>  > Has anyone ever seen (in real life) a collision in the hash function
>  > which encodes polymorphic variants?  Just wondering ...  It seems like
>  > it could occur.
> 
> Yes it could occur, but there is a check a link time for such collisions.

Out of curiousity, I wrote a short program to enumerate possible
collisions.  (If you examine the hash_variant function in
typing/btype.ml, it's clear that any base-223 representation of a
multiple of 2^31 in which the "digits" are legal identifier characters
will hash to zero, and will therefore be an "invisible prefix".)

For example, for all strings XXX, the variants `XXX and `zyctRecXXX
collide.

Here's a small sampling of other invisible prefixes:

    CibPXd UMEDdm d1usNc hS1P1' jagJhn oZshTt Atmtemb CAoStes DHobutv
    PeoQMeo SQufoxX alzzdgn dRtEXEl eeAnNdc glMavfi stYKKKs vbasThr

My guess is that none of them are likely to be chosen by
humans, but might occur in program-generated code.

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

Re: Maximum non-constant constructors

[Stefan Monnier]

> I'm starting to think I should invest some time developing a new parser
> generator for OCaml.

BTW, has anyone ported SML/NJ's ml-yacc to OCaml?
I really like its automatic error recovery.


        Stefan

Re: [Caml-list] Maximum non-constant constructors

[Marcin 'Qrczak' Kowalczyk]

Eric Cooper <ecc@cmu.edu> writes:

> (If you examine the hash_variant function in typing/btype.ml, it's
> clear that any base-223 representation of a multiple of 2^31 in
> which the "digits" are legal identifier characters will hash to
> zero, and will therefore be an "invisible prefix".)

Beware of the birthday paradox: the probability of finding two values
with the same hash is much larger than the probability of finding a
single value with the given hash (a square root of the previous one).

-- 
   __("<         Marcin Kowalczyk
   \__/       qrczak@knm.org.pl
    ^^     http://qrnik.knm.org.pl/~qrczak/

Re: [Caml-list] Maximum non-constant constructors

[Jon Harrop]

On Thursday 17 March 2005 14:00, Eric Cooper wrote:
> For example, for all strings XXX, the variants `XXX and `zyctRecXXX
> collide.

So they do:

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

> My guess is that none of them are likely to be chosen by
> humans, but might occur in program-generated code.

Good point! I think this justifies the existence of a library function to 
compare the hashes of string names of polymorphic variants. Does such a 
function exist?

-- 
Dr Jon D Harrop, Flying Frog Consultancy Ltd.
Objective CAML for Scientists
http://www.ffconsultancy.com/products/ocaml_for_scientists

Re: [Caml-list] Maximum non-constant constructors

[Richard Jones]

On Thu, Mar 17, 2005 at 06:32:06PM +0100, Marcin 'Qrczak' Kowalczyk wrote:
> Beware of the birthday paradox: the probability of finding two values
> with the same hash is much larger than the probability of finding a
> single value with the given hash (a square root of the previous one).

Yes, I was thinking about this too:

http://en.wikipedia.org/wiki/OCaml#Code_examples

(Good excuse to get rid of the terrible "99 bottles of beer" example
too).

Rich.

-- 
Richard Jones, CTO Merjis Ltd.
Merjis - web marketing and technology - http://merjis.com
Team Notepad - intranets and extranets for business - http://team-notepad.com

Re: [Caml-list] Maximum non-constant constructors

[Jacques Garrigue]

From: Jon Harrop <jon@ffconsultancy.com>
> On Thursday 17 March 2005 14:00, Eric Cooper wrote:
> > For example, for all strings XXX, the variants `XXX and `zyctRecXXX
> > collide.
> > My guess is that none of them are likely to be chosen by
> > humans, but might occur in program-generated code.
> 
> Good point! I think this justifies the existence of a library function to 
> compare the hashes of string names of polymorphic variants. Does such a 
> function exist?

Here it is:

let hash_variant s =
  let accu = ref 0 in
  for i = 0 to String.length s - 1 do
    accu := 223 * !accu + Char.code s.[i]
  done;
  (* reduce to 31 bits *)
  accu := !accu land (1 lsl 31 - 1);
  (* make it signed for 64 bits architectures *)
  if !accu > 0x3FFFFFFF then !accu - (1 lsl 31) else !accu

It is also available in the C runtime (where it is useful for
interfacing) but if you really need it in your program just copy the
above code.

To give you an idea of the probability of conflict, here are the
conclicts I found in a 235882 word dictionary (/usr/share/dict/web2 on
FreeBSD)
Tag `Cretacic conflicts with `cornigerous
Tag `gedackt conflicts with `aquicolous
Tag `myeloencephalitis conflicts with `adequative
Tag `Nemorensian conflicts with `condor
Tag `nonrioter conflicts with `anematosis
Tag `omphaloma conflicts with `crimelessness
Tag `persecute conflicts with `paraenetic
Tag `soredioid conflicts with `genitorial
Tag `subpopulation conflicts with `oxyquinone
Tag `sympathy conflicts with `herbman
Tag `trophaeum conflicts with `prepossession
Tag `unbreaded conflicts with `neback
Tag `undragooned conflicts with `nuisance
Tag `unlistened conflicts with `disturb
Tag `veratrine conflicts with `absolutely
You will get different conflict if you change the capitalization, but
not more.

So much for the birthday paradox: variants fully use 31 bits, so that
the probability only gets more than 0.5 when you have more than 32000
constructors in the same type... Of course this is assuming a perfect
distribution, but as the above dictionary shows, reality is close to
that.

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.
The same hash function is also used for method names (with the same
compile-time check), but fortunately it is hard to imagine an object
with more than 10000 methods.

Jacques Garrigue