Fall 2004 Programming Languages Qualifier

October 8, 2004

Directions: Do Not Put Your Name On Your Answer Pages! – Only The Number Assigned To You.

Answer 5 of the following 6 questions.

1.

a. In less than a page explain how OBDDs are used in symbolic model checking to deal with the state explosion problem.

b. In less than a page, comment on the following statement: OBDDs are essentially deterministic finite state automata.

2.

a. In less than 1/2 a page explain how measure functions are used to prove that abstract reduction systems terminate.

b. Give an example of a terminating abstract reduction system

for which there is no measure function that maps elements

of your abstract reduction system into the natural numbers

(with the standard less than ordering). Prove that your

reduction system enjoys the above property.

3. Consider the concept of the "paradigm" of a programming language. For example, we have the functional, procedural, logic programming, and object-oriented paradigms.

a. Give an informal characterization of each of these. That is, for each provide a paragraph that says something like "the X paradigm is characterized by languages that have the following properties".

b. Describe how you would go about giving a formal characterization of programming language paradigms. What formalism would you use?

What is the essential difference between languages in different paradigms?

4. Loop interchange: Loop interchange is an important technique for optimizations esp. for locality etc. Give an example where loop interchange is illegal due to underlying dependences. What are the two important techniques to resolve such a case of illegal interchange due to a particular dependence vector? Give a case when one of the

techniques fails some times ie, it can not change the dependence vector which would allow interchange.

5. Consider the problem of computing ud chains. A simple approach is to perform reaching definition analysis and then compute the u-d chains by chaining a use to the corresponding reaching definitions. In this approach, the ud chain computation is a side effect of reaching definition analysis. We would like to devise an approach of

computing u-d chains directly from the intermediate form without relying on the presence of reaching definition analysis. Formulate this problem. Is it a backward or a forward problem? Give dataflow equations and also an algorithm that is properly initialized which iterates towards reaching a fix point. In light of how ud chain information may be used, articulate on the safety condition of the solution and show how your algorithm is computing a safe (but may be imprecise) solution through a small example.

6. Garbage collection is the automatic program memory reclamation. The opposite is explicit memory reclamation (e.g., through a "free" or "delete" statement). Typically garbage collected languages also allow for object movement and languages that use explicit memory reclamation do not allow object movement. Analyze instead the atypical cases of

a. a garbage-collected environment where object movement is not allowed.

b. an explicit reclamation environment where object movement is allowed.

Under what conditions can each of these take place? Can you name representative systems in these spaces (if there exist any)? What are the general advantages and disadvantages of each of the above combinations, with respect to both performance and programmability?

(Be extensive in your discussion of advantages/disadvantages although you don't need to quantify or substantiate your arguments with literature references.)