How to traverse typed abstract syntax tree in OCam

Question

I'm trying to dump type information of all identifiers in an OCaml project, basically it's the same as traversing the typed abstract syntax tree(https://github.com/ocaml/ocaml/blob/trunk/typing/typedtree.mli). Since I'm new to OCaml compiler's codebase, I'm not sure whether the Compiler has provided apis so we could easily write a plugin to do the job or we have to hack the compiler code? Also how does this interact with OCamlbuild? Thanks for any hints or advices.

Answer 1

OCaml provides its own compiler as a library named compiler-libs. It has everything in it, allowing one to move from a concrete syntax towards executable, with all intermidiate steps under your control, including typedtree, of course.

The bad news is that it is not documented. I would suggest you, to use utop or merlin to explore this library.

You do not need anything special to do with ocamlbuild to use compiler-libs, it is a regular library.

Answer 2

Assuming you have already got a typed AST of type structure somehow.

The classic way is simply to write a big recursive function to traverse the AST by yourself.

But now there is module TypedtreeIter available in OCaml compiler source code and it is exposed to compiler-libs. For simple traversal, this is very handy.

TypedtreeIter provides a functor to build your own iterator over typed ASTs. Here is a very simple example to print all the pattern identifiers with their types:

(* ocamlfind ocamlc -package compiler-libs.common -c example.ml *)
open Typedtree
open TypedtreeIter

module MyIteratorArgument = struct
  include DefaultIteratorArgument

  let enter_pattern p = match p.pat_desc with
    | Tpat_var (id, _) ->
        Format.printf "@[<2>%s@ : %a@]@."
          (Ident.name id)
          Printtyp.type_scheme p.pat_type
    | _ -> ()
end

module Iterator = TypedtreeIter.MakeIterator(MyIteratorArgument)

Module type TypedtreeIter.IteratorArgument is to specify what your iterator does for each AST construct. You have two points to execute your job: when the traversal enters a construct and when it exits from it. For pattern, for example, you have enter_pattern and exit_pattern. You do not need to worry about the recursion traversal itself: it is the job of the functor MakeIterator. Giving an IteratorArgument module it wires up all the enter_* and exit_* recursively and returns a module with bunch of iterators.

Normally you are interested only in some part of AST and want to skip the others. DefaultIteratorArgument is a module whose enter_* and exit_* do nothing. Your IteratorArgument module should include DefaultIteratorArgument to inherit this default behaviour, then implement only the parts which do something special.

If you want not only to traverse typed ASTs but also to modify some part of them, use TypedtreeMap instead of TypedtreeIter. There is a small example of TypedtreeMap at https://bitbucket.org/camlspotter/compiler-libs-hack/src/340072a7c14cbce624b98a57bf8c4c6509c40a31/overload/mod.ml?at=default.

(I do not use ocamlbuild, so I cannot help that point.)