Section 10.6. FUTURE WORK

10.6. FUTURE WORK

In this section, we describe two prospective extensions to JL: semantic checking and class hierarchy optimization. We also propose two topics for future research: a treatment of mixins as types and a reconciliation of two approaches to implementing parametric polymorphism in object-oriented languages.

10.6.1. Semantic Checking

Even with deep conformance, undesirable mixin compositions can still be easily created. The ability to restrict how mixins are ordered or how many times a mixin can appear in an instantiation requires a higher level of checking than is convenient using OO-type systems. We call this extended capability semantic checking because mixin compositions should be not only type-safe but also meaningful.

JL's semantic checking uses semantic attributes, which are identifiers or tags chosen by programmers to represent meaningful characteristics in an application. At compile-time, an ordered attribute list is associated with each class hierarchy. Attributes are added to lists using provides clauses in class definitions. Attribute lists are tested using requires clauses in class definitions. These tests use regular expression pattern matching and a count operator to validate the presence, absence, cardinality, and ordering of mixins in a composition. Semantic checking occurs only at compile-time; there is no run-time overhead. Chapter 4 of Cardone's dissertation provides greater detail about the design of the JL's semantic checking facility [12].

10.6.2. Class Hierarchy Optimization

JL's programming methodology of stepwise refinement can create deep hierarchies of small classes. The use of many small classes can increase load time and the memory footprint of an application. In addition, stepwise refinement can also increase method call overhead, because multiple mixin methods are often called to perform the work of a single method in a conventionally written application.

At design time, we want the modularity of stepwise refinement; At runtime, we want fast code unimpeded by multiple layers of indirection. By extending existing technology [36] that compresses class hierarchies, we believe the run-time effects of design time layering can be largely eliminated. Chapter 5 of Cardone's dissertation provides greater detail about the design of the Class Hierarchy Optimization [12].

10.6.3. Mixins as Types

Most mixin research falls into one of two categories. The first uses parametric polymorphism to implement mixins by generalizing the idea of a parameterized type. The second defines mixins as types and generalizes the idea of a class. In this section, we propose a way to bring these two approaches together.

Using parametric polymorphism, mixins and other parameterized types are typically treated as type functions or type schemas, which generate types but are not themselves types. In languages that already support parametric types, adding mixins can be an almost trivial extension. Mixin research in this category often uses C++ template classes, which already support mixins. Such research [14, 27, 37] emphasizes software engineering concerns and often includes experiments that test the effectiveness of different mixin programming techniques. Java Layers builds directly on this line of research.

On the other hand, mixins can be defined as types that extend their supertypes without relying on parametric polymorphism. The research [4, 8, 15] in this area focuses on the formal semantics of mixins and on the integration of mixins into existing type systems. This integration typically uses the keyword mixin to declare new types, which either replace or work in conjunction with existing types (e.g., classes).

JAM [3] is a recently implemented language that treats mixins as types. JAM integrates mixin types into Java by adding two new keywords and by extending Java's type system. The JAM code in Listing 10-10 illustrates how mixin type M is declared and how it is used to define two subclasses (Child1 and Child2) of two parent classes (Parent1 and Parent2).

Listing 10-10. Mixins as types in Java

 mixin M { ... } class Child1 = M extends Parent1; class Child2 = M extends Parent2; 

Since mixins are types in JAM, Child1 is a subtype of both M and Parent1 in the Listing 10-10. Child2 is also a subtype of M, which allows objects of types Child1 and Child2 to be treated as type M objects.

To avoid some of the restrictions of JAM, such as the inability to compose mixins with other mixins, and to support parametric polymorphism, we propose an implementation of parametric types that supports full and partial instantiation. A parametric type is fully instantiated when all type parameters are bound; a parametric type is partially instantiated when at least one type parameter is unbound. The asterisk (*) is used to indicate unbound type parameters in instantiations.

A key component of this proposal is that all instantiations are types, but only full instantiations can be constructed. The code in Listing 10-11 depicts mixin M and two lines of code that appear outside of M. The variable partial has type M<*>, which is a partial instantiation of mixin M. Any full instantiation of M can be constructed and assigned to partial, as objects of types M<Parent1> and M<Parent2> here have been.

Listing 10-11. Constructing full instantiations

 class M<T> extends T { ... } M<*> partial = new M<Parent1>(); partial = new M<Parent2>(); 

In this proposal, parametric polymorphism (with mixin support) is fundamentally integrated into the type system. In addition, partial instantiation implies partial evaluation: In partial instantiations, members of parametric types that are not dependent on unbound type parameters are accessible.

10.6.4. Implementing Parametric Polymorphism

There are two basic ways to implement parametric polymorphism in object-oriented languages. Homogeneous implementations execute the same compiled code for all instantiations of a parametric type. Heterogeneous implementations, on the other hand, generate a specialized version of compiled code for each distinct instantiation of a parametric type. In this section, we propose a way to realize the benefits of both approaches in the same implementation.

The homogeneous approach is implemented by Generic Java (GJ) [10] and will be used in future versions of Java [19]. These implementations work by erasing type parameters at compile time and replacing them with general types that are appropriate for all instantiations.

Figure 10-6 shows parametric class C and its erasure, which gets compiled. In GJ, no type parameter information is available at runtime. Instead, the GJ compiler inserts dynamic type casts into code to guarantee type safety. It also inserts bridge methods to guarantee that method overriding works properly.

Figure 10-6. Homogeneous type parameter erasure.

In general, homogeneous implementations are memory-efficient, because a single class implements all instantiations of a parametric type. Homogeneous implementations, however, also have a number of disadvantages. Type erasure loses information because actual type parameter bindings known at compile time are not available at runtime. This means, for example, that a type parameter cannot specify the (non-array) type in a new expression, since the actual type is not known at runtime and cannot be allocated. For the same reason, type parameters cannot be used as the types in cast, catch, or instanceof expressions. Most significant, however, is that pure homogeneous implementations in Java cannot support mixins because different mixin instantiations require different supertypes.

Alternatively, the heterogeneous approach is implemented by C++ and Java Layers. JL uses a heterogeneous implementation, because mixins can be supported and because of its increased expressiveness; i.e., the ability to use type parameters wherever a type is legal.

Figure 10-7 shows parametric class C and the instantiation of C<String>, which gets compiled. Since each instantiation generates specialized code, heterogeneous implementations, like JL and C++, can experience code bloat if a large number of instantiations is used. In addition, the substitution of actual type parameters in instantiated types can lead to access control restrictions when the actual type and the parametric type are in different packages [10].

Figure 10-7. Heterogeneous instantiation.

Unfortunately, the choice between homogeneous and heterogeneous implementation affects the programming language and its usage. Homogeneous implementations place numerous restrictions on the use of type parameters; heterogeneous implementations require programmers to consider code size and package placement issues. Rather than lock a language into one approach or the other, we propose to combine the two approaches and to give the programmer control over their use.

Specifically, we propose that parametric types declared with the new specialize modifier be instantiated using the heterogeneous approach; otherwise, the homogenous approach is used.^[2] Heterogeneously instantiated parametric types can support mixins and the less restrictive use of type parameters. Thus, specialize determines how type parameters are used in parametric types. Our proposal gives programmers explicit control over instantiation, whereas programmers currently are implicitly controlled by the implementation choice made by the language.

^[2] Alternately, a generalize modifier could be defined, but specialize fits in better with the current plan for Java generics.