From mboxrd@z Thu Jan  1 00:00:00 1970
Received: (from majordomo@localhost) by pauillac.inria.fr (8.7.6/8.7.3) id KAA25292; Mon, 5 May 2003 10:21:24 +0200 (MET DST)
X-Authentication-Warning: pauillac.inria.fr: majordomo set sender to owner-caml-list@pauillac.inria.fr using -f
Received: from concorde.inria.fr (concorde.inria.fr [192.93.2.39]) by pauillac.inria.fr (8.7.6/8.7.3) with ESMTP id KAA25233 for <caml-list@pauillac.inria.fr>; Mon, 5 May 2003 10:21:22 +0200 (MET DST)
Received: from pauillac.inria.fr (pauillac.inria.fr [128.93.11.35])
	by concorde.inria.fr (8.11.1/8.11.1) with ESMTP id h458LMH09508
	for <caml-list@inria.fr>; Mon, 5 May 2003 10:21:22 +0200 (MET DST)
Received: (from xleroy@localhost) by pauillac.inria.fr (8.7.6/8.7.3) id KAA11072 for caml-list@inria.fr; Mon, 5 May 2003 10:21:21 +0200 (MET DST)
Date: Mon, 5 May 2003 10:21:21 +0200
From: Xavier Leroy <xavier.leroy@inria.fr>
To: caml-list@inria.fr
Subject: [Caml-list] recursive modules
Message-ID: <20030505102121.B23988@pauillac.inria.fr>
Mime-Version: 1.0
Content-Type: text/plain; charset=us-ascii
X-Mailer: Mutt 1.0i
X-Spam: no; 0.00; publi:01 camlcvs:01 recursion:01 val:01 struct:01 pervasives:01 elt:01 fixpoint:01 pragmatic:01 cristal:01 ocaml:01 sig:01 int:01 rec:01 node:02 
Sender: owner-caml-list@pauillac.inria.fr
Precedence: bulk

Since the issue of recursive modules has (again) popped up on this
list, it seems that now is a good time to announce an experimental
design and implementation for recursive modules in OCaml that I've
been working on lately.  A note describing the design is at

     http://cristal.inria.fr/~xleroy/publi/recursive-modules-note.pdf

and the implementation can be downloaded from the CVS repository
on camlcvs.inria.fr, tag "recursive_modules".

What this extension provides is a "module rec ... and ..." binding
that allows the definition of mutually-recursive modules within the
same compilation units.  Recursion between compilation units is a
different problem that is not adressed yet.  To give a flavor of the
extension, one can write for instance

    module A : sig
                 type t = Leaf of string | Node of ASet.t
                 val compare: t -> t -> int
               end
             = struct
                 type t = Leaf of string | Node of ASet.t
                 let compare t1 t2 =
                   match (t1, t2) with
                     (Leaf s1, Leaf s2) -> Pervasives.compare s1 s2
                   | (Leaf _, Node _) -> 1
                   | (Node _, Leaf _) -> -1
                   | (Node n1, Node n2) -> ASet.compare n1 n2
               end
    and ASet : Set.S with type elt = A.t
             = Set.Make(A)

The other point worth mentioning is that the detection of ill-founded
recursive definitions (definitions that have no fixpoint in a
call-by-value evaluation regime) is not completely static and may
cause an "Undefined" exception to be thrown at program initialization
time.  Fully static prevention of ill-founded recursion would, in the
current state of our knowledge, either rule out too many valuable
uses, or require major complications in the type system.  The proposed
approach is a pragmatic compromise rather than a 100% intellectually
satisfying solution.

No decision has been taken yet concerning the possible integration of
this extension in a future release of OCaml.

Comments and feedback are most welcome, as long as they are of the
constructive kind.

- Xavier Leroy

-------------------
To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr
Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners