Fall 1999 Qualifying Examination for the Programming Languages Area
November 9, 1999
Please answer Problem 1 and any 5 of the other 8 problems.
1. There are many object oriented programming languages differing in a variety of ways. Consider the languages Smalltalk, Eiffel, Ada95, C++, and Java. Consider the concept of "type."
Discuss the meaning of "type" in each of these languages. Use a small common example to illustrate how types are defined and used.
Discuss how the type systems of these languages deal with issues such as the following: invariants, static/dynamic typing, casting/coercion, genericity, whether type information is first class, covariance/contravariance, subclassing/subtyping, multiple inheritance, recursion, polymorphism, abstract classes and methods, and constraints (pre and post conditions on operations).
Is it meaningful to think in terms of an integrated or standard type system for OO languages? Why or why not?
2. More and more systems are built using more than one programming language, and, in many cases, the languages belong to different families or paradigms.
Discuss the difficulties that language designers have in providing foreign-language interfaces to programs written in their languages.
Considering object-oriented, functional, and logic programming languages: how feasible would it be to have a unified language providing these styles of programming within a single program. Discuss the design issues that would have to be resolved.
3. Various textbook authors have tried to characterize polymorphism. For example, one author breaks polymorphism into universal and ad hoc, where universal polymorphism is further divided into parametric and subtyping, and ad hoc polymorphism is divided into overloading and implicit coercion.
Provide a high-level definition of polymorphism in programming languages.
List and define the various instances of polymorphism. For each instance, indicate languages that provide that type of polymorphism.
Is it meaningful and useful to group all of these concepts under one name ("polymorphism")? Why or why not?
4. Consider an object-based language without classes, where new objects are "cloned" from existing "prototype" objects. Existing objects can be dynamically altered, having new features (fields and methods) added and old features deleted or overridden.
What language design issues arise in providing a meaningful definition for cloning in this language.
Choosing either the lambda calculus, denotational semantics, or axiomatic semantics, provide a semantics for this language feature. Indicate why you chose the method you did.
5. A variety of program analysis tools have been developed to support program maintenance, for example, tools to generate the call graph of a program. Many of these tools require similar forms of analysis; for example, most tools require a program to be parsed. Considering only static analysis tools and a single programming language, discuss the issue of providing one or more common intermediate representations using which analysis tools can communicate results and save overall effort.
6. Since the development of the LR and LL parsing techniques, quite a few tools for automating parsing have been developed, with yacc and its descendants being perhaps the most widely available. While automating the job of producing a parser is undoubtedly useful, more is needed, since a compiler writer is interested in doing something with the structure recognized by a parser, not just knowing whether or not a program can be parsed correctly.
Describe the design alternatives for enabling a compiler writer to use the syntactic structure recognized by an automatically generated parser and discuss their relative advantages and disadvantages.
Since the correctness of a program depends on certain static semantic checks as well as its syntactic structure, programs that can be parsed correctly are often rejected thereafter as semantically erroneous. How might the two kinds of correctness checking be combined in a parser-generation tool? What are the practical limitations of this combined approach?
7. A number of recurrent themes are recognizable in the history of programming language development, such as: trade-offs between simplicity and complexity, concern about portability of programs, and desire for more cost-effective implementations through use of a "universal" intermediate representation. Discuss how the designs and common implementations of popular current languages reflect particular thinking relative to these trends and any other issues you consider to be of equivalent significance.
8. The inclusion of pointers (as in C) or references (as in object-oriented languages) in a programming language substantially complicates optimization and other tasks that require significant program analysis. Explain the basic problem and the impact this problem has on program analysis tasks. Describe the methods used to handle this problem, the kinds of transformations they enable, and their principal limitations.
9. When a method of a class is defined with a precondition, an obvious expectation is that the method should not be called unless the precondition is true.
What must be available to a client object of the class in order for it to be sure it meets this expectation?
If the class is used in a multi-threaded environment, why is it hard for a client object to guarantee that the expectation is met? How can exceptions be used to mitigate this problem? How might the problem be solved in a more elegant (and efficient) manner?