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=1.5 required=5.0 tests=AWL,DNS_FROM_RFC_POST 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 C07E7BBAF for ; Thu, 12 Mar 2009 00:08:46 +0100 (CET) X-IronPort-Anti-Spam-Filtered: true X-IronPort-Anti-Spam-Result: AlYBAKjht0mArgVhlGdsb2JhbACCfol2iEUBAQEBCQsICREEvCIHggyBegaGeA X-IronPort-AV: E=Sophos;i="4.38,346,1233529200"; d="scan'208";a="25447091" Received: from expredir6.cites.uiuc.edu ([128.174.5.97]) by mail1-smtp-roc.national.inria.fr with ESMTP/TLS/DHE-RSA-AES256-SHA; 12 Mar 2009 00:08:45 +0100 Received: from axyr (aryx.cs.uiuc.edu [128.174.236.106]) by expredir6.cites.uiuc.edu (8.14.2/8.14.2) with ESMTP id n2BN8e1g007753; Wed, 11 Mar 2009 18:08:40 -0500 (CDT) To: Yitzhak Mandelbaum Cc: Markus Mottl , yoann padioleau , Caml-list List Subject: Re: [Caml-list] typing problem with sexplib and mutually recursive polymorphic types References: <87prgoydy1.fsf@aryx.cs.uiuc.edu> <21952156.346634.1236751878001.JavaMail.www@wwinf1b03> <6D1EF1C5-3561-4D45-AE32-48F80EC84E58@cs.princeton.edu> From: Yoann Padioleau Date: Wed, 11 Mar 2009 18:08:37 -0500 In-Reply-To: <6D1EF1C5-3561-4D45-AE32-48F80EC84E58@cs.princeton.edu> (Yitzhak Mandelbaum's message of "Wed\, 11 Mar 2009 10\:32\:26 -0400") Message-ID: <87ljrby7wq.fsf@aryx.cs.uiuc.edu> User-Agent: Gnus/5.11 (Gnus v5.11) Emacs/22.1 (gnu/linux) MIME-Version: 1.0 Content-Type: text/plain; charset=us-ascii X-Spam: no; 0.00; recursive:01 yitzhak:01 mandelbaum:01 camlp:01 inference:01 recursion:01 undecidable:01 ocaml:01 recursive:01 cheers:01 yitzhak:01 markus:01 mottl:01 recursion:01 undecidable:01 Yitzhak Mandelbaum writes: > While I'm not sure it will help you in this case (because the code is > generated), The code is generated, but I am ok with modifying it. I use typeconv/sexplib/binprot and camlp4 just as a way to produce a first draft and then I refine the result. I prefer to see the generated code and have concrete files (and in this case in fact I have no choice as the the default generated code is not good enough). > 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 Thanks. I tried the {f: 'a. 'a } trick and it works on my simplified example but I failed using it on my original file. Never mind, I artificially broke the mutually recursive dependency and now it works. Thanks. > > 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