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
Weekly Newsletter Brought to you by PSU – Corporate and Personal Security www.psuchina.com.cn Information for May 18-24, 2012 Date Headline Crime & Public Security Date Headline Crime & Public Security Beijing(Suburbs) Changping District Date Headline Crime & Public Security Shanghaidailynet Shanghaidailynet Baoshan District
Depresión, Prozac y publicidad engañosa La manipulación en el desarrollo y validación científica de fármacos confunde a médicos, perjudica a pacientes y prostituye el proceso de creación científica En el frívolo y apresurado mundo actual en que vivimos existe una preocupante distorsión entre la información que ofrecen las compañías farmacéuticas sobre sus productos y los efectos reales de éstos. Se trata de vender a toda costa, incluso a costa de nuestra salud, escondiendo en algunos casos tanto los resultados de estudios que no son favorables al fármaco como la escasa –o nula– validez científica de las investigaciones realizadas para su desarrollo y comercialización. Acaba de publicarse en PLoS Medicine un revelador artículo sobre la desconexión que existe entre los anuncios de medicamentos antidepresivos y la realidad científica que los ampara. Por Xurxo Mariño.
