A major problem for writing extensible software arises when
recursively defined datatypes and operations on these types have to be
extended simultaneously without modifying existing code. This paper
introduces extensible algebraic datatypes with defaults which promote
a simple programming pattern to solve this well known problem. We show
that it is also possible to encode extensible algebraic datatypes in
an object-oriented language, using a new design pattern for extensible
visitors. Our technique has been successfully applied in the
implementation of an extensible Java compiler. It allows for the reuse
of existing components in compiler extensions without the need for any
adaptations.
