This syllabus gives an overview of the background expected for students planning to do PhD research in Programming Languages. One of the reasons for using a web page is to allow for easy updates as new topics arise in the area of programming languages and compilers. Comments on the syllabus are welcome. Please send mail to Professors Aiken, Graham, Hilfinger, and Yelick. In particular, please let us know if you find online copies of the papers, so we can add the appropriate links.

The prelim syllabus is divided into the following general topics:

• Programming skills
• Semantics
• Language Design
• Types
• Implementation
• Program Analysis
• Optimization
• Software Engineering

Although much too extensive to be considered part of the syllabus, students should also be aware of the page of links to specific languages, critiques, and other programming language research topics. To get some help in navigating through the literature, including a short history of some of the languages and their relationships, see Introduction to the Literature in Programming Language Design, by Gary Leavens.

Programming Skills

• ML
• Scheme
• Prolog
• C
• C++
• Java

Semantics

• Lambda calculus and combinators.
  Introduction to Combinators and Lambda Calculus, Roger Hindley and Jonathan Seldin, Cambridge University Press, 1986.
  Chapters 1-3 (excluding Boehm's theorem).
• Denotational semantics
  The Formal Semantics of Programming Languages, Glynn Winskel, MIT Press, 1996.
  The chapters on denotational semantics and domain theory.
• Operational semantics.
  The Formal Semantics of Programming Languages, Glynn Winskel, MIT Press, 1996.
  The chapters on operational semantics (structural and one-step versions).
• Axiomatic semantics.
  The Formal Semantics of Programming Languages, Glynn Winskel, MIT Press, 1996.
  The chapters on axiomatic semantics.
• Proving properties of programs.
  The Science of Programming, David Gries, Springer-Verlag, 1981.
  Part II covers the essential material on semantics.

Language Design

• Practical issues
  
  • Hints on Programming-Language Design, C. A. R. Hoare, in "Essays in Computing Science," by C. A. R. Hoare and C. B. Jones, 1989.
    
  • Lisp: Good News, Bad News, and How to Win Big. Richard P. Gabriel, Lucid, Inc., 1991.
• Functional languages
  
  • Can Programming by Liberated from the von Neumann Style? A Functional Style and its Algebra of Programs, John Backus, Communications of the ACM, 21(8):613-641, August, 1978.
    
  • Conception, Evolution, and Application of Functional Programming Languages, P. Hudak, ACM Computing Surveys, 21(3):359-411.
  • A Critique of Standard ML, Andrew Appel, CS Department, Princeton University, TR-364-92, February 1992.
• Object-oriented languages
  
  • Self: The Power of Simplicity David Ungar and Randall B. Smith, SIGPLAN Notices 22(12), December, 1987. (Also published in Lisp and Symbolic Computation 4(3), Kluwer Academic Publishers, June, 1991.)
  • Engineering a Programming Language: The Type and Class System of Sather, by Clemens Szypersky, Stephen Omohundro, and Stephan Murer, International Computer Science Insitute Techreport TR-93-064, 1993.
  • Pizza into Java: Translating theory into practice, Martin Odersky and Philip Wadler, Proc. 24th ACM Symposium on Principles of Programming Languages, January 1997.
• Logic programming
  
  • Algorithm = Logic + Control, R. Kowalski, CACM July, 1979.
• Algol family languages
  
  • Revised Report on the Algorithmic Language ALGOL 60, Naur, Backus, Bauer, Green, Katz, McCarthy, Perlis, Rutishauser, Samelson, Vauquois, Wegstein, van Wijngaarden, and Woodger, CACM 1(17), January 1963.
• Parallel languages
  
  • Parallel programming in Split-C, David E. Culler, Andrea Dusseau, Seth Copen Goldstein, Arvind Krishnamurthy, Steven Lumetta, Thorsten von Eicken, and Katherine Yelick, Supercomputing '93, pages 262-273, Portland, Oregon, November 1993.
  • Programming Parallel Algorithms, Guy Blelloch, CACM, May 1996.
  • Jade: A High-Level, Machine-Independent Language for Parallel Programming, M. C. Rinard and D. J. Scales and M. S. Lam, IEEE Computer, June, 1993.
  • An Introduction to Programming with Threads, Andrew Birrell, DEC SRC Reports, January, 1989.

Types

• Basic Static semantics
  
  • Compilers: Principles, Techniques, and Tools, Aho, Sethi, and Ullman, Addison-Wesley, 1988. Chapter 6.
• Data Abstraction
  
  • Abstraction mechanisms in CLU
    B.H. Liskov, A. Synder, R. Atkinson, and C. Schaffert., Communication of the ACM 20(8):564-576, 1977.
• Type Inference
  • Simply-typed lambda calculus, Hindley and Seldin, Chapter 13.
  • A Theory of Type Polymorphism in Programming, R. Milner, JCSS, vol. 17, no. 3, 1978, p. 348-375.
• Subtyping
  • A Behavioral Notion of Subtyping, Barbara Liskov, Jeannette M. Wing, TOPLAS 16(6): 1811-1841 (1994).
  • Subtyping Recursive Types, Roberto Amadio, Luca Cardelli, TOPLAS 15(4): 575--631 (1993).
• Interfaces
• Formal specification of types
  • Abstraction and Specification in Program Development, Barbara Liskov and John Guttag, The MIT Press, 1986. Chapters 4 and 10.

Implementation

• Lexical Analysis
• Parsing
  • See Muchnick (above) for most topics on parsing, in particular: context-free grammars, top-down parsing and LL grammars, bottom-up parsing and LR grammars, and syntax-directed translation.
  • Practical LR error recovery, S. L. Graham, C. B. Haley, and W. N. Joy, . Proceedings of the SIGPLAN '79 Symposium on Compiler Construction, August 1979.
  • A practical method for LR and LL syntactic error diagnosis and recovery, Michael G. Burke and Gerald A. Fisher, ACM Transactions on Programming Languages and Systems, Vol. 9, No. 2, April 1987, pages 164-197.
• Attribute grammars
  
  • Optimal-time incremental semantic analysis for syntax-directed editors. T. Reps, Ninth Annual ACM Symposium on Principles of Programming Languages, pages 169-176, January 1982.
• Automated code selection
  • BURG -- Fast Optimal Instruction Selection and Tree Parsing, Christopher. W. Fraser, Robert R. Henry, and Todd A. Proebsting. ACM SIGPLAN Notices 27 , 4:68-76, April 1992.
  • Optimal Code Generation for Expression Trees: An Application of BURS Theory, Eduardo Pelegri-Llopart and Susan L. Graham. Proceedings of the 1988 ACM SIGACT/SIGPLAN Symposium on Principles of Programming Languages, pages 294-308, January 1988.
  • BURS Automata Generation., Todd A. Proebsting. ACM Transactions on Programming Languages and Systems, 17(3):461-486, May 1995.
  • One-Pass, Optimal Tree Parsing - With Or Without Trees, Todd A. Proebsting and Benjamin A. Whaley, CC'96 April 1996.
  • Hard-coding bottom-up code generation tables to save time and space, Christopher W. Fraser and Robert R. Henry, Software-Practice and Experience 21, (1):1-12, January 1991.
• Tree-transformation techniques
• CPS conversion
  • Essentials of Programming Languages, Friedman, Wand and Haynes. McGraw-Hill, (ISBN 0-07-022443-9). Chapter 8 covers CPS.
• Garbage collection
  • Uniprocessor Garbage Collection Techniques, Paul R. Wilson, 1992 International Workshop on Memory Management", St. Malo, France, September 1992. (The Proceedings has been published as Springer-Verlag Lecture Notes in Computer Science no. 637.)
  • Garbage Collection in an Uncooperative Environment, H.-J. Boehm and M. Weiser, Software-Practice and Experience, 18(9):807-820, September 1988.
  • Garbage Collection can be Faster than Stack Alocation, Andrew Appel, Information Processing Letters, 25(4):275-279, June 1987.
  • Simple generational garbage collection and stack allocation, Software-Practice and Experience, 19(2):171-183, February 1989.
  • Students should also be familiar with the idea of garbage collection based on reference counting.
• Numerics
  
  • Compiler Support for Floating-point Computation. C. Farnum, Software-Practice and Experience, 18:701-709, 1988.
• Runtime representations
  • Continuation-passing, closure-passing style, A. Appel and T. Jim, Sixteenth Annual ACM Symposium on Principles of Programming Languages, pages 293-302, January 1989.
  • A new implementation technique for applicative languages, D.A. Turner, Software-Practice and Experience, 9:31-49, 1979.
  • Object layout for OO languages. CS264 lecture notes
  • Programming Languages: An Interpreter-Based Approach, S. Kamin, Addison-Wesley, 1990. The material on backtracking search for logic programming languages; see also CS263 Logic Programming lecture notes.

• Dataflow analysis
  • See the analyses listed under Optimization below.
• Abstract interpretation.
  • Abstract Interpretation: A Unified Lattice Model for Static Analysis of Programs by Contruction or Approximation of Fixed Points, P. Cousot and R. Cousot, POPL, 1977, pp. 238-252.
    
  • The theory and practice of transforming call-by-need into call- by-value, A. Mycroft, Proceedings of the 4th International Symposium on Programming, pages 269-281, April 1980. In LNCS No. 83.
• Call graphs for higher-order languages
  
  • Control Flow Anlaysis in Scheme, O. Shivers, PLDI proceedings, 1988, pp. 164-174.
  • Object-oriented type inference, Palsberg and M. I. Schwartzbach, Proceedings of the ACM Conference on Object-Oriented Programming: Systems, Languages, and Applications, October 1991.
• Type-based analysis
  
  • Global tagging optimization by type inference, F. Henglein, Proceedings of the 1992 ACM Conference on Lisp and Functional Programming, pages 205-215, July 1992.
  • Barrier Inference, A. Aiken and D. Gay, Proceedings of the 25th ACM Symposium on Principles of Programming Languages, January 1998.

Optimization

• Intermediate representations
  
• Analyses
  The coverage of analyses includes control flow, data flow, dependence, interprocedural, aliasing, and pointers.
• Loop optimization
• Register management
• Memory hierarchy optimization
• Instruction scheduling
  
• Dynamic compilation
  • Dynamic vs. Static Optimization Techniques for Object-Oriented Languages, Urs Holzle and Ole Agesen, TAPOS 1996.
  • Annotation-Directed Run-Time Specialization in C, B. Grant, M. Mock, M. Philipose, C. Chambers, S.J. Eggers, Symposium on Partial Evaluation and Semantics-Based Program Manipulation, June 1997.
  • Fast, Effective Dynamic Compilation, J. Auslander, M. Philipose, C. Chambers, S.J. Eggers and B.N. Bershad, Conference on Programming Language Design and Implementation, May 1996.
• Parallelization and Vectorization
  • Automatic translation of Fortran Programs to Vector Form, Randy Allen and Ken Kennedy, ACM Transactions on Programming Languages and Systems, 9(4):491-542, October 1987.
  • Compiler Transformations for High-Performance Computing, D.F. Bacon and S.L. Graham and O.J. Sharp, ACM Computing Surveys, 26(4):345-420, 1994.

Software Engineering

• Classical models of software development.
• Methods and tools: testing, configuration management, etc.
• Criteria of good program/module design and their rationale.
• Software development environments.
• Some familiarity with some design methodologies.