Pattern 12Embedded 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 ...

Get Language Implementation Patterns now with the O’Reilly learning platform.

O’Reilly members experience books, live events, courses curated by job role, and more from O’Reilly and nearly 200 top publishers.