Extending recursive functors

Learning
,
1

I am writing a compiler and would like for the representation of the ast to evolve during compilation, but I also would like to factorize the code I write as much as possible. Here are the basic data structure I am working with.

module type CustomType = sig
  type t
end

module type AllTypes = sig
  type exp
  type ty
  type exp_descr
end

module type AST = sig
  type exp
  type ty =
    | Unknown
    | Typed of exp
  type exp_descr =
    | Leaf
    | Node of exp
end

module MakeAST (E: CustomType) = struct
  type exp = E.t

  type ty =
    | Unknown
    | Typed of exp

  type exp_descr =
    | Leaf
    | Node of exp
end

module TypedExp (TD: AllTypes) = struct
  type t =
    {
      ty : TD.ty;
      descr : TD.exp_descr;
    }
end

module rec TExp : sig type t = { ty : TAST.ty; descr : TAST.exp_descr; } end = TypedExp(TAST)
and TAST : AST with type exp = TExp.t = MakeAST(TExp)

I have factorized some code in AST and wrote an independent module to represent expressions because I know that I am going to change the representation once everything is type-checked.

Now, I want to write a printing module for this representation:

module type ExpPrint = sig
  type t
  val string_of_t: t -> string
end

module type ASTPrint = sig
  module AST : AST
  val string_of_ty: AST.ty -> string
  val string_of_exp_descr: AST.exp_descr -> string
  val string_of_exp: AST.exp -> string
end

module MakeASTPrint (R: AST) (E: ExpPrint with type t = R.exp) = struct
  module AST = R
  let string_of_exp = E.string_of_t
  let string_of_ty = function
    | R.Unknown -> "Unknown"
    |   Typed e -> "Typed: " ^ string_of_exp e

  let string_of_exp_descr = function
    | R.Leaf   -> "Leaf"
    |   Node e -> "Node: " ^ string_of_exp e
end

module  TExpPrint (R: ASTPrint) (E: module type of   TypedExp(R.AST)) = struct
  type t = E.t
  let string_of_t e = R.string_of_exp_descr e.E.descr ^ " " ^ R.string_of_ty e.ty
end

module rec TEPrint : ExpPrint with type t = TExp.t = TExpPrint(TPrint)(TExp)
and TPrint : ASTPrint with module AST = TAST = MakeASTPrint(TAST)(TEPrint)

I am trying to make sure that if my AST changes in the future and more of the types need to be custom I will be able to reuse the printing module I wrote for TExp, namely TExpPrint.

Unfortunately, I receive the following error message:

File "pock.ml", line 75, characters 71-75:
Error: Signature mismatch:
       Modules do not match:
         sig type t = TExp.t = { ty : TAST.ty; descr : TAST.exp_descr; } end
       is not included in
         sig
           type t =
             TypedExp(TPrint.AST).t = {
             ty : TPrint.AST.ty;
             descr : TPrint.AST.exp_descr;
           }
         end
       Type declarations do not match:
         type t = TExp.t = { ty : TAST.ty; descr : TAST.exp_descr; }
       is not included in
         type t =
           TypedExp(TPrint.AST).t = {
           ty : TPrint.AST.ty;
           descr : TPrint.AST.exp_descr;
         }
       File "pock.ml", line 34, characters 2-68: Expected declaration
       File "pock.ml", line 41, characters 22-72: Actual declaration

I do not understand why the compiler does not realize that the two types are really the same.

One way to fix it, is to replace module type of TypedExp(R.AST) by module type of TExp in the definition of TExpPrint. For that matter, I could also remove E altogether in this definition and hardcode a dependency toward TExp.
But, I wouldn’t be able to use TExpPrint with another representation than AST even if I reuse TypedExp.

EDIT: I changed TExpPrint, TEPrint and TPrint to the following definitions:

module  TExpPrint (AST: AST) (R: ASTPrint with module AST = AST) (E: module type of TypedExp(AST)) = struct
  type t = E.t
  let string_of_t e = R.string_of_exp_descr e.E.descr ^ " " ^ R.string_of_ty e.ty
end

module rec TEPrint : ExpPrint with type t = TExp.t = TExpPrint(TAST)(TPrint)(TExp)
and TPrint : ASTPrint with module AST = TAST = MakeASTPrint(TAST)(TEPrint)

The error message now is:

File "test.ml", line 75, characters 77-81:
Error: Signature mismatch:
       Modules do not match:
         sig type t = TExp.t = { ty : TAST.ty; descr : TAST.exp_descr; } end
       is not included in
         sig
           type t =
             TypedExp(TAST).t = {
             ty : TAST.ty;
             descr : TAST.exp_descr;
           }
         end
       Type declarations do not match:
         type t = TExp.t = { ty : TAST.ty; descr : TAST.exp_descr; }
       is not included in
         type t =
           TypedExp(TAST).t = {
           ty : TAST.ty;
           descr : TAST.exp_descr;
         }
       File "test.ml", line 34, characters 2-68: Expected declaration
       File "test.ml", line 41, characters 22-72: Actual declaration

Is it an OCaml compiler bug or what am I missing?

2

On your second problem, you are just not exporting the identity between Texp.t and TypedExp(TAST).t, the compiler is thus right to reject the inclusion. You can fix it with

module rec TExp : sig
  type t = TypedExp(TAST).t = { ty : TAST.ty; descr : TAST.exp_descr; }
end = TypedExp(TAST)
and TAST : AST with type exp = TExp.t = MakeAST(TExp)
3

Thanks, I wasn’t aware that there were two problems in there. I thought that adding AST as an argument to TExpPrint was adding redundancy. Does that mean that it is needed to implement a module that extends every module created from applying the functor TypedExp?

4

To be honest, I only see one problem (@octachron: what is the first problem you see?): a typechecking one, because you only have two isomorphic types which are distinct.

Your situation is similar with this one:

module A = struct
  type t = {foo : int}
  let v = {foo = 1}
end

module B = struct
  type t = {foo : int}
  let v = {foo = 1}
end

Here A.t and B.t are incompatible types, because the fully qualified record fields are not foo but A.foo and B.foo, which are distinct.

For instance, when you write A.v.foo you will trigger a warning:

A.v.foo;;
Characters 4-7:
Warning 40: foo was selected from type A.t.
It is not visible in the current scope, and will not 
be selected if the type becomes unknown.

To be precise, in this case you should write:

A.(v.foo);;
- : int = 1

(* or *)

A.v.A.foo;;
- : int = 1

and if you try to compare A.v and B.v you’ll have a type checking error, as if you use record field A.foo with B.v:

A.v = B.v;;
Error: This expression has type B.t but an expression was expected of type A.t

B.v.A.foo;;
Error: The field A.foo belongs to the record type A.t
       but a field was expected belonging to the record type B.t

Nevertheless, the two types are distinct but isomorphic:

let a_to_b {A.foo} = {B.foo};;
val a_to_b : A.t -> B.t = <fun>

let b_to_a {B.foo} = {A.foo};;
val b_to_a : B.t -> A.t = <fun>

The solution, if you want a module with a type t equal to A.t, is to define:

module C = struct
  type t = A.t = {foo : int}
  let v = {foo = 1}
end

then you can do:

A.v = C.v;;
- : bool = true

A.v.C.foo;;
- : int = 1

C.v.A.foo;;
- : int = 1

Hence, @octachron solution to your type checking problem is to write the record type identity in TExp signature.

5

Sorry, I was unclear, I meant looking at your edited code and the corresponding issue.