扩展互递归函子

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 的所有信息，除了抽象类型 M.t 的存在。这种抽象类型不可用，因为这种类型与外界之间没有函数。

例如，这个模块定义定义了一个类型并立即向外界隐藏它：

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.

这是您的代码的核心问题：它隐藏了所有可能对您定义的类型进行有意义操作的信息。

比如去掉对functor result的签名约束后，修复递归模块约束中的签名，简化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

并且我希望接下来会出现其他错误，因为可以共享正确的类型等式。

扩展互递归函子

Extend mutually recursive functors

recursion

ocaml

functor