Name:

SE580 final exam: Autumn 2002-2003

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) Method overriding.

c) Covariance.

d) Contravariance.

e) Generics.

Question 1 continued

Question 2 (20 points)

A sample Java program to multiply all of the elements in a non-empty array is:

  interface BinOp {
    public BinOp times (Binop arg);
  }
  class Integer implements BinOp ...
  class Float implements BinOp ...
  class MultiplyArray {
      BinOp multiplyAll (BinOp[] array) {
        BinOp result = array[0];
        for (int i=1; i<array.length; i++) {
          result = result.times (array[i]);
        }
        return result;
      }
  }

a) What is the binary method problem?

b) Explain why the BinOp 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.

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 RRef[type a] {
    method get () : a;
  }







b)

  interface RRef[type a] {
    method get () : a;
  }
  interface RWRef[type b] extends RRef[b] {
    method set (x:b);
  }
  class RWRefImpl[type c] implements RWRef[c] {
    mutable field contents : c;
    method get () : c { return this.contents; }
    method set (x:c) { this.contents := x; }
  }







c)

  interface RRef[type a] {
    method get () : a;
  }
  interface RWRef[type b] extends RRef[b] {
    method set (x:b);
  }
  class RWRefImpl[type c] implements RWRef[c] {
    mutable field contents : c;
    method get () : a { return this.contents; }
    method set (x:b) { this.contents := x; }
  }

Question 3 continued

d)

  interface RRefObject {
    method get () : Object;
  }
  interface RRefString extends RRefObject {
    method get () : String;
  }
  class RRefStringImpl implements RRefString {
    mutable field contents : String;
    method get () : String { return this.contents; }
  }







e)

  interface RWRefObject {
    method get () : Object;
    method set (x:Object);
  }
  interface RWRefString extends RWRefObject {
    method get () : String;
    method set (x:String);
  }
  class RWRefStringImpl implements RWRefString {
    mutable field contents : String;
    method get () : String { return this.contents; }
    method set (x:String) { this.contents := x; }
  }







Question 4 (20 points)

a) What are generic objects?

b) Give an example program which shows that adding generic objects to a language can reduce the amount of space a program uses.

c) Give an example program which shows that mutable generic objects are not type-safe.

Question 4 continued

Question 5 (20 points)

A concurrent programming model should support some form of concurrency control such as locks or monitors.

Concurrency controls need to supply at least an atomic read-and-write operation (such as atomic swap), and a blocking operation (such as blocking while a field has a given value).

a) Give the dynamic semantics of atomic swap.

b) Give the dynamic semantics of field blocking.

c) Show how a semaphore can be implemented using atomic swap and field blocking.

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.