This is a quick note building off of Array Systems - #4 by owenlynch.
Suppose you have an AST like
data Term = Plus Term Term
| Minus Term
| Const Int
This can be expressed by an array system with three objects: Plus
, Minus
, and Const
, and then morphisms
plus_lhs : Plus -> (Plus + Minus + Const)
plus_rhs : Plus -> (Plus + Minus + Const)
minus_val : Minus -> (Plus + Minus + Const)
const_val : Const -> Int
This is a more efficient way of storing an AST than allocating syntax nodes on a heap and also is better for cache. In fact, there are high-performance compilers, for instance the zig compiler, which are built around this technique.