CS 3723/3721
Programming Languages
Generic Constructs in C++ and Java
|
Introduction:
Generic constructs are part of the larger goal of reuseability
in programming languages: one would like to write code for one project
and then reuse the code on the next project.
For example, it would be nice to implement a stack of one kind of
object, and have the same code work for any object.
As we will see later
in the course during the study of interpreted languages, one often
gets reusability immediately in this setting, but at the cost of
less runtime efficiency. Thus a stack in Lisp can hold any
object with no further work.
For compiled languages, generic constructs are provided in a more
limited fashion, so as to reach a compromise between efficiency
and reusability.
C, by several methods:
There are several methods to fake generic constructs in C,
along with a complex legitimate method.
It is possible to deal with pointers to general objects in C
using void * pointers. The book The C Programming
Language by Kernighan and Ritchie shows a generic quicksort
on page 120.
The quicksort code has a first parameter which is an array of
void * pointers, then two integer parameters
to manage the quicksort, and a final function parameter
which a comparison function, whatever is appropriate for the
specific types being sorted. This is a legitimate method, but is
not widely used because of its complexity.
C++, using templates:
This is the way to get genericity that is simultaneously almost
as fast as the non-generic constructs, and yet is fully generic.
Essentially the compiler lets one make a "textual" substitution
of a typename into a parameter (like a substitution done by a
text editor). After the substitution, the comiler is invoked,
and sees the code as if a specific type in "hard-wired" into the
construct. C++ supports this confusing construct, and Java
may later.
Java, using Objects:
Java allows one to work with collections of arbitrary objects,
and one can determine which object is involved using
the instanceof operator. This does not lead
to reasonable object-oriented programming, as is explained in
the links below:
- Using the Java library Stack class,
which allows a stack of Objects:
.html,
.ps,
.pdf.
Java, using interfaces:
As was explained above, in handling a collection of objects of
different types, there needs to be a common operation that one
wants to perform on each of the objects. Thus for each type
involved, you need a common function, given the same name.
Providing code for this common function is what Java refers to
as "implementing an interface" that contains the common function.
The one can call the function given a pointer to any of the types
implementing the interface, so that no code change is needed
to add another object to the collection.
- Comparison of list of ints with list of
Comparables:
.ps,
.pdf.
- The generic list code above, along with 3 mains using it:
.html,
.ps,
numbered .ps,
.pdf,
numbered .pdf.
- Using exactly the same list code with a user-defined type
(Rational:
.html,
.ps,
.pdf,
small .ps,
small .pdf.
New generic features in Java:
The next release of the Java is adding
generic features, which behave somewhat like those in C++.
Here is a writeup describing the new features:
Catching more errors at compile time with Generic Java:
A proposal to add parametric types to the Java language.
This particular reference is old, and I haven't yet studied
these new features.
For more on Generic Java, see Eric Allen's four-part series,
Diagnosing Java code: Java generics without the pain:
-
Part 1 introduces generic types and support features.
-
Part 2 discusses extension limitations and implementation strategies.
-
Part 3 examines adding support for new operations.
-
Part 4 looks at adding support for mixins through generic types.
Revision date: 2004-10-22.
(Please use ISO 8601,
the International Standard Date and Time Notation.)