Object a; Point p = new Point(10,20); Point q; a = p; // legal since a point is a kind of an object q = a; // NOT LEGAL (since the compiler only knows that a is of type Object)Similarly, if we had a method that expects an object as a parameter, we can pass it a Point, a String, or any other object.
[*] -> [*] -> [*](the type of the append function).
The user can't declare types of this sort in Java. This leads to less precise type declarations, less machine-checkable documentation, and more runtime casts. For example, the built-in collection classes in Java (Set, ArrayList, etc) all have Object as the type of the contents -- you can't declare that x is a set of strings, or a set of points.
For example, consider the following Java code fragment.
ArrayList a = new ArrayList(); Point p = new Point(10,20); Point q; // add the point p to the arraylist a.add(1,p); // now get the point out of the arraylist and assign it to q // bleah! I know perfectly well that I've only put points into a, but // Java's type system says that the type of a.get(i) is Object. So I // need to put in a cast and have it do a runtime check. q = (Point) a.get(1);
Point[] a = new Point[10]; Point p = new Point(10,20); Point q; a[0] = p; q = a[0]; // no cast needed - we know a[0] is a PointAlas, Java's type checking for arrays is unsound! Bleah again! However, the Java designers were well aware of this problem, and so Java includes a runtime check (so you get an exception, not a crash). Consider:
import java.awt.Point;
class ArrayException {
public static void main(String[] args) {
String[] s;
s = new String[10];
s[0] = "hi there";
test(s);
}
public static void test(Object[] a) {
System.out.println("in test - before storing into a");
a[1] = new Point(10,20);
System.out.println("in test - after storing into a");
}
}
This gives the following result:
in test - before storing into a
Exception in thread "main" java.lang.ArrayStoreException
at ArrayException.test(ArrayException.java:16)
at ArrayException.main(ArrayException.java:11)
So there is even a specialized kind of exception for this situation.
The technical term for the kind of type checking rule that Java uses for arrays (and that has this unsoundness problem) is covariant typing. Two other flavors of type rule are contravariant typing and equivariant typing. These are both sound. (These terms are defined in an optional set of notes on Subtypes in object-oriented languages.)
It looks like GJ-style parametric polymorphism will be supported in a future version of Java itself.
class Cell<A> {
A contents;
// the constructor
Cell(A contents) {
this.contents = contents;
}
void set(A contents) {
this.contents = contents;
}
A get() {
return contents;
}
}
Cell<String> a = new Cell("I'm a string!");
Cell<int> b = new Cell(17+4);
b.set(9);
int i = b.get();
String s = a.get();
public class TwoTypes<A, B> {
public A first;
public B second;
public TwoTypes(A first, B second) {
this.first = first;
this.second = second;
}
}
TwoTypes<String, int> getValues() {
return new TwoTypes(aString, anInt);
}
Interface to sets of elements of a parameterised type:
interface Set<A> {
boolean contains(A x);
Set<A> union(Set<A> s);
}
Heterogenous translation: specialized copy of code for each type (faster, more code)
Homogeneous translation: one copy of code (slower due to wrapping and run-time checks, less code)
First, here is an obvious but unfortunately wrong approach.
interface Ord {
boolean less(Ord o);
}
class OrdInt implements Ord {
private int i;
public int intValue() {return i;}
public boolean less(OrdInt o) {return i < o.intValue();}
}
Alas, the class OrdInt doesn't implement Ord. Mini-exercise:
why not?
So let's try again.
public boolean less(Ord o) {return i < o.intValue();}
Alas and alack, this doesn't do what we want either. (Why not?)
A correct version uses an F-bound (a type variable that appears both as the bounded variable and in the bound).
F-bounded polymorphism was introduced in the paper "F-bounded polymorphism for object-oriented programming." (A pdf file of the paper linked from the Java section of the 341 web, but you aren't expected to read it unless you're interested.) That paper used a very simple model of object-oriented programming. Objects are records (perhaps with both simple and functional types as components) -- no classes, no information hiding, no implementation inheritance. The paper goes on to show how to correctly give types for binary operations, using F-bounds, and shows that the F-bound is the most general possible type bound that gives the correct semantics.
The Pizza version of F-bounded polymorphism follows. Note that in the definition of Pair (taken from the paper), elem appears both as the bounded variable and in the bound.
interface Ord<elem> {
boolean less(elem o);
}
class OrdInt implements Ord<OrdInt> {
int i;
public boolean less(OrdInt o) {return i < o.intValue();}
}
class OrdString implements Ord<OrdString> {
String s;
public boolean less(OrdString o) {return s.stringCompare(o);}
}
class Pair<elem implements Ord<elem>> {
elem x; elem y;
Pair (elem x, elem y) {this.x=x; this.y=y};
elem min() {if (x.less(y)) return x; else return y;}
}
Pair<OrdInt> p = new Pair (new OrdInt(41), new OrdInt(42));
System.out.println(p.min().intValue());
Here's another example. Let's define an interface Translateable for
objects that implement the translate method. Points, rectangles, and
other graphical objects will all be translateable.
translate should take an x and a y and return a
new object of the same type, translated by the desired amount. So
translating a point should return a point, translating a rectangle should
return a rectangle, and so forth.
So this doesn't work:
interface Translateable {
Translateable translate(int dx, int dy);
}
Instead, here's a correct interface and a class that implements it:
interface Translateable<elem> {
elem translate(int dx, int dy);
}
class Point implements Translateable<Point> {
public int x;
public int y;
Point(int x, int y) {
this.x = x;
this.y = y;
}
Point translate(int dx, int dy) {
return new Point(x+dx,y+dy);
}
}
class Rectangle implements Translateable<Rectangle> {
...
}
Point p1,p2;
Rectangle r1,r2;
p1 = new Point(100,200);
p2 = p1.translate(1,1);
r1 = new Rectangle(0,0,100,100);
r2 = r1.translate(20,20);
And another example, of things that have a min method:
interface Minimizable<elem> {
elem min(elem x);
}
class Point implements Minimizable<Point> {
public int x;
public int y;
Point min (Point p) {
return new Point(Math.min(x,p.x),Math.min(y,p.y);
}
}
double :: num->num double x = 2*xand then use it to double every element in a list:
map double [1,2,3,4,5]This version of the member function illustrates the use of non-local variables in a function:
my_member a x = or (map (=a) x)
class Radix {
int n = 0;
(char)->boolean radix(int r) {
return fun (char c)->boolean {
n++; return '0' <= c && c < '0'+r;
};
}
String test () {
(char)->boolean f = radix(8);
return f('0') + " " + f('9') + " " + n;
}
}
In the body of the abstraction (the function), c is a formal
parameter, and r and n are non-local variables.
r is bound to the parameter of the radix method, and
n is bound to the field n of Radix. (These non-local
variables are thus found using the usual lexical scoping rules.)
Evaluating new Radix().test() returns:
"true false 2"
/* illustration of inner classes in Java (this does the same thing in the
example in the Pizza paper of higher-order functions in Java */
class Radix {
int n = 0;
/* TestChar is an inner class, inside of Radix, and the name TestChar
is not visible outside of Radix */
class TestChar {
int r;
TestChar(int r) {
this.r = r;
}
public boolean test(char c) {
n++;
return '0' <= c && c < '0'+r;
}
}
String test () {
TestChar f = new TestChar(8);
return f.test('0') + " " + f.test('9') + " " + n;
}
public static void main(String[] args) {
Radix r = new Radix();
System.out.println(r.test());
}
}
Evaluating new Radix().test() returns the same thing:
"true false 2"
When we compile this, we get two .class files:
Radix.class Radix$TestChar.class
Note that there are some interesting interactions between inner classes and static scoping. The class TestChar is within the scope of Radix - so from elsewhere in the package, this name is not known. (So for one thing, you avoid cluttering up the name space.) Also, since it is not declared as static, it is allowed to reference the instance field n -- if it were declared as static, it couldn't reference n.
Inner classes provide a clean way to implement iterators in Java. One can define the iterator as an inner class, so that it gets access to all of the fields of the collection, and so that its name doesn't clutter up the namespace. For example, if we were defining a class MySet, we could define an inner class MySetIterator inside of MySet. The class MySetIterator would implement the Iterator interface, and would have full access to the fields of MySet. The iterator method of MySet would have a return type of Iterator (that interface is known outside of MySet, even though MySetIterator isn't).
Here is an example:
/* illustration of using inner classes to implement iterators */
import java.util.*;
class MyArray {
Object[] a;
/* the constructor */
public MyArray (int size) {
a = new Object[size];
}
/* get an element */
public Object at (int i) {
return a[i];
}
/* set an element */
public void set (int i, Object value) {
a[i] = value;
}
class MyIterator implements Iterator {
int index;
MyIterator () {
index = 0;
}
public Object next () {
Object temp;
temp = a[index];
index++;
return temp;
}
public boolean hasNext () {
return index<a.length;
}
public void remove () {
/* dummy method for now */
}
}
public Iterator iterator () {
return new MyIterator();
}
/* simple test method. Make a MyArray with 2 elements, and print
them out */
public static void main(String[] args) {
MyArray m = new MyArray(2);
m.set(0,"first");
m.set(1,"second");
for (Iterator i = m.iterator(); i.hasNext();) {
System.out.println(i.next());
}
}
}
This prints
first second