Name:

SE580 final exam: Winter 2001-2002

Answer all questions.

Time allowed: 2 hours

Total number of points: 100

Question 1 (15 points)

Give a one- or two-sentence definition of:

a) Subtyping.

b) Subclassing.

c) Covariance.

d) Contravariance.

e) Invariance.

Question 1 continued

Question 2 (20 points)

In order to implement a sorted binary tree in Java, we need to implement a Comparable interface:

  interface Comparable {
    public int compareTo (Comparable other);
  }
  class Integer implements Comparable ...
  class Float implements Comparable ...
  class SortedBinaryTree {
      void insert (Comparable x) ...
      int size () ...
      Comparable get (int index) ...
  }

a) What is the binary method problem?

b) Explain why the Comparable interface suffers from the binary method problem.

c) What is F-bounded polymorphism?

d) Translate the above interfaces into a language which supports F-bounded polymorphism (such as Generic Java or Hobbes).

Question 2 continued

Question 3 (20 points)

Which of the following declarations type-checks? In each case, give a one- or two-sentence explanation for your answer.

a)

  interface Foo[type a] {
    method get () : a;
  }







b)

  interface Foo[type a] {
    method get () : a;
  }
  interface Bar[type b] extends Foo[b] {
    method get () : b;
  }








c)

  interface Foo [type a] {
    method set (x : B[a]);
  }
  interface Baz [type a] extends Foo[a] {
    method set (x : A[a]);
  }
  interface A [type a] { }
  interface B [type a] extends A[a] { }







Question 3 continued

d)

  interface Foo [type a] {
    method set (x : A[a]);
  }
  interface Baz [type a] extends Foo[a] {
    method set (x : B[a]);
  }
  interface A [type a] { }
  interface B [type a] extends A[a] { }







e)

  interface Foo [type a] {
    method set (x : B[B[a]]);
  }
  interface Baz [type a] extends Foo[a] {
    method set (x : A[A[a]]);
  }
  interface A [type a] { }
  interface B [type a] extends A[a] { }







f)

  interface Foo [type a] {
    method set (x : B[B[a]]);
  }
  interface Baz [type a] extends Foo[a] {
    method set (x : A[B[a]]);
  }
  interface A [type a] { }
  interface B [type a] extends A[a] { }







Question 4 (20 points)

The type rules for type-checking field overriding is:

a) Give an example program showing a correct use of the type rule for overriding immutable fields, demonstrating the use of covariant immutable field overriding.

b) Give an example program showing an incorrect use of the type rule for overriding mutable fields, demonstrating that covariant mutable field overriding can lead to a type-unsafe language.

Question 4 continued

Question 5 (20 points)

Consider the following program:

  class Person {
    field name : String;
    method equals (p : myType) : Boolean {
      return this.name == p.name;
    }
  }
  class Student {
    field id : Integer;
    method equals (p : myType) : Boolean {
      return this.name == p.name && this.id == p.id;
    }
  }
  interface Cloner [type a] {
    method clone (x : a) : a;
  }
  class PersonFactory implements Cloner[Person] {
    method build (name : String) : Person {
      return new Person { name=name };
    }
    method clone (p : Person) : Person {
      return new Person { name=p.name };
    }
  }

a) What is a self type (myType in this example).

b) Why are self types useful?

c) Give an example program which shows that self types are not type safe when subclassing implies subtyping.

d) Write an extension of the Person class and the PersonFactory class which adds an extra method method clone () : myType to Person. Hint: add an extra field cloner : Cloner[myType] to the Person class.

Question 5 continued

Question 6 (5 points)

a) What was your favorite topic in this course?

b) What was your least favorite topic in this course?

c) If you could add one topic to this course, what would it be?

Worksheet

You can use this sheet as scrap paper.

Worksheet

You can use this sheet as scrap paper.

Worksheet

You can use this sheet as scrap paper.

Worksheet

You can use this sheet as scrap paper.