Re: Is C++ really used ?

Kevin Jacobs <jacobs@darwin.cwru.edu> writes:
> > In Andrew Appel's case, his "Modern Compiler Implementation in Java"
> > hardly uses any object oriented design features in the compiler
> > implementation. In fact he recommends in chapter 1 that all
> > programs be written in as close to pure functional style as
> > possible. I can only assume that his ML bias is showing through;
> > after all New Jersey ML is his primary compiler research platform.


Daniel Wang wrote:
> He also takes some pain to explain in Chapter 4 why OO features don't
> work well in compiler frameworks. The basic argument being that in a
> compiler the objects you deal with are fixed. (IR or AST nodes) The
> computations you want to preform on them aren't. i.e. various data
> flow analysis.


One way I've seen of addressing this issue within an OO framework is
in the book, "Design Patterns", by Gamma, Helm, Johnson, and Vlissides
(Addison-Wesley, 1995). Their section on the Visitor pattern actually
uses a compiler as a main example.


The basic idea is that the AST nodes are defined as a simple class
hierarchy, with each kind of node having a general Accept() method
associated with it as well as the usual constructors, destructors,
accessors, etc. These Accept() methods are passed a visitor object
which is used to dispatch to the appropriate method in whatever the
given visitor object is. Essentially, it is just a double dispatching
scheme, but it allows the many different types of "computations" on
the AST nodes to be kept in their own separate classes without
"polluting" the fixed AST node class hierarchy.


So, for example, each pass of the compiler can be defined as its own
Visitor class. You have a TypeCheck visitor, an Optimize visitor, a
CodeGen visitor, etc. They are all cleanly separated from each other
as well as the AST class hierarchy itself. Each new visitor class is
just derived from an abstract base Visitor class with fixed methods
corresponding to the AST Node classes.


> Therefore you should structure your code so that it is easy to add new
> computations on the objects. If your code in a traditonal OO style
> where each AST/IR object has a method for each analysis you have to
> spread the implementation of your analysis across several objects, and
> every time you change your analysis then you have to make globabl
> changes to your code base. [...]


This is exactly what the Visitor scheme "fixes". Once you have the
AST node class hierarchy well defined and fairly stable it is possible
to have different people work on different passes (visits) on the AST
without interefering with each other. And if you decide to later add
new "computations", such as an extra Optimize phase or a
PrettyPrinter, you don't have to touch the existing code base, you
just derive new visitors for them.


We are actually using this Visitor scheme on a compiler I am currently
developing (in C++). We wanted to use OO for the AST structures and
the Visitor scheme provides a way to avoid the distribution of the
implementation of the different passes over all the AST classes. We
have, for example, two different code generators that different people
are working on, and we may add more in the future. So it is very
important that we don't have to necessarily always go back and modify
all the existing AST code base in order to add or remove different AST
passes such as code generation.


-Bruce Duncan (bduncan@tiac.net)
--

Return to the comp.compilers page.
Search the comp.compilers archives again.