Four-hour project

For the four-hour project, you will be asked to give (formal) presentations on two research papers. The first of these presentations will be mid-April and the second two weeks after that (exact dates will depend on all our schedules). All four-hour students will need to be present for these presentations.

The presentations will not be graded, but will simply be marked "satisfactory" or "unsatisfactory." Your course grade will be determined from the graded materials, like all other students. If your presentation is unsatisfactory, you will have to revise it and re-present it.

The first presentation will be on a paper on language implementation and the second on language design. You are free to suggest your own papers to present, subject to my approval; good sources would be annual programming languages conferences like POPL, PLDI, OOPSLA, or ICFP, or journals like TOPLAS and J. Functional Programming. However, here are some choices that I think would be good in terms of overall length and difficulty.

I do not want to have more than one presentation on the same paper, so please email me your choices right away.

First presentation

• 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.

• 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.)

Second presentation

These papers are more theoretical, and therefore more difficult, than the first group. 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.

• 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.