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
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
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.
- J. Aycock and N. Horspool,
Practical Earley Parsing,
The Computer Journal 45(6), 2002.
- A.V. Aho and S.C. Johnson,
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
- R. Cytron, J. Ferrante, B.K. Rosen, M. Wegman, F.K. Zadeck,
Efficiently Computing Static Single
Assignment Form and the Control
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
(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.)
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
- 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.