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.2 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 mail1-relais-roc.national.inria.fr (mail1-relais-roc.national.inria.fr [192.134.164.82]) by yquem.inria.fr (Postfix) with ESMTP id AF840BBAF for ; Wed, 11 Mar 2009 15:32:45 +0100 (CET) X-IronPort-Anti-Spam-Filtered: true X-IronPort-Anti-Spam-Result: AkYCAPRot0mAcIhIkWdsb2JhbACCfol1iDwBAQEBCQsKBxEFrBaGeYhNghOBegY X-IronPort-AV: E=Sophos;i="4.38,343,1233529200"; d="scan'208";a="25422077" Received: from redflag.cs.princeton.edu ([128.112.136.72]) by mail1-smtp-roc.national.inria.fr with ESMTP/TLS/DHE-RSA-AES256-SHA; 11 Mar 2009 15:32:37 +0100 Received: from YitzhakMac.client.research.att.com ([135.207.174.180]) (authenticated bits=0) by redflag.CS.Princeton.EDU (8.13.8/8.13.8) with ESMTP id n2BEWS32001625 (version=TLSv1/SSLv3 cipher=AES128-SHA bits=128 verify=NOT); Wed, 11 Mar 2009 10:32:31 -0400 (EDT) Cc: yoann padioleau , Caml-list List Message-Id: <6D1EF1C5-3561-4D45-AE32-48F80EC84E58@cs.princeton.edu> From: Yitzhak Mandelbaum To: Markus Mottl In-Reply-To: Content-Type: text/plain; charset=US-ASCII; format=flowed; delsp=yes Content-Transfer-Encoding: 7bit Mime-Version: 1.0 (Apple Message framework v930.3) Subject: Re: [Caml-list] typing problem with sexplib and mutually recursive polymorphic types Date: Wed, 11 Mar 2009 10:32:26 -0400 References: <87prgoydy1.fsf@aryx.cs.uiuc.edu> <21952156.346634.1236751878001.JavaMail.www@wwinf1b03> X-Mailer: Apple Mail (2.930.3) X-Proofpoint-Virus-Version: vendor=nai engine=5.3.00 definitions=5549 signatures=505505 X-Proofpoint-Spam-Reason: safe X-Spam: no; 0.00; yitzhak:01 mandelbaum:01 recursive:01 inference:01 recursion:01 undecidable:01 ocaml:01 cheers:01 yitzhak:01 markus:01 mottl:01 recursive:01 recursion:01 undecidable:01 markus:01 While I'm not sure it will help you in this case (because the code is generated), I should note that type *inference* for polymorphic recursion is undecidable, but type *checking* is not. Moreover, its pretty easy to do in OCaml (if a bit clunky). An earlier discussion on this list covered a number of ways to do it. Here's one: http://groups.google.com/group/fa.caml/msg/d85e3f62dd52d365 Cheers, Yitzhak On Mar 11, 2009, at 10:20 AM, Markus Mottl wrote: > On Wed, Mar 11, 2009 at 02:11, yoann padioleau > wrote: >> Yes on this example, but what if I can't move it out because >> the types really need to be mutually recursive ? > > I'm afraid, I don't see any straightforward way of achieving this > goal. If the above were allowed in a truly recursive way, you'd > essentially end up with polymorphic recursion, which is undecidable. > > Regards, > Markus > > -- > Markus Mottl http://www.ocaml.info > markus.mottl@gmail.com > > _______________________________________________ > 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 ----------------------------- Yitzhak Mandelbaum