Re: Is C++ really used ?

Bruce Duncan writes:
> 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 visitor pattern is not that popular amongst compiler writers
(perhaps not as popular as it should be). The problem is that you
must duplicate your AST class structure (the book calls the AST
classes ConcreteElement classes) in the functions doing the visiting.
This is pointed out in the design patterns book, and addressed in
consequences 3 (Adding new ConcreteElement classes is hard). For most
visitors, the operations on large subsets of the ConcreteElement
classes is the same. For example most operations treat all binary
operators the same (or group them by associativity or similar
algebraic property). As a compiler writer, I don't want to repeat the
code for each operation over all the binary operators which are
identical.


There are at least two ways to solve this problem.


One way is to have several distinct abstract Visitor classes. The
different abstract Visitor classes allow the AST classes to be
partitioned into different subsets. The normal abstract Visitor class
partitions each ConcreteElement class into a unique function. A
second abstract Visitor class might treat all binary operator
ConcreteClasses as calling the same VisitConcreteClass function (say
VisitBinaryOperator). There is some overhead in having multiple
abstract Visitor classes, but if there are several important visitors
that share the same categorizations it can be worthwhile.


Another alternative, the one I use most often, is to use an array of
function pointers to represent the ConcreteVisitors (the functions
being applied). I initialize each ConcreteElement class with a
pointer to the appropriate array of visitor functions as I am creating
it (a lot like a virtual function table isn't it). Applying the
appropriate visitor functions is simply a matter of iterating over the
AST and executing the function in the appropriate slot. That
technique preserves many of the benefits of the normal Visitor
implementation--in particular, I can group all the functions related
to one visitation together. It also allows me to reuse visitor code
for as many ConcreteClasses (or ConcreteVisitor classes) as desired, I
simply use the same function in each slot.


Finally, if you are using a language with multiple dispatch, the
problem "goes away", you simply define your functions to dispatch on
both the object being applied to (the ConcreteClass) and operation
being performed (the ConcreteVisitor) and define the correct set of
functions for the iteration, with the language hopefully applying the
right rules to minimize code duplication.


By the way, as a compiler writer I often find that I am about equally
likely to define a new AST class (or new subset of AST classes) as I
am a new operation. For example, it is often useful to generate a new
AST class to represent a special case sequence that you have
recognized as part of optimization. In the MIPS based compilers we
used at DEC (acc), we added a whole set of operators to represent
special case operations relating to conditional flow of control
patterns. This was partially done because the Alpha hardware
supported a CMOVE instruction which implemented "if (cond) x=y else
x=z" in one step. However, having once implemented it, it also
improved most other optimizations by allowing us to coallesce basic
blocks (as well as some algebraic optimizations we were able to
perform once we recognized the pattern as an abs, max, or other
special case). In any event, this was a case where, without changing
the language being parsed, we wanted to add new features to our AST
classes. (They weren't actually classes, since the compiler wasn't
OO, but the point is the same. And not being OO, it took several
months to find all the ConcreteVisitors and determine what changes
that needed to be made to them, but that is another story.)


-Chris Clark
--

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