Convert from one complicated type(like AST) to another

There is an AST, it’s very complex, like OCaml AST. Also, I have another modified version of this AST with only a few changes and want to convert it from the old one.

There is a naive solution: “pattern matching” all and copy them recursively. There will be a lot of boring code that almost does the same things. Is there any better way to do this? Thanks.

1 Like

This topic (or, family of topics) was raised a year+ ago, FWIW: An AST typing problem

That’s not to say it’s not worth asking again; I don’t think I’ve seen any “good” approach so far, despite a fair amount of my own reading/searching. Compared to writing compilers in e.g. a lisp with a reasonable macro system, I’ve just accepted that doing so in ML-likes involves an unfortunate degree of verbosity and repetition in exchange for the compiler’s assurances.

(I keep meaning to finally dig into MetaOCaml with the hope of addressing this exact problem for myself, but it seems the costs of the aforementioned verbosity haven’t risen to the point of motivating me enough to do so, yet.)

1 Like


  • Both input and output are typechecked. Boring.
  • The compiler will let you know if you forget to cover a case. <yawn>
  • The code is obvious and easy to maintain. Not great job security.
  • You miss out on all the fun of metaprogramming tools that 1 person on the planet understands and 0 are willing to maintain.


1 Like

Can you show a simplified example of the problem?

I know you’re having a bit of fun, but I can’t let metaprogramming slander go unanswered :wink:

As much as I have accepted the benefits provided by e.g. OCaml in this department, there are costs and weaknesses that I don’t think we should try to snark away – and repetitive code (especially beyond some point of scale, je ne sais quoi) is one of them. It’s absolutely a pity that OCaml doesn’t provide metaprogramming facilities, especially since quality typesafe options (from Rust’s macros to Racket’s Turnsile) are far from fringe tools at this point.

1 Like

My point is there’s nothing wrong with repetitive code if it’s cheaper to maintain than the alternative.

1 Like

the package clangml does AST transformations from the full C AST to a simpler one IIRC

@thierry-martinez might now a lot on this topic
At some point, clangml was using some camlp4 magic.
I don’t know if it is the case anymore, I had a lot of trouble understanding and modifying such camlp4 code.

See also:

Isn’t ppx comparable to Rust’s macros? I haven’t seen anything done in rust macros that doesn’t have some comparable ppx. (But I’m not an expert in this area.) Is the big difference that rust macros are perhaps easier to write and don’t require Defining a lib? (I’d not make much of the later constraint, since it is trivial to add a sub package to a project in OCaml).

Iiuc, Turnstile is an application of Rackets macros system? While it would be very neat to have lisp-comparable metaprogramming (ala TyperML (pdf)), I don’t think it’s pitiful that OCaml hasn’t “caught up” to lisp ito meta programming :wink:

There are equivalently powerful, but quite different: while rust macros allow you to define forms using regular Rust syntax (modulo some splicing operators, etc, quite similar to what you see in lisp macro systems and MetaOCaml AFAICT), ppx requires generated forms to be defined in terms of an AST model. This requires ppx authors to interact with said model and the various utilities surrounding it; it’s obviously a tractable exercise, but I don’t think anyone can claim that it’s easy in the same way that lisp and rust macros are.

(Anecdote: to date, I’ve found it to be far easier to simply push code generation (producing types and associated data structures from predefined JSON files for example) to bespoke separate programs that Format.printf code to where it needs to go, and tied together with dune rules. Doing the same thing via ppx was just much more complicated and touched types and APIs that I knew I wasn’t going to recall in the slightest the week after, nevermind a year from now.)

I’d call Turnstile an extension of Racket macros, but the fact that both “extension” and “application” net out to the same thing points to the essential benefit of lisp-style metaprogramming.

Thanks for the TyperML reference, that looks very interesting!

Not pitiful, but IMO unfortunate. I want to have my cake and eat it too!

1 Like

Two parts:

(1) I think that a “migration” PPX rewriter is really valuable – it makes your code much, much more succinct, and it gives you a flexibility in being able to modify your AST types and then, with relatively small changes, get a lot of stuff generated for you easily. Am example of this is: when a new OCaml AST version comes out, it typically takes me 30min to generate the migration for it. That’s a lot faster than having to do it “by hand”.

(2) Hereinafter I’m going to describe pa_ppx_migrate, a PPX rewriter that automates much of the process of creating “migrations” between two very-similar-but-not-identical families of AST types., e.g. OCaml v 4.02 and v4.03.

Caveat: what I describe below is based on Camlp5 and pa_ppx, so it’s possible (OK: near-certain) that you won’t want to use it, b/c it will be … not so compatible with the standard PPX rewriters. Notwithstanding, the ideas in this PPX rewriter should be easily re-implementable in a PPX rewriter based on the standard tooling.

Link: GitHub - camlp5/pa_ppx_migrate: PPX Rewriter to help write AST migrations for Ocaml (using Camlp5 and pa_ppx)

You can look at examples in the tests directory, or full examples of migrations between the various versions of the OCaml AST in pa_ocaml_migrate_parsetree .

The idea is this: you define two types[1], the SRC and the DST, and then, as a type-deriver on SRC, you provide (hopefully) minimal hints to the machinery that generates a function from SRC to DST. The migration is specified as a bunch of “type migrations” one for each type, or more precisely, for type-patterns. That is, you write a pattern in the type-language of the types of SRC, and then you specify a type in the type-language of DST. If the types match up, then auto-generated match code will do the job. For the cases where it does not, you can supply the few case-branches that change, or specify which fields are omitted or added-in, or even specify the entirety of the code. For polymorphic type-constructors, you can either specify instances (with type-variables instantiated to concrete types), and a migration for each instance. Or, you can specify a migration for the polymorphic type, in which case the machinery generates a migration function that takes migrations for the parameter-types. There are lots of examples of these in the tests.

I’ve worked thru migrations for all the OCaml AST versions 4.02…4.12, mostly 4.N <-> 4.{N+1) but also from 4.02 to a bunch of other versions (just to see how it would work out). I’ve also use this PPX rewriter in other PPX rewriters, like camlp5/pa_ppx_ag (an attribute-grammar evaluator-generator).

Again, I would strongly note that if you want to keep using the standard set of PPX rewriters, you can probably use pa_ppx_migrate for the one task of generating migrations, but again, it’s not designed to be composable with the standard set, b/c it’s based on Camlp5 and pa_ppx.

As another set of examples, I use this machinery to generate migrations amongst

  1. an AST type
  2. that same AST type with hashcons nodes inserted (camlp5/pa_ppx_hashcons)
  3. that same type with unique-ids at every node (camlp5/pa_ppx_unique) (hence, “anti-hash-consing”)
  4. that same AST with slots added in nodes for attributes (camlp5/pa_ppx_ag).

Obviously, it would be tedious to maintain all of these manually, as one changes the base AST type.

If you want to use this as an example to implement your own migration PPX rewriter using the standard tooling, I’d be happy to explain how it works – ti’s basically does matching and rewriting on type-expressions, to drive the generation of the match-code. Not actually very complicated at all.

[1] actually, two sets of mutually-recursive types, of course.

1 Like

A strategy I used in the past is to use a tool to automatically generate the boilerplate, and fine-tune the boilerplate after. If the 2 ASTs are mostly similar, the tuned-part should be small.
See GitHub - aryx/ocamltarzan: Compile Time Reflection or Metaprogramming for OCaml
At least it saves you the initial boilerplate.