Dynamic Composition with Package Templates

               Fredrik Sørensen                       Eyvind W. Axelsen                     Stein Krogdahl
                University of Oslo                     University of Oslo                  University of Oslo
            Department of Informatics              Department of Informatics           Department of Informatics
             P.O. Box 1080, Blindern                P.O. Box 1080, Blindern             P.O. Box 1080, Blindern
              N-0316 Oslo, Norway                    N-0316 Oslo, Norway                 N-0316 Oslo, Norway
               fredrso@ifi.uio.no                     eyvinda@ifi.uio.no                  steinkr@ifi.uio.no


ABSTRACT                                                           separately compiled after the system they are loaded into
We show how package templates, a mechanism for code mod-           has been started.
ularization, can be extended with features for dynamic load-
ing. We pose the question of whether or not this is may a          Although a set of such classes may be written, compiled and
useful mechanism with respect to software composition and          loaded together, they are still considered as separate entities
dynamic configuration of software.                                 and not checked as one coherent entity upon loading. There
                                                                   is no assurance that the individual classes belong to the same
                                                                   version of the extension. In this work, we are looking at a
Categories and Subject Descriptors                                 way to dynamically load an entity that represents a group of
D.3 [Software]: Programming Languages; D.3.3 [Progra-              classes in a package or template. We believe it to be useful
mming Languages]: Language Constructs and Features—                if one is allowed to take a group of statically checked classes,
Classes and objects; D.3.3 [Programming Languages]:                that are compiled and tested together, and adapt them in a
Language Constructs and Features—Modules, packages                 coordinated fashion to an existing system.

General Terms                                                      A recent paper [15] describes a new language mechanism
Languages, Design                                                  called PT (short for Package Templates), which is meant to
                                                                   be a useful tool for software composition. The mechanism
                                                                   is intended for object oriented languages in order to support
Keywords                                                           better code modularization, where statically type-checked
OOP, Modularization, Dynamicity, Templates                         templates can be written independently and subsequently
                                                                   be instantiated in programs with such flexibility that classes
1.   INTRODUCTION                                                  may be merged, methods renamed and new classes added.
There are several challenges when working with a large soft-       Templates may contain hierarchies of classes (single inheri-
ware system, including modularization, separation of con-          tance) and these hierarchies are preserved when a template
cerns and reuse. These challenges are large enough in them-        is used. Also, different instantiations of the same templates
selves when writing, testing and maintaining a large system.       are independent of each other, creating unique types.
However, even more challenges arise when there are many
different variations of a system, when the environment chan-       The basic PT mechanism allows flexibility in package reuse,
ges over time and when new requirements and extensions             program composition and support for readability and reusabil-
may arrive after the initial system has started running and        ity in large systems. The way that multiple classes may be
should not be taken down.                                          affected by instantiating a template gives the language an
                                                                   AOP-like quality. More AOP-specific extensions to PT have
Given these challenges, it seems beneficial to have similar        also been studied in [3].
support for such dynamic features as one has for the static
build of large systems. One mechanism that is useful in this       In this work, we look at a possible extension to the basic
respect is the use of interfaces and abstract classes in writing   package template mechanism that supports dynamic load-
the system and the possibility of loading different implemen-      ing of package templates. We ask to what extent this will
tations into a running system based on configurations and          be a useful tool for dynamic configuration of software sys-
runtime events. These implementations may be written and           tems. Furthermore, we discuss some of the properties of this
                                                                   mechanism.

                                                                   We introduce an extension to PT where templates are pa-
                                                                   rameterized by templates. A template with template param-
                                                                   eters must be instantiated with actual templates that “ex-
                                                                   tend” the formal parameters’ bounds. In standard PT, all
                                                                   instantiations of templates are done at compile-time. How-
                                                                   ever, in this work we look at extending this concept so that
                                                                   templates may be loaded dynamically into a running sys-
tem, not unlike how classes may be loaded dynamically in         package P {
languages like Java. We discuss how this can be achieved           inst T with A => C, B => D;
with template extensions and with parameterized templates.         class C adds { ... }
                                                                   class D adds { ... } // D extends C, see text
                                                                 }
Being able to load classes dynamically into a system is use-
ful since it allows extensions to be written after the system    In this example, a unique instance of the contents of the
has started running. It also allows one to configure and re-     package template T will be created and imported into the
configure a running systems and for a system to configure        package P. In its simplest form, the inst statement just
itself based on discovery of its environment.                    names the template to be instantiated, e.g. inst T, without
                                                                 any other clauses. In the example above the template classes
Dynamically loading classes in a controlled type-checked         A and B are also renamed to C and D, respectively, and ex-
way has advantages over other dynamic linking mechanisms.        pansions are made to these classes. Expansions are written
A compiler and loader will together have checked that the        in adds-clauses, and may add variables and methods, and
loaded class can be used in a type safe way. Doing this at the   also override virtual or implement abstract methods from
levels of templates, each containing several related classes,    the template class.
extends the reach of this checking.
                                                                 An important property of PT is that everything in the in-
The mechanism proposed here for dynamically loading tem-         stantiated template that was typed with classes from this
plates in PT preserves the relation between the classes in the   template (A and B) is re-typed to the corresponding expan-
template and thereby supports family polymorphism [9]. It        sions (C and D) at the time of instantiation (PT rules guar-
has the advantage of the flexible adaption and name change       antee that this is type-safe). Any sub/super-type relations
mechanisms of PT while still being dynamic. Since new            within the template is preserved in the package where it is
types are created when a template is loaded, different ver-      instantiated. Therefore, implicitly D extends C since B ex-
sions of the same software package can safely be used simul-     tends A.
taneously in the same runtime without name clashes. Thus,
PT extended this way becomes more a mechanism of dy-             Another important property is that classes from different,
namic composition than a static mechanism of reuse and           possibly unrelated, templates may also be merged to form
extension.                                                       one new class, upon instantiation. Consider the simple ex-
                                                                 ample below.
We will first present an overview of the basic package tem-
plate mechanism. Then we will present templates that ex-         template T {
tend other templates and template parameterized templates.         class A { int i; A m1(A a) { ... } }
                                                                 }
After that, we will present dynamic loading before a discus-     template U {
sion and a survey of related work.                                 class B { int j; B m2(B b) { ... } }
                                                                 }

2.   OVERVIEW OF THE PACKAGE TEMP-
     LATE MECHANISM                                              Consider now the following usage of these templates:
We here give a brief and general overview of the package         inst T with A => MergeAB;
template mechanism as it is described in [15]. The mech-         inst U with B => MergeAB;
anism is not in itself tied to any particular object-oriented
language, but the examples will be presented in a Java-like      class MergeAB adds {
syntax, and the forthcoming examples will be based on Java.         int k;
                                                                    MergeAB m2(MergeAB ab) { return ab.m1(this); }
                                                                 }
A package template looks much like a regular Java package,
but the classes are always written in one file and a syntax is   These instantiations result in a class MergeAB, that contains
used where curly braces enclose the contents of the template,    the integer variables i, j and k, and the methods m1 and
e.g. as follows:                                                 m2.1 Note that both m1 and m2 now have signatures of the
                                                                 form MergeAB → MergeAB.
template T {
  class A { ... }
  class B extends A { ... }                                      Summing up, some of the useful properties of PT are: It
}                                                                supports writing reusable templates of interdependent, co-
                                                                 operating classes which may be statically type checked with-
Valid contents of a template (with a few exceptions) are also    out any information about their usage. Upon instantiation,
valid as plain Java programs. As such, templates may also        a template class may be customized, and merged with other
be type checked independently of their potential usage(s).       template classes. References within a template to a tem-
                                                                 plate class will be re-typed according to the instantiation.
In PT, a template is instantiated at compile time with an        After all the instantiations, a PT program will have a set of
inst statement like below. This has some significant differ-     regular classes with single inheritance, like an ordinary Java
ences from Java’s import. Most notably, an instantiation         program.
will create a local copy of the template classes, potentially    1
                                                                  The handling of potential name clashes resulting from a
with specified modifications, within the package where the       merge is beyond the scope of this article, but PT has rules
inst statement occurs.                                           and the rename mechanism discussed to deal with this
3.   TEMPLATE EXTENSIONS AND TEMP-                              as override methods from these classes. Furthermore, it may
     LATE PARAMETERS                                            instantiate other templates using a normal inst statement,
In this section we propose an extension to PT where tem-        and add its own classes (such as C in the example below).
plates may have bounded template parameters. Dynamic
                                                                template Use<template E extends Ext> {
loading of templates will be presented in the next section.       inst E;
                                                                  class A adds { ... }
To be able to enforce a bound on template parameters, we          class B adds {
also introduce the concept of a template extending another,         void m2(A a) { ... } // redefines m2
and thus also of sub-templates. A skeleton of a parameter-          void m3(B b) { ... } // new method m3
                                                                  }
ized template may look as follows.
                                                                  class C {              // new class C
template W <template S extends U, template T extends V>             void foo(B b) {
{ ... }                                                               new A().m1(b);
                                                                    }
S and T are template parameters and U and V are statically        }
known templates that serve as parameter bounds for the          }
respective parameters.
                                                                In a program, the template Use can be instantiated with Ex-
When a parameterized template is instantiated, one must         tOne as its actual parameter, as shown in the example below.
provide an actual template for each parameter, which must       In the package2 Program, the contents of the parameterized
be an extension of the bound of the formal parameter.           template and of the actual parameter are statically known,
                                                                and make up the available classes (and interfaces) accessible
Below is a template called Ext. This template could be part     from the instance of Use<ExtOne>. For these classes, addi-
of a framework and programmers would be supposed to write       tions may be supplied in the normal PT manner, as shown
extensions to it in order for their code to use the function-   below for A, B, C and D. Other templates may be instantiated
ality of the framework. Other templates in the framework        as well, and merging may be performed as for normal PT
(like Use below) may have parameters bounded by the tem-        instantiations.
plate and may hence be instantiated with a programmer’s
sub-templates of Ext as parameters. The template Ext and        package Program {
a sub-template ExtOne may look as follows.                        inst Use<ExtOne> with Use.C=>C, ExtOne.C=>D;
                                                                  rename ExtOne.B.m3=>m4;
template Ext {                                                    class A adds { ... }
  class A { void m1(B b) { ... } }                                class B adds { ... }
  class B { void m2(A a) { ... } }                                class C adds { ... }
}                                                                 class D adds { ... }
template ExtOne extends Ext {                                     class E { ... }
  class A adds { ... }                                          }
  class B adds {
    void m2(A a) { ... } // redefines m2                        Both the actual parameter (here ExtOne) and the parame-
    void m3(B b) { ... } // new method m3
  }
                                                                terized template (here Use) may have a class that overrides a
  class C { ... }        // new class C                         method in a class defined in the template bound Ext (like m2
}                                                               above). In that case, the general rule is that changes from
                                                                the parameterized template (Use) override changes from the
There may be an open ended number of extensions to a            extending template (ExtOne). This rule fits into a program-
template, written separately and without knowledge of each      ming pattern where it is the programmer of the parameter-
other. The extensions may override method implementa-           ized template who is in charge and wants to use the method
tions and add methods and properties to classes, and they       in the parameterized template regardless of the extension to
may also add new classes and instantiate other templates.       the base template. However, we envision that there might be
Extension templates can only extend one template, and there     a need for users to change this precedence, but we explicitly
is an implicit instantiation (inst) of the extended template    leave that topic open for future work.
within the extension. For now, we will not consider the pos-
sibility of allowing name changes in extension templates.       A similar issue is the question of what should happen when
                                                                the extension (actual parameter) and the parameterized tem-
Below, the template Use is defined with a template parame-      plate both have defined new classes with the same name (like
ter E bounded by Ext. The template parameter can be used        C above). In such situations, these new classes are considered
in an inst statement in Use, but the actual instantiation is    to be separate classes, and must be renamed in the package
postponed until an actual parameter is provided.                Program in the regular PT fashion to avoid ambiguity (as in
                                                                the example above). The same goes for methods within an
Within Use, it is known from the bound Ext and the inst         existing class (like m3 above). A regular package may also
statement that the template will have at least the classes A    add classes (like E).
and B from Ext, and they may be used in Use in the same
way as classes from a regular inst statement.                   Below is an example that illustrates some of the different sit-
                                                                uations that might occur with regards to method overrides.
Thus, through the use of adds-clauses (such as A and B be-
low), the parameterized template may add fields and meth-       2
                                                                  Like templates, packages are written within curly brackets
ods to the classes defined in the parameter bounds, as well     in PT.
template U {                                                      However, we shall also use template types in a way that is
  class A { void m(){ ... } }                                     somewhat unusual, by saying that each template instance
  class B extends A { void m(){ ... } }                           has a type of it own which includes both the template of
}
template V extends U {
                                                                  which it is an instance, and the identity of the instance.
  class A adds { void m(){ ... } }                                Thus, two instances of the same template have different
  class B { void m(){ ... } } // extends A implicitly             types. This is done to make it easier to handle the fact that
}                                                                 the “same” local class in different instances of a template
template X <template UU extends U> {                              are indeed different classes. To form a consistent model, we
  class A adds { void m(){ ... } }                                also say that the full type of an instance is a subtype of the
  class B { void m(){ ... } } // extends A implicitly
}
                                                                  template it is an instance of.
package P {
  inst X<V>;                                                      In the following discussion, we will use as an example the
}                                                                 three templates below. Templates U1 and U2 can be written
Package P will have classes A and B, both with a method m.        after a program referring to U has started running. They
The methods will be the ones from template X, since they          can be separately compiled and neither of U1 and U2 need
override the others. As with regular single inheritance a call    any knowledge of the other (nor does U need any knowledge
to super in B will invoke the method defined in A. If, on the     of its descendants, obviously).
other hand, A in X did not define an override of m, a call to     template U { class A {...} class B {...} }
super.m in X.B.m would call the implementation in V.A.            template U1 extends U {
                                                                    class A adds {...}   class B adds {...} }
However, if one wants to reuse the methods that are overrid-      template U2 extends U {
den by the template mechanism as opposed to by ordinary             class A adds {...}   class B adds {...} }
class inheritance, the keyword tsuper may be used, and a          In this context, U can often be seen as a sort of “template
call to tsuper in A in template X will call the method defined    interface”, providing mostly abstract classes (in a template
in A in the template that is given as the actual parameter (in    sense), and U1 and U2 can then be different implementations
P this is V). A call to tsuper in A in template V will invoke     of this interface. At runtime, a program referring to U may
the one in A in template U. Combining super and tsuper            load one of the templates U1 or U2 (or further sub-templates
yields a useful and flexible mechanism for reuse.                 of these) and create one or more instances of it. Such in-
                                                                  stances can be kept track of by template-typed variables and
A package can be used as a regular Java package in other          can be passed around by assignments etc. according to nor-
compilation units and its classes are regular classes. A reg-     mal object-oriented polymorphism rules, e.g as the following
ular Java class may, for example, refer to (and import) the       code.
class P.A. We will see later that regular classes can also have
template parameters, and these work in a different way.           Instance<instance ? of U> u = /* A dynamically
                                                                               generated instance of U, U1 or U2 */;
                                                                  Instance<instance ? of U1> u1 = /* A dynamically
We have not worked out rules for visibility or access restric-
                                                                               generated instance of U1 */;
tion at the package level yet. Hence, there is no mention of      u = u1;
public or private classes or methods.
                                                                  Here, Instance<T> is a class much like the class Class in
There are obviously many other questions around templates         Java. It is parameterized by an instance type T and has
with template parameters that are not fully answered in the       the signature class Instance <instance T>. It represents
text above, but to keep this exposition fairly short, we will     a template instance (and not a template) in the same way
not pursue all of these questions here.                           that Class represents a class. The reason that we use a class
                                                                  that represents the instance and not the template is that
4.   DYNAMIC INSTANTIATIONS                                       every instance generation results in the creation of a new
We saw in Section 2 how to instantiate templates, and how         instance type and new types for all the classes in the instan-
to merge classes from different templates by using the compile-   tiated template. The concrete mechanism for performing
time inst construct. In section 3 we saw how templates can        a dynamic load and instantiation will be explained shortly,
have template parameters and how to write sub-templates.          but the result is an object of the class Instance<T>. The
In this section we introduce dynamic instantiation and adap-      special syntax <instance ? of U> tells the compiler that
tion of templates. We believe this is very useful, as which       the exact instance is not known statically, but that it is
features (in the form of templates) should be used is of-         a sub-template of U. The parameter T of Instance will be
ten not known until after the execution has started. For          bound to the type of the instance. As is shown in the last
simplicity and to keep this short we limit our detailed dis-      line above, template instance references may be assigned to
cussion here to instantiating templates dynamically without       a template variable having a more general type. Also, an
any name changes or merges.                                       obvious form of casting can be used for the opposite case.

The approach we use is based on the hierarchies of templates      In the program, a method can have template parameters
formed through the extends-relation, and on using this some-      bounded by U in the following way:
what like the hierarchies of subclasses in traditional object-
                                                                  <instance T of U> void method(){
oriented programming. Thus, we can type e.g. a variable             T.A a = new T.A();
with a template based type, and it can thereby refer to in-         a.doStuff();
stances of that template, or to instances of a sub-template.      }
Within such a parameterized method, elements can be typed         <instance T of U> void method_1() {
with classes from the template using the template type as           T.A a1 = new T.A();
a prefix, like T.A above. Code like this makes it possible to       T.B a2 = new T.B();
                                                                    method_2<T>(a1, a2); // <T> may be omitted as it
use classes and invoke methods in dynamically instantiated
                                                                  }                       // can be inferred
templates in a type-safe way. Type safety depends on the
fact that, in the scope, T is bound to an instance and T (a       <instance Z extends U> void method_2(Z.A a1, Z.B b) {
type parameter) does not change like object variables.              ...; a1.m(b); ...;
                                                                  }
We are considering whether a syntax like the following should     When method_1 is invoked, T is bound to the type of some
be allowed:                                                       template instance u. The clause T.A is bound to the type
                                                                  of A for that particular instance. The second method takes
Instance<instance ? of U> u = /* A dynamically
               generated instance of U1 or U2 */;
                                                                  two formal parameters that are of types called Z.A and Z.B
...                                                               where Z is a the type of the template instance (a sub-type
method<u.TYPE>();                                                 of U). The invocation of this method in the first method can
                                                                  be type checked since both the actual parameters are typed
Here, the formal parameter T in the method is bound to            with class A from the same template which is also a sub-
the current type of u (which is identical with the instance       template of U. Inside the second method, the methods (for
identity), and will remain so throughout the body of the          example m) defined in template U can be called.
method. This will fail if u is a null value.
                                                                  In a scope, there is often only one known template that
A class can be written with the same kind of template pa-         is being used and it would be nice not to have to write
rameter. This can look as follows:                                the instance type parameter T all the time. Therefore, we
                                                                  propose the shorthand notation shown below. Within the
class P <instance T of U> {                                       with-block, class names can be written without the type
  public T.A a;                                                   prefix.
  public P(){
    ...                                                           <instance T of U> void method(){
    a = new T.A();                                                  ...
    ...                                                             with(T) do {
  }                                                                   ...; .A a = new .A(); ...;
}                                                                   }
                                                                    ...;
This class can be statically and separately checked in the        }
same way that a generic class can be type checked, with the       Other times, one may want to work with two (or more) dif-
difference being the dot-named classes, like T.A. T will be the   ferent instances of a template (or more likely, two instances
same type in this scope and T will be an instance of U or of a    of different sub-templates) at the same time. Below we as-
subtype of U. Thus, the class T.A can be seen as a type just      sumes that A in Ext has a field b of type B and that B has a
like any type and it has all the properties of A in U. Note       field x of type int.
that if A has a method void m(B b) it can be invoked with         <instance T of Ext, instance U of ExtOne>
m(new T.B()) here. T.A and T.B will, since T is the same,                             U.A[] method(T.A tas[]) {
be from the same instance and at runtime the actual type            U.A uas[] = new U.A[tas.length];
of B will match up with the method signature.                       for (int i = 0; i<tas.length; i++){
                                                                      uas[i] = new U.A();
                                                                      uas[i].b = new U.B();
The class P can then be used e.g. as follows:
                                                                      uas[i].b.x = tas.[i].b.x; // A and B from different
                                                                    }                           // instances are never
Instance<instance ? of U> u = /* Instance of U or of a
                                                                    return uas;                 // mixed up
                       sub-template */;
                                                                  }
P<?> pu = new P<u.TYPE>();
                                                                  Dynamically generated instances of templates are produced
...   // Maybe another assignment to u                            by a special loader, with a method instantiate that has a
                                                                  template parameter, and a normal String parameter. The
P<?> pu1 = new P<u.TYPE>();
                                                                  first parameter should be a statically known template, and
pu = pu1;        // OK                                            the second should be a filename (or net-address, etc.) where
pu.a = pu1.a;    // COMPILE TIME ERROR !                          a sub-template of the template parameter can be found. The
                                                                  loader will check that this is the case, and maybe also com-
Here, P<?> is a type where ? is similar to ? in Java generics     pile the template if necessary. Thus, a dynamic instantiation
in that pu can point to any object of P. Similarly, u can         may look as below. The exact details of the loader and its
point to an instance class for any instance of U or instance      implementation are not worked out, but at runtime it can
of a sub-template of U. Since it is not known statically in       be checked that it will only return an instance of the given
this scope if pu and pu1 point to an object created with the      template or a sub-template.
same template instance (because of the question mark), the
                                                                  Instance<instance ? of U> u =
last assignment is not legal.                                                     TLoader.instantiate<U>("-file-");

Objects of the classes of a template instance may be passed       Just as metods and classes in regular classes can be param-
around like the template instance itself. This can be illus-      eterized with regular template instances and used with any
trated by the following two methods:
instance of any sub-template, they can also be parameter-         make sure that objects created from different template in-
ized with a parameterized template. The example below is a        stances have their own type. This enables a form of family
class that uses the template Use from earlier as a parameter      polymorphism [9].
bound.
                                                                  The dynamic loading and composition proposed is not as
class StartOff<instance T of Use>{
  run(){ ...                                                      dynamic as some other systems. Requiring that the loaded
     new T.C().foo(new T.B());                                    template be a sub-template of some bound, the program can
     ... }                                                        be type checked and if the loading itself does not fail, the
}                                                                 system will not cause type errors during execution.
An object can be created of this class using any instance
                                                                  Loading single classes, as is usual in Java, means that one
of Use instantiated with any sub-template of Ext. All the
                                                                  can only depend on a single interface with named methods
classes known in Ext can be used within this class, prefixed
                                                                  that have parameters that are of statically known and un-
by T. Below is an example of instantiating an instance of
                                                                  changeable types. Loading a complete template not only
Use with ExtOne and using StartOff.
                                                                  allows one to view several classes as a whole, but in PT the
Instance<instance ? of Use> u =                                   types of the parameters of methods and variables in the tem-
          TLoader.instantiate<Use>("-Use<ExtOne>-");              plate itself are adapted to new types. This is a useful new
StartOff<?> s = new StartOff<u.TYPE>();                           feature of package templates and dynamic package templates
s.run();
                                                                  in particular – which does this composition at runtime.
Note that the use of the name C in StartOff refers to the
one originating in Ext and that the one from ExtOne is not        PT is more flexible in renaming, etc, than is discussed here.
visible in StartOff.                                              There is also more flexibility in using template parameters
                                                                  than what has been discussed. There is work going on look-
All these examples of regular classes and methods parame-         ing at merging and other type safe mechanisms for creating
terized by templates are mainly there to be starting points       instances from multiple dynamically loaded templates and
for the code within the templates. The interesting code will      on abstract methods in templates.
probably be inside templates Ext and Use and classes like
StartOff will usually just set this off.                          We have not discussed how this proposal would work to-
                                                                  gether with the aspect oriented extensions discussed in [3].
There are more details about dynamic instantiations of pack-      A consistent combination of the two extensions should be
age templates that have not been discussed here and open          worked out. For an even more dynamic approach, there
questions obviously still exist, but we nevertheless believe      is also a study of a similar mechanism for the dynamically
that the mechanism should be useful as a starting point for       typed language Groovy [2].
developing a language mechanism for dynamically config-
ured and composed systems.                                        We are also looking at doing dynamic updates to running
                                                                  code, that is updating already loaded template instance, by
5.   DISCUSSION AND FURTHER WORK                                  for example redirecting calls to new methods. Allowing this
                                                                  in some restricted way, could create even more useful aspect
The aim of this work is to develop tools that allow parts of
                                                                  oriented features in the language.
larger software systems to be written as independent pieces
and that can be merged in a flexible way. This should pro-
                                                                  The most important future work is to settle the open ques-
vide flexibility in both organization of a system and reuse of
                                                                  tions concerning the rules of the language, prove its type
components. To be truly flexible, merging and composition
                                                                  safety and building a compiler.
of independently written parts of software should even be
allowed at runtime. However, one would like to do this with
some sort of static checking to avoid some of the often oc-       6.   RELATED WORK
curring errors with uncoupled code. Also, there is value in       The authors of the trait mechanism [22] approach the prob-
the ability to run different versions of a library or framework   lem of composition from the angle that the primary unit
in the same runtime without having to deal with conflicting       to be composed is the class. A trait is as such a construct
types. We try to solve this with an extension of the package      that encloses a stateless3 collection of provided and required
template (PT) mechanism.                                          methods. Traits may subsequently be used to compose new
                                                                  traits or as part of a class definition. The composition of
PT and the extensions proposed here should provide some of        traits is then said to be flattened. This entails that (1)
the apparatus not only for merging and composing unrelated        the trait ordering in each composition is irrelevant, and (2)
templates of cooperating classes, but also for doing so in a      that a class composed from traits is semantically equal to
running system.                                                   a class in which all the methods are defined directly in the
                                                                  class. When used to compose a class, all requirements must
One feature of the PT approach is that the classes within the     be satisfied by the final composition. Traits were originally
templates form a whole and that the relations and inheri-         developed for the dynamic language Squeak, and supports
tance between the classes are preserved during instantiation.     method aliasing and exclusion upon composition. A stati-
                                                                  cally typed version also exists [20]. Still, neither the static
New types are created whenever a template is instantiated.        3
                                                                   Traits were originally defined to be stateless, although a
Each instance is kept separate, and in addition to allow-         more recent paper [5] has shown how a stateful variant may
ing flexibility in merging and renaming, this can be used to      be designed and formalized.
nor the dynamic version have explicit support for runtime         Like PT, Mixin layers [23] is a mechanism for writing an ad-
selection of which features that should be composed.              dition with affect accross multiple entities like classes. Mixin
                                                                  layers can be composed by instantiating a layer with another
Mixins [6] are similar in scope to traits, in that they target    as its parameter and thus mixin layers are both reusable and
the reuse of small units of code. Mixins also define provided     interchangeable. They are also nested. However, there does
and required functionality, and the main difference between       not seem to be a way to build hierarchies withing a mixin
them and traits is arguably the method of composition. Mix-       layer.
ins traditionally rely on inheritance, by defining a subclass
with as-of-yet undefined parent, and thereby requiring that       BETA [18, 17], gbeta [9] and J& [21] (pronounced ”jet”) are
mixins are linearly composed.                                     systems that in many ways are similar to each other and
                                                                  in many respects can achieve similar end results to those of
Functionality similar to that of traits and mixins can quite      PT. A common property of all of them (except PT, that is)
easily be mimicked with PT. For instance, to create a reusable    is that they utilize virtual classes (as introduced by BETA)
collection of methods (with or without accompanying state),       to enable specialization and adaption of hierarchies of re-
one might simply define a template with a single class, con-      lated classes. gbeta and J& support multiple inheritance,
sisting of the methods that are subject to reuse. This class      and this may to a certain extent be used to ”merge” (in the
may then be merged with other classes where the functional-       PT sense of the word) independent classes. Neither BETA,
ity is needed. When it comes to specifying required methods,      gbeta nor J& support concepts similar to runtime template
PT provides no such concept out-of-the-box, but a solution        instantiations.
might be to define abstract and/or virtual methods in the
template class. As is the case with traits, merge/composition     As we now introduce dynamicity and more free-standing
order is not significant in PT.                                   template instances, the mechanism we present will become
                                                                  more similar to a solution with virtual classes and family
Perhaps the biggest conceptual difference between mixins/traits   polymorphism, as e.g. in gbeta [9]. However, the rules and
and PT comes in form of intended scope, in the sense that         restrictions used to keep the system consistent will be dif-
PT is targeted towards reusing and specializing larger chunks     ferent in our version.
of code as one coherent unit. In that regard, the former two
can be seen as a special case of what can be accomplished         In a subject-oriented [13] programming (SOP) system, dif-
with PT, admittedly with a slightly more involved syntax          ferent subjects may have differing views of the (shared) ob-
and some ’glue code’.                                             jects of an application. There is no global concept of a class;
                                                                  each subject defines ’partial classes’ that model that sub-
Aspect-oriented programming (AOP) [14] involves several           ject’s world view. What is called a merge in SOP, is some-
concepts related to PT. For instance, intertype declarations      what different from a merge in PT. In SOP, a merge is an
in AspectJ [7] may (statically) add new members to existing       example of a composition strategy (and there may be many
classes, and may as such be used to compose previously un-        of them), that tells the system how to compose separate
related features. An example of this is exemplified through       subjects with overlapping methods and/or state. Like with
the Observer design pattern [10] in [11]. However, this im-       mixins and traits, there seems to be a difference in intended
plementation, and on a higher level the general approach em-      scope when comparing SOP with PT; SOP targets a broader
ployed to composition, is arguably less than optimal, given       scope, with entire (possibly distributed) systems (that may
that it suffers from the fact that the aspect itself entan-       even be written in different languages) being composed. One
gles several conceptual roles within a single aspect, and that    could, however, picture an extended PT-like mechanism as
this aspect also exists as a unit at runtime, lacking a clear     a basis for an implementation of SOP.
mapping to objects from the problem domain. The Caesar
language [1, 19] supports both aspect-oriented programming        Our approach to typing classes and methods with instance
constructs and code reuse and specialization through the use      types to keep different instances of a template apart at run-
of virtual classes. It also supports wrappers for defining ad-    time is based on a clever idea for keeping different implemen-
ditional behavior for a class, and dynamic deployment of          tations of a single API apart at runtime using Java generics
aspects at runtime (through use of the deploy keyword).           and tying the classes of an implementation together using a
Dynamically deployed aspects are in effect from all calls         type parameter. This idea is found in [12].
propagating down the call stack with respect to the lexi-
cal scope of a deploy construct. Expanding on the notion          Ada originally (in 1983, [16]) had no mechanisms supporting
of dynamic deployment, Tanter [24] describes a mechanism          object-orientation, but it had a mechanism called generic
for controlling the scope of dynamically deployed aspects (in-    packages with some of the same aims as PT, in that packages
cluding propagation down the call stack and to new objects).      can contain type definitions and that you get a new set of
Note, however, that these aspects may affect behavior only,       these each time the generic package is instantiated. Generic
and not class structure or hierarchy, as opposed to dynamic       packages also have type parameters.
instantiations in PT.
                                                                  In Ada 95 [4] a slightly untraditional mechanism for object-
Context-oriented programming (COP) [8] provides a way to          orientation was introduced, and it was further elaborated
activate and deactivate layers of a class definition at run-      in Ada 2005. Thus, the potential for PT-like mechanisms
time. Layer activation can be nested, and propagate down          should be there, but as far as the authors understand it,
the call stack (for the current thread).                          there is nothing similar to virtual classes (at compile-time or
                                                                  at runtime) in the language, and the mechanims for adapt-
ing a package to its use during instantiation are not very       [11] J. Hannemann and G. Kiczales. Design pattern
advanced.                                                             implementation in Java and AspectJ. SIGPLAN Not.,
                                                                      37(11):161–173, 2002.
7.   CONCLUSION                                                  [12] W. Harrison, D. Lievens, and F. Simeoni. Safer typing
We have proposed an extension to the package template                 of complex api usage through java generics. In PPPJ
mechanism that will allow dynamic loading and instantia-              ’09: Proceedings of the 7th International Conference
tions of templates. We have discussed some of the properties          on Principles and Practice of Programming in Java,
of the proposed language. It is in some crucial ways different        pages 67–75, New York, NY, USA, 2009. ACM.
from other mechanisms that try to solve similar challenges.      [13] W. Harrison and H. Ossher. Subject-oriented
The practical consequences of these differences need to be            programming: a critique of pure objects. In OOPSLA
worked out.                                                           ’93: Proceedings of the eighth annual conference on
                                                                      Object-oriented programming systems, languages, and
Further studies need to be done to find out if the language is        applications, pages 411–428, New York, NY, USA,
really useful for dynamic software composition, and details           1993. ACM.
of the language need to be worked out based on a study of        [14] G. Kiczales, J. Lamping, A. Menhdhekar, C. Maeda,
what makes most sense in a practical language.                        C. Lopes, J.-M. Loingtier, and J. Irwin.
                                                                      Aspect-oriented programming. In M. Akşit and
Although our initial work on finding a translation of the             S. Matsuoka, editors, Proceedings European
mechanism to Java generics suggests that the language is              Conference on Object-Oriented Programming, volume
type safe, a proof of this needs to be worked out and a               1241, pages 220–242. Springer-Verlag, Berlin,
compiler must be built.                                               Heidelberg, and New York, 1997.
                                                                 [15] S. Krogdahl, B. Møller-Pedersen, and F. Sørensen.
8.   REFERENCES                                                       Exploring the use of package templates for flexible
 [1] I. Aracic, V. Gasiunas, M. Mezini, and K. Ostermann.             re-use of collections of related classes. Journal of
     An overview of CaesarJ. In Trans. AOSD I, volume                 Object Technology, 8(7):59–85, 2009.
     3880 of LNCS, pages 135–173. Springer Berlin /              [16] H. Ledgard. Reference Manual for the ADA
     Heidelberg, 2006.                                                Programming Language. Springer-Verlag New York,
 [2] E. W. Axelsen and S. Krogdahl. Groovy package                    Inc., Secaucus, NJ, USA, 1983.
     templates: supporting reuse and runtime adaption of         [17] O. L. Madsen and B. Møller-Pedersen. Virtual classes:
     class hierarchies. In DLS ’09: Proceedings of the 5th            a powerful mechanism in object-oriented
     symposium on Dynamic languages, pages 15–26, New                 programming. In OOPSLA ’89: Conference
     York, NY, USA, 2009. ACM.                                        proceedings on Object-oriented programming systems,
 [3] E. W. Axelsen, F. Sørensen, and S. Krogdahl. A                   languages and applications, pages 397–406, New York,
     reusable observer pattern implementation using                   NY, USA, 1989. ACM.
     package templates. In ACP4IS ’09: Proceedings of the        [18] O. L. Madsen, B. Møller-Pedersen, and K. Nygaard.
     8th workshop on Aspects, components, and patterns                Object-Oriented Programming in the BETA
     for infrastructure software, pages 37–42, New York,              Programming Language. Addison-Wesley, 1993.
     NY, USA, 2009. ACM.                                         [19] M. Mezini and K. Ostermann. Conquering aspects
 [4] J. Barnes. Programming in Ada95. Addison Wesley                  with Caesar. In AOSD ’03, pages 90–99, New York,
     Longman Publishing Co., Inc., Redwood City, CA,                  2003. ACM.
     USA, 1995.                                                  [20] O. Nierstrasz, S. Ducasse, S. Reichhart, and
 [5] A. Bergel, S. Ducasse, O. Nierstrasz, and R. Wuyts.              N. Schärli. Adding Traits to (Statically Typed)
     Stateful traits and their formalization. Computer                Languages. Technical Report IAM-05-006, Institut für
     Languages, Systems & Structures, 34(2-3):83–108,                 Informatik, Universität Bern, Switzerland, December
     2008.                                                            2005.
 [6] G. Bracha and W. Cook. Mixin-based inheritance. In          [21] N. Nystrom, X. Qi, and A. C. Myers. J&: nested
     N. Meyrowitz, editor, Proc. Conf. O-O. Prog.: Syst.,             intersection for scalable software composition. In
     Lang., and Appl. / Proc. ECOOP, pages 303–311,                   OOPSLA ’06, pages 21–36, New York, 2006. ACM.
     Ottawa, Canada, 1990. ACM Press.                            [22] N. Schärli, S. Ducasse, O. Nierstrasz, and A. Black.
 [7] A. Colyer. AspectJ. In Aspect-Oriented Software                  Traits: Composable units of behavior. In ECOOP
     Development, pages 123–143. Addison-Wesley, 2005.                2003, volume 2743 of LNCS, pages 327–339. Springer
 [8] P. Costanza and R. Hirschfeld. Language constructs               Berlin / Heidelberg, 2003.
     for context-oriented programming: an overview of            [23] Y. Smaragdakis and D. Batory. Mixin layers: an
     contextl. In DLS ’05: Proceedings of the 2005                    object-oriented implementation technique for
     symposium on Dynamic languages, pages 1–10, New                  refinements and collaboration-based designs. ACM
     York, NY, USA, 2005. ACM.                                        Trans. Softw. Eng. Methodol., 11(2):215–255, 2002.
 [9] E. Ernst. gbeta - a language with virtual attributes,       [24] É. Tanter. Expressive scoping of dynamically-deployed
     block structure, and propagating, dynamic                        aspects. In AOSD ’08: Proceedings of the 7th
     inheritance, 1999.                                               international conference on Aspect-oriented software
[10] E. Gamma, R. Helm, R. Johnson, and J. Vlissides.                 development, pages 168–179, New York, 2008. ACM.
     Design Patterns -Elements of Reusable
     Object-Oriented Software. Addison-Wesley, 1994.