馮輝寧
Thomas Huining Feng
Prolemy Group, EECS, U.C. Berkeley
huining.feng@gmail.com

Programming Languages Prelim (Spring 2005)

Contents

1. External Links
2. Related Courses
3. Programming Language Tutorials
4. Book Chapters
5. Papers
5.1. Language design
5.2. Types
5.3. Implementation
5.4. Program Analysis
5.5. Optimization
6. Questions Asked in the Prelim (20050201)

1. External Links

Original PL Prelim Syllabus

Jeremy Condit's mirror of PL Prelim Syllabus

Bor-Yuh Chang's Programming Language Prelim Study Schedule

4. Book Chapters

Introduction to Combinators and λ-Calculus [5].

  1. Chapter 1. λ-Calculus. P.1-19

  2. Chapter 2. Combinatory Logic. P.20-31

  3. Chapter 3. The Power of λ and Combinators. P.32-46 (excluding Boehm's theorem)

  4. Chapter 13. Typed Terms. P.159-167

The Formal Semantics of Programming Languages - an Introduction [3].

  1. Chapter 2. Introduction to Operational Semantics. P.11-26

  2. Chapter 5. The Denotational Semantics of IMP. P.55-76

  3. Chapter 6. The Axiomatic Semantics of IMP. P.77-98

  4. Chapter 8. Introduction to Domain Theory. P.119-140

The Science of Programming [8].

  1. Chapter 7. The Predicate Transformer wp. P.108-113

  2. Chapter 8. The Commands skip, abort and Composition. P.114-116

  3. Chapter 9. The Assignment Command. P.117-130

  4. Chapter 10. The Alternative Command. P.131-137

  5. Chapter 11. The Iterative Command. P.138-148

  6. Chapter 12. Procedure Call. P.149-162

Compilers: Principles, Techniques, and Tools [4].

  1. Chapter 6. Type Checking. P.343-388

Types and Programming Languages [1].

  1. Chapter 8. Typed Arithmetic Expressions. P.91-98

  2. Chapter 9. Simply Typed Lambda-Calculus. P.99-111

Abstraction and Specification in Program Development [6]

  1. Chapter 4. Data Abstraction. P.56-98

  2. Chapter 10. Writing Formal Specifications. P.187-218

Essentials of Programming Languages [2]

  1. Chapter 7. Continuation-Passing Interpreters. P.241-300

  2. Chapter 8. Continuation-Passing Style. P.301-344

Note 1: The above chapter list contains only the chapters most relavent to the prelim. I.e., it may be very helpful reading other chapters in the same books.

Note 2: If you are another Spring 2005 PL prelim taker waiting for the same books from the UCB libraries, please contact me directly.

5. Papers

5.2. Types

Data Abstraction

Type Inference

Subtyping

6. Questions Asked in the Prelim (20050201)

There are 2 questions for the prelim, half an hour for each. The examiners are Prof. Ras Bodik and Prof. Sue Graham. These questions are open ended. What the students are asked as sub-questions of each question depends heavily on their previous answers.

  1. SSA (Ras Bodik).

    • What is "SSA" short for?

    • Define SSA. (You could give some examples and then derive a more formal answer.)

    • Since I gave an example like this: 

      v = ...
u1 = v;
while (...) {
  u2 = v;
  v = ...;
  u3 = v;
}

      I was asked to perform the SSA transformation on v.

    • What's the growth of program size after transforming it into SSA (linear/quadratic/exponential)? In terms of a single variable? In terms of all the existing variables?

    • What is SSA good for? It can make some analysis more powerful and some faster. Give an example of analysis made faster by using SSA.

    • How to achieve minimal SSA?

    • Suppose now you don't care about performance. Give an SSA transformation algorithm.

    • Since I gave a bruteforce algorithm (right, the least efficient one), I was asked to improve it slightly (dominance frontier algorithm).

    • Size of definition-use chains of variables after transformed into SSA.

    28 minutes passed.

  2. Macro (Sue Graham).

    • Give a definition for macros.

    • Are macros good or bad? Give examples.

    • Since I carelessly mentioned macros introduce no overhead, I had to clarify this statement, and compare macro expansion with method calls. :(

    • In which stage are macros handled?

    • Someone says macros are not natural in a language because they are expanded with a preprocessor that does not belong to the compiler. If we're not gonna use preprocessors, how to implement macros with languages constructs? You're free to invent any constructs appropriate.

    • Since I proposed method inlining, I had to compare the power of inlining and macros. :(

    • In which way bindings differ in programming languages than in macros?

    • How to implement multiple return values and iterators without macros?

    • It's common to define macros for different compilation targets. How to use PL constructs to achieve the same effect?

    15 minutes out of time. :)

Copyright © 2005-2011 Thomas Huining Feng. Generated on Apr 22, 2023.