What are the reasons to choose a homogeneous vs. a heterogeneous AST representation for implementing a complex domain-specific programming language?
Just to be very clear about what I'm asking, here is some extra background:
By homogeneous, I mean a tree constructed of nodes which are a single generic type. For example, I think this question is really language independent, but using a C++-like struct for illustration, I'd consider this a minimal homogeneous abstract syntax tree node:
struct Node {
int tag;
void *data;
Node *first_child;
Node *next_sibling;
};
By heterogeneous, I mean a tree constructed of nodes which are multiple individual types (e.g. one for each grammar production). For example, I don't want to assume a particular language, but again using C++-like structs for illustration, I'd consider these types part of a hierarchy used to build a heterogenous abstract syntax tree tree:
struct Node {};
struct Integer_Node : Node {
int value;
};
struct Plus_Node : Node {
Node *right;
Node *left;
};
struct If_Statement : Node {
Node *Condition;
Node *Then_Expression;
Node *Else_Expression;
};
// ... more types, depending on the language ...
Over the years, I've implemented several small, special-purpose compilers, usually in a very ad-hoc way. I've never used much of a real "AST" because usually syntax-direct translation has been good enough.
Now I'm in the process of designing and implemented a new, much more complex language, where I will be building an AST and then walking over it with multiple passes for verification, semantic analysis, and so forth.
For example, it seems that using a homogeneous scheme reduces the amount of code up front, but I wonder if a heterogeneous scheme will pay off better in the long run for reasons I'm not considering. On the other hand, the heterogeneous scheme seems like it allows benefiting from the compiler's static type checking, virtual method dispatch, etc, but I wonder if any of that is really very useful when developing semantic passes and so forth.
Basically, I'm hoping to gain some insight from those who may have some real experience here. I've read many compiler books and have a moderate amount of basic compiler-writing experience, but I haven't seen this particular dichotomy addressed in any literature I can get my hands on.