Proposal: Access to Generic Type Parameters at Compile-Time (original) (raw)

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 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 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 { void summary(LabelDigraph.Node from, LabelDigraph.Node through, LabelDigraph.Node to, LabelDigraph labelDigraph); ... }

public class FloydWarshall {...}

To use it:

public class LeastPathSemiring implements Semiring<NextStepDigraph<BaseDigraph,LeastPathLabel>>

 {
     public void summary(BaseDigraph.Node from,
                         BaseDigraph.Node through,
                         BaseDigraph.Node to,
                         NextStepDigraph labelDigraph)
     {...}
     ...
 }

 LeastPathSemiring<DialogGraph> shortestLabelsSemiring = new

LeastPathSemiring(new TestPathMeter());

 FloydWarshall<LeastPathSemiring<DialogGraph>> floydWarshall = new

FloydWarshall<LeastPathSemiring>();

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