Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Recursive modules need qualified names? #2660

Closed
vicuna opened this issue Jun 10, 2004 · 4 comments
Closed

Recursive modules need qualified names? #2660

vicuna opened this issue Jun 10, 2004 · 4 comments

Comments

@vicuna
Copy link

vicuna commented Jun 10, 2004

Original bug ID: 2660
Reporter: administrator
Status: acknowledged
Resolution: open
Priority: normal
Severity: feature
Category: typing
Tags: recmod
Monitored by: "Julien Signoles"

Bug description

Full_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"))

@vicuna
Copy link
Author

vicuna commented Jun 20, 2004

Comment author: administrator

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

@vicuna
Copy link
Author

vicuna commented Jun 20, 2004

Comment author: administrator

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

@github-actions
Copy link

This issue has been open one year with no activity. Consequently, it is being marked with the "stale" label. What this means is that the issue will be automatically closed in 30 days unless more comments are added or the "stale" label is removed. Comments that provide new information on the issue are especially welcome: is it still reproducible? did it appear in other contexts? how critical is it? etc.

@github-actions github-actions bot added the Stale label May 18, 2020
@xavierleroy
Copy link
Contributor

See #2629 for another example where eta-expansion is needed. We haven't made progress towards static detection of ill-founded "module rec" in 16 years, so I'll close this report.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Projects
None yet
Development

No branches or pull requests

3 participants