# Name:

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 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:

• `eax`: contains the `this` parameter, and the function result
• `ebx`: contains the first formal parameter
• `ecx`: contains the second formal parameter
• `edx`: contains the third formal parameter

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 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:

• For small-degree nodes: simplification of unhinted nodes; coalescing of hinted nodes (based on George's algorithm); freezing of other hinted nodes.
• For high-degree nodes: aggressive coalescing of unhinted nodes (if this is possible); spilling of other unhinted nodes; coalescing of hinted nodes (if this is possible); freezing of other hinted nodes.

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 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 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 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.

### 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.