Transcript Java - Indiana University

Java
Goals
• A Generic Programming system in Java
• Respect the Spirit of Java
– Use OO techniques for system design
– Use the compile and runtime type systems
– Use reflection for flexibility
• Meet or exceed what is possible with
Java Generics
Definition
“A style of programming that allows algorithms to be
implemented once and used over and over with
arbitrary data types.”
“Object oriented programming empowered types …
Generic Programming empowers algorithms”
Concepts
interface TrivialIterator {
public Object next();
}
interface ForwardIterator extends
TrivialIterator {
public boolean hasNext();
}
Algorithms
static Object find(ForwardIterator first,
EqualityComparable value) {
Object retVal = null, temp;
while(first.hasNext()) {
temp = first.next();
if(value.isEqual(temp)) {
retVal = temp;
break;
}
}
return retVal;
}
Libraries
Vector v = new Vector();
Integer i = new Integer(80), iFind = null;
for(int j=0;j<100;j++) {
v.add(new Integer(j));
}
iFind =(Integer)Algorithms.find(v.iterator(),i);
How
• The Concept Checker design pattern
enables library writers to implement
concise libraries that support compile
and runtime concept checking
• The GenericProxy allows any class that
models a concept to be used with an
algorithm
• The users does not have to do anything
special
Concept Checker Pattern
• Library writers implement two methods
– The concept checker uses runtime type
checking to verify that all arguments model
the concepts and wraps those that don’t
directly implement the interfaces using the
GenericProxy
– The actual algorithm is the implementation
of the algorithm and uses only the concept
arguments, opaque associated types, and
associated concepts
Associated Types
• Opaque
– These are objects that the algorithm
shuttles around but performs no action on.
They are always of type Object.
• Associated Concepts
– These are objects that are provided by the
arguments that the algorithm performs
operations on. They only need to model
the concepts, the algorithm performs the
appropriate runtime checks.
Example
Generic Signature static Object find(Object first, Object value) {
ForwardIterator gfirst;
if(first instanceof ForwardIterator) {
gfirst = (ForwardIterator)first;
} else {
gfirst = (ForwardIterator) GenericProxy.newInstance(first,
ForwardIterator.class);
}
Check Concepts
EqualityComparable gvalue;
if(value instanceof EqualityComparable) {
gvalue = (EqualityComparable)value;
} else {
gvalue = (EqualityComparable) GenericProxy.newInstance(value,
EqualityComparable.class);
}
Call Algorithm
return find(gfirst, gvalue);
}
GenericProxy
Concept c = GenericProxy.newInstance(obj, Concept.class)
• obj is an instance of an object that models Concept
• Concept.class is Concept’s Class object
• newInstance() uses java.lang.reflect.Proxy to
create a new Class at runtime that wraps obj and implements
Concept
• GenericProxy.invoke() is called when a method on the
proxy is called. It in turn calls the method on obj that matches
the Concept’s method
Fill
Additional Concepts
interface Assignable {
public void set(Object obj);
}
interface AssignableForwardIterator
extends ForwardIterator, Assignable { };
Algorithm
static Object fill(AssignableForwardIterator first, Object value) {
while(first.hasNext()) {
*note opaque type
first.next();
first.set(value);
}
return first;
}
Functors
class TestTransform {
Method sumMethod = TestTransform.class.getMethod("sum", new Class[]
{ Integer.class, Integer.class });
Method sumMethod4 = TestTransform.class.getMethod("sum", new Class[]
{ Integer.class, Integer.class, Integer.class, Integer.class });
public static Integer sum(Integer a, Integer b) {
return new Integer(a.intValue() + b.intValue());
}
public static Integer sum(Integer a, Integer b, Integer c, Integer d) {
return new Integer(a.intValue() + b.intValue() +
c.intValue() + d.intValue());
}
}
Functors are simply Method objects. They are retrieved
from a class using Class.getMethod(name, args).
Transform
Vector a = new Vector(), b = new Vector(), c = new Vector();
// Put one value in a
a.add(new Integer(100));
// Initialize b to index values, c with nothing.
Integer one = new Integer(1);
for(int i=0; i < 10; i++) {
b.add(new Integer(i));
c.add(one);
}
Algorithms.transform(new Object[] { a.iterator(), b.iterator() },
c.listIterator(), sumMethod);
// c = {100, 101, 102, 103, 104, 105, 106, 107, 108, 109}
Algorithms.transform(new Object[] { a.iterator(), b.iterator(),
a.iterator(), b.iterator()) },
c.listIterator(), sumMethod4);
// c = {200, 202, 204, 206, 208, 210, 212, 214, 216, 218}
Concept Hierarchy
Graph
EdgeListGraph
IncidenceGraph
VertexListGraph
VertexListAndIncidenceGraph
VertexList And Incidence
And EdgeList Graph
Concepts Easily Build On Each Other Using Interfaces
public interface ConceptVertexListAndIncidenceGraph extends
ConceptVertexListGraph, ConceptIncidenceGraph{}
Need For a Naming Convention
Object Return Types
Concepts as Return Types?
public interface ConceptEdgeListGraph extends ConceptGraph {
Object edges(); // should return Object that implements ForwardIterator
Object source(ConceptGraphEdge e);
Object target(ConceptGraphEdge e);
}
Supporting Retroactive Modeling
for(ConceptForwardIterator v_iter =
forward_iterator.getForwardIterator(g.vertices()); v_iter.hasNext(); )
Hand-Coded Proxy For Speed
Hand-Coding Proxies for Specific Situations
public class iterator_proxy implements ForwardIterator {
myIterator proxyIter;
public iterator_proxy(myIterator iter) {proxyIter = iter;}
public Object next() (return(proxyIter.next());}
public boolean hasNext() {return(proxyIter.hasNext();}
}
Wrapped Class Must Still Model the Concept
Conclusion
Multi-type concepts
Mulitple constraints
Associated type access
Retoractive Modeling
Type aliases
Separate compilation
Implicit instanciation
Concise syntax
Documentation
Via refinement
Opaque/Assc. Concepts
GenericProxy
Not necessary
Yup
Not necessary
Oh yeah