<p>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.</p>
<p>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.</p>
<p>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.</p>

<implementation><compilers><interpreters>
Utilising recursion schemes when implementing compilers
CC BY-SA 4.0
2023-05-17T00:41:19.280Z
@kaya3 I haven't personally heard of the visitor pattern, but it seems to be a less powerful version of recursion schemes - https://blog.sumtypeofway.com/posts/introduction-to-recursion-schemes.html serves as a good introduction if you know Haskell to at least a somewhat decent level. I say "less powerful" as recursion schemes seem to require significantly less manual work and boilerplate to generalise over a given datastructure - I'm not entirely sure about how powerful the two are, seeing as I'm not familiar with the visitor pattern.
blueberry
CC BY-SA 4.0
2023-05-17T00:48:45.980Z
@kaya3 Upon some further research, the visitor pattern is indeed weaker then recursion schemes, as the visitor pattern requires each class that implements it to define a way to access it's members, whereas recursion schemes + a little bit of compiler assistance can do it completely automatically.
blueberry
<p>Recursion schemes are good ways to refactor out recursions <strong>only if</strong> these recursions can be translated into type-theoretic eliminators (e.g. the &quot;foldr&quot; or the (co)algebra in the (co)algebraic data type).</p>
<p>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).</p>
<p>In a compiler, it is very common to have multi-variable recursion, like when writing an expression type-checking function:</p>
<pre><code>check : (Expr, Type) -&gt; Result
check (Lambda ...) (FunTy ...) = ...
check (Tuple ...) (TupleTy ...) = ...
</code></pre>
<p>For these functions, you'll have a hard time translating them into eliminators, which makes recursion schemes difficult to be applied.</p>
<p>For simple functions like counting some references from an AST, it will be <em>very</em> 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.</p>

CC BY-SA 4.0
2023-05-17T14:30:28.667Z
2023-05-17T14:30:28.667Z
ice1000
<p>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 <em>feel</em> 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.</p>
<p>Regardless, I'd like to make the case that recursion schemes can be useful.
Consider the following grammar:</p>
<pre><code>type expr =
| Int of int
| Plus of expr * expr
| Var of string
| Let of string * expr * expr
| Ifz of expr * expr * expr
</code></pre>
<p>Consider a dead code elimination pass that rewrites <code>ifz</code>:</p>
<pre><code>let rec dce e =
  match e with
  | Int _ | Var _ -&gt; e
  | Plus(e1, e2) -&gt; Plus(dce e1, dce e2)
  | Let(x,e1,e2) -&gt; Let(x, dce e1, dce e2)
  | Ifz(Int 0,e1,_e2) -&gt; dce e1
  | Ifz(Int _,_e1,e2) -&gt; dce e2
  | Ifz(c,e1,e2) -&gt; Ifz(dce c,dce e1,dce e2)
</code></pre>
<p>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 <code>dce</code> above are just <code>Ifz(Int 0, _, _)</code> and <code>Ifz(Int _, _, _)</code>.</p>
<p>We can define one of many recursion schemes to factor out the recursion:</p>
<pre><code>let map f e =
  match e with
  | Int _ | Var _ -&gt; e
  | Plus(e1,e2) -&gt; Plus(f e1, f e2)
  | Let(x,e1,e2) -&gt; Let(x, f e1, f e2)
  | Ifz(c,e1,e2) -&gt; Ifz(c, e1, e2)
</code></pre>
<p>With this, we car re-define our <code>dce</code> to be much more succinct and, thus, likely more maintainable:</p>
<pre><code>let rec dce e =
  match e with
  | Ifz(Int 0,e1,_e2) -&gt; dce e1
  | Ifz(Int _,_e1,e2) -&gt; dce e2
  | _ -&gt; map dce e
</code></pre>
<p>This simple example shows that recursion schemes can be a viable coding pattern when implementing a compiler.</p>

CC BY-SA 4.0
2023-05-17T06:46:59.833Z
2023-05-17T06:46:59.833Z
NaCl
<p>I'm not that familiar with Recursion Schemes (though I had read about a half of &quot;Bananas, Lenses and Barbed Wire&quot; paper quite some years ago), but I'd say they're mostly useful to work with <strong>tree-like</strong> data structures.</p>
<p>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.</p>

CC BY-SA 4.0
2023-05-17T08:33:19.297Z
2023-05-17T14:01:14.243Z
2023-05-17T14:01:14.243Z
Alex Chichigin
# Utilising recursion schemes when implementing compilers
Posted by: username_0 on 2023-05-16
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.
**Tags:** implementation compilers interpreters
> **Comments:**
> **username_0**: @kaya3 I haven't personally heard of the visitor pattern, but it seems to be a less powerful version of recursion schemes - https://blog.sumtypeofway.com/posts/introduction-to-recursion-schemes.html serves as a good introduction if you know Haskell to at least a somewhat decent level. I say "less powerful" as recursion schemes seem to require significantly less manual work and boilerplate to generalise over a given datastructure - I'm not entirely sure about how powerful the two are, seeing as I'm not familiar with the visitor pattern.  
> **username_0**: @kaya3 Upon some further research, the visitor pattern is indeed weaker then recursion schemes, as the visitor pattern requires each class that implements it to define a way to access it's members, whereas recursion schemes + a little bit of compiler assistance can do it completely automatically.  
---
## 3 answers
### Answer by username_3 on 2023-05-17. Score: 3 | Accepted answer
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 by username_1 on 2023-05-17. Score: 4
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.
---
### Answer by username_2 on 2023-05-17. Score: 4
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.
---
