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.