From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: X-Spam-Checker-Version: SpamAssassin 3.1.3 (2006-06-01) on yquem.inria.fr X-Spam-Level: X-Spam-Status: No, score=0.0 required=5.0 tests=none autolearn=disabled version=3.1.3 Received: from discorde.inria.fr (discorde.inria.fr [192.93.2.38]) by yquem.inria.fr (Postfix) with ESMTP id 5C0B9BC69; Wed, 29 Aug 2007 12:58:09 +0200 (CEST) Received: from smtp1-g19.free.fr (smtp1-g19.free.fr [212.27.42.27]) by discorde.inria.fr (8.13.6/8.13.6) with ESMTP id l7TAw86q028513; Wed, 29 Aug 2007 12:58:09 +0200 Received: from smtp1-g19.free.fr (localhost.localdomain [127.0.0.1]) by smtp1-g19.free.fr (Postfix) with ESMTP id D22131AB2C6; Wed, 29 Aug 2007 12:58:08 +0200 (CEST) Received: from [192.168.144.128] (unknown [82.65.168.69]) by smtp1-g19.free.fr (Postfix) with ESMTP id 205811AB309; Wed, 29 Aug 2007 12:58:07 +0200 (CEST) Message-ID: <46D55122.2090709@univ-savoie.fr> Date: Wed, 29 Aug 2007 12:57:38 +0200 From: Christophe Raffalli User-Agent: Thunderbird 1.5.0.13 (X11/20070824) MIME-Version: 1.0 To: Daniel de Rauglaudre Cc: caml-list@inria.fr Subject: Re: [Caml-list] how to upset the ocaml type system.... References: <20070828131850.GA32264@pulp.rsise.anu.edu.au> <20070829005634.GA7888@yquem.inria.fr> In-Reply-To: <20070829005634.GA7888@yquem.inria.fr> X-Enigmail-Version: 0.94.2.0 Content-Type: multipart/signed; micalg=pgp-sha1; protocol="application/pgp-signature"; boundary="------------enig8239CA2681C3C4E9E7C8105A" X-Miltered: at discorde with ID 46D55140.002 by Joe's j-chkmail (http://j-chkmail . ensmp . fr)! X-Spam: no; 0.00; christophe:01 raffalli:01 christophe:01 raffalli:01 univ-savoie:01 ocaml:01 rauglaudre:01 inference:01 -rectypes:01 subtypes:01 ocaml:01 28,:98 cubic:98 wrote:01 caml-list:01 X-Attachments: cset="utf-8" name="Christophe.Raffalli.vcf" name="Christophe.Raffalli.vcf" type="application/pgp-signature" name="signature.asc" name="signature.asc" This is an OpenPGP/MIME signed message (RFC 2440 and 3156) --------------enig8239CA2681C3C4E9E7C8105A Content-Type: multipart/mixed; boundary="------------040502080502070405070302" This is a multi-part message in MIME format. --------------040502080502070405070302 Content-Type: text/plain; charset=ISO-8859-1 Content-Transfer-Encoding: quoted-printable Daniel de Rauglaudre a =E9crit : > Hi, > > On Tue, Aug 28, 2007 at 11:18:50PM +1000, Pietro Abate wrote: > > =20 >> the other day I was looking for a fringe case to show me the worst >> complexity of the type inference algorithm... >> =20 > > Interesting. To see the resulting time, I changed the code into: > > let f =3D > let x1 =3D fun x -> (x,x) in > let x2 =3D fun y -> x1 ( x1 y ) in > let x3 =3D fun y -> x2 ( x2 y ) in > let x4 =3D fun y -> x3 ( x3 y ) in > let x5 =3D fun y -> x4 ( x4 y ) in > x5 ( fun z -> z ) ;; > > =20 This is strange, it is problematic even with -rectypes while this is not necessary if the subtypes are shared ... I already so ocaml printing some types with sharing, so why is this not the case here ? (I am using 3.09.2) With pml I seem to get a polynomial behavior (at least quadratic but probably cubic), I tested up to 9. This is because the type of xi is bigger and bigger (but linear in i) and it is copied by the generalisation and particularisation for each i. Christophe --------------040502080502070405070302 Content-Type: text/x-vcard; charset=utf-8; name="Christophe.Raffalli.vcf" Content-Transfer-Encoding: quoted-printable Content-Disposition: attachment; filename="Christophe.Raffalli.vcf" begin:vcard fn:Christophe Raffalli n:Raffalli;Christophe org:LAMA (UMR 5127) email;internet:Christophe.Raffalli@univ-savoie.fr title;quoted-printable:Ma=3DC3=3DAEtre de conf=3DC3=3DA9rences tel;work:+33 4 79 75 81 03 note;quoted-printable:Message sign=3DC3=3DA9 cryptographiquement avec pgp= , la clef publique est sur=3D subkeys.pgp.net x-mozilla-html:TRUE version:2.1 end:vcard --------------040502080502070405070302-- --------------enig8239CA2681C3C4E9E7C8105A Content-Type: application/pgp-signature; name="signature.asc" Content-Description: OpenPGP digital signature Content-Disposition: attachment; filename="signature.asc" -----BEGIN PGP SIGNATURE----- Version: GnuPG v1.4.6 (GNU/Linux) Comment: Using GnuPG with Mozilla - http://enigmail.mozdev.org iD8DBQFG1VEpi9jr/RgYAS4RAt9yAKCk3MTu4TX3FUkbXe07s4Vfj9Yc7ACfaHZK eLZWgYjx++6ll2nabSatF0w= =tSmw -----END PGP SIGNATURE----- --------------enig8239CA2681C3C4E9E7C8105A--