CSC548 Midterm exam: Spring 2002

This is a closed-book, closed-note exam.

Answer all questions.

Time allowed: 2 hours

Total number of points: 100

Question 1 (20 points)

Any typechecking algorithm has to allow for the scope of variables, in particular let statements and if statements. This is done using a symbol table.

a) Describe the state of the symbol table at each indicated point in the following program:

  class Bar {
    method foo (a : Integer) : Integer {

      // The symbol table here is { this:Bar, a:Integer }

      let b : Integer = a * 2;

      // What is the symbol table here?

      if (b < 10) {
        let c : Integer = a+b;

        // What is the symbol table here?

        return c;
      } else {
        let d : Integer = a-b;

        // What is the symbol table here?

        return d;

b) Describe how an immutable symbol table is maintained, giving the algorithm for a let block and an if statement.

c) What changes to your answer to part (b) are needed for a mutable symbol table?.

d) Give a short (one- or two-sentence) description of how an immutable symbol table can be implemented.

Question 1 continued

Question 2 (25 points)

a) Calculate the interference graph for the following program. To do this, you should annotate the program with the live variables at each point, then translate the live variable sets into an interference graph.

b) Add precolored nodes for registers to the graph. There are four registers: eax, ebx, ecx and edx, which are all caller-save. The following calling convention is being used:

The code generator copies arguments into parameters in left-to-right order.

Arithmetic operations such as + and - are inlined, and are not method calls.

c) Add hints (move edges) to the graph. Do not include hints for arithmetic operations.

  method fib (n : Integer) : Integer {

    let tmp1 : Boolean = (n <= 2);

    if (tmp1) {

      return 1;

    } else {

      let tmp2 : Integer = n-1;

      let tmp3 : Integer = this.fib (tmp2);

      let tmp4 : Integer = n-2;

      let tmp5 : Integer = this.fib (tmp4);

      let tmp6 : Integer = tmp3 + tmp5;

      return tmp6;


Question 2 continued

Question 3 (20 points)

For the following interference graph with hints (move edges, indicated as dashed lines), show how a graph coloring algorithm can try to 3-color the graph (with colors A, B and C).

The algorithm should use the following steps:

George's algorithm for coalescing: coalesce uncolored SD node n with m if a) n and m do not interfere, and b) every large degree neighbor of m interferes with n.

For each step, explain which step you are using, and draw the transformed graph. (Note that spilling may be needed in this case!)

Question 3 cont.

Question 4 (20 points)

a) What is multiple inheritance?

b) Give two example vtable layout techniques for languages which support multiple inheritance. Give a one-paragraph description of each technique.

c) Give one advantage and one disadvantage of the two techniques you described in part (b).

d) For each technique you described in part (b), show the vtable layouts generated for the following program:

  class A { method foo () { ... } }
  class B extends A { method bar () { ... } }
  class C extends A { method baz () { ... } }
  class D extends B, C { }

Question 4 continued

Question 5 (10 points)

In Generic Java, generic types cannot be instantiated with base types, for example List<double> is not allowed. In Standard ML such types are allowed.

a) Give one advantage of allowing generic types to be instantiated with base types.

b) Give one disadvantage of allowing generic types to be instantiated with base types.

c) Give a one- or two-sentence explanation of why instantiating generic types with base types can cause problems for a garbage collector.

Question 5 continued

Question 6 (5 points)

a) What is your favorite OO programming language?

b) If you could change one feature of the language you named in part (a) in order to make it easier to implement, what would that feature be? Give a one- or two-sentence justification for your answer.


You can use this sheet as scrap paper.


You can use this sheet as scrap paper.


You can use this sheet as scrap paper.