Utilising recursion schemes when implementing compilers

Question

I haven't personally seen much use of recursion schemes when building compilers or interpreters, and I'm honestly not quite sure why. Almost all the common ones (cata/ana/para/apo) seem quite handy for various tasks, especially when manipulating ASTs. Is this just because most implementation languages lack the type systems require to express them, or some other reason I'm not seeing? If your language of choice performs specialisation based on type, I don't see them causing much slowdown.

Context: I want to use recursion schemes in my compiler, but I don't see them used much, and I want to know why so I can hopefully avoid any pitfalls I'm missing.

I am not referring to the visitor pattern, which appears to be a slightly weaker version of recursion schemes for OO languages, due to requiring manual creation of functions to access the children of a node, whereas recursion schemes + a little bit of compiler magic can do it fully automatically.

Answer 1

I'm not that familiar with Recursion Schemes (though I had read about a half of "Bananas, Lenses and Barbed Wire" paper quite some years ago), but I'd say they're mostly useful to work with tree-like data structures.

The main tree in a compiler is obviously AST, but you ditch that pretty fast. Two main things you do with AST keeping it tree-shaped are 1. name resolution and 2. type-checking. After that you transform your AST into some graph-based IR — SSA, Sea-of-Nodes or alike — and perform most of optimizations and code transformations on this IR. Here Recursion Schemes are unlikely to provide much help. That's I assume the main reason they are not employed in compilers.

Answer 2

Recursion schemes are a coding pattern to factor out recursion. Some people may see them as beneficial, others may not. In the end, this is more about software engineering than anything and you shouldn't apply recursion schemes just because you can, but because they feel like the right thing to do in that particular case. Given the huge body of research and industrial strength of OOP-languages, it seems plausible that recursion schemes are just not that well known.

Regardless, I'd like to make the case that recursion schemes can be useful. Consider the following grammar:

type expr =
| Int of int
| Plus of expr * expr
| Var of string
| Let of string * expr * expr
| Ifz of expr * expr * expr

Consider a dead code elimination pass that rewrites ifz:

let rec dce e =
  match e with
  | Int _ | Var _ -> e
  | Plus(e1, e2) -> Plus(dce e1, dce e2)
  | Let(x,e1,e2) -> Let(x, dce e1, dce e2)
  | Ifz(Int 0,e1,_e2) -> dce e1
  | Ifz(Int _,_e1,e2) -> dce e2
  | Ifz(c,e1,e2) -> Ifz(dce c,dce e1,dce e2)

It's easy to see that for any pass we do over the syntax of our little language, we'd have to pattern match and propagate the recursive calls to our pass itself, covering every case, even though the only relevant ones for dce above are just Ifz(Int 0, _, _) and Ifz(Int _, _, _).

We can define one of many recursion schemes to factor out the recursion:

let map f e =
  match e with
  | Int _ | Var _ -> e
  | Plus(e1,e2) -> Plus(f e1, f e2)
  | Let(x,e1,e2) -> Let(x, f e1, f e2)
  | Ifz(c,e1,e2) -> Ifz(c, e1, e2)

With this, we car re-define our dce to be much more succinct and, thus, likely more maintainable:

let rec dce e =
  match e with
  | Ifz(Int 0,e1,_e2) -> dce e1
  | Ifz(Int _,_e1,e2) -> dce e2
  | _ -> map dce e

This simple example shows that recursion schemes can be a viable coding pattern when implementing a compiler.

Answer 3

Recursion schemes are good ways to refactor out recursions only if these recursions can be translated into type-theoretic eliminators (e.g. the "foldr" or the (co)algebra in the (co)algebraic data type).

This sentence may sound tautological, but it emphasizes the limitation: if you have multi-variable recursion or general recursion, translating to recursion schemes can make the code more cumbersome (or maybe even impossible).

In a compiler, it is very common to have multi-variable recursion, like when writing an expression type-checking function:

check : (Expr, Type) -> Result
check (Lambda ...) (FunTy ...) = ...
check (Tuple ...) (TupleTy ...) = ...

For these functions, you'll have a hard time translating them into eliminators, which makes recursion schemes difficult to be applied.

For simple functions like counting some references from an AST, it will be very convenient to use recursion schemes there, and I believe such a use case will remind you of recursion schemes. I believe you just haven't found such a use case yet.