Prophet

I've spend a lot of time trying to do this now, but I'm fairly convinced it's just not possible with modules.

Superficially, it seems like Trees That Grow would be an amazing fit for functors!

The aim of TTG is to be able to extend an annotate a syntax tree without having to duplicate the entire definition. In Haskell, this is achieved by parameterizing the syntax tree over the current pass and selecting the annotations with type families.

In OCaml, Functors sound like a great solution for this! One could just parameterize the syntax module over a module containing every single extension type like this

(* Syntax.ml *)

module Make(sig
    type name

    type var_ext
    type app_ext
    type lambda_ext
end) = struct
    type expr =
        | Var of var_ext * name
        | App of app_ext * expr * expr
        | Lambda of lamba_ext * name * expr
end

module Parsed = Make(struct
    type name = string
    type var_ext = unit
    type app_ext = unit
    type lambda_ext = unit
end)

module Renamed = Make(struct
    type name = some_better_name_representation
    type var_ext = unit
    type app_ext = unit
    type lambda_ext = unit
end)

Looks great right? This is what I did until now actually! It's just that... this doesn't work.

Let's say your syntax module looks like this and now you want to add a type checker to your language and annotate every expression with its type.

So you extend your syntax module with types and add a new pass

module Make (...) = struct
    type expr = ...

    type ty = 
        | Fun of ty * ty
        | Var of name
        | Forall of name * ty
end

...

module Typed = Make(struct
    type name = some_better_name_representation
    type var_ext = ???
    type app_ext = ???
    type lambda_ext = ???
end)

How do you refer to types now? The type you want is Typed.ty, but you cannot refer to the module Typed while defining it.

Mutually recursive modules sound like an obvious solution

module rec TypedArg = struct
    type name = some_better_name_representation
    type var_ext = Typed.ty
    type app_ext = Typed.ty
    type lambda_ext = Typed.ty
end
and Typed = Make(TypedArg)

But this doesn't compile. Recursive modules only compile with explicit module signatures and in order to export every single constructor from the module, you would need to write out the entire type definition, defeating the point of using TTG to avoid duplicate definitions in the first place.

module rec TypedArg : sig ... end = struct
    ...
end
and Typed : sig
    type expr = ...
    type ty = ...
end = Make(TypedArg)

Reconstructing the module type with module type of doesn't work either, since the resulting type depends on the functor argument and there is no way to say "give me the module type of this functor when applied to this module".

I've given up now, I don't think this is possible with modules. I'm going to try writing a PPX rewriter (kind of like TemplateHaskell) instead to generate the definitions. This doesn't allow me to write pass-agnostic functions, but I'm content if I get this working at all.