Language Implementation Patterns

Pattern 12

Embedded Heterogeneous Tree Walker

Purpose

This pattern walks heterogeneous ASTs using a set of recursive methods defined within the node class definitions.

Discussion

As object-oriented programmers, it is natural for us to think about adding tree-walking methods to node definitions. For each task, we’d add a different set of recursive methods. For example, to print trees back to text, we could define an abstract print method in the root class. To evaluate expressions, we could add an abstract eval method to the abstract expression class.

This is the easiest tree-walking pattern to understand, but, ultimately, this approach doesn’t scale well. Because it distributes tree-walking code across all node definitions, it works best when there ...