Midterm 2, CSCI 5535, Nov 6th 2002

You have 50 minutes to answer these questions.  Please read all questions before you start.

1. [30 points] This question explores the difference between equality types and polytypes in SML. 
   1. Give an example of a SML function whose argument type would be inferred as a polytype.  Explain why.
   2. Give an example of a SML function whose argument type would be inferred as an equality type. Explain why.
2. [40 points] Consider a record TwoValues implemented as follows:
   TwoValues = {  create: int -> int -> (int*int) = λ(x: int). λ(y: int) . (x,y);
                             getFirst: (int*int) -> int = λ(v: int*int). proj1(v);
                             getSecond: (int*int)->int = λ(v: int*int). proj2(v); }

   In other words, TwoValues is a package for working with two values of integer type.  This package represents the two values as a pair (two-tuple).  Recall that proj1 and proj2 extract the first and second item in the pair respectively.

   1. [10 points] Rewrite TwoValues so that it works on two values of any type (as long as both values are of the same type).  For example, one may want to use it for two strings, rather than two integers.  Your rewrite must be in lambda calculus (i.e., do not use SML).
   2. [20 points] Give lambda-calculus code to hide the fact that TwoValues uses a pair (i.e., int*int) to represent the two values.
   3. [10 points] Combine your answers to (a) and (b) to give am implementation of TwoValues that not only can handle two values of any type but also hides the internal pair representation.
3. [20 points] Give a code fragment that uses inclusion polymorphism that would be hard to do in a language that supports only parametric polymorphism (i.e., universal quantification but not bounded universal quantification).  Explain why.
4. [10 points] Briefly describe how class-based languages and prototype-based languages differ