Programming Languages and Compilers

Books Required

1.    The union of Aho, Sethi, and Ullman. Compilers: Principles, Techniques, and Tools, Addison Wesley, 1988.  Fischer and LeBlanc. Crafting a Compiler. Benjamin/Cummings, 1988.
Appel. Modern Compiler Implementation in C  (or in ML), Cambridge University Press.
[You have to be very familiar with one of the above, and aware of the material covered in the other two.]


2.    Dershem and Jipping, Programming Languages Structures and Models, Addison Wesley
or Alice E. Fischer, The Anatomy of Programming Languages, Prentice Hall.

Recommended (Required for Compilers Students)
3.    Muchnick. Advanced Compiler Design and Implementation, Morgan Kauffman, 1997.
4.    Wolfe. High-Performance Compilers for Parallel Computing, Addison Wesley, 1996.

Recommended (Required for Language Theory Students)
5.    Apt and Olderog, Verification of Sequential and Concurrent Programs (2nd Ed), Springer-Verlag, 1997.  [Only the introductory chapters are required: Ch.1-3.]

Recommended (Required for Formal Methods Students)

6.    Chapters 1-7 of Mathematical Logic, 2nd Ed, by H.-D. Ebbinghaus, J. Flum, and W. Thomas
7.    Chapters 1,2,3.1,4,5 of Term Rewriting and All That by Franz Baader and Tobias Nipkow
8.    Chapters 1-9 of Model Checking by Clarke, Grumbuerg, and Peled

Specification Documents (In-depth knowledge required for Languages students, familiarity required for Compilers and Formal Methods students)

1.    Stroustrup. The C++ Programming Language, 3rd Ed. Addison Wesley,  1997.
[You should know about the significant features of C++, including templates and the STL, but low-level details are not necessary.]
2.    Gosling, Joy, Steele, Bracha. The Java Language Specification, 2nd Ed. Addison Wesley.
3.    Kelsey, Clinger, Rees (eds.). The Revised (5) Report on the Algorithmic Language Scheme. ACM SIGPLAN Notices, 33, Sep 1998. (Many online versions can be found.)

Papers
[You should fully understand the main concepts of a paper, even if this means studying all its references and their references transitively. Some of the more recent papers are included not because they are fundamental by themselves, but because they refer to all the fundamental work up-to-date.]

Language Design (Recommended for Compilers students, required for Languages students and Formal Methods students)

1.    L. Cardelli and P. Wegner. On Understanding Types, Data Abstraction, and Polymorphism. ACM Computing Surveys, Vol. 17, No. 4, 1985, 471-522.
2.    Milner, A theory of type polymorphism in programming. Journal of Computer and System Sciences, 17:348--375, Dec 1978.
3.    Bracha, Odersky, Stoutamire, Wadler, Making the future safe for the past: Adding Genericity to the Java Programming Language. OOPSLA '98 proceedings, pp. 183-200.

Language Implementation (Recommended for Compilers students, required for Languages students and Formal Methods students)

1.    Alpern, Cocchi, Fink, Grove, Efficient Implementation of Java Interfaces: Invokeinterface Considered Harmless. OOPSLA 2001 proceedings, pp. 108-124.
2.    Wilson, Johnstone, Neely, Boles. Dynamic Storage Allocation: A Survey and Critical Review. In International Workshop on Memory Management, Kinross, Scotland, UK, 1995. Also online.
3.    Wilson, Uniprocessor garbage collection techniques. In International Workshop on Memory Management in the Springer-Verlag Lecture Notes in Computer Science series., St. Malo, France, September 1992. Also online.

Semantics (Recommended for Compilers students, required for Languages students and Formal Methods students)

1.    Edsger W. Dijkstra. Guarded Commands, Nondeterminancy and Formal Derivation of Programs. CACM, Vol. 18, No. 8, August 1975.
2.    K. R. Apt. Ten years of Hoare logic: A survey--Part 1 . ACM Transactions on Programming Languages and Systems Vol. 3, No. 4, pp. 431-483, 1981.
3.    Wing, J. "A Specifier's Introduction to Formal Methods", Computer 23(9): 8-26, September, 1990.

Compiling (Recommended for Languages students and Formal Methods students, required for Compilers studenrs)

1.    Briggs, Cooper, Torczon, Improvements to Graph Coloring Register Allocation, ACM TOPLAS, 16(3), May 1994, pp. 428-455.
2.    Knoop, Ruthing, Bernhard, Lazy Code Motion, PLDI 1992, pp. 224-234.
3.    Johnson, Pingali, Dependence-Based Program Analysis, PLDI 1993, pp. 78-89.
4.    Zhang, Youtao, Gupta, Timestamped Whole Program Path Representation and its Applications, PLDI 2001, pp. 180-190.
5.    Allen, Kennedy, Automatic Translation of Fortran Programs to Vector Form, ACM TOPLAS, October 1987, 9(4):491-542.
6.    Pugh, A Practical Algorithm for Exact Array Dependence Analysis, CACM, August 1992, 35(8):102-114.
7.    DeFouw, Grove, Chambers, Fast Interprocedural Class Analysis, POPL'98.
8.    Schlansker, Mahlke, Johnson, Control CPR: A Branch Height Reduction Optimization for EPIC Architectures, PLDI 1999, pp. 155-168.
9.    Srivastava and Wall, A Practical System for Intermodule Code Optimization at Link Time, Journal of Programming Languages, 1(1), 1993, pp. 1-18.
10.    Ron Cytron, Jeanne Ferrante, Barry K. Rosen, Mark N. Wegman, F. Kenneth Zadeck. Efficiently Computing Static Single Assignment Form and the Control Dependence Graph. Transactions on Programming Languages and Systems, October 1991, Vol. 13, No. 4, 451-490.


Current for Fall 2003.