Efficient ASTs via Array Systems

General
1

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.

1 Like