Mantis Bug Tracker

View Issue Details Jump to Notes ] Issue History ] Print ]
IDProjectCategoryView StatusDate SubmittedLast Update
0002660OCamlOCaml generalpublic2004-06-10 23:082013-08-30 23:28
Reporteradministrator 
Assigned To 
PrioritynormalSeverityfeatureReproducibilityalways
StatusacknowledgedResolutionopen 
PlatformOSOS Version
Product Version 
Target VersionFixed in Version 
Summary0002660: Recursive modules need qualified names?
DescriptionFull_Name: Christopher Dutchyn
Version: 3.07+2
OS: Windows XP
Submission from: cypress.cs.ubc.ca (142.103.11.23)


In the attached code, why does MakeMiddle.{inj,op} need to fully qualify the
names imported as Above.top{Ext,Inj,Op} rather than using the otherwise
intra-module names topExt, topInj, and topOp (look for the lines with !!!!)? If
you use the intra-module names, then you get errors about missing recursive
modules.

Chris D.

module type LAYER =
  sig
    (* open recursion to top layer *)
    type topT
    type topV
    val topInj : string -> topT
    val topOp : topT -> topV
    val topExt : topV -> string

    (* customize this actual body of the module *)
    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
*)
module MakeBase (Above : LAYER)
    : LAYER with type topT = Above.topT
             and type topV = Above.topV =
  struct
    type topT = Above.topT
    type topV = Above.topV
    let topInj = Above.topInj
    let topOp = Above.topOp
    let topExt = Above.topExt

    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 (Below : LAYER)
    (Above : LAYER)
    : LAYER with type topT = Above.topT
             and type topV = Above.topV =
  struct
    type topT = Above.topT
    type topV = Above.topV
    let topInj = Above.topInj (*use Above.topInj in code within this
module*)
    let topOp = Above.topOp (*ditto*)
    let topExt = Above.topExt (*ditto*)

    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, Above.topInj (String.sub s 2 ((String.length
s)-2))) (*why is Above. needed here? !!!!*)
      | _ -> 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) ^ (Above.topExt
(Above.topOp t))) (*ditto !!!!*)
              
    let ext =
      function
        | BelowV v -> Below.ext v
        | StringV s -> s
  end

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

(* cap level -- close the open recursion of topXXX *)
module MakeCap (Below : LAYER) : LAYER =
  struct
    type t = Below.t
    type v = Below.v
          
    let inj = Below.inj
    let op = Below.op
    let ext = Below.ext
        
    type topT = t
    type topV = v
    let topInj = inj
    let topOp = op
    let topExt = ext
  end

(* simplest test *)
module rec B : LAYER = MakeBase(T)
       and T : LAYER = MakeCap(B)

(* simple test *)
module rec B : LAYER = MakeBase(M)
       and M : LAYER = MakeMiddle(B)(T)
      (* imagine there were more levels *)
       and T : LAYER = MakeCap(M)

;; T.topInj "1x"
;; T.topOp (T.topInj "1x")
;; T.topExt (T.topOp (T.topInj "1x"))

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

Tagsrecmod
Attached Files

- Relationships

-  Notes
(0000222)
administrator (administrator)
2004-06-20 16:55

> In the attached code, why does MakeMiddle.{inj,op} need to fully
> qualify the names imported as Above.top{Ext,Inj,Op} rather than
> using the otherwise intra-module names topExt, topInj, and topOp
> (look for the lines with !!!!)? If you use the intra-module names,
> then you get errors about missing recursive modules.

Even if you use the fuly-qualified names, your program won't do what
you think it does. Consider a simplification of your example:

> module MakeMiddle (Below : LAYER) (Above : LAYER) ... = struct
> let topInj = Above.topInj
> let inj = fun s -> ... topInj s' ...
> end

> module rec B : LAYER = MakeBase(M)
> and M : LAYER = MakeMiddle(B)(T)
> (* imagine there were more levels *)
> and T : LAYER = MakeCap(M)

The evaluation of this 'module rec' proceeds as outlined in the
reference manual. Namely, the modules B, M and T are initialized with
default functions (functions that raise an Undefined exception)
for all of their value components. Then, the right-hand sides (the
functor applications) are computed. Thus, the MakeMiddle functor
fetches the default function from T.topInj and makes it the topInj
component of its result. Finally, the initial values in B, M, T are
replaced by the real values from the r.h.s. At this point, T.topInj is
the correct function, no longer the default function, but since
MakeMiddle computed T.topInj "too early", M.topInj is still a default
function, not T.topInj.

The correct solution is to do eta-expansion to delay the computation
of T.topInj:

> module MakeMiddle (Below : LAYER) (Above : LAYER) ... = struct
> let topInj = fun s -> Above.topInj s
> let inj = fun s -> ... topInj s' ...
> end

The workaround you proposed:

> module MakeMiddle (Below : LAYER) (Above : LAYER) ... = struct
> let topInj = Above.topInj
> let inj = fun s -> ... Above.topInj s' ...
> end

doesn't solve the problem entirely: the "inj" function works correctly
because it accesses Above.topInj at a time when the value of the
latter is correct (thanks to the delay in evaluation introduced by
"fun s -> ..."); but the "topInj" function in the result struct is
still evaluated too early and is a default function that will fail
when applied.

I agree the semantics of "module rec" aren't particularly intuitive,
but this is essentially the best we can do in a call-by-value language
like OCaml. In the future, I plan to replace the run-time failures
(exception Undefined) by a compile-time detection of bad "module rec"
definitions. Such a detection would have flagged both of your
examples, but recognized the eta-expanded form I suggest as correct.

Hope this clarifies the issue.

- Xavier Leroy

(0000223)
administrator (administrator)
2004-06-20 16:57

Feature wish: static detection of ill-founded "module rec".

- Issue History
Date Modified Username Field Change
2005-11-18 10:13 administrator New Issue
2013-08-30 23:28 doligez Tag Attached: recmod


Copyright © 2000 - 2011 MantisBT Group
Powered by Mantis Bugtracker