caml-list - the Caml user's mailing list
 help / color / mirror / Atom feed
* [Caml-list] recursive modules
@ 2003-05-05  8:21 Xavier Leroy
  2003-05-05 11:29 ` Markus Mottl
                   ` (2 more replies)
  0 siblings, 3 replies; 6+ messages in thread
From: Xavier Leroy @ 2003-05-05  8:21 UTC (permalink / raw)
  To: caml-list

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


^ permalink raw reply	[flat|nested] 6+ messages in thread
* [Caml-list] Recursive Modules
@ 2003-08-29 20:17 Christopher Dutchyn
  0 siblings, 0 replies; 6+ messages in thread
From: Christopher Dutchyn @ 2003-08-29 20:17 UTC (permalink / raw)
  To: CAML List

[-- Attachment #1: Type: text/plain, Size: 3226 bytes --]

I think the recursive modules definitions do not completely propagate safe
definitions: I get

Exception: Undefined_recursive_module ("SimpleLayer.ml", 104, 23)

with the attached code.

 

Chris D.

 

module type LAYER =

  sig

    type topT

    type topV

    val topInj : string -> topT

    val topOp  : topT -> topV

    val topExt : topV -> string

 

    type t

    type v

 

    val inj : string -> t

    val op : t -> v

    val ext : v -> string

  end

 

 

(* base module -- no lower layer present, empty types, all operations are
errors *)

(* *** ``safe'' module (section 7.8 of refman) *** *)

module MakeBase =

  functor (Above : LAYER) ->

  struct

    type topT = Above.topT

    type topV = Above.topV

    let topInj = fun x -> Above.topInj x(*safe*)

    let topOp  = fun x -> Above.topOp x (*safe*)

    let topExt = fun x -> Above.topExt x(*safe*)

 

    type t = EmptyT              (* wouldn't revised syntax be nice *)

    type v = EmptyV

          

    let inj = fun _ -> raise (Failure "inj")

    let op  = fun _ -> raise (Failure "op")

    let ext = fun _ -> raise (Failure "ext")

  end

 

(* an intermediate level *)

module MakeMiddle =

  functor (Below : LAYER) ->

    functor (Above : LAYER) ->

  struct

    type topT = Above.topT

    type topV = Above.topV

    let topInj = Above.topInj

    let topOp  = Above.topOp

    let topExt = Above.topExt

 

    type t =

      | BelowT of Below.t

      | OneT of char

      | TwoT of char * topT

            

    type v =

      | BelowV of Below.v

      | StringV of string

            

    let inj = fun s ->           (* <T> ::= 1_ [OneT _] | 2_? [TwoT _ ?] |
<Below.T> *)

      match (String.get s 0) with

      | '1' -> OneT (String.get s 1)

      | '2' -> TwoT(String.get s 1, topInj (String.sub s 2 ((String.length
s)-2)))

      | _ ->   BelowT (Below.inj s)

          

    let op =

      function

        | BelowT t -> BelowV (Below.op t)

        | OneT(c) -> StringV ("1" ^ (String.make 1 c))

        | TwoT(c,t) -> StringV ("2" ^ (String.make 1 c) ^ (topExt (topOp
t)))

              

    let ext =

      function

        | BelowV v -> Below.ext v

        | StringV s -> s

  end

 

(* imagine there were more levels -- maybe even tree/graph structured *)

 

(* top level -- close the open recursion of topInj and topExt *)

(* *** ``safe'' module (section 7.8 of refman) *** *)

module MakeTop =

  functor (Below : LAYER) ->

  struct

    type t = Below.t

    type v = Below.v

          

    let inj = fun x -> Below.inj x      (*safe*)

    let op  = fun x -> Below.op x       (*safe*)

    let ext = fun x -> Below.ext x      (*safe*)

 

    type topT = t

    type topV = v

    let topInj = fun x -> inj x         (*safe*)

    let topOp  = fun x -> op x          (*safe*)

    let topExt = fun x -> ext x         (*safe*)

  end

 

(* simplest test *)

module rec B : LAYER = MakeBase(T)

       and T : LAYER = MakeTop(B)

 

(* simple test *)

module rec B : LAYER = MakeBase(M)

       and M : LAYER = MakeMiddle(B)(T)

      (* imagine there were more levels *)

       and T : LAYER = MakeTop(M);;

 

T.topOp (T.topInj "2x1x");;

T.topExt (T.topOp (T.topInj "2x1x"))

 


[-- Attachment #2: Type: text/html, Size: 18585 bytes --]

^ permalink raw reply	[flat|nested] 6+ messages in thread
end of thread, other threads:[~2003-08-29 20:17 UTC | newest]

Thread overview: 6+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2003-05-05  8:21 [Caml-list] recursive modules Xavier Leroy
2003-05-05 11:29 ` Markus Mottl
2003-05-16 16:31   ` brogoff
2003-05-05 12:20 ` John Max Skaller
2003-05-05 16:59 ` brogoff
2003-08-29 20:17 [Caml-list] Recursive Modules Christopher Dutchyn

This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for NNTP newsgroup(s).