Uniform abstract syntax trees
Chris Clark · ACM SIGPLAN Notices · 2000
Simplicity is beautiful.It can also be practical.This column talks about a simple form of Abstract Syntax Trees (AST's).They are simple because every node in the tree has the same structure.Because every node has the same uniform structure, I call them uniform AST nodes. BenefitsWhy would someone want all their AST nodes to have the same structure?One reason is that this makes all the nodes have the same size, shape, and type.That makes them interchangeable and easy to manipulate. InterchangeabilityUniform types allow the nodes to be used interchangeably.Any AST node can be used in place of any other.Now, this may seem like an odd feature.Why would anyone want to replace one node with another?However, the answer is important--to edit the tree.The key reason one might want to use AST nodes with uniform structure is so that those nodes can be easily moved around.With uniform structure the nodes in the tree can be reshaped into a variety of trees easily.By having uniform structure, the nodes do not need to change when moved from one part of the tree to another.This property may be true of other representations, but it is trivially true for uniform AST nodes.