Do I violate the Single Responsibility Principle with my multi-purpose AST Class?

Question

I am writing a compiler, for which I devised a rather classic architecture: it's composed of sequential passes piped together, starting with a lexer and a parser, continuing with a macro processor, then a semantic analysis/type checker pass, and finally an intermediate code generator (and maybe IR optimizer that will come later).

My current approach is the following. The parser is building an AST, where each type of AST node inherits from an "AST" base class. I plan that virtual functions of the AST will implement the functionality of subsequent passes. To provide a simplified example:

• macroExpand() finds, evaluates and substitutes all the macros in the AST, recursively;
• typeCheck() performs type checking, type inference and general semantic analysis/error checking on the now-desugared tree, completing each node with type annotations (which are implemented as member variables);
• codeGen(), finally, generates some kind of IR from the annotated AST.

However, I'm afraid that having all this functionality in one single class violates the single-responsibility principle.

I reckon that macro expansion especially does not fit in: I was thinking about integrating semantic analysis and code generation into just one set of functions instead of separating them, simply because I don't think I need to traverse the entire tree twice, and I would have to look at the types at codegen time anyway, even if I've pre-inferred and pre-checked them previously.

But even with this structural change, there are still at least two completely different sets of methods on my AST classes. I don't yet see any particular reason why this in itself would be bad in my specific case, but I'm pretty sure the single responsibility principle was discovered for a good reason.

One way to remedy (?) this issue would be to use the visitor pattern and write separate visitor class hierarchies for the AST for each purpose (macro expansion, semantic analysis and/or code generation). But I really don't feel like doing so. (In all honesty, I really dislike the idea.) So far it only seems to introduce unnecessary complexity and burden (by means of forcing me to maintain parallel class hierarchies).

Currently, I'm writing this compiler in C++, but I'm pretty sure that if I were using a language that permitted after-the-fact modification and augmentation of classes (e.g. Objective-C categories), I would surely make use of this feature of the language and I would just decorate my base AST classes with the necessary set of methods, independently of the "core" interface and implementation of said classes.

I could sort of simulate that in C++ by putting all the method declarations in one header file, but writing the implementation of each category of functions in different implementation files. This, however, contradicts the usual "one class, one file" practice.

To sum up, my question is: is my current approach of giving two or three different functionality to one class really bad?

• If so, are any of my suggested fixes considered to be good practice, or…

• If it isn't, can you suggest something better?

Answer 1

You're bumping up against a classic problem in programming language theory, the expression problem. It exposes a weakness of both classic object-oriented design (that it's hard to add operations to a data structure with multiple subtypes) and algebraic data types (that it's hard to add new type cases to an adt when there are multiple operations defined on it).

There are various solutions; the visitor pattern is certainly a common one, but in my opinion object-oriented pattern matching is probably the nicest - there's an implementation for c++ here.

Answer 2

Yes, that's a terrible, terrible plan. Those are completely different things. Violating SRP is just the beginning of your problem. Other problems are things like not being able to offer parse-only support for tooling, for example.

A semantic analyser should perform a translation from an AST to a semantic graph. The AST should not be mutated, nor should it ever hold any semantic information. The AST should never hold any code generation information. The AST should never, ever, do anything but hold syntax.

The issue of parallel class hierarchies just doesn't come up in reality because all of these trees and graphs do completely different things with completely different representations and implementations. If your semantic tree closely parallels your syntax tree, you're probably building either a very basic interpreter or doing it very wrong.