CSC548 Midterm exam: Spring 2001

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

Answer all questions.

Time allowed: 2 hours

Total number of points: 100

Question 1 (15 points)

Any typechecking algorithm has to allow for the scope of variables, in particular let statements and if statements.

a) Give an example of a program which requires the type checker to keep track of variable scope.

b) Explain how a type checker deals with variable scope.

c) Discuss how your answer to part (b) will depend on whether the symbol table is stored mutably or immutably.

Question 1 continued

Question 2 (15 points)

Java requires the byte code generated by a Java compiler to include type information.

C++ does not require the machine code generated by a C++ compiler to include type information.

a) Give one advantage and one disadvantage of Java's requirement.

b) Describe how this requirement might affect a Java compiler.

Question 2 continued

Question 3 (20 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 fact (n : Integer) : Integer {
    let tmp1 : Boolean = (n <= 1);
    if (tmp1) {
      return 1;
    } else {
      let tmp2 : Integer = n-1;
      let tmp3 : Integer = this.fact (tmp2);
      let tmp4 : Integer = tmp3 * n;
      return tmp4;

Question 3 continued

Question 4 (20 points)

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

The algorithm should use the following steps:

For each step, explain which step you are using, and draw the transformed graph.

Question 4 cont.

Question 5 (15 points)

Object oriented languages with multiple inheritance can use hashing or global graph coloring as the implementation of vtable layout.

a) Explain the hashing implementation of vtable layout.

b) Explain the global graph coloring implementation of vtable layout.

c) Give one advantage and one disadvantage of hashing over global graph coloring.

Question 5 continued

Question 6 (15 points)

Some SML compilers use implicit boxing for their implementation of generics. Generic Java uses explicit boxing.

a) Describe the implicit boxing implementation of generics.

b) Describe the explicit boxing implementation of generics.

c) Give one advantage and one disadvantage of implicit boxing over explicit boxing.

Question 6 continued


You can use this sheet as scrap paper.


You can use this sheet as scrap paper.


You can use this sheet as scrap paper.