Name:

SE580 final exam: Autumn 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) Self types (also known as myType).

Question 1 continued

Question 2 (20 points)

In order to multiply two matrices together, we need to be able to add two matrix elements together, and to multiply two matrix elements together. A sample interface for immutable matrices in Java is:

  interface MatrixElement {
    public MatrixElement times (MatrixElement x);
    public MatrixElement add (MatrixElement x);
  }
  interface Matrix {
    public int height ();
    public int width ();
    public MatrixElement get (int i, int j);
    public Matrix set (int i, int j, MatrixElement x);
    public Matrix times (Matrix m);
  }
  interface MatrixFactory {
    public Matrix build (int i, int j, MatrixElement x);
  }

a) What is the binary method problem?

b) Explain why the MatrixElement 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 (15 points)

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

a)

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



b)

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



c)

  interface Bar [contravariant type a] {
    method setFoo (x : Foo[a]);
  }
  interface Foo [covariant type a] {
    method setBar (x : Bar[a]);
  }



d)

  interface Bar [invariant type a] {
    method setFoo (x : Foo[a]);
  }
  interface Foo [covariant type a] {
    method setBar (x : Bar[a]);
  }



e)

  interface Foo [contravariant type a] {
    method setFooFoo (x : Foo[Foo[a]]);
    method getFooFooFoo () : Foo[Foo[Foo[a]]];
  }

Question 4 (20 points)

Generic Java supports impredicative polymorphism, where Hobbes supports predicative polymorphism.

a) What is predicative polymorphism?

b) Give an example program which demonstrates predicative polymorphism.

c) What is impredicative polymorphism?

d) Give an example program which demonstrates impredicative polymorphism.

e) Give one advantage and one disadvantage of a language supporting impredicative polymorphism.

Question 4 continued

Question 5 (25 points)

Consider the following program:

  interface Point {
    method getX () : Integer;
    method getY () : Integer;
    method moveX (x : Integer) : myType;
    method moveY (y : Integer) : myType;
  }
  interface PointFactory [type point] {
    method setX (p : point, x : Integer) : point;
    method setY (p : point, y : Integer) : point;
  }
  class PointImpl {
    field factory : PointFactory [myType];
    field x : Integer;
    field y : Integer;
    method getX () : Integer { return this.x; }
    method getY () : Integer { return this.y; }
    method moveX (x : Integer) : myType {
      return this.factory.setX (this, this.x + x);
    }
    method moveY (y : Integer) : myType {
      return this.factory.setX (this, this.x + x);
    }
  }
  class PointFactoryImpl implements PointFactory[PointImpl] {
    method setX (p : PointImpl, x : Integer) {
      return new PointImpl { x=x, y=p.y };
    }
    method setY (p : PointImpl, y : Integer) {
      return new PointImpl { x=p.x, y=y };
    }
  }
  interface ColoredPoint extends Point {
    method getColor () : Color;
    method setColor (c : Color) : myType;
  }
  interface ColoredPointFactory [type point] extends PointFactory[point] {
    method setColor (p : point, c : Color) : point;
  }

Question 5 continued

a) Complete the following class definition:

  class ColoredPointImpl extends PointImpl implements ColoredPoint {























  }

b) Complete the following class definition:

  class ColoredPointFactoryImpl implements ColoredPointFactory[ColoredPointImpl] {























  }

Question 5 continued

c) In the definition of the interfaces Point and ColoredPoint, is myType used covariantly, contravariantly or invariantly? Give a one- or two-sentence explanation for your answer.

d) In the definition of the classes PointImpl and ColoredPointImpl, is myType used covariantly, contravariantly or invariantly? Give a one- or two-sentence explanation for your answer.

e) Give an example of why Hobbes requires interfaces to use myType covariantly.

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.