Health Articles

 

Independently extensible solutions to the expression problem

Independently Extensible Solutions to the Expression Problem Matthias Zenger, Martin Odersky École Polytechnique Fédérale de Lausanne 1015 Lausanne, Switzerland Technical Report IC/2004/33 challenge is now to find an implementation techniquewhich satisfies the following list of requirements: The expression problem is fundamental for the develop-ment of extensible software. Many (partial) solutions to • Extensibility in both dimensions: It should be possible this important problem have been proposed in the past.
to add new data variants and adapt existing opera- None of these approaches solves the problem of using tions accordingly. Furthermore, it should be possible different, independent extensions jointly. This paper pro- to introduce new processors.
poses solutions to the expression problem that make it • Strong static type safety: It should be impossible to possible to combine independent extensions in a flexible, apply a processor to a data variant which it cannot modular, and type-safe way. The solutions, formulated in the programming language Scala, are affected with onlya small implementation overhead and are easy to imple- • No modification or duplication: Existing code should ment by hand.
neither be modified nor duplicated.
• Separate compilation: Compiling datatype exten- The Expression Problem sions or adding new processors should not encom-pass re-type-checking the original datatype or exist- Since software evolves over time, it is essential for soft- ing processors.
ware systems to be extensible. But the development ofextensible software poses many design and implemen- We add to this list the following criterion: tation problems, especially, if extensions cannot be an- • Independent extensibility: It should be possible ticipated. The expression problem is probably the most to combine independently developed extensions so fundamental one among these problems. It arises when that they can be used jointly recursively defined datatypes and operations on thesetypes have to be extended simultaneously. The term ex- Implementation techniques which meet the last criterion pression problem was originally coined by Phil Wadler in allow systems to be extended in a non-linear fashion.
a post on the Java-Genericity mailing list in which he Such techniques typically allow programmers to consol- also proposed a solution written in an extended version idate independent extensions in a single compound ex- of Generic Java Only later it appeared that Wadler's tension as illustrated by Figure By contrast, without solution could not be typed.
support for independent extensibility, parallel extensions For this paper, we paraphrase the problem in the fol- diverge, even if they are completely orthogonal This lowing way: Suppose we have a datatype which is defined makes a joint use of different extensions in a single sys- by a set of cases and we have processors which operate tem impossible.
on this datatype. There are primarily two directions along This paper presents two families of new solutions to which we can extend such a system: the expression problem. One family is based on object-oriented decomposition while the other is based on func- • The extension of the datatype with new data vari- tional decomposition using the visitor pattern. In its orig- inal form, each of these decomposition techniques allows • The addition of new processors.
extensibility only in one direction (data or operations), yetdisallows extensibility in the other. The solutions pre- We require that processors handle only a finite number sented here achieve independent extensibility of data and of data variants and thus do not provide defaults which operation extensions. They are sufficiently simple and could handle arbitrary cases of future extensions. The concise to be immediately usable by programmers.

Partial Solutions The expression problem has been intensively studied inthe literature. However, none of the proposed solutionssatisfies all the requirements stated in Section This sec- Extension 1 + 2 tion gives an overview over some of the most importantsolutions proposed in the past.
In object-oriented lan- guages, the Interpreter design pattern can be usedto implement datatypes in an extensible fashion. Here, Figure 1: Combination of independent extensions.
a datatype would be implemented by an abstract super-class which specifies the signature of methods that imple- Our solutions are expressed in the programming lan- ment the various processors. Concrete subclasses rep- guage Scala Scala is a strongly statically typed resent the data variants and implement the processors.
programming language which fuses object-oriented and This approach makes it easy to add new data variants functional programming concepts.
For instance, (SML- simply by defining new subclasses, but adding new pro- style) module systems are expressed in a purely object- cessors involves modifications of the abstract superclass oriented way by identifying modules with objects, func- as well as all concrete subclasses.
tors with classes, and signatures with interfaces. It fol-lows from this identification that objects in Scala can With the Visitor design pat- contain types as members.
Furthermore, these type tern it is possible to address the problem in a more members can be either abstract or concrete. The path- functional fashion. This pattern allows one to separate dependent types of the νObj calculus give a type the- the representation of data from functionality operating oretic foundation for languages like Scala where types on such data.
Processors are encapsulated in Visitor can be members of objects.
objects which provide for every data variant a method In module systems, abstract type members are pri- that handles the particular case. This approach makes marily used for information hiding — they allow one to it straightforward to write new processors, but adding abstract from concrete implementations. In this paper new data variants requires that all existing processors are they are used as a means of composition. We will see modified to include methods that handle the new cases.
that each decomposition technique uses an abstract typemember to keep the system open for future extensions in Krishnamurti, Felleisen, and Fried- the "dual" dimension (i.e. the dimension in which exten- man propose the Extensible Visitor pattern a slightly sions are normally not possible).
modified variant of the Visitor design pattern which Two other type-systematic constructs explored in makes it possible to add both new data variants and new νObj and implemented in Scala also play important roles processors. Unfortunately, this approach is based on type in our solutions. Mixin composition allows to merge in- casts which circumvent the type system and therefore Explicitly typed self references make extensions unsafe. In this pattern, all existing visi- overcome a problem in the visitor-based solutions which tor classes have to be subclassed whenever a new variant made Wadler's original proposals untypable.
class is added. Otherwise a runtime error will appear as Scala has been designed to interact smoothly with soon as an old visitor is applied to a new variant.
Java or .NET host environments. All solutions in thispaper compile as given with the current Scala compilerand can be executed on a Java VM, version JDK 1.4 or Extensible visitors with defaults Zenger and Odersky refine the Extensible Visitor pattern into a programming The rest of the paper is organized as follows. Section protocol in which datatype extensions do not automati- analyzes previous work on the expression problem based cally entail adaptations of all existing processors and vice on the criteria mentioned initially. Section discusses an versa Technically, extensibility of data and func- independently extensible solution to the expression prob- tionality is achieved by adding default cases to type and lem formulated in an object-oriented programming style.
visitor definitions; these default cases handle all possi- An alternative approach based on a functional decompo- ble future extensions. While this approach allows pro- sition is presented in Section Section discusses the grammers to reuse existing visitors for new data variants implemenation of binary methods. Section concludes and therefore does not suffer from the runtime errors with an analysis of the language features that are required described above, it is still not fully satisfactory, since it by the discussed approaches.
allows to apply visitors to data variants for which the vis-itor was not designed for originally.
to use the schema in practice. His operation-centered so- multiple dispatch via multi-methods provide good sup- lution relies on a clever trick to pass a visitor object as port for extensibility with default cases.
argument to itself in order to overcome the typing prob- is a Java-based programming language that allows lems encountered by Wadler. However, this is not exactly programmers to add new methods to existing classes an obvious technique for most programmers and it be- without modifying existing code and without breaking comes progressively more expensive in the case of several encapsulation properties. While new, externally specified mutually recursive visitor classes. An interesting varia- methods require default cases, internal methods (i.e.
tion of Torgersen's solution uses Java's wildcards to methods that are defined inside of the corresponding achieve object-level extensibility, i.e. reusability of actual class) are not subject to this restriction. A precise analy- expression objects across extensions.
sis of the constraints that are required to enable modulartypechecking for such internal and external methodsis given by Millstein, Bleckner, and Chambers, in their work on EML Opposed to all the approaches men-tioned before, EML makes it possible to use independent This section presents a solution of the expression prob- extensions jointly.
lem in Scala using an object-oriented approach. Fol-lowing Wadler's original problem statement, we evolve asimple datatype for representing arithmetic expressions Generic visitors Palsberg and Jay's Generic Visitors, also together with operations on this type by incrementally called Walkabouts, offer a way to completely decou- adding new datatype variants and new operations.
ple data representations from function definitions Therefore, walkabouts are very flexible to use and to ex-tend.
But since they rely on reflective capabilities of the underlying system, this approach lacks static type- We start with a single data variant Num for representing safety and is subject to substantial runtime penalties.
integer numbers and an operation eval for evaluating ex- Grothoff recently showed that the performance decrease pressions. An object-oriented implementation is given in can be avoided by using runtime code generation tech- the following program: trait Base {
Self types Recently, Bruce presented a way to make the type exp <: Exp;
trait Exp {
Interpreter design pattern extensible His approach def eval: int
is based on the existence of a new ThisType type con-
struct, referring to the public interface of the self ref- class Num(v: int) extends Exp {
erence this inside of a class. Like this, the meaning
val value = v;
of ThisType changes when a method whose signature
def eval = value
refers to ThisType is inherited in a subclass. This feature
makes it possible to keep the type of the data variants open for future extensions. A severe limitation of this ap- The trait Exp lists the signature of all available operations proach is that for type-safety reasons, the exact runtime and thus defines an interface for all data variants. Traits type of the receiver of a method referring to ThisType
has to be known at compile-time. A further limitation is Scala are very similar to interfaces in Java; the main difference is that traits may contain concrete implemen- that ThisType cannot be used to make the visitor design
tations for some methods.
pattern extensible.
The only data variant is implemented by class Num.
This class extends Exp with a method value which re- Generic classes Solutions to the expression problem turns the corresponding integer value. It also defines a which rely on generic classes and F-bounds have recently concrete implementation for operation eval.
been proposed by Torgersen Similar to our ap- To keep the set of operations on expressions open for proach, Torgersen proposes two kinds of solutions: one future extensions, we abstract over the expression type data-centered solution based on an object-oriented de- and use an abstract type exp whenever we want to refer composition, and a operation-centered solution based on to expression objects. An abstract type definition intro- a functional decomposition using the visitor design pat- duces a new named type whose concrete identity is un- tern. Torgersen's solutions satisfy our first four require- known; type bounds may be used to narrow possible con- ments stated in Section but do not address the problem crete incarnations of this type. This mechanism is used of independent extensibility. Another drawback is the in the program above to declare that exp is a subtype of relatively extensive and complex programming protocol our preliminary expression interface Exp.
the programmer has to observe. For instance, his data- Since we want to be able to refer to our three abstrac- centered solution requires a fixed point operation for all tions exp, Exp, and Num as a whole, we wrap them into a classes at each instantiation, which makes it cumbersome top-level trait Base. Base has to be subclassed in order to either extend it, or to use it for a concrete application.
mixin class composition with trait BaseNeg only incorpo- The latter is illustrated in the following program: rates the new class members and omits the ones that getinherited from BaseNeg's superclass Base.
object BaseTest extends Base with Application {
Mixin class composition in Scala is similar to both type exp = Exp;
the mixin construct of Bracha and to the trait com- val e: exp = new Num(7);
position mechanism of Schärli, Ducasse, Nierstrasz, and As opposed to multiple inheritance, base classes are inherited only once. In a mixin composition This program defines a top-level singleton object whose A with B with C, class A acts as actual superclass of
class is an extension of trait Base. The type alias defi- mixins B and C, replacing the declared superclasses of B nition type exp = Exp overrides the corresponding ab-
and C. To maintain type soundness, A must be a subclass stract type definition in the superclass Base, turning the of the declared superclasses of B and C. A super refer-
abstract type exp into a concrete one (whose identity is ence in either B or C will refer to a member of class A. As The last two lines in the code above instantiate is the case for trait composition, Scala's mixin composi- the Num class and invoke the eval method. The clause tion is commutative in the mixins — A with B with C is
with Application in the header of the object definition
equivalent to A with C with B.
is a mixin class composition which, in this case, adds a A class inheriting from A with B with C inherits
main method to BaseTest to make it executable. We will members from all three base classes. Concrete members explain mixin class compositions in the next subsection.
in either base class replace abstract members with thesame name in other base classes. Concrete members ofthe mixin classes B and C always replace members with the same name in the superclass A.
Linear Extensions The object-oriented decomposition member m is implemented in both B and C, then the inher- scheme makes it easy to create new data variants. In iting class has to resolve the conflict by giving an explicit the following program we present two extensions of trait overriding definition of m.
Base. BasePlus extends our system by adding a new Unlike the original mixin and trait proposals, Scala Plus variant, BaseNeg defines a new Neg variant. Note does not have different syntactic constructs for classes that in general, we type expressions using the abstract on the one hand and mixins or traits on the other hand.
type exp instead of the type defined by the concrete class Every class can be inherited as either superclass or mixin Traits in Scala are simply special classes without state or constructors.
This distinction is nec- trait BasePlus extends Base {
essary because of the principle that base classes are in- class Plus(l: exp, r: exp) extends Exp {
herited only once.
If both B and C have a base class val left = l; val right = r;
T, then the two instances are unified in the composition def eval = left.eval + right.eval
A with B with C. This presents no problem as long as
T is a trait, i.e. it is stateless and does not have an explicit trait BaseNeg extends Base {
constructor. For non-trait base classes T, the above mixin class Neg(t: exp) extends Exp {
composition is statically illegal. The idea to have a com- val term = t;
mon syntactic construct for classes and mixins/traits is def eval = - term.eval;
Operation Extensions Adding new operations requires more work than adding Combining Independent Extensions new data variants. For instance, here is how we can add a ploy the two extensions independently of each other; but show method to expressions of our base language.
Scala also allows us to merge the two independent exten-sions into a single compound extension. This is done us- trait Show extends Base {
ing a mixin class composition mechanism which includes type exp <: Exp;
the member definitions of one class into another class.
trait Exp extends super.Exp {
The following line will create a system with both Plus def show: String;
and Neg data variants: class Num(v: int) extends super.Num(v) with Exp {
def show = value.toString();
trait BasePlusNeg extends BasePlus with BaseNeg;
Trait BasePlusNeg extends BasePlus and incorpo- rates all the member definitions of trait BaseNeg. Thus, it In this example, we first have to create an extended trait inherits all members from trait BasePlus and all the new Exp which specifies the new signature of all operations members defined in trait BaseNeg. Note that the mem- (the old ones get inherited from the old Exp trait, the new bers defined in trait Base are not inherited twice. The ones are specified explicitly), then we have to subclass all ments. We now show what is involved when writing tree data variants and include implementations of the new op- transformer operations, which also return tree elements erations in the subclasses. Furthermore, we have to nar- as results. As an example, let's add a method dble to the row the bound of our abstract type exp to our newly de- expression type defined in trait BasePlusNeg. Method fined Exp trait. Only this step makes the new operations dble is supposed to return a new expression which eval- accessible to clients since they type expressions with the uates to a number which is twice the value of the original abstract type exp.
Note that the newly defined Exp and Num classes Instead of first introducing the new operation in the shadow the former definitions of these classes in super- base system (which would also be possible), we choose to class Base. The former definitions are still accessible in specify it directly in an extension. The following program the context of trait Show via the super keyword.
illustrates the steps required to add method dble to the Shadowing vs. overriding constitutes one of the key expression type defined in trait BasePlusNeg.
differences between classes in Scala and virtual classesWith virtual classes, class members override equally trait DblePlusNeg extends BasePlusNeg {
type exp <: Exp;
named class members of a base class, whereas in Scala trait Exp extends super.Exp {
the two class members exist side by side (similar to what def dble: exp;
happens to object fields in Java or C#). The overriding behavior of virtual classes is potentially quite powerful, def Num(v: int): exp;
but poses type safety problems due to covariant over- def Plus(l: exp, r: exp): exp;
riding. There exist proposals to address the type safety def Neg(t: exp): exp;
problems of virtual classes but the resulting type class Num(v: int) extends super.Num(v) with Exp {
systems tend to be complicated and have not yet been ex- def dble = Num(v * 2);
plored fully.
}
class Plus(l: exp, r: exp)
extends super.Plus(l, r) with Exp {
Linear extensions We can adapt our previously defined def dble = Plus(left.dble, right.dble);
systems so that even data variants defined in extensions of Base support the show method. Again, this is done class Neg(t: exp) extends super.Neg(t) with Exp {
with a mixin class composition. This time we mix the def dble = Neg(t.dble);
new Show trait into extensions of existing traits such as BasePlusNeg of Section Since all our data variantshave to support the new show method, we have to create Note that we cannot simply invoke the constructors of subclasses of the inherited data variants which support the various expression classes in the bodies of the dble the new Exp trait.
methods. This is because method dble returns a value oftype exp, the type representing extensible expressions, trait ShowPlusNeg extends BasePlusNeg with Show {
class Plus(l: exp, r: exp) extends super.Plus(l, r)
but all data variant types like Plus and Num extend only with Exp {
trait Exp which is a supertype of exp. We can establish the def show = left.show + "+" + right.show;
necessary relationship between exp and Exp only at the stage when we turn the abstract type into a concrete one class Neg(t: exp) extends super.Neg(t) with Exp {
(with the type alias definition type exp = Exp). Only
def show = "-(" + term.show + ")";
then, Num is also a subtype of exp. Since the implementa- tion of dble requires the creation of new expressions of type exp, we make use of abstract factory methods, one object ShowPlusNegTest extends ShowPlusNeg
for each data variant. The concrete factory methods are with Application {
type exp = Exp;
implemented at the point where the abstract type exp is val e: exp = new Neg(
resolved. For instance, they can be implemented at the new Plus(new Num(7), new Num(6)))
point where we use the new dble method: Console.println(e.show + " = " + e.eval); object DblePlusNegTest extends DblePlusNeg
with Application {
The previous program also illustrates how to use the type exp = Exp;
new system. The singleton object ShowPlusNegTest first def Num(v: int): exp = new Num(v);
closes the (still open) definition of type exp, then it in- def Plus(l: exp, r: exp): exp = new Plus(l, r);
def Neg(t: exp): exp = new Neg(t);
stantiates an expression involving all different kinds of val e: exp = Plus(Neg(Plus(Num(1), Num(2))),
data variants. Finally, both the eval and the show method are invoked.
Tree transformer extensions So far, all our operations All examples presented here are type-safe, in the sense took elements of the tree only as their receiver argu- that it is impossible to mix data from different languages, combining independent extensions on demand.
nor to invoke an operation on a data object which does combining extensions with new data variants is relatively not understand it. For instance, here is what happens simple to implement, combining extensions with differ- when we try to compile a program which violates both ent new operations is technically more difficult.
object erroneous {
Functional Decomposition val t1 = new ShowPlusNegTest.Num(1);
val t2 = new DblePlusNegTest.Neg(t1);
For applications where the data type implementations are fixed and new operations are added frequently, it is of- // type mismatch; ten recommended to use the Visitor design pattern. This // required: DblePlusNegTest.Exp pattern physically decouples operations from data repre-sentations. It provides a double dispatch mechanism to val t3 = t1.dble;
apply externally defined operations to data objects. In this section we will show how to use a techniques similar // value dble is not a member of to the ones presented in the previous section to imple- ment this pattern in an extensible fashion, allowing both data and operation extensions and combinations thereof.
Combining independent extensions how to combine the two traits ShowPlusNeg and The following program presents a framework for a DblePlusNeg to obtain a system which provides expres- visitor-based implementation of expressions supporting sions with both a double and a show method. In order to an eval operation. In this framework, we use the type do this, we have to perform a deep mixin composition of defined by trait Exp directly for representing expressions.
the two traits; i.e. we have to combine the two top-level Concrete expression classes like Num implement the Exp traits ShowPlusNeg and DblePlusNeg as well as the traits trait which defines a single method accept. This method and classes defined inside of these two top-level traits.
allows programmers to apply a visitor object to the ex- Since Scala does not provide a language mechanism for pression. A visitor object is an encoding for an operation.
performing such a deep mixin composition operation, we It provides methods of the form visit. for the vari- have to do this by hand, as the following program demon- ous expression classes. The accept method of a concrete expression class simply selects its corresponding visitmethod of the given visitor object and applies it to its trait ShowDblePlusNeg extends ShowPlusNeg
encapsulated data.
with DblePlusNeg {
type exp <: Exp;
trait Base {
trait Exp extends super[ShowPlusNeg].Exp
trait Exp {
def accept(v: visitor): unit;
class Num(v: int)
class Num(value: int) extends Exp {
def accept(v: visitor): unit = v.visitNum(value);
with Exp;
class Plus(l: exp, r: exp)
type visitor <: Visitor;
extends super[ShowPlusNeg].Plus(l, r)
trait Visitor {
with super[DblePlusNeg].Plus(l, r)
def visitNum(value: int): unit;
with Exp;
class Neg(t: exp)
class Eval: visitor extends Visitor {
var result: int = _;
def apply(t: Exp): int = { t.accept(this); result }
with Exp;
def visitNum(value: int): unit = {
For merging the two Exp traits defined in ShowPlusNeg and DblePlusNeg, we extend one of the two traits and mix the other trait definition in. We use the syntactic
form super[.] to specify to which concrete Exp trait
To keep the set of expression classes open, we have to ab- we are actually referring. The same technique is used for stract over the concrete visitor type. We do this with the the other three classes Num, Plus, and Neg.
abstract type visitor. Concrete implementations of the The previous examples show that the object-oriented visitor interface such as class Eval typically implement approach described in this section supports both data its bound Visitor.
and operation extensions and provides good support for Class Eval uses a variable result for returning val- The top-level trait BasePlus also defines a new Eval class ues. This is necessary since the visitNum method has implementing the refined Visitor trait which can also as result type unit, and therefore cannot return a non- handle Plus objects. Note that we have to annotate the trivial result. It would seem more natural to return a re- new Eval class again with an explicit type for its self ref- sult directly from the visit methods. Then the Visitor erence. This is required because for type-safety reasons class would have to be parameterized with the type of class extensions have to redefine self types covariantly.
the results.
However, in that case the abstract type In the same way, we can now create another extension name visitor would be bounded by the type construc- BaseNeg which adds support for negations.
tor Visitor. Such abstract type constructors have notyet been studied in detail in the context of νObj and con- trait BaseNeg extends Base {
type visitor <: Visitor;
sequently have not been implemented in Scala.
trait Visitor extends super.Visitor {
To facilitate the processing of result values in clients, def visitNeg(term: Exp): unit;
the Eval class provides instead an apply method which returns the most recent result value. The body of this class Neg(term: Exp) extends Exp {
method exhibits a technical problem.
def accept(visitor: v): unit =
t.accept(this), but the type Eval is not a subtype of
the abstract visitor type visitor required by the accept method of expressions. In Scala we can overcome this class Eval: visitor extends super.Eval with Visitor {
problem by declaring the type of this explicitly. Such
def visitNeg(term: Exp): unit = {
result = -apply(term); an explicitly typed self reference is expressed in the pro- gram above with the statement :visitor directly follow- ing the name of class Eval. The type assigned to this is
arbitrary; however, classes with explicitly typed self ref-
erences can only be instantiated if the type defined by
the class is a subtype of the type assigned to this. Since
Combining independent extensions Eval is not a subtype of visitor we cannot create in- the two independent extensions BasePlus and BaseNeg stances of Eval in the context of the top-level trait Base.
such that we have a system providing both, addition and For creating new instances of Eval we would have to re- negation expressions. In the previous object-oriented de- sort to factory methods.
composition scheme such a combination was achieved Note that explicitly typed self references are different using a simple mixin composition. In the functional ap- from Bruce's mytype construct even though the two proach, a deep mixin composition is required to achieve techniques address some of the same problems. Unlike mytype, explicitly typed self references do not change co-variantly with inheritance. Therefore, they are a good fit trait BasePlusNeg extends BasePlus with BaseNeg {
with standard subtyping, whereas mytype is a good fit type visitor <: Visitor;
trait Visitor extends super.Visitor
class Eval: visitor extends super.Eval
Linear extensions New data variants are added to the system by including new visit methods into the Visitortrait and by overriding the abstract type visitor with the The program extends the previous extensions BasePlus extended Visitor trait. The next program extends Base and mixes in the other extension BaseNeg. All concrete by adding a new Plus expression class.
visitor implementations such as Eval are also mergedby mixin composing their implementations in the two trait BasePlus extends Base {
base classes. The type visitor <: Visitor;
Scala type system requires that trait Visitor extends super.Visitor {
abstract types such as visitor are refined covariantly.
def visitPlus(left: Exp, right: Exp): unit;
Since the bounds of visitor in the two previous exten- sions are not compatible, we have to explicitly override class Plus(left: Exp, right: Exp) extends Exp {
the abstract type definition of visitor such that the new def accept(v: visitor): unit =
bound is a subtype of both old bounds. Above, this is done by creating a new Visitor trait that merges the two class Eval: visitor extends super.Eval with Visitor {
The following implementation shows how to use a lan- def visitPlus(l: Exp, r: Exp): unit = {
guage. As usual, the scheme is the same for base language result = apply(l) + apply(r); and extensions. In every case, we close the operations un- der consideration by fixing the visitor type with a type object BasePlusNegTest extends BasePlusNeg {
trait ShowDblePlusNeg extends DblePlusNeg
type visitor = Visitor;
val op: visitor = new Eval;
Console.println(op.apply(
This example illustrates a duality between functional and new Plus(new Num(1), new Neg(new Num(2)))));
object-oriented approaches when it comes to combining independent extensions. The functional decompositionapproach requires a deep mixin composition for mergingdata extensions but only a shallow mixin composition for Operation Extensions merging operation extensions. For the object-oriented ap-proach, the situation is reversed; data extensions can be Adding new operations to a visitor-based system is merged using shallow mixin composition whereas opera- straightforward, since new operations are implemented tion extensions require deep mixin composition.
simply with new classes implementing the visitor inter- Hence, the fundamental strengths and weaknesses of face. The following code shows how to add a new oper- both decomposition approaches still show up in our set- ation Dble to the BasePlusNeg system. The Dble opera- ting, albeit in a milder form. A merge of extensions in tion returns an expression representing the double value a given dimension which was impossible before now be- of a given expression.
comes possible, but at a higher cost than a merge in the trait DblePlusNeg extends BasePlusNeg {
other dimension.
class Dble: visitor extends Visitor {
var result: Exp = _;
def apply(t: Exp): Exp = {
The previous examples discussed operations where the def visitNum(value: int): unit = {
tree appeared as receiver or as method result. We now result = new Num(2 * value)
study binary methods, where trees also appear as a non- receiver arguments of methods. As an example, consider def visitPlus(l: Exp, r: Exp): unit = {
adding a structural equality test eql to the expression result = new Plus(apply(l), apply(r))
x eql y should evaluate to true if x and y are
def visitNeg(term: Exp): unit = {
structurally equal trees. The implementation given here result = new Neg(apply(term))
is based on object-oriented decomposition; the dual im- plementation based on functional decomposition is left as an exercise for the reader. We start with an implemen- tation of the eql operation in the base language.
In a similar fashion we can create a second, independent trait Equals extends Base {
extension ShowPlusNeg which adds an operation for dis- type exp <: Exp;
playing expressions in textual form.
trait Exp extends super.Exp {
def eql(other: exp): boolean;
trait ShowPlusNeg extends BasePlusNeg {
def isNum(v: int) = false;
class Show: visitor extends Visitor {
var result: String = _;
class Num(v: int) extends super.Num(v) with Exp {
def apply(t: Exp): String = {
def eql(other: exp): boolean = other.isNum(v);
override def isNum(v: int) = v == value;
def visitNum(value: int): unit = {
result = value.toString() The idea is to implement eql using double dispatch. A def visitPlus(l: Exp, r: Exp): unit = {
call to eql is forwarded to a test method which is specific result = apply(left) + "+" + apply(right) to the receiver type. For the Num class this test method is isNum(v: int). A default implementation of isNum def visitNeg(term: Exp): unit = {
which always returns false is given in class Exp. This
result = "-(" + apply(term) + ")" implementation is overridden in class Num.
An extension with additional data types requires addi- Combining Independent Extensions We can now imple- tional test methods which are analogous to isNum. Hence, ment a system which supports both operations Dble and we need to use a combination of our schemes for data Show by using a simple shallow mixin class composi- and operation extensions. Here is an extension of class tion involving the two orthogonal independent extensions Equals with Plus and Neg types.
DblePlusNeg and ShowPlusNeg: trait EqualsPlusNeg extends BasePlusNeg with Equals {
class Plus(l: exp, r: exp)
type exp <: Exp;
trait Exp extends super[BasePlusNeg].Exp
with super[ShowPlusNeg].Plus(l, r)
with super[Equals].Exp {
with Exp;
def isPlus(l: exp, r: exp): boolean = false;
class Neg(term: exp)
def isNeg(t: exp): boolean = false;
class Num(v: int) extends super[Equals].Num(v)
with Exp;
with Exp;
class Plus(l: exp, r: exp) extends Exp
with super.Plus(l, r) {
As can be seen from this example, we apply precisely def eql(other: exp): boolean = other.isPlus(l, r);
the deep mixin composition scheme for merging opera- override def isPlus(l: exp, r: exp) =
tion extensions — compare with trait ShowDblePlusNeg (left eql l) && (right eql r) in Section This shows that no special techniques are needed to adapt binary methods to operation extensions.
class Neg(t: exp) extends Exp
We conclude with a main program which uses the with super.Neg(t) {
eql and show methods. Again, no special provisions are def eql(other: exp): boolean = other.isNeg(t);
override def isNeg(t: exp) = term eql t
needed for binary methods.
object EqualsShowPlusNegTest extends EqualsPlusNeg
with Application {
type exp = Exp;
val term1 = new Plus(new Num(1), new Num(2));
isPlus(l: exp, r: exp) and isNeg(t: exp) to class val term2 = new Plus(new Num(1), new Num(2));
Exp. Since the addition of these test methods constitutes val term3 = new Neg(new Num(2));
an operation extension, we need to refine the abstract Console.print(term1.show + "=" + term2.show + "? "); type exp, similar to what was done in Section Console.println(term1 eql term2); Note that Scala allows any binary method to be used Console.print(term1.show + "=" + term3.show + "? "); as an infix operator. An expression such as left eql l Console.println(term1 eql term3); is syntactic sugar for left.eql(l).
Note also that the order of inheritance is reversed in classes Plus and Neg when compared to class Num. Thisis due to the restriction that the superclass A in a mixin composition A with B must be a subclass of the declared
superclass of the mixin B. In our example, Num's super-
We have presented two families of type-safe solutions to class is Num as given in Equals, which is a subclass of the expression problem, which are dual to each other.
class Exp as given in Equals. On the other hand, the su- One family is based on object-oriented decomposition, perclass of Plus is the current definition of Exp, which the other on functional decomposition using the visitor is a subclass of Exp as given in BasePlusNeg. The differ- pattern. Either family makes it easy to extend a system ence in the inheritance order is due to the fact that classes in one dimension — data extensions for object-oriented Num and Plus/Neg themselves come from different base decomposition and operation extensions for functional classes of EqualsPlusNeg. Num comes from class Equals composition. Extensions in the dual dimension are made whereas Plus and Neg come from class BasePlusNeg.
possible by abstracting over a type — the tree type inthe case of object-oriented decomposition and the visi- Operation Extensions tor type in the case of functional decomposition. Exten-sions in the dual dimension require a bit more overhead A desirable property of binary methods is that they adapt than extensions in the primary dimension. In particular, automatically to (operation) extensions.
the merge of independent extensions in the dual dimen- holds in our setting, as is demonstrated by the following sion requires a deep mixin composition as compared to example, which adds the show method to the classes in a shallow mixin composition for a merge in the primary trait EqualsPlusNeg by mixin-composing them with the contents of class ShowPlusNeg from Section This principle applies to several variants of opera- trait EqualsShowPlusNeg extends EqualsPlusNeg
tions: simple operations that access the tree only as the with ShowPlusNeg {
receiver of operation methods, tree transformers that re- type exp <: Exp;
turn trees as results, and binary methods that take trees trait Exp extends super[EqualsPlusNeg].Exp
as additional arguments.
All implementation schemes discussed in this paper class Num(v: int)
are sufficiently simple to be directly usable by program- mers without special support for program generation. We conclude that they constitute a satisfactory solution to with Exp;
the expression problem in its full generality.
The examples in this paper also demonstrate that [8] C. Clifton, G. T. Leavens, C. Chambers, and T. Mill- Scala's abstract type members, mixin composition and stein. MultiJava: Modular open classes and symmet- explicitly typed self references provide a good basis for ric multiple dispatch for Java. In Proceedings of the type-safe extensions of software systems.
Conference on Object-Oriented Programming: Sys- proaches to this problem have also been investigated; tems, Languages, and Applications, pages 130–145.
in particular family polymorphism based on virtual ACM Press, October 2000.
classes or delegation layers these approaches, [9] E. Ernst. Family polymorphism. In Proceedings of the Scala's constructs expose the under- lying mechanisms to a higher degree. On the other hand, European Conference on Object-Oriented Program- they have a clearer type-theoretic foundation, and their ming, pages 303–326, Budapest, Hungary, 2001.
type soundness has been established in the νObj core cal- [10] E. Ernst. Higher-order hierarchies. In Proceedings of the European Conference on Object-Oriented Pro-gramming, LNCS 2743, pages 303–329, Heidelberg, Philippe Altherr, Vincent Cremet, Germany, July 2003. Springer-Verlag.
Burak Emir, Stéphane Micheloud, Nikolay Mihaylov, [11] E. Gamma, R. Helm, R. Johnson, and J. Vlissides. De- Michel Schinz, and Erik Stenman have contributed to the sign Patterns: Elements of Reusable Object-Oriented Scala design and implementation, which was partially Software. Addison-Wesley, 1994.
supported by grants from the Swiss National Fund un-der project NFS 21-61825, the Swiss National Competence [12] C. Grothoff.
Walkabout revisited: The Runabout.
Center for Research MICS, Microsoft Research, and the In Proceedings of the 17th European Conference on Hasler Foundation. We also thank Philip Wadler, Shriram Object-Oriented Programming, Darmstadt, Germany, Krishnamurti, and Kim Bruce for useful discussions on the expression problem.
[13] S. Krishnamurthi, M. Felleisen, and D. Friedman. Syn- thesizing object-oriented and functional design to promote re-use. In European Conference on Object-Oriented Programming, pages 91–113, 1998.
[1] G. Bracha. Personal communication, July 2002.
[14] O. L. Madsen and B. Møller-Pedersen. Virtual Classes: [2] G. Bracha and W. Cook.
A powerful mechanism for object-oriented program- In N. Meyrowitz, editor, Proceedings of the Confer- ming. In Proceedings OOPSLA'89, pages 397–406, ence on Object-Oriented Programming: Systems, Lan- October 1989.
guages, and Applications, pages 303–311, Ottawa,Canada, 1990. ACM Press.
[15] T. Millstein, C. Bleckner, and C. Chambers. Modular typechecking for hierarchically extensible datatypes [3] G. Bracha, M. Odersky, D. Stoutamire, and P. Wadler.
and functions. In Proceedings of the International Making the future safe for the past: Adding gener- Conference on Functional Programming, Pittsburg, icity to the Java programming language. In Proceed- PA, October 2002.
ings of OOPSLA '98, October 1998.
[16] M. Odersky, P. Altherr, V. Cremet, B. Emir, S. Mich- [4] K. B. Bruce. Some challenging typing issues in object- eloud, N. Mihaylov, M. Schinz, E. Stenman, and oriented languages. Electronic Notes in Theoretical M. Zenger. Scala distribution. École Polytechnique Computer Science, 82(8), 2003.
Fédérale de Lausanne, Switzerland, January 2004.
http://scala.epfl.ch [5] K. B. Bruce, A. Fiech, and L. Petersen. Subtyping is not a good "Match" for object-oriented languages. In [17] M. Odersky, V. Cremet, C. Röckl, and M. Zenger. A Proceedings of the European Conference on Object- nominal theory of objects with dependent types. In Oriented Programming, pages 104–127, 1997.
Proceedings of the European Conference on Object-Oriented Programming, Darmstadt, Germany, July [6] K. B. Bruce, A. Schuett, and R. van Gent. PolyTOIL: A type-safe polymorphic object-oriented language. InProceedings of the European Conference on Object- [18] K. Ostermann. Dynamically composable collabora- Oriented Programming, pages 27–51, 1995.
tions with delegation layers. In Proceedings of the16th European Conference on Object-Oriented Pro- [7] J. Buckley, T. Mens, M. Zenger, A. Rashid, and gramming, Malaga, Spain, 2002.
G. Kniesel. Towards a taxonomy of software change.
To appear in Journal of Software Maintenance and [19] J. Palsberg and C. B. Jay. The essence of the visitor Evolution: Research and Practice (Special Issue on pattern. Technical Report 5, University of Technol- USE), 2004.
ogy, Sydney, 1997.
[20] N. Schärli, S. Ducasse, O. Nierstrasz, and A. Black.
Traits: Composable units of behavior. In Proceedingsof the 17th European Conference on Object-OrientedProgramming, Darmstadt, Germany, June 2003.
[21] C. Szyperski.
Independently extensible systems – software engineering potential and challenges. InProceedings of the 19th Australian Computer ScienceConference, Melbourne, Australia, 1996.
[22] M. Torgersen. Virtual types are statically safe. In 5th Workshop on Foundations of Object-Oriented Lan-guages, San Diego, CA, USA, January 1998.
[23] M. Torgersen. The expression problem revisited — Four new solutions using generics. In Proceedingsof the 18th European Conference on Object-OrientedProgramming, Oslo, Norway, June 2004.
[24] M. Torgersen, C. P. Hansen, E. Ernst, P. vod der Ahé, G. Bracha, and N. Gafter. Adding wildcards to theJava programming language.
In Proceedings SAC 2004, Nicosia, Cyprus, March 2004.
[25] P. Wadler and et al. The expression problem. Discus- sion on the Java-Genericity mailing list, December1998.
[26] M. Zenger and M. Odersky.
Extensible algebraic datatypes with defaults. In Proceedings of the In-ternational Conference on Functional Programming,Firenze, Italy, September 2001.
[27] M. Zenger and M. Odersky. Implementing extensible compilers. In ECOOP Workshop on MultiparadigmProgramming with Object-Oriented Languages, Bu-dapest, Hungary, June 2001.

Source: http://scala-lang.org/docu/files/IC_TECH_REPORT_200433.pdf