Behold the power
of parametric
polymorphism - JavaWorld February
2000
Tutorial Details:
Behold the power of parametric polymorphism
Behold the power of parametric polymorphism
By: By Eric Allen
Adding generic types to Java could mean less coding and fewer
uppose you want to implement a list class in Java. You start with an abstract class, List , and two subclasses, Empty and Cons , representing empty and nonempty lists, respectively. Since you plan to extend the functionality of these lists, you design a ListVisitor interface, and provide accept(...) hooks for ListVisitor s in each of your subclasses. Furthermore, your Cons class has two fields, first and rest , with corresponding accessor methods.
What will the types of these fields be? Clearly, rest should be of type List . If you know in advance that your lists will always contain elements of a given class, the task of coding will be considerably easier at this point. If you know that your list elements will all be integer s, for instance, you can assign first to be of type integer .
However, if, as is often the case, you don't know this information in advance, you must settle for the least common superclass that has all possible elements contained in your lists, which typically is the universal reference type Object . Hence, your code for lists of varying type elements has the following form:
abstract class List {
public abstract Object accept(ListVisitor that);
}
interface ListVisitor {
public Object _case(Empty that);
public Object _case(Cons that);
}
class Empty extends List {
public Object accept(ListVisitor that) {
return that._case(this);
}
}
class Cons extends List {
private Object first;
private List rest;
Cons(Object _first, List _rest) {
first = _first;
rest = _rest;
}
public Object first() {return first;}
public List rest() {return rest;}
public Object accept(ListVisitor that) {
return that._case(this);
}
}
Although Java programmers often use the least common superclass for a field in this way, the approach has its disadvantages. Suppose you create a ListVisitor that adds all the elements of a list of Integer s and returns the result, as illustrated below:
class AddVisitor implements ListVisitor {
private Integer zero = new Integer(0);
public Object _case(Empty that) {return zero;}
public Object _case(Cons that) {
return new Integer(((Integer) that.first()).intValue() +
((Integer) that.rest().accept(this)).intValue());
}
}
Note the explicit casts to Integer in the second _case(...) method. You are repeatedly performing runtime tests to check properties of the data; ideally, the compiler should perform these tests for you as part of program type checking. But since you are not guaranteed that AddVisitor will only be applied to List s of Integer s, the Java type checker cannot confirm that you are, in fact, adding two Integer s unless the casts are present.
You could potentially obtain more precise type checking, but only by sacrificing polymorphism and duplicating code. You could, for instance, create a special List class (with corresponding Cons and Empty subclasses, as well as a special Visitor interface) for each class of element you store in a List . In the example above, you would create an IntegerList class whose elements are all Integer s. But if you wanted to store, say, Boolean s in some other place in the program, you would have to create a BooleanList class.
Clearly, the size of a program written using this technique would increase rapidly. There are further stylistic issues, as well; one of the essential principles of good software engineering is to have a single point of control for each functional element of the program, and duplicating code in this copy-and-paste fashion violates that principle. Doing so commonly leads to high software development and maintenance costs. To see why, consider what happens when a bug is found: the programmer would have to go back and correct that bug separately in every copy made. If the programmer forgets to identify all of the duplicated sites, a new bug will be introduced!
But, as the example above illustrates, you will find it difficult to simultaneously keep a single point of control and use static type checkers to guarantee that certain errors will never occur when the program executes. In Java, as it exists today, you often have no choice but to duplicate code if you want precise static type checking. To be sure, you could never eliminate this aspect of Java entirely. Certain postulates of automata theory, taken to their logical conclusion, imply that no sound type system can determine precisely the set of valid inputs (or outputs) for all methods in a program. Consequently, every type system must strike a balance between its own simplicity and the expressiveness of the resulting language; the Java type system leans a bit too much in the direction of simplicity. In the first example, a slightly more expressive type system would have let you maintain precise type checking without having to duplicate code.
Such an expressive type system would add generic types to the language. Generic types are type variables that can be instantiated with an appropriately specific type for each instance of a class. For the purposes of this article, I will declare type variables in angle brackets above class or interface definitions. The scope of a type variable will then consist of the body of the definition at which it was declared (not including the extends clause). Within this scope, you can use the type variable anywhere that you can use an ordinary type.
For example, with generic types, you could rewrite your List class as follows:
abstract class List {
public abstract T accept(ListVisitor that);
}
interface ListVisitor {
public T _case(Empty that);
public T _case(Cons that);
}
class Empty extends List {
public T accept(ListVisitor that) {
return that._case(this);
}
}
class Cons extends List {
private T first;
private List rest;
Cons(T _first, List _rest) {
first = _first;
rest = _rest;
}
public T first() {return first;}
public List rest() {return rest;}
public T accept(ListVisitor that) {
return that._case(this);
}
}
Now you can rewrite AddVisitor to take advantage of the generic types:
class AddVisitor implements ListVisitor {
private Integer zero = new Integer(0);
public Integer _case(Empty that) {return zero;}
public Integer _case(Cons that) {
return new Integer((that.first()).intValue() +
(that.rest().accept(this)).intValue());
}
}
Notice that the explicit casts to Integer are no longer needed. The argument that to the second _case(...) method is declared to be Cons , instantiating the type variable for the Cons class with Integer . Therefore, the static type checker can prove that that.first() will be of type Integer and that that.rest() will be of type List . Similar instantiations would be made each time a new instance of Empty or Cons is declared.
In the example above, the type variables could be instantiated with any Object . You could also provide a more specific upper bound to a type variable. In such cases, you could specify this bound at the type variable's point of declaration with the following syntax:
extends
For instance, if you wanted your List s to contain only Comparable objects, you could define your three classes as follows:
class List {...}
class Cons {...}
class Empty {...}
Although adding parameterized types to Java would give you the benefits shown above, doing so would not be worthwhile if it meant sacrificing compatibility with legacy code in the process. Fortunately, such a sacrifice is not necessary. It is possible to automatically translate code, written in an extension of Java that has generic types, to bytecode for the existing JVM. Several compilers already do this -- the Pizza and GJ compilers, written by Martin Odersky, are particularly good examples. Pizza was an experimental language that added several new features to Java, some of which were incorporated into Java 1.2; GJ is a successor to Pizza that adds only generic types. Since this is the only feature added, the GJ compiler can produce bytecode that works smoothly with legacy code. It compiles source to bytecode by means of type erasure, which replaces every instance of each type variable with that variable's upper bound. It also allows type variables to be declared for specific methods, rather than for whole classes. GJ uses the same syntax for generic types that I use in this article.
Work in progress
At Rice University, the programming languages technology group in which I work is implementing a compiler for an upward-compatible version of GJ, called NextGen. The NextGen language was jointly developed by Professor Robert Cartwright of Rice's computer science department and Guy Steele of Sun Microsystems; it adds the ability to perform runtime checks of type variables to GJ.
Another potential solution to this problem, called PolyJ, was developed at MIT. It is being extended at Cornell. PolyJ uses a slightly different syntax than GJ/NextGen. It also differs slightly in the use of generic types. For example, it does not support type parameterization of individual methods, and currently, doesn't support inner classes. But unlike GJ or NextGen, it does allow type variables to be instantiated with primitive types. Also, like NextGen, PolyJ supports runtime operations on generic types.
Sun has released a Java Specification Request (JSR) for adding generic types to the language. Unsurprisingly, one of the key goals listed for any submission is the maintenance of compatibility with existing class libraries. When generic types are added to Java, it is likely that one of the proposals discussed above will serve as the prototype.
There are some programmers who are opposed to adding generic types in any form, despite their advantages. I'll refer to two co
Read
Tutorial at: Click here to view the tutorial
Rate Tutorial: Behold the power
of parametric
polymorphism - JavaWorld February
2000
View Tutorial: Behold the power
of parametric
polymorphism - JavaWorld February
2000
Related
Tutorials:
 Object-oriented
language basics, Part
7
Object-oriented
language basics, Part
7
|
Connect the
enterprise with the JCA, Part 1
Connect the
enterprise with the JCA, Part 1
|
Diagnose common runtime problems with
hprof
Diagnose common runtime problems with
hprof
|
Make the Java-Oracle9i
connection
Make the Java-Oracle9i
connection
|
Finally, getting hands in !
Finally, getting hands in !
|
Simple classes for JDBC
Simple classes for JDBC
|
SLAMD Distributed Load Generation Engine
SLAMD Distributed Load Generation Engine
The SLAMD Distributed Load Generation Engine (SLAMD) is a Java-based application designed for stress testing and performance analysis of network-based applications. It was originally developed by Sun Microsystems,
|
The power of table-oriented programming
The power of table-oriented programming
When object-oriented programming languages began to be used in enterprise applications, designers had problems fitting the object-oriented model with the relational model. In the object-oriented model, data is enca
|
SeSAm - Shell for Simulated Agent Systems
Multi-Agent Simulation Environment
SeSAm (Shell for Simulated Agent Systems) provides a generic environment for modelling and experimenting with agent-based simulation. We specially focused on providing a tool for the easy construction of complex models,
|
Distributed Objects & Components: JavaBeans
What is JavaBeans ? (from the FAQ)
|
Hibernate simplifies inheritance mapping.
Learn three easy-to-implement strategies to map class hierarchies. Hibernate is an object-relational mapping and persistence framework that provides a lot of advanced features, ranging from introspection to polymorphism and inheritance mapping.
|
Integrating Struts, Tiles, and JavaServer Faces
Integrating Struts, Tiles, and JavaServer Faces. Bring the power, flexibility, and manageability of the three technologies together.
|
What is Persistence Framework?
What is Persistence Framework?
What is Persistence Framework?
A persistence framework moves the program data in its most natural form (in memory objects) to and from a permanent data store the database. The persistence framework manages the
|
Core Java Interview Questions!
Core Java Interview Questions!
Core Java Interview Questions
Question: What is transient variable?
Answer: Transient variable can't be serialize. For example if a variable is declared as transient in a Serializable class and the class is written
|
Application Servers Available in Market. Web Servers. J2EE server.
Application Servers Available in Market. Web Servers. J2EE server.
Application Servers Available in Market
Before we go into the grater details of the EJB let's look at some of the EJB Application Servers available in the market. Application
|
We are providing Knoppix 3.6 Live Linux CD's
We are providing Knoppix 3.6 Live Linux CD's
Knoppix Linux CD's
Now Available Linux Knoppix 3.6 CD's
What is KNOPPIX?
KNOPPIX is a bootable Linux CD with a collection of various GNU/Linux software. It auto-detects hardware and supports many
|
We are providing Downloadable Version of Mandrake 10.1 Power Pack Linux CD's.
We are providing Downloadable Version of Mandrake 10.1 Power Pack Linux CD's.
Mandrake 10.1 Power Pack Linux
Now Available Mandrake 10.1 Power Pack CD's
Power Pack is a Linux system that will appeal to all advanced users. It's great for Office
|
New Technical Articles: 64-bit Programming on Solaris 10 OS for x86 Platforms
Four technical articles describe the new Sun Studio 10 software's 64-bit programming features on the Solaris 10 OS for x86 and AMD64 platforms. Important issues regarding the AMD64 ABI (Application Binary Interface), debugging, migration to 64-bits, and p
|
Locking Down Server Access to SSH With SunScreen Software (Community Submission)
This Tech Tip shows how to lock down a server to a group of client machines, allowing SSH access only, using SunScreen software.
|
Solaris 10 OS Certification Beta Exams
If you are an expert in system and network administration, you can get involved in the creation of three new Solaris 10 certification exams. These Beta exams count toward official Solaris Certification and allow you to provide comments and technical feedb
|
|
|
|
