CSE 341 -- Pizza

Java's type rules

A brief recap: remember Java's rules for type compatibility. If B is a subtype of A, then we can use an object of type B anywhere that we expect something of type A. For example:
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.

Parametric Polymorphism

Recall that Miranda's type system allows one to declare types such as
[*] -> [*] -> [*]
(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);

Java Arrays

Java arrays are an exception to this otherwise bleak situation: rather than just being able to declare arrays of Object, one can declare an array of ints, Points, etc. (Note that this works both for primitive types and for objects.) Java checks that you are putting the right kind of object or type into the array, and knows that you're getting the same type out. For example:
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 Point
Alas, 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.)

Pizza - Key ideas

Of these, parametric polymorphism is the most important, and also appears also in GJ, a successor language extension that takes care to be upwardly compatible with Java. (The Pizza collection classes aren't compatible with the Java ones.) Higher-order functions are less important now that inner classes are a part of Java; and algebraic data types have dropped away as well.

It looks like GJ-style parametric polymorphism will be supported in a future version of Java itself.

Pizza - Parametric Polymorphism

class Cell<A> {
   A contents;

   // the constructor
   Cell(A contents) {
      this.contents = contents;
   }

   void set(A contents) {
      this.contents = contents;
   }

   A get() {
      return contents;
   }
}

Using Cell

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();

Multiple type parameters

public class TwoTypes<A, B> {
   public A first;
   public B second;

   public TwoTypes(A first, B second) {
      this.first = first;
      this.second = second;
   }
}

Using this class to return two values:

TwoTypes<String, int> getValues() {
   return new TwoTypes(aString, anInt);
}

Interfaces

All the things we did to classes can also be done to interfaces.

Interface to sets of elements of a parameterised type:

interface Set<A> {
   boolean contains(A x);
   Set<A> union(Set<A> s);
}

Implementation

Pizza compiles to Java. Two translations: heterogenous and homogeneous.

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)

F-Bounds

Suppose that we want to define an interface Ord for objects that can be compared using less. We want to have a class OrdInt and another class OrdString that implement this interface. Further, we want to be able to compare two OrdInts (ordered integers), and two OrdStrings -- but not to compare an OrdInt with an OrdString. And finally, we want to check that we're using the classes correctly at compile time -- no casts or runtime type checks.

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);
  }

}

Recap: Higher-Order Functions in Miranda

To double every element of a list, we could define a double function:
double :: num->num
double x = 2*x
and 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)

Pizza - Higher-Order Functions

Here is the example from the Pizza paper:
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"

Relation to Inner Classes

In more recent versions of Java, we can do much the same thing using inner classes. (This example is stored on ceylon on ~borning/java/Radix.java if you want to try it.)
/* 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