CSC123 : Pizza Assignment

            Due Tuesday before Thanksgiving break.


Please write the following programs in Pizza.  The sample program
"plain.pizza" has compilation instrutions.  Use lots of napkins; don't
make a mess.

1.  Looking at the code for polymorphic linked lists I gave you,
    define a type for polymorphic binary trees. You can choose to
    use either null pointers or a single static (shared) nil node
    to represent the leafs of the tree.  

    Also define polymorphic methods to:
 
       a. print the tree in a post-order traversal
       b. find depth of the tree (length of longest branch).  
         : algorithm hint: recursively find the longest branches
           of the left and right subtrees.

2.  This part requires another ability that Pizza adds to Java:
    static polymorphic functions and the ability to inline functions.
    Given two functions: f of type B->C and g of type A->B, their
    composition F o G is defined as FoG(x) = F(G(x)).  The type of the
    composed function is naturally A->C.  Write a (static) polymorphic
    pizza function that takes two functions and return a *function* 
    that represents their composition.

    public static <A,B,C> ...

3. (optional) The S combinator is lambda x. lambda y. lambda z. (x z) (y z).

What is the generic type of this function?  It is possible to derive it's
type.  Let me show you the first few steps:

  Since there are 3 lambdas in front, we know that the form of the
type is generally  a -> b -> c -> d   (-> associates to the right) and
that x:a (x has type a), y:b, and z:c.

but x is applied to z, so a = c->e  for some e (remember z has type c).

similary, y is applied to z, so b = c->f for some f.

At this point, we know that:

x : c -> e
y : c -> f
z : c

So the entire term S has a type of the *form*

(c->e) -> (c->f) -> c -> d

But we're not done.  There are still other contraints that can be applied
to further pin down the type.  Derive the general type of S, and 
write it as a (static) polymorphic function in Pizza.  The type you 
derive is going to be a true proposition (a tautology), which the 
temporary form above is not.