CSE 505 - Pizza

Java Recap

Java features particularly relevant to this work: I'll assume you know this material already, or can learn it on your own.

Parametric Polymorphism

Haskell's type system allows one to declare types such as 
[a] -> [a] -> [a]
(the type of the append function).

You can't do this in Java, which 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.

Pizza - Key ideas

Of these, parametric polymorphism is the most important, and appears also in GJ, a successor language extension that takes care to be upwardly compatible with Java; and in NextGen, a closely related language, which requires VM changes to be supported. Higher-order functions are less important now that inner classes are a part of Java.

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 Pair<A, B> {
   public A first;
   public B second;

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

Using this class to return two values: 

Pair<String, int> getValues() {
   return new Pair(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? Answer this question first assuming Java's subtyping rules (equivariance with overloading) , and then assuming the contravariant rule.

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?)

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", linked from the optional reading list. 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 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);}
}
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 Haskell

To double every element of a list, we could define a double function: 
double :: Integer -> Integer
double x = 2*x
and then use it to double every element in a list: 
map double [1,2,3,4,5]
Or we could use an anonymous function: 
-- double every element of a list
map (\x -> 2*x) [1,2,3,4,5]
These versions of the member function illustrates the use of non-local variables in a function: 
my_member a x = or (map (==a) x)

-- or another (clunkier) version, with a lambda:
my_member a x = or (map (\b -> a==b) 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, r is a free variable, and n is an instance variable.

Calling new Radix().test() returns: 

"true false 2"

In more recent versions of Java, we can do much the same thing using inner classes: 

class Radix {
   int n = 0;

   public class TestChar {
      int r;
      TestChar(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;
   }
}
Calling new Radix().test() should return the same thing.