Flattening the AST

April 11, 2025

QLogo, Code, Compiler

LLVM, Compiler, Logo Programming, Tree-Walking Interpreter

Limitations of the Tree-Walk Interpreter #

QLogo was implemented as a tree-walk interpreter. What this means is that the execution happens by traversing the AST nodes and performing the corresponding operations for each node. For example, this code:

PRINT 2 + 3 * FN :A

Generates this tree:

AST Print Example

So, using a tree-walk interpreter in this example would generate three nested subroutine calls from the call to PRINT to the call to FN :A. The nested subroutine calls can get computationally expensive.

To solve this issue I started working on flattening the AST. I quickly realized that I was essentially designing a new state machine language, which would require significant effort. This led me to explore compiling to LLVM-IR instead.

Compiling to LLVM-IR still requires substantial work, but I believe it’s more manageable than designing and implementing a new state machine language. As an added benefit, LLVM-IR gets compiled to native machine code, which should provide significant performance improvements!