Reducing duplicate code in modules with parameterized type

Learning
, ,
1

Hello,
I found myself writing the following piece of code, and I’m wondering how can I reuse more code and not repeat re-declaring type expr = ... in both modules (since outside of this minimal example this would be a large grammar and repeating it twice or even more times would be bad).

module SimpleAST = struct 
  type 'a ast_node = 'a
  type expr = Bool of bool ast_node | Int of int ast_node
  (* more type definitions shared between SimpleAST and TypedAST *)
  (* ... *)
end

module TypedAST = struct 
  type 'a ast_node = {node: 'a; type_info: TType} (* everything is the same except the definion of ast_node *)
  type expr = Bool of bool ast_node | Int of int ast_node
  (* more type definitions shared between SimpleAST and TypedAST *)
  (* ... *)
end

Ultimately, what I’m trying to achieve is having tree variatinons which represent the same structure (e.g. an expr will always have as children a Bool and an Int across all variations, but the actual nodes of each tree to be of different type)

Also, the reason I am not creating a signature for both modules is that I want the definitions of expr etc to be public, so if I had a type module I would have to triplicate the definitions. As a result this is preventing me from using functors (but possibly there’s something I’m missing here).

Is there any way to achieve that or factor out the redundant code above? Thanks!

2

You may introduce a module type just for parameterizing by ast_node, without duplicating the definition of expr.

module type Ast_node = sig
  type 'a t
end

module MakeAST (Ast_node : Ast_node) = struct
  type expr = Bool of bool Ast_node.t | Int of int Ast_node.t
  (* more type definitions shared between SimpleAST and TypedAST *)
end

module SimpleAST = struct 
  type 'a ast_node = 'a
  include MakeAST (struct type 'a t = 'a ast_node end)
  (* ... *)
end

module TypedAST = struct 
  type 'a ast_node = {node: 'a; type_info: ttype} (* everything is the same except the definion of ast_node *)
  include MakeAST (struct type 'a t = 'a ast_node end)
  (* ... *)
end
1 Like
3

Another option is to make expr a type constructor and then reuse it with each of your other types.

type ('bool, 'int) generic_expr = Bool of 'bool | Int of 'int

module SimpleAST = struct 
  type 'a ast_node = 'a
  type expr = (bool ast_node, int ast_node) generic_expr
end

module TypedAST = struct 
  type 'a ast_node = {node: 'a; type_info: TType.t}
  type expr = (bool ast_node, int ast_node) generic_expr
end
4

This is interesting, I don’t think I’ve seen this approach before. Only problem I see is that for a “real” AST with say 20 variants, applying each as a type parameter would be pretty unwieldy. But for a small type like this it works nicely.