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 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 50109BC6B for ; Wed, 19 Sep 2007 13:39:36 +0200 (CEST) X-IronPort-Anti-Spam-Filtered: true X-IronPort-Anti-Spam-Result: AgAAADOn8EbAXQImn2dsb2JhbACOEgIBAQcEBgcIGA X-IronPort-AV: E=Sophos;i="4.20,273,1186351200"; d="scan'208";a="16415624" Received: from discorde.inria.fr ([192.93.2.38]) by mail4-smtp-sop.national.inria.fr with ESMTP; 19 Sep 2007 13:40:50 +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 l8JBe7lS010960 (version=TLSv1/SSLv3 cipher=RC4-SHA bits=128 verify=OK) for ; Wed, 19 Sep 2007 13:40:08 +0200 X-IronPort-Anti-Spam-Filtered: true X-IronPort-Anti-Spam-Result: Ah4FADOn8EaLEwECZmdsb2JhbACOEgsEBgcH X-IronPort-AV: E=Sophos;i="4.20,273,1186351200"; d="scan'208";a="16415621" Received: from mx2.mpi-sb.mpg.de (HELO francois.mpi-sb.mpg.de) ([139.19.1.2]) by mail4-smtp-sop.national.inria.fr with ESMTP; 19 Sep 2007 13:40:48 +0200 Received: from loopback.mpi-sb.mpg.de ([127.0.0.1]:41657 helo=localhost ident=amavis) by francois.mpi-sb.mpg.de (envelope-from ) with esmtp (Exim 4.50) id 1IXxvD-0007nY-QI for caml-list@inria.fr; Wed, 19 Sep 2007 13:40:47 +0200 Received: from francois.mpi-sb.mpg.de ([127.0.0.1]) by localhost (aspirin.mpi-sb.mpg.de [127.0.0.1]) (amavisd-new, port 10024) with ESMTP id 28329-05 for ; Wed, 19 Sep 2007 13:40:47 +0200 (CEST) Received: from zak.mpi-sb.mpg.de ([139.19.1.28]:48482) by francois.mpi-sb.mpg.de (envelope-from ) with esmtp (Exim 4.50) id 1IXxvD-0007nO-Fl for caml-list@inria.fr; Wed, 19 Sep 2007 13:40:47 +0200 Received: from swsao0703.ds.mpi-sws.mpg.de ([139.19.131.41]:53724) by zak.mpi-sb.mpg.de with esmtpsa (TLS-1.0:DHE_RSA_AES_256_CBC_SHA:32) (Exim 4.50) id 1IXxvD-0005Qe-7A for caml-list@inria.fr; Wed, 19 Sep 2007 13:40:47 +0200 X-Notes-Item: NOT CHECKED; name=$DNSBLSite Message-ID: <46F10ABF.3050502@mpi-sws.mpg.de> Date: Wed, 19 Sep 2007 13:40:47 +0200 From: Andreas Rossberg User-Agent: Mozilla-Thunderbird 2.0.0.4 (X11/20070619) MIME-Version: 1.0 To: caml-list@inria.fr Subject: Re: [Caml-list] Mutually recursive functions in different modules References: <74cabd9e0709172327g42d34407wc7027db6d8c6fba6@mail.gmail.com> In-Reply-To: Content-Type: text/plain; charset=ISO-8859-1; format=flowed Content-Transfer-Encoding: 7bit X-Virus-Scanned: by amavisd-new-20030616-p10 (Debian) at mpi-sb.mpg.de X-Miltered: at discorde with ID 46F10A97.001 by Joe's j-chkmail (http://j-chkmail . ensmp . fr)! X-Spam: no; 0.00; rossberg:01 rossberg:01 recursive:01 signoles:01 recursive:01 higher-order:01 filliatre:01 functors:01 sig:01 val:01 struct:01 sig:01 val:01 struct:01 compilation:01 Julien Signoles wrote: > I know (at least) 4 solutions to your problem: one use recursive modules > as suggested by Jacques Garrigue, one use higher-order functions as > suggested by Jean-Christophe Filliatre, one use functors and one use > references on functions. Having used most of these solutions in practice I thought that I may add my 2 cents. > (* 1- using recursive modules *) > module rec A : sig val f : int -> int end = struct > let f x = if x <= 0 then 0 else B.f (x - 2) > end and B : sig val f : int -> int end = struct > let f x = if x = 1 then 1 else A.f (x - 2) > end That certainly is the natural solution, but unfortunately, does not currently allow separate compilation. > (* 2- using higher-order functions *) > module A' = struct let f g x = if x <= 0 then 0 else g (x - 2) end > module B = struct let rec f x = if x = 1 then 1 else A'.f f (x - 2) end > module A = struct let f = A'.f B.f end In my experience, this solution does not scale at all. As soon as there are several mutual recursive functions involved that have to be called cross-module you have to parameterise all functions in A' over all those from B, and pass them through all local recusive calls in A'. That quickly gets out of hand, even if you use tuples. And don't even consider it for cases with more than 2 recursive modules. > (* 3- using functors *) > module FA(X:sig val f : int -> int end) = struct > let f x = if x <= 0 then 0 else X.f (x - 2) > end > module B = struct > let rec f x = > let module A = FA(struct let f = f end) in > if x = 1 then 1 else A.f (x - 2) > end > module A = FA(struct let f = B.f end) Note that this solution is quite expensive, since the functor is applied repeatedly on each recursive invocation. Also, it would simply be incorrect if A had state. The following variant probably is more appropriate: (* 3a - using functors and recursive modules *) module type B = sig val f : int -> int end module FA(B : B) = struct let f x = if x <= 0 then 0 else B.f (x - 2) end module rec A : A = FA(B) and B : B = struct let f x = if x = 1 then 1 else A.f (x - 2) end Note that you can separately compile FA and B. This is basically solution 2 lifted to the module level. You could also turn B into a functor as well to make it more symmetric and avoid having the actual definition of A being placed in B's compilation unit: (* 3b - using functors and recursive modules symmetrically *) module type A = sig val f : int -> int end module type B = sig val f : int -> int end module FA(B : B) = struct let f x = if x <= 0 then 0 else B.f (x - 2) end module FB(A : A) = struct let f x = if x = 1 then 1 else A.f (x - 2) endnd module rec A : A = FA(B) and B : B = FB(A) > (* 4- using references on functions *) > module A' = struct let f = ref (fun _ -> assert false) end > module B = struct let f x = if x = 1 then 1 else !A'.f (x - 2) end > module A = struct > let () = A'.f := fun x -> if x <= 0 then 0 else B.f (x - 2) > let f = !A'.f > end This is what I mostly use in practice. It scales best, because it keeps the problem of tying the recursive knot local to the concerned modules and works directly with compilation units - i.e., no need for nesting the actual module definitions. Also, it does not get more complicated when more than 2 modules participate in the recursion. I usually stylise this approach by making the forward references to another module part of the signature as follows: module A : sig module B : sig val f : (int -> int) ref end val f : int -> int end = struct module B = struct let f = ref (fun _ -> assert false) end let f x = if x <= 0 then 0 else !B.f (x - 2) end module B : sig val f : int -> int end = struct let f x = if x = 1 then 1 else A.f (x - 2) let () = A.B.f := f end The fact that this approach works best is somewhat unfortunate, because it relies on spurious use of state, and even makes that visible to the outside world. In any case, all this gets much hairier when you want cross-module recursion across type definitions... - Andreas