Name:

SE580 final exam: Practice Exam

Answer all questions.

Time allowed: 2 hours

Total number of points: 100

Question 1 (10 points)

Give a one- or two-sentence definition of:

a) Subtyping.

b) Subclassing.

c) Generics.

d) Type variables.

e) Covariant type variables.

Question 2 (15 points)

a) What is the binary method problem?

b) What is F-bounded polymorphism?

c) Give an example of how F-bounded polymorphism can be used to solve the binary method problem.

d) What is predicative (as opposed to impredicative) polymorphism? Does Hobbes support impredicative polymorphism? Does Generic Java?

Question 3 (10 points)

Consider the following type declarations:

  interface Maybe[covariant type a] {
    method get () : a;
    method isNull () : Boolean;
  }
  interface List[covariant type a] {
    method head () : a;
    method tail () : List[a];
    method accept (v : ListVisitor[a]);
  }
  interface ListVisitor[contravariant type a] {
    method visitEmpty ();
    method visitCons (hd : a, tl : List[a]);
  }
  interface Factory[covariant type a] {
    method build () : a;
  }
  interface Shape { ... }
  interface Triangle extends Shape { ... }
  interface Rectangle extends Shape { ... }

Which of the following are true? In each case, give a one- or two-sentence explaination for your answer.

a) List[Triangle] <: List[Shape]

b) List[Triangle] <: List[Rectangle]

c) Maybe[List[Triangle]] <: Maybe[List[Shape]]

d) List[ListVisitor[Triangle]] < List[ListVisitor[Shape]]

e) ListVisitor[ListVisitor[Triangle]] < ListVisitor[ListVisitor[Shape]]

Question 4 (20 points)

a) Consider the following program:

  interface Maybe[type a] {
    method isNull () : Boolean;
    method get () : a;
    method infix :: (x : a) : Maybe[a];
  }
  class MaybeNo[type a] implements Maybe[a] {
    method isNull () : Boolean { return True; }
    method get () : a { return this.get (); }
    method infix :: (x : a) : Maybe[a] { return new MaybeYes[a] { contents = x }; }
  }
  class MaybeYes[type a] implements Maybe[a] {
    field contents : a;
    method isNull () : Boolean { return False; }
    method get () : a { return this.contents; }
    method infix :: (x : a) : Maybe[a] { return new MaybeYes[a] { contents = x }; }
  }
  object Null [type a] : MaybeNo[a] {}

i) Does this program type check? Give a one- or two-sentence explaination for your answer.

ii) What objects are added to the heap by the following thread:

  thread PartA {
    let x : Maybe[Integer] = Null[Integer] :: 37;
    let y : Maybe[String] = Null[String] :: "hello";
  }

iii) What is the value of x after executing this thread?

iv) What is the value of y after executing this thread?

Question 4 continued

b) Consider the following addition to the program in part (a):

  interface Ref[type a] {
    method get () : a;
    method set (x : a);
  }
  mutable class RefImpl[type a] {
    field contents : Maybe[a];
    method get () : a { return this.contents.get (); }
    method set (x : a) { this.contents := this.contents :: x; }
  }
  object R [type a] : RefImple[a] { contents = Null[a] }

i) Does this program type check? Give a one- or two-sentence explaination for your answer.

ii) What is the value of R.contents after executing the following thread:

  thread PartB {
    R[Integer].set (37);
    let z : String = R[String].get ();
  }

iii) What is the value of z after executing this thread?

Question 5 (20 points)

a) What is the self type myType?

b) Give an example of how myType can be used to solve the binary method problem.

c) Give an example which shows that contravariant uses of myType are not sound for subtyping.

d) Give two approaches which a programming language designer could take the the problem described in part (c).

e) Give one advantage for each of the approaches in your answer to part (d).

Question 6 (20 points)

a) Name three components of the Java concurrency model.

b) The Java concurrency model supports the notion of stale objects: what is a stale object? How can stale objects arise?

c) Give two approaches which a programming language designer could take to the problem of stale objects.

d) Give one advantage for each of the approaches in your answer to part (c).

Question 7 (5 points)

If you could change one feature of Java Generics, what would it be?

Give a one- or two-sentence explaination for your answer.

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.