Programming Languages and Compilers Qualifying Exam,

Spring 2002.

April 15, 2002

 

Answer 6 of the 8 questions. Use of the web constitutes cheating.

1. Define and contrast parametric & ad-hoc polymorphism. Give examples of both. What is the benefit of polymorphism, in general?

Define and contrast call-by-name and call-by-value. What are advantages and disadvantages of either?

 

2. Describe a situation where a generational garbage collector would be inefficient.

Describe when a stop-and-copy garbage collector would be appropriate and inappropriate.

 

3. An expression e is said to be "very busy" at a program point p if it is evaluated on all paths emanating from that program point and there is no redefinition of any of its operands between p and each point of evaluation. Our goal is to find a set of very busy expressions at the entry and exit of each basic block. Formulate this as a dataflow problem. Is it a forward or a backward problem? Write the dataflow equations for a basic block. Write an algorithm to find the very busy expressions at entry and exits of basic blocks.

 

4. What are the complications of multiple inheritance with respect to object layout and dynamic dispatch? If you were designing a runtime system for a language with multiple inheritance, what implementation approach would you follow and why? What conditions (e.g., dynamic class loading, availability of the full hierarchy, etc.) would influence your choices?

 

5. Describe the standard subtyping rules for function types. Why are mutable cells (records of a single element) not subtypable?

 

6. What are dominators? Give a simple algorithm to compute dominators given a control flow graph. Give an outline of an algorithm to compute changes to dominator relation (tree) when edges are added or deleted to the control flow graph (CFG). We call this the incremental version of the dominator algorithm. Show an example of incrementally computing the dominator relation showing some edge additions and deletions.

 

7. The code for a binary search is given below. Is this code correct? (Assume normal preconditions, e.g., about the ordering of array elements.) Can you prove it using the Hoare axioms? (The main point you should show is the loop invariant, not the low-level algebra, although the low-level algebra is what will seal the correctness of the proof.)

int bsearch(int a[], int len, int key) {
int l=0, r=len;

while( l < r ) {

int m = (l+r)/2;
int y = a[m];
if( key < y ) then r = m;
else if( key > y ) then l = m+1;
else return m
 }
return -1; /* No find. */
 }

 

8. Describe and contrast inheritance and delegation as software development techniques. Why do some argue that inheritance should not be used in favor of delegation?