Parametric Polymorphism

To illustrate a very simple example we'll write a class that stores an element (source: StoreSomething.pizza):

class StoreSomething<A> {
     A something;

     StoreSomething(A something) {
         this.something = something;
     }

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

     A get() {
         return something;
     }
}

StoreSomething<String> a = new StoreSomething("I'm a string!");
StoreSomething<int> b = new StoreSomething(17+4);

b.set(9);

int i = b.get();
String s = a.get();

You might say we could have done it using Java's Object class. In that case we wouldn't be able to store a variable of Java's basic types (as int). Furthermore we would be forced to use several type casts to get the correct types when we use the get() method.

We can extend this class as any other Java class:

class StoreString extends StoreSomething<String> { 
    StoreString(String something) {
        super(something);
    }
}

class StoreSomething2<A> extends StoreSomething<A> {

    StoreSomething2(A something) {
        super(something);
    }

    void print() {
        System.out.println(""+something);
    }
}

Ok, ok the StoreSomething class is not really helpfull. Let's write a class to store two bits of data:

public class Pair<A, B> {

    public A fst;
    public B snd;

    public Pair(A fst, B snd) {
        this.fst = fst;
        this.snd = snd;
    }
}

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

All the things we did to classes can also be done to interfaces. As an example we consider this interface to sets of elements of a parameterised type:

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

A common implementation of a set is a linked list storing the elements. To implement the funcionality of a set we'll use two classes: EmptyList to represent a list without any elements and NonEmptyList. Both extend this abstract list class (source: Polymorph.pizza):

     abstract class LinkedList<A> implements Set<A> {

         public abstract boolean contains(A x);

         public LinkedList<A> insert(A x) {
             if (contains(x)) return this;
             else return new NonEmptyList(x, this);
         }

         public Set<A> include(A x) {
             return insert(x);
         }
     }

     class EmptyList<A> extends LinkedList<A> {

         public boolean contains(A x) {
             return false;
         }
     }

     class NonEmptyList<A> extends LinkedList<A> {

         private A elem;
         private LinkedList<A> rest;

         public NonEmptyList(A elem, LinkedList<A> rest) {
             this.elem = elem;
             this.rest = rest;
         }

         public boolean contains(A x) {
             return ((Object)elem).equals((Object)x) || 
             rest.contains(x);
         }
     }

As an example for the usage we consider this program which tests whether its first command line argument is repeated in subsequent arguments.

     public class TestForDuplicates {

         public static void main(String[] args) {
             Set<String> set = new EmptyList();
             for (int i = 1; i < args.length; i++)
                 set = set.include(args[i]);
             System.out.println(set.contains(args[0]));
         }
     }

So we set up an interface to wich we'll bind our parameter types:

     interface Comparable {
         boolean equals(Object x);
         boolean less(Object x);
     }

     interface Set<A implements Comparable> {
         boolean contains(A x);
         Set<A> include(A x);
     }

Our implementation of trees consists again of an abstract class, a class for empty trees and a class for non-empty trees (source: Bounded.pizza):

     abstract class Tree<A implements Comparable>
                                    implements Set<A> {
         public abstract boolean contains(A x);
         public abstract Tree<A> insert (A x);

         public Set<A> include(A x) {
             return insert(x);
         }
     }

     class EmptyTree<A implements Comparable> extends Tree<A> {
         public boolean contains(A x) {
             return false;
         }
         public Tree<A> insert(A x) {
             return new Branch(x, this, this);
         }
     }


     class Branch<A implements Comparable> extends Tree<A> {
         A elem;
         Tree<A> left;
         Tree<A> right;
         
         public Branch(A elem, Tree<A> left, Tree<A> right) {
             this.elem = elem;
             this.left = left;
             this.right = right;
         }

         public boolean contains(A x) {
             if (x.less(elem)) 
                 return left.contains(x);
             else if (elem.less(x))
                 return right.contains(x);
             else // we assume total ordering, therefore x.equals(elem)
                 return true;
         }

         public Tree<A> insert(A x) {
             if (x.less(elem)) 
                 return new Branch(elem, left.insert(x), right);
             else if (elem.less(x))
                 return new Branch(elem, left, right.insert(x));
             else // we assume total ordering, therefore x.equals(elem)
                 return this;
         }
     }

     class ComparableString implements Comparable {

         private String s;

         ComparableString(String s) {
             this.s = s;
         }

         public boolean less(Object other) {
             if (other instanceof ComparableString) 
                 return s.compareTo(((ComparableString)other).s) < 0;
             else
                 throw new Error("can't compare to non-strings");
         }
     }

     public class TestForDuplicates {

         public static void main(String[] args) {
             Set<ComparableString> set = new EmptyTree();
             for (int i = 1; i < args.length; i++)
                 set.include(new ComparableString(args[i]));
             System.out.println(
                 set.contains(new ComparableString(args[0])));
         }
     }

F-bounded Polymorphism

     interface Comparable<A> {
         boolean less(A x);
     }

     interface Set<A implements Comparable<A>> {
         boolean contains(A x);
         Set<A> include(A x);
     }

class ComparableString implements Comparable<ComparableString> {

    private String s;

    ComparableString(String s) { this.s = s; }

    public boolean less(ComparableString other) {
        return s.compareTo(other.s) < 0;
    }
}

Polymorphic Functions

Sometimes, it is neccessary to also have polymorphic static functions. Or, one wants a dynamic method which is polymorphic independently of any type parameters. This can be done by prefixing the method return type with a type-variable section:

     class TreeUtils {
         static <A implements Comparable<A>> 
             Tree<A> insertArray(Tree<A> tree, A[] elems) {

             for (int i = 0; i < elems.length; i++)
                 tree = tree.insert(elems[i]);
             return tree;
         }
     }

Implementing parametric types

• Two translations are possible
• The homogeneous translation map type variables to Objects and inserts appropriate casts.
• The heterogeneous translation creates many instances of a parameterised class, one for each instance type.
• Pizza is designed so that any of the two translations can be used.
• Both translations are explained in more detail in the language definition and the Paper "Two ways to bake your Pizza" which you'll find on the Pizza papers page.
• The homogeneous translation effectively erases type information.
• This leads to a couple of restrictions on the uses of parameterised types.
• In the current Pizza compiler the homogeneous translation is used only!
• Future versions of Pizza will include more type information, using some of the features of Java's reflection API, so that the restrictions can be lifted.

Restrictions on parametric types

• The target type of a coercion must be a Java type -- no type parameters allowed
• OK:
(Tree)object which is of type Tree<A>, for some unknown type variable A.
• Not OK:
(Tree<int>)object

• The element type of an array creation expression new T[...] must also be a Java type.
• OK:
new Tree[10] This allocates an array of 10 trees. Their element type is determined by the context.
• Not OK:
new A[10] where A is a type variable.

First class functions

With first class functions we can avoid the effort of wrapping classes to make them implement a special interface. We define all the functions we need to be passed as parameters to our methods. (Yes, we pass a function as parameter to a function!)

The syntax for function types is:
(argtype, ..., argtype) -> resulttype.

Or, if exceptions are thrown by the function:
(argtype, ..., argtype) throws exception, ..., exception -> resulttype.

Any method with a matching signature may be substituted for a function parameter. So a function boolean doIt(int, String) matches (int, String) -> boolean or int read(InputStream) throws IOException matches (InputStream) throws IOException -> int.

As an example we consider the compareTo() method of the Java class String. This method compares to Strings lexically and case sensitve. Now we want to sort Strings. We want to change the behaviour of the sorting by providing the function that compares to Strings:

class PrintSortedStrings {

    static void print(String[] args, (String, String) -> int compare) {
        ....
        if (compare(args[i], args[j]) > 0) 
        ....
    }
}

int myCompare(String s1, String s2) {
    return s1.compareTo(s2);
}

int myCompareNoCase(String s1, String s2) {
    return s1.toLowerCase().compareTo(s2.toLowerCase());
}

String[] myStrings = { "These", "Strings", "will", "be", "sorted", "!"};
PrintSortedStrings.print(myStrings, myCompare);
PrintSortedStrings.print(myStrings, myCompareNoCase);

The use of first class functions becomes much more important if you are using parametric polymorphism.

So we go back to our tree example. We needed the method less which was introduced via an interface. We now refine our class Tree to take a function as parameter to the methods contains and insert:

abstract class Tree<A> {
    public abstract boolean contains((A,A)->boolean less, A x);
    public abstract Tree<A> insert((A,A)->boolean less, A x);
}

    public boolean contains((A, A) -> boolean less, A x) {
        if (less(x, elem)) 
            return left.contains(less, x);
        else if (less(elem, x))
            return right.contains(less, x);
        else // we assume total ordering, therefore x.equals(elem)
            return true;
    }

class Branch<A> extends Tree<A> {
    A elem;
    Tree<A> left;
    Tree<A> right;
    
    public Branch(A elem, Tree<A> left, Tree<A> right) {
        this.elem = elem;
        this.left = left;
        this.right = right;
    }

    public boolean contains((A, A) -> boolean less, A x) {
        if (less(x, elem)) 
            return left.contains(less, x);
        else if (less(elem, x))
            return right.contains(less, x);
        else // we assume total ordering, therefore x.equals(elem)
            return true;
    }

    public Tree<A> insert((A, A) -> boolean less, A x) {
        if (less(x, elem)) 
            return new Branch(elem, left.insert(less, x), right);
        else if (less(elem, x))
            return new Branch(elem, left, right.insert(less, x));
        else 
            return this;
    }
}

class StringBranch extends Branch<String> {

    StringBranch(String elem, Tree<String> left, Tree<String> right) {
        super(elem, left, right);
    }

    private static boolean stringLess(String x, String y) {
        return x.compareTo(y) > 0;
    }

    public boolean contains(String x) {
        return contains(stringLess, x);
    }

    public Tree<String> insert(String x) {
        return insert(stringLess, x);
    }
}

interface Set<A> {
    boolean contains(A x);
    void include(A x);
}

class TreeSet<A> implements Set<A> {
    private (A, A) -> boolean less;
    Tree<A> elems = new EmptyTree();

    public TreeSet((A, A) -> boolean less) {
        this.less = less;
    }
    public boolean contains(A x) {
        return elems.contains(less, x);
    }
    public void include(A x) {
        elems = elems.insert(less, x);
    }
}

public class TestForDuplicates {

    static boolean stringLess(String x, String y) {
        return x.compareTo(y) < 0;
    }

    public static void main(String[] args) {
        Set<String> s = new TreeSet(stringLess);
        for (int i = 1; i < args.length; i++)
            s.include(args[i]);
        System.out.println(s.contains(args[0]));
    }
}

Anonymous Functions

Pizza's syntax to define an anonymous function is:

fun(arguments) -> resulttype { statements }

public class TestForDuplicatesAnonymous {

    public static void main(String[] args) {
        Set<String> s = 
          new TreeSet(
            fun(String x, String y) -> boolean { 
              return x.compareTo(y) < 0; 
            }
          );
        for (int i = 1; i < args.length; i++)
            s.include(args[i]);
        System.out.println(s.contains(args[0]));
    }
}

As a short example we consider an incrementer which will return consecutive integer values on each call. We can easily instantiate several counters of this kind:

      () -> int makeIncr() {
          int count = 0;
          return fun() -> int {
              return count++;
          }
      }

     () -> int incr1 = makeIncr();
     () -> int incr2 = makeIncr();
     System.out.println(
          incr1() + " " + incr1() + " " + incr2() + " " + incr1());

We could also write incrementers with a startvalue as parameter:

      () -> int makeIncr(int start) {
          int count = start;
          return fun() -> int {
              return count++;
          }
      }

The following function applies a given function in infix order to all elements of a binary tree.

void <A> traverse(Tree<A> t, (A)->void proc) {
    if (t instanceof Branch) {
        Branch b = (Branch)t;
        traverse(b.left, proc);
        proc(b.elem);
        traverse(b.right, proc);
    }
}

int sum(Tree<int> t) {
    int n = 0;
    traverse(t, fun(int x) -> void { n += x; });
    return n;
}

Algebraic Data Types

But if we want to examine a structure (like our List) from outside we need to use type tests and type casts (like in the traverse example in the last section).

Pizza gives us an easy to use syntax to avoid the complicated abstract class/concrete cases construction: algebraic data types

In Pizza class can contain declarations of these forms:

case ident(arguments);
case ident;

class Tree<A> implements Set<A> {
    case Empty;
    case Branch(A elem, Tree<A> left, Tree<A> right);
}

To instantiate a tree with three elements we can write:

Tree<int> t = Tree.Branch(2,
     Tree.Branch(1, Tree.Empty, Tree.Empty),
     Tree.Branch(3, Tree.Empty, Tree.Empty));

import Tree.*;

class Tree<A> {
    case Empty;
    case Branch(A elem, Tree<A> left, Tree<A> right);
}

public class Test {
    public static void main(String[] args) {
        Tree<int> t = Branch(2,
            Branch(1, Empty, Empty),
            Branch(3, Empty, Empty));
    }
}

Pattern matching

Tree<String> t = ... ;
String s;
if (t instanceof Branch) {
    s = (Branch)t.elem;
} else {
    s = "(empty)";
}

class Tree<A> {
    case Empty;
    case Branch(A elem, Tree<A> left, Tree<A> right);

    public boolean contains((A, A) -> boolean less, A x) {
        switch (this) {
        case Empty:
            return false;
        case Branch(A elem, Tree<A> l, Tree<A> r):
            if (less(x, elem)) 
                return l.contains(less, x);
            else if (less(elem, x))
                return r.contains(less, x);
            else 
                return true;
        }
    }

    public Tree<A> insert((A, A) -> boolean less, A x) {
        switch (this) {
        case Empty:
            return Branch(x, Empty, Empty);
        case Branch(A elem, Tree<A> l, Tree<A> r):
            if (less(x, elem)) 
                return Branch(elem, l.insert(less, x), r);
            else if (less(elem, x))
                return Branch(elem, l, r.insert(less, x));
            else 
                return this;
        }
    }
}

In the matching patterns we can replace parameters we don't want to access with a single '_':

    Tree<A> goRight() {
        switch (this) {
        case Empty:
            return this;
        case Branch(_, _, Tree<A> r):
            return r.goRight();
        }
    }

Deep pattern matching

    static <A,B> List<C> mapPairs((A,B)->C f, List<A> xs, List<B> ys) {

        List<C> result;
        switch (Pair.Pair(xs, ys)) {
        case Pair(List.Nil, _):
        case Pair(_, List.Nil):
            result = List.Nil;
            break;
        case Pair(List.Cons(A x, List<A> xs1),
                  List.Cons(B y, List<B> ys1)):
            result = List.Cons(f(x, y), mapPairs(f, xs1, ys1));
            break;
        case _: System.out.println("case 2"); break;
        }
        return result;
    }

Special case: Classes with a single constructor

class Pair<A,B> {
    case Pair(A fst, B snd);
}

class Pair<A,B> {
    A fst;
    B snd;
    Pair(A fst, B snd) {
        this.fst = fst;
        this.snd = snd;
    }
}

Special case: Enums

class Color {
    case Red;
    case Green;
    case Blue;

    String toString() {
        switch (this) {
        case Red: return "Red";
        case Green: return "Green";
        case Blue: return "Blue";
        }
    }
}

int basicX;
Integer integerX;
Object objectX;

basicX = (int)integerX;
basicX = (int)objectX;
integerX = (Integer)basicX;
objectX = (Object)basicX;

continue int veryRecursive(int howDeep) {
    if (howDeep == 0) {
        System.out.println("I'm there -- finally!");
        return -1;
    } else return goto veryRecursive(howDeep - 1);
}

Package pizza.lang: