Proposal: Access to Generic Type Parameters at Compile-Time
David Walend
david at walend.net
Mon Mar 16 19:37:22 PDT 2009
I've been hesitating to submit this proposal because I have seen so
few other people push generics as hard as I do. However, the
discussion around method and field literals -- and adding type
parameters to Field and Method -- may make it more relevant than I
first thought.
My test for reflection APIs is using the API to convert between a
class in memory and bytes in a stream. One common corner case is
converting Map<Key,Value>. I often create a simple class for the
chore. If Field becomes parameterized, I'll be using
Field<Map<Key,Value>> in that class, and will perhaps be creating
specialized classes for different Keys and Values. If the Key or Value
types take parameters, the generics will be three layers deep.
Type parameters on methods that return types with their own type
parameters invites developers to wade into the depths of layered
generics. This proposal addresses one of the associated pain points.
I've attempted to write a spec section which I hope is clear. I'm not
sure it's wrong.
What do you think?
Dave
David Walend
david at walend.net
---
Access to Generic Type Parameters at Compile-Time
AUTHOR: David Walend
OVERVIEW
FEATURE SUMMARY:
This feature allows a developer to gain dot access to the type
parameters of type parameters in classes and interfaces, similar to
accessing encapsulated fields in the class, but only in source code.
For example, given Digraph<Node,Edge>, one could declare
Subgraph<ContainerGraph extends Digraph> extends
Digraph<ContainerGraph.Node,ContainerGraph.Edge>.
MAJOR ADVANTAGE: This change will simplify the use of layered generics
and opens the door to richer general purpose code.
MAJOR BENEFIT: This change transfers the rote work of resolving
specified types from the developer to the compiler. Given the
mechanical nature of the task, that is where the work belongs.
MAJOR DISADVANTAGE: Generics in Java are already complex; the Java
Generics FAQ is very large. This change will make it slightly longer,
and require developers to learn one more (relatively intuitive)
detail.
ALTERNATIVES:
1) Do nothing.
2) Full reification, if done well, would provide similar compile-time
language-level access beyond the type specifiers. (This option is one
of the case examples of things too large for project coin.)
3) Diminish generics' prominent position in Java by removing the
compile-time warnings.
4) Remove generics from Java.
EXAMPLES:
My examples are directed graph examples from the JDiraph project on
java.net. The semiring (advanced) example was inspired by Cormen,
Leiserson and Rivest, 26.4. I show what the code looks like in JDK5
first, then with the access to generic type parameters proposed.
---
SIMPLE EXAMPLE: Given interface Digraph<Node,Edge>, define Paths
through the Digraph, a Digraph representing a probalistic transitions
in the dialog, and an instance of Path that represents a conversation.
JDK5 Syntax -- three type specifiers, one of which requires the
developer to match the first two by hand:
interface Path<Node,Edge,ThruGraph extends Digraph<Node,Edge>>
extends Digraph<Node,Edge>
{
Node getHead();
...
}
To use it:
class DialogGraph extends Digraph<Phrase,Double> {...}
//If the developer gets one of these type specifiers wrong,
//it won't compile
//But the right answers already exist in DialogGraph
Path<Phrase,Double,DialogGraph> conversation = ...
With access to the encapsulated type parameters -- The developer's
class has one type parameter and the developer repeats none of the
work that the compiler must do:
interface Path<ThruGraph extends Digraph>
extends Digraph<ThruGraph.Node,ThruGraph.Edge>
{
ThruGraph.Node getHead();
...
}
To use it:
class DialogGraph extends Digraph<Phrase,Double> {...}
//Path requires only one type specifier.
//The compiler determines that Nodes are Phrases
//and Edges are Doubles.
Path<DialogGraph> conversation = ...
ADVANCED EXAMPLE: Semirings and Digraph Minimization Algorithms.
For a problem domain defined by a Digraph, a Semiring defines a
solution domain and a set of four operators: identity, annihilator,
extension and summary. The solution domain is a Digraph with the
original nodes, but edges that label (summarize) relevant subgraphs
of the original digraph. The full solution is an overlay of the
original digraph. One Semiring can be used to determine the digraph's
connectivity. Other Semirings may find shortest path, least path, most
probable path or other labels involving traversing the graph. These
graph minimization algorithms, like Floyd-Warshall, Dijkstra or A*,
are defined in terms of the operators in the Semiring. The same graph
minimization code can be
reused with different semirings.
JDK5 Syntax -- Each layer of the problem domain is exposed. The type
parameter list is monstrous. Getting the type specifiers right is
daunting and the resulting code assaults the eyes.
interface Semiring<Node,
Edge,
Label,
BaseDigraph extends Digraph<Node,Edge>,
LabelDigraph extends
OverlayDigraph<Node,Label,Edge,BaseDigraph>>
{
void summary(Node from,
Node through,
Node to,
LabelDigraph labelDigraph);
...
}
public class FloydWarshall<Node,
Edge,
Label,
BaseDigraph extends Digraph<Node,Edge>,
LabelDigraph extends
OverlayDigraph<Node,Label,Edge,BaseDigraph>,
SRing extends
Semiring<Node,Edge,Label,BaseDigraph,LabelDigraph>>
{...}
To use it:
public class LeastPathSemiring<Node,Edge,BaseDigraph extends
Digraph<Node,Edge>>
implements Semiring <Node,
Edge,
LeastPathLabel,
BaseDigraph,
NextStepDigraph<Node,LeastPathLabel,Edge,BaseDigraph>>
{
public void summary(Node from,Node through,Node
to,NextStepDigraph<Node,LeastPathLabel,Edge,BaseDigraph> labelDigraph)
{...}
...
}
LeastPathSemiring<String,Double,DialogGraph>
shortestLabelsSemiring = new
LeastPathSemiring<String,Double,DialogGraph>(new TestPathMeter());
FloydWarshall<String,
Double,
LeastPathLabel,
DialogGraph,
NextStepDigraph<String,LeastPathLabel,Double,DialogGraph>,
LeastPathSemiring<String,Double,DialogGraph>> floydWarshall
= new FloydWarshall<String,
Double,
LeastPathLabel,
DialogGraph,
NextStepDigraph<String,LeastPathLabel,Double,DialogGraph>,
LeastPathSemiring<String,Double,DialogGraph>>();
With access to the encapsulated type parameters -- Only the outermost
layer of the problem domain is exposed. The type parameter list
collapses to a single parameter. The compiler does the work to get the
type specifiers correct. The code becomes much more readable.
interface Semiring<LabelDigraph extends OverlayDigraph>
{
void summary(LabelDigraph.Node from,
LabelDigraph.Node through,
LabelDigraph.Node to,
LabelDigraph labelDigraph);
...
}
public class FloydWarshall<SRing extends Semiring>
{...}
To use it:
public class LeastPathSemiring<BaseDigraph extends Digraph>
implements Semiring<NextStepDigraph<BaseDigraph,LeastPathLabel>>
{
public void summary(BaseDigraph.Node from,
BaseDigraph.Node through,
BaseDigraph.Node to,
NextStepDigraph labelDigraph)
{...}
...
}
LeastPathSemiring<DialogGraph> shortestLabelsSemiring = new
LeastPathSemiring<DialogGraph>(new TestPathMeter());
FloydWarshall<LeastPathSemiring<DialogGraph>> floydWarshall = new
FloydWarshall<LeastPathSemiring<DialogGraph>>();
DETAILS
SPECIFICATION: A new 4.5.2.1 can hold the changes. Sections 5.1.10,
6.4.1, 6.8.7, 8.1.2, 8.4.4, 8.8.4 and 9.1.2 may all need to be
touched, but seem fine to my inexpert eye.
4.5.2.1
Members and Constructors of Referenced Parameterized Types From
Parameterized Types
Let C be a class or interface declaration with formal type parameters
A1 extends P1,...,An extends Pn.
Let P1..Pn be class or interface declarations, each of which may have
its own formal type parameters B11..B1p, ... Bn1..Bnp.
Let C<T1,Tn> be an invocation of C, where Ti are types (not wildcards)
with parameters Ti<U1..Up>, and Uj are types (not wildcards).
Let m be a member or constructor declaration in C, whose type as
declared is A.B. Then the type of m (see 8.2 and 8.8.6) in the type
C<T1,...,Tn> with Ti<U1..Up> is U[A1.B1 := T1.U1, ..., An.Bp := Tn.Up].
Let m be a member or constructor declaration in D, where D is a class
extended by C or an interface implemented by C. Let D<V1,...,Vk> be
the supertype of C<T1,...,Tn> that corresponds to D. Then the type of
m in C<T1,...,Tn> is the type of m in D<V1,...,Vk>. (Same paragraph as
found in 4.5.2.)
If any of the type arguments to a parameterized type are wildcards,
the type of its members and constructors is undefined.
COMPILATION: This change requires no changes to bytecodes. Erasure
will work as it does now. The type specification resolver within the
compiler will need to map named types to the contained type parameters
instead of just checking the developer's work.
TESTING: This change will require additions to the suite of
generics cases to test. Feel free to pull test cases from JDigraph.
LIBRARY SUPPORT: Existing libraries may remain unchanged or take
advantage of this new feature. Widely implemented interfaces and
extended classes that can not change existing APIs still can not
change existing type parameter lists to take advantage of this feature.
REFLECTIVE APIS: No change.
OTHER CHANGES: Some new examples will be needed in the docs. The
generics FAQ will grow a bit.
MIGRATION: Widely implemented interfaces and extended classes with
complex type specifiers can not change their type parameters. Those
interfaces and classes could be subclassed with adapters. However, few
people have taken advantage of this part of generics' expressive power
to date. Few examples of layered generics exist.
COMPATIBILITY
BREAKING CHANGES: Adding this access is an an additive change. Nothing
will break.
EXISTING PROGRAMS: I'll be able to simplify the semiring package in
JDigraph. See comments in MIGRATION. Existing programs will need no
changes.
REFERENCES
EXISTING BUGS: http://bugs.sun.com/view_bug.do?bug_id=6448707
http://weblogs.java.net/blog/dwalend/archive/2006/05/tilting_at_the_1.html
is probably the best blog.
JDigraph is at https://jdigraph.dev.java.net .
More information about the coin-dev
mailing list