扩展相互递归的仿函数

Question

我正在编写一个编译器,需要表示几个共同递归的结构,并依赖于表示表达式的数据结构.在编译开始时,我的表达式没有输入,但我会在稍后阶段输入它们.

我编写了以下仿函数,以便在此过程中重用代码:

module type Exp = sig                                                                                                                  
  type t                                                                                                                               
end  

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

module MyIR (E: Exp) = struct                                                                                                           
  type ty =                                                                                                                             
    | Unknown                                                                                                                           
    | Typed of E.t                                                                                                                      

  type exp_descr =
    | Leaf 
    | Node of E.t

  type exp = E.t  
end       

module UntypedExp (TD: IR) : (Exp with type t = TD.exp_descr) = struct
  type t = TD.exp_descr
end                          

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

module rec UTExp : Exp = UntypedExp(UTIR)
and UTIR : IR = MyIR(UTExp)

module rec TExp : Exp = TypedExp(TIR)
and TIR : IR = MyIR(TExp)

我现在有2个中间表示,一个使用无类型表达式,另一个使用类型表达式.

我现在想要编写一个打印模块,我想以与之前相同的方式对代码进行分解.下面是我不成功的尝试,我不明白如何正确延伸TExp和UTexp.更具体地说,我不知道如何共享定义的字段构造函数TypedExp.

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

module type IRPrint = sig
  include IR
  val string_of_ty: ty -> string
  val string_of_exp_descr: exp_descr -> string
  val string_of_exp: exp -> string
end

module MyExpPrint (R: IR) (E: ExpPrint with type t = R.exp) : (IRPrint with type exp := R.exp and type exp_descr := R.exp_descr and type ty := R.ty) = struct
  open 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 UTExpPrint (E : module type of UTExp) (R: IRPrint with type exp = E.t) : (ExpPrint with type t := R.exp_descr) = struct
  open E
  let string_of_t = R.string_of_exp_descr
end

module TExpPrint (E : module type of TExp) (R: IRPrint with type exp = E.t) : (ExpPrint with type t := R.exp) = struct
  open E
  let string_of_t e = R.string_of_exp_descr e.TExp.descr ^ " " ^ R.string_of_ty e.ty
end

编辑:解决问题 MyExpPrint

Answer 1

由于模块类型Exp定义为

 module type Exp = sig type t end

形式的任何签名约束M: Exp使得M不能使用的,因为它隐藏了所有m的信息,除了抽象类型山因为有这种类型的与外界之间没有功能该抽象类型不可用的存在.

例如,此模块定义定义了一个类型并立即将其隐藏到外部世界:

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

你想要的只是简单

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

如果你真的想要添加签名约束,那么正确的约束就是

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

请注意,我没有使用Exp with type t = ...有两个原因:首先,with约束不能定义新类型.其次,Exp with type t = ...只是一种复杂的写作方式sig type t = ... end.

这是您的代码的核心问题:它隐藏了所有可以有意义地操纵您定义的类型的信息.

例如,在删除仿函数结果的签名约束后,在递归模块约束中修复签名,将IRprint的签名简化为

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

然后TExpPrint可以修复仿函数

module TExpPrint
    (E : module type of TExp)
    (R: IRPrint with type exp_descr = TIR.exp_descr
                 and type exp = E.t
                 and type ty = TIR.ty)
=
struct
  open E
  let string_of_t e =
    R.string_of_exp_descr e.E.descr ^ " " ^ R.string_of_ty e.ty
end

我希望其余的错误可以遵循,因为它可以分享正确的类型平等.