From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from concorde.inria.fr (concorde.inria.fr [192.93.2.39]) by yquem.inria.fr (Postfix) with ESMTP id 72054BC48 for ; Thu, 17 Mar 2005 15:01:05 +0100 (CET) Received: from ux9.sp.cs.cmu.edu (UX9.SP.CS.CMU.EDU [128.2.220.166]) by concorde.inria.fr (8.13.0/8.13.0) with SMTP id j2HE14Fh001447 for ; Thu, 17 Mar 2005 15:01:05 +0100 Received: from c-24-3-154-200.client.comcast.net ([24.3.154.200]) by ux9.sp.cs.cmu.edu id aa23207; 17 Mar 2005 9:00 EST Received: from ecc by stratocaster.home with local (Exim 4.44) id 1DBvYA-0001qJ-Rs for caml-list@yquem.inria.fr; Thu, 17 Mar 2005 09:00:34 -0500 Date: Thu, 17 Mar 2005 09:00:34 -0500 To: caml-list@yquem.inria.fr Subject: Re: [Caml-list] Maximum non-constant constructors Message-ID: <20050317140034.GA7049@localhost> Mail-Followup-To: caml-list@yquem.inria.fr References: <42388E28.6050808@confluent.org> <42389A3B.5060107@inria.fr> <20050316233228.GA5689@furbychan.cocan.org> <16953.31187.263581.694769@gargle.gargle.HOWL> Mime-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Disposition: inline In-Reply-To: <16953.31187.263581.694769@gargle.gargle.HOWL> User-Agent: Mutt/1.5.6+20040907i From: Eric Cooper X-Miltered: at concorde with ID 42398DA0.000 by Joe's j-chkmail (http://j-chkmail.ensmp.fr)! X-Spam: no; 0.00; caml-list:01 constructors:01 filliatre:01 hash:01 encodes:01 variants:01 curiousity:01 hash:01 btype:01 variants:01 ...:98 wrote:01 wrote:01 writes:01 polymorphic:01 X-Spam-Checker-Version: SpamAssassin 3.0.2 (2004-11-16) on yquem.inria.fr X-Spam-Status: No, score=0.0 required=5.0 tests=none autolearn=disabled version=3.0.2 X-Spam-Level: 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