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.7 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 mail2-relais-roc.national.inria.fr (mail2-relais-roc.national.inria.fr [192.134.164.83]) by yquem.inria.fr (Postfix) with ESMTP id C1ED0BCCD for ; Thu, 21 Aug 2008 09:49:49 +0200 (CEST) X-IronPort-Anti-Spam-Filtered: true X-IronPort-Anti-Spam-Result: AgADALRLrEjAXQIniGdsb2JhbACRWz4BAQEPIJxrhnQBAoNe X-IronPort-AV: E=Sophos;i="4.32,242,1217800800"; d="scan'208";a="14145928" Received: from concorde.inria.fr ([192.93.2.39]) by mail2-smtp-roc.national.inria.fr with ESMTP; 21 Aug 2008 01:54:51 +0200 Received: from mail1-relais-roc.national.inria.fr (mail1-relais-roc.national.inria.fr [192.134.164.82]) by concorde.inria.fr (8.13.6/8.13.6) with ESMTP id m7KNspBg013545 for ; Thu, 21 Aug 2008 01:54:51 +0200 X-IronPort-Anti-Spam-Filtered: true X-IronPort-Anti-Spam-Result: AgABALRLrEjRVcitlGdsb2JhbACRWz4BAQEBCQMKBxEDnGiGdAECg14 X-IronPort-AV: E=Sophos;i="4.32,242,1217800800"; d="scan'208";a="16310080" Received: from wf-out-1314.google.com ([209.85.200.173]) by mail1-smtp-roc.national.inria.fr with ESMTP; 21 Aug 2008 01:54:08 +0200 Received: by wf-out-1314.google.com with SMTP id 25so759486wfa.0 for ; Wed, 20 Aug 2008 16:54:07 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=gamma; h=domainkey-signature:received:received:message-id:date:from:sender :to:subject:mime-version:content-type:content-transfer-encoding :content-disposition:x-google-sender-auth; bh=960nYmEHBFpxfDxPJd1f5Lon/9dGh7NRKMvk/9Dsb9M=; b=jjOz2Y5d7j1pozuhSMhiDI/0ktCBST3Dl8UPVxbSJ6ot6ZFfbUSvZCTSS/WC5rbmvk oFOC7TlT4rSUZcxgKzf2Buw4cqnsSTQFxDpF9NKvGmiowrRKp7cFyVKNJcWwFWc86ZgK YCA+mkFz8OtFw3Ocl+My8BsTmvyXzEW+O2f3Y= DomainKey-Signature: a=rsa-sha1; c=nofws; d=gmail.com; s=gamma; h=message-id:date:from:sender:to:subject:mime-version:content-type :content-transfer-encoding:content-disposition:x-google-sender-auth; b=OhUnulrMp83Y1GswR+OYo9mr/tVMt7zguWB1bY60EXOaQUxWtDTVLO1lOuBGU5/cyU NGqdVoqnnn6XbvwaYTAN2gb35ZOpOmszCJRnTW5/p41f7aNBrmZUXsJ0gIcjdJMfuBed /FdvIdvN7UMfSPdXcDEvuDgHuwqyNfqaKO628= Received: by 10.142.13.13 with SMTP id 13mr249437wfm.127.1219276446944; Wed, 20 Aug 2008 16:54:06 -0700 (PDT) Received: by 10.142.105.11 with HTTP; Wed, 20 Aug 2008 16:54:06 -0700 (PDT) Message-ID: <2b7b425b0808201654i61d3f878gbed5c27ca9114438@mail.gmail.com> Date: Thu, 21 Aug 2008 01:54:06 +0200 From: "=?ISO-8859-1?Q?J=E9r=E9mie_Lumbroso?=" Sender: jeremie.lumbroso@gmail.com To: caml-list@inria.fr Subject: Separating two mutually recursive modules (was Specifying recursive modules?) MIME-Version: 1.0 Content-Type: text/plain; charset=ISO-8859-1 Content-Transfer-Encoding: quoted-printable Content-Disposition: inline X-Google-Sender-Auth: 184bb90a1a6bcb66 X-Miltered: at concorde with ID 48ACAECB.000 by Joe's j-chkmail (http://j-chkmail . ensmp . fr)! X-Spam: no; 0.00; recursive:01 recursive:01 functors:01 functor:01 sig:01 struct:01 sig:01 struct:01 functor:01 bool:01 nat:01 arises:01 prefixing:01 bool:01 nat:01 Hello, In the same vein as: let rec p_even odd x =3D if x =3D 1 then false else x =3D 0 || (odd (x - 1)) let rec p_odd even x =3D if x =3D 0 then false else x =3D 1 || (even (x - 1)) ... let rec even x =3D p_even odd x and odd x =3D p_odd even x where I define two mutually recursive functions but only combine them later, I would like to separate two modules, named Boxes and Validator, which are mutually recursive. I've tried to imitate the above-mentionned transformation, but such attempts haven't amounted to much because, (a) I am unable to write recursive functors, i.e.: crazy stuff such as "module rec F : functor(A : TA with type t =3D F(A).t) -> TF"; (b) not only are my main modules mutually recursive, but one depends on itself as well. The crux of my problem, is that I have "grammar" that *must* be broken down into several modules: different "components" from this grammar are handled (entirely) by separate modules, and no module should be dependent on how each modules handles its task (of course). It is as if I had: module Bools(Main : M) : sig type t ... end =3D struct type t =3D True | False | Not of t | Equal of Main.t * Main.t ... end module Nats(Main : M) : sig type t ... end =3D struct type t =3D Zero | Succ of t ... end module Minilanguage =3D functor (BoolMod : ...) -> functor (NatMod : ...) -> struct type t =3D | Stuff of ... | Bool of BoolMod.t | Nat of NatMod.t ... ... end The problem is not in defining this language; it arises when I try to write a "fold" function on the grammar, while maintaining these conditions: - the individual 't' types are abstract (I don't want the details of the grammar to be accessible from "outside"); - because the goal is modularization I *cannot* resort to some trick wherein I create a "parent" module which contains all types, and then have the other modules "inherit" from it; - the various solutions I've examined (for instance, making Boxes.B.t a parameterized type) have been unsatisfactory (for various reasons with which I don't want to burden this paper with---even more than it already is!); - the fold must, for instance allow the Bools module to provide a function that takes a Minilanguage.t tree value, and transforms it by prefixing every boolean with a Not, i.e.: Bool(Equal(Nat(Zero), Nat(Succ(Zero)))) --> Bool(Not(Equal( .., .. ))) I have been unable to cleanly specify the code below (or something equivalent) without resorting to Obj.magic. (In the example below, "Boxes.B.t" as referenced by the Validator module would ideally simply be "Boxes.t", and Validator would not "see" the submodules;) (****************) (* MODULE Boxes *) (****************) module rec Boxes : sig (* NOTE: I which modules A and B where only accessible by Boxes itself, but not by Validator. (And have something such as type t =3D B.t)*) module A : sig (* This type was simplified for explanatory purposes. *) type t =3D private =09 | Anil =09 | Aout of Validator.t end module B : sig type t =3D private =09 | Bnil =09 | Bout of Boxes.A.t * t end end =3D struct module rec A : sig type t =3D | Anil | Aout of Validator.t val boolfold : ('a -> bool) -> ('a -> bool) -> Boxes.A.t -> bool end =3D struct type t =3D | Anil | Aout of Validator.t let boolfold p1 p2 =3D let rec aux =3D function | Boxes.A.Anil -> false | Boxes.A.Aout elt -> Validator.fold_on_B (fun x -> B.boolfold p1 p2 x) (||) false elt in aux end and B : sig type t =3D | Bnil | Bout of A.t * t val boolfold : ('a -> bool) -> ('a -> bool) -> Boxes.B.t -> bool end =3D struct type t =3D | Bnil | Bout of A.t * t let boolfold p1 p2 =3D let rec aux =3D function | Boxes.B.Bnil -> false | Boxes.B.Bout(a, elt) -> (A.boolfold p1 p2 a) || (aux elt) in aux end end (********************) (* MODULE Validator *) (********************) and Validator : sig (* This type has been simplified for explanatory purposes. *) (* IDEALLY, Boxes.B.t would simply be B.t. *) type t =3D Me of int | Node of t * t | B of Boxes.B.t val fold_on_B : (Boxes.B.t -> 'a) -> ('a -> 'a -> 'a) -> 'a -> t -> 'a end =3D struct type t =3D Me of int | Node of t * t | B of Boxes.B.t (* This functions must allow me to do "fold-like" operations on objects of type t, specifically targetting nodes of type B of Boxes.B.t *) let fold_on_B f combinator default =3D let rec aux =3D function (* Recursive calls down the tree. *) | Node(b1, b2) -> combinator (aux b1) (aux b2) (* Leaves which must be processed. *) | B r -> f r (* Leaves which must be ignored, and return the default value. *) | _ -> default in aux end This is a Gordian knot---of that I am fully aware. I'd welcome any help/hint/moral support with arms wide open; at this point I fear I've simply hit a (Berlin-sized) wall. J=E9r=E9mie