UNM Computer Science

Programming Languages and Systems

Programming Languages and Systems
Comprehensive Exam
Computer Science Department
University of New Mexico
August 13, 2001

Do any five questions. Each question counts 20 points. Answer only one question on a sheet of paper and write only on one side of each sheet. An answer can continue on several sheets. In this case, only write on one side of each sheet and number the sheets. Write on each sheet the number of the question you are answering.

You can use a computer as a word processor for this exam but you cannot access any information on the computer or on the Internet or run any other programs to help you answer the questions.

1. Compilers (20 points) What is position-independent code? Define what the back-end of a compiler must do in order to generate position-independent code. Why is position-independent code necessary for dynamic linking?
2. Garbage collection (20 points) Consider a compiled language with copying garbage collection of the stop-the-world variety: either the program (the mutator) runs, or the garbage collector runs. When the garbage collector starts running, it chooses some part of the heap it will collect. A copying garbage collector that does not collect the entire heap, i.e., does not copy all live objects each time it is invoked, must somehow keep track of references (pointers) that, at collection time, point from the part of the heap that is not being collected, to the part of the heap that is being collected. (For instance, a generational copying garbage collector must keep track of pointers from objects in older generations to objects in younger generations.) There are several ways in which this can be accomplished; however any solution will include a mutator-time component, and a collection-time component.

   1. (1 pt.) Why is the mutator-time component called a write barrier?
   2. (15 pts.) Describe one complete design: what actions must be done while the mutator runs, and what actions must be done at the beginning of garbage collection and during collection? Describe the data structures and code involved.
   3. (4 pts.) Discuss design alternatives, and their performance tradeoffs.
3. Data abstraction (20 points) Consider an abstract data type (a disjoint union) with several variants and with several tools that operate on it. It could be given as follows in ML syntax:

   datatype Shape =
   Square of real
   | Circle of real
   | Translate of Point × Shape
   

   and the tools are:

   ContainsPt: Point × Shape ® bool
   fun ContainsPt (point, Square side) = ¼
   | ContainsPt (point, Circle radius) = ¼
   | ContainsPt (point, Translate (displacement, s)) = ¼ ContainsPt (point^¢, s) ¼
   

   Shrink: real × Shape ® Shape
   fun Shrink (percent, Square size) = Square ¼
   | Shrink (percent, Circle radius) = Circle ¼
   | Shrink (percent, Translate (displacement, s)) = Translate (displacement, Shrink (percent, s))
   

   How would you represent this in Java (or C++), using subclasses for variants? What is entailed in extending the data type to have an additional variant? What is entailed in extending the data type to have an additional tool? The implementor of the original data type wishes to package and sell the data type, so the implementation is not visible to the buyer, only the interface. The buyer nevertheless wishes to extend the data type, as above. Which problems arise, and how can they be resolved?

4. Lambda calculus (20 points)

   1. (7 pts.) Formally define the term fixed-point operator. (Note: this is the same as a fixed-point combinator.)
   2. (3 pts.) Let A \triangleq lxy. y (xxy). Let Q\triangleq AA. Show that Q is a fixed-point operator.
   3. (10 pts.) Let:

      £ = labcdefghijklmnopqstuvwxyzr.  r (thisisafixedpointcombinator)
      $ = ££££££££££££££££££££££££££

      Show that $ is a fixed-point operator.
5. Declarative programming (20 points) What is declarative programming? In what ways is Prolog declarative, and in what ways does it violate the assumptions of the declarative paradigm? Describe another declarative language.
6. Persistent programming languages and persistent data structures (20 points) The adjective persistent is used in different, though related, meanings in the two question parts that follow. (a) What is a persistent programming language? Describe what is entailed in adding persistence to an object-oriented programming language, e.g., Java. What is a persistent object store? (b) What is a persistent data structure? Give an example of an application that naturally uses a persistent data structure. Discuss the relative difficulty of implementing persistent data structures in ML and C.
7. Databases (20 points) What is a temporal database? Give an example of an application that naturally uses a temporal database. If you have at your disposal an SQL database server, how would you implement a temporal database? Discuss performance issues.
8. Architectural Patterns (20 points) What is the distinction between architectural patterns and design patterns? Is this distinction hard or is there a continuum between the two? Explain why the interpreter pattern has been been called both. Give three architectural patterns and indicate when you would use each one.
9. Lazy Languages (20 points)

   1. Some functional languages use lazy parameter passing. What does this mean and how does it differ from eager parameter evaluation? What are the advantages and disadvantages of lazy parameter evaluation?
   2. Parameters passed with lazy parameter passing are only evaluated once no matter how many times they are used. Describe the implementation required to make this happen.
   3. In programming languages we also talk about early and late binding of variables (and attributes of variables.) Relate this idea to eager/lazy evaluation. Be sure to point out the important differences between these two concepts.
   4. Suppose you have a language with parallel processing facilities. What would be a strategy that is a combination of lazy and eager evaluation? Sketch out an implementation of how such a strategy would be used for parameter passing. How would you handle the problems of parallel processing and coordination of processes?
   5. Lazy functional languages take this concept to another level. Explain the difference between a full lazy language and a language that uses lazy parameter evaluation. What are the additional advantages of a full lazy language?