Project for four-unit grad students

Four-hour graduate students will be asked to read and present three research papers in the course of the semester. These presentations will be required, but not graded; the course grades for the four-hour graduate students will be calculated exactly as for the three-hour graduate students.

The presentations will be done as a group, with each student giving approximately a formal presentation on the assigned paper of approximately 20-30 minutes. All four-hour students will attend the paper presentations, which should last about two hours. I will contact the four-hour students about scheduling the first of these session toward the end of February.

The papers will be in three general areas: parsing, code generation, and languages. In each case, you will have a choice of several papers from which to choose. (It is okay if more than one student picks the same paper. The presentations should be prepared and given separately.) These will mainly be classic or tutorial papers, i.e. papers that are self-contained.

The first group of papers is on parsing. Please choose one of the following papers to present:

• J. Aycock and N. Horspool, Practical Earley Parsing, The Computer Journal 45(6), 2002.

• A.V. Aho and S.C. Johnson, LR Parsing, Computing Surveys 6(2), 1974.

• T.J. Parr and R.W. Quong, ANTLR: A Predicated-LL(k) Parser Generator , Software-Practice and Experience 25(7), 1995.

The second group of papers is on optimization and code generation. Please choose one of the following papers to present, or suggest another paper in this area:

• D. Kuck, R.H. Kuhn, D. Padua, B.Leasure, M. Wolfe, Dependence Graphs and Compiler Optimizations, 8th POPL, 1981. (Classic paper on intermediate representation for compiler optimization, especially for parallelisation.)

• R. Cytron, J. Ferrante, B.K. Rosen, M. Wegman, F.K. Zadeck, Efficiently Computing Static Single Assignment Form and the Control Dependence Graph, ACM TOPLAS 13(4), 1991. (Classic paper on static single-assignment form, another IR for compilers.)

• U. Holzle, D. Ungar, Optimizing Dynamically-Dispatched Calls with Run-Time Type Feedback , PLDI, 1994. (Early work on just-in-time compilation.)

• C. Lattner, V. Adve, LLVM: A Compilation Framework for Lifelong Program Analysis & Transformation , Intl. Symp. on Code Generation and Optimization, 2004. (First paper on LLVM.)

The third group of papers is on theoretical aspects of programming languages. Because these are theory papers, they are rather more difficult to read than the previous ones; as always, I'm happy to talk to you about them.

I've divided the list into two parts, with the second part containing a few papers that are classics, but are more difficult than the ones in the first part; only choose from the second group if you really enjoy this kind of stuff. Also, unlike the previous presentations, I want to have each of you present a different paper, so get your bids in early.

• L. Damas, R. Milner, Principal type-schemes for functional programs, 9th POPL, 1982.

• C.A.R. Hoare, An axiomatic basis for computer programming , Comm. ACM 12(10), 1969.

• P. Landin, The mechanical evaluation of expressions , Computer Journal 6(4), 1964.

• P. Landin, The next 700 programming languages , Comm. ACM 9(3), 1966.

• J. McCarthy, Recursive Functions of Symbolic Expressions Their Computation by Machine, Part I , Comm. ACM 3(4), 1960. (Bonus extra: the tech report version of this paper.)

• J. McCarthy, A basis for a mathematical theory of computation , In Computer Programming and Formal System, P. Braffort and D. Hirshberg (eds.), North Holland, 1963.

• D. Turner, A New Implementation Technique for Applicative Languages , Software-Practice and Experience 9, 1979.

This group is the more technical one, but each paper is considered among the very best papers ever written on programming languages.

• R. Milner, A Theory of Type Polymorphism in Programming , J. of Computer and System Sciences 17, 1978.

• G. Plotkin, Call-by-name, call-by-value, and the lambda-calculus , Theoretical Computer Science 1, 1975.

• J. Reynolds, Towards a theory of type structure , in Proc. Colloque sur la programmation, 1974, Springer-Verlag Lecture Notes in Computer Science 19.