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.1 required=5.0 tests=AWL autolearn=disabled version=3.1.3 X-Original-To: caml-list@yquem.inria.fr Delivered-To: caml-list@yquem.inria.fr Received: from mail4-relais-sop.national.inria.fr (mail4-relais-sop.national.inria.fr [192.134.164.105]) by yquem.inria.fr (Postfix) with ESMTP id 6D014BC69 for ; Fri, 5 Oct 2007 18:18:51 +0200 (CEST) X-IronPort-Anti-Spam-Filtered: true X-IronPort-Anti-Spam-Result: AgAAAFsABkfBMHhLn2dsb2JhbACOOQIBAQcEBgkIGA X-IronPort-AV: E=Sophos;i="4.21,236,1188770400"; d="asc'?scan'208";a="17344154" Received: from discorde.inria.fr ([192.93.2.38]) by mail4-smtp-sop.national.inria.fr with ESMTP; 05 Oct 2007 18:18:51 +0200 Received: from mail4-relais-sop.national.inria.fr (mail4-relais-sop.national.inria.fr [192.134.164.105]) by discorde.inria.fr (8.13.6/8.13.6) with ESMTP id l95GIokg023078 (version=TLSv1/SSLv3 cipher=RC4-SHA bits=128 verify=OK) for ; Fri, 5 Oct 2007 18:18:50 +0200 X-IronPort-Anti-Spam-Filtered: true X-IronPort-Anti-Spam-Result: AgAAAFsABkfBMHhLn2dsb2JhbACOOQIBAQcEBgkIGA X-IronPort-AV: E=Sophos;i="4.21,236,1188770400"; d="asc'?scan'208";a="17344153" Received: from net.univ-savoie.fr ([193.48.120.75]) by mail4-smtp-sop.national.inria.fr with ESMTP; 05 Oct 2007 18:18:50 +0200 Received: from post.bourget.univ-savoie.fr (post.bourget.univ-savoie.fr [193.48.120.73]) by net.univ-savoie.fr (8.12.3/jtpda-5.4) with ESMTP id l95GIjpN017877 ; Fri, 5 Oct 2007 18:18:45 +0200 Received: from [193.48.123.45] (d45.lama.univ-savoie.fr [193.48.123.45]) by post.bourget.univ-savoie.fr (8.12.3/jtpda-5.4) with ESMTP id l95GIfBf020770 ; Fri, 5 Oct 2007 18:18:41 +0200 Message-ID: <470663E2.2060702@univ-savoie.fr> Date: Fri, 05 Oct 2007 18:18:42 +0200 From: Christophe Raffalli User-Agent: Thunderbird 1.5.0.13 (X11/20070824) MIME-Version: 1.0 To: Vincent Aravantinos , caml-list@inria.fr Subject: Re: [Caml-list] Depend-type beginner question References: <2EF33DCA-1E28-4F10-AEAB-F3258E976CA7@gmail.com> <4a051d930710050841t7de7dfa3qf695ee271b38bcb7@mail.gmail.com> In-Reply-To: X-Enigmail-Version: 0.94.2.0 Content-Type: multipart/signed; micalg=pgp-sha1; protocol="application/pgp-signature"; boundary="------------enig72942B200EDFF1F7769258FF" X-Scanned-By: MIMEDefang 2.33 (www . roaringpenguin . com / mimedefang) X-Miltered: at discorde with ID 470663EA.000 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 undecidable:01 ocaml:01 decidability:01 undecidable:01 chablais:01 73376:01 univ-savoie:01 hurdles:98 equality:01 X-Attachments: type="application/pgp-signature" name="signature.asc" name="signature.asc" This is an OpenPGP/MIME signed message (RFC 2440 and 3156) --------------enig72942B200EDFF1F7769258FF Content-Type: text/plain; charset=ISO-8859-1 Content-Transfer-Encoding: quoted-printable Vincent Aravantinos a =E9crit : >=20 > Le 5 oct. 07 =E0 17:41, Christopher L Conway a =E9crit : >=20 >> On 10/5/07, Vincent Aravantinos wrote:= >>> why actually dependant types cannot be implemented in ocaml ? Is the >>> type checking undecidable ? Or is it for other reason (e.g. >>> arithmetic) ? I guess it's both. But could someone develop precisely = ? >> >> It's not that dependent types can't be implemented in OCaml, just that= >> they haven't. See, e.g., http://www.cs.bu.edu/~hwxi/DML/DML.html >> >> I suspect the OCaml development team is not inclined to add "sexier" >> types to the core language, though I can't say if there are any >> specific technical hurdles preventing it (certainly, decidability is >> an issue)... >=20 > I can't get how the following could ever be typed at compile time: >=20 >> if ... then [] else [a] >=20 if b then [] else [a] has type list(if b then 0 else 1) where is the problem ? if b then 0 else 1 may or may not be simplified if you know b. The problem is that equality over such complex types in undecidable and y= ou have to provide proofs ... --=20 Christophe Raffalli Universite de Savoie Batiment Le Chablais, bureau 21 73376 Le Bourget-du-Lac Cedex tel: (33) 4 79 75 81 03 fax: (33) 4 79 75 87 42 mail: Christophe.Raffalli@univ-savoie.fr www: http://www.lama.univ-savoie.fr/~RAFFALLI --------------------------------------------- IMPORTANT: this mail is signed using PGP/MIME At least Enigmail/Mozilla, mutt or evolution can check this signature. The public key is stored on www.keyserver.net --------------------------------------------- --------------enig72942B200EDFF1F7769258FF 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 iD8DBQFHBmPmi9jr/RgYAS4RApQnAJ9sdDMpwSTlO5y+nBTYzZRMzesOEgCgma5O sDcxPvqymOCGAkJrMtE87zE= =hiOl -----END PGP SIGNATURE----- --------------enig72942B200EDFF1F7769258FF--