Schedule for CSE 501: Implementation of Programming Languages

Autumn 2010

The class meets TuTh 12:00-1:20, in room CSE 403.

Read the listed paper before the given class meeting.

Thu Sep 30

Introduction
Assignment (due Monday, Oct 4): Put project ideas on the wiki

Tue Oct 5

Thu Oct 7

Dataflow
Properties of Data Flow Frameworks: a Unified Model, by T. J. Marlowe and B. G. Ryder, Acta Informatica, 28:121-163, 1990.
Project proposal due today (see the logistics document)

Tue Oct 12

"Abstract Interpretation: a semantics-based tool for program analysis", by Neil Jones and Flemming Nielson. First two sections only. PostScript.
By today, meet the instructor to have your project proposal approved (see the logistics document)

Thu Oct 14

No reading.
Revised project proposal due by Friday at 4pm.

Tue Oct 19

No class (Mike at OOPSLA)

Thu Oct 21

SSA: Efficiently computing static single assignment form and the control dependence graph, by Ron Cytron et al., TOPLAS, 1991

Tue Oct 26

Type inference:
Wikipedia on lambda calculus
Principal type-schemes for functional programs, by Luis Damas and Robin Milner, POPL 1982. There is a typo in Algorithm W part (ii): on the second line, e2 and t2 should be e1 and t1. "e2" and "t2" are correct on third line.
Chapter 30 (book pages 273-283, which are pages 289-299 in the PDF) of Programming Languages: Application and Interpretation by Shriram Krishnamurthi.

Thu Oct 28

Type polymorphism

Tue Nov 2

Comparing optimizations: Wake Up and Smell the Coffee: Evaluation Methodology for the 21st Century by Blackburn et al., in CACM (2008).
Project related work and methodology due today (see the logistics document)

Thu Nov 4

Register allocation: Register allocation via graph coloring by Preston Briggs. Phd dissertation, Rice University, April 1992, Chapters 1, 2, 3, 5, 6, and 9.
Don't panic at the seemingly-daunting reading; the typeface and line spacing are large, and the text is well-written.

Tue Nov 9

No class (Mike at FSE)

Thu Nov 11

No class (Mike at FSE)

Tue Nov 16

No class (Mike at Workshop on Usable Verification)

Thu Nov 18

Garbage collection: Uniprocessor garbage collection techniques by Paul R. Wilson

Tue Nov 23

No class. Snow day.
Project initial results due today (see the logistics document)

Thu Nov 25

No class (Thanksgiving).

Tue Nov 30

Immix: a mark-region garbage collector with space efficiency, fast collection, and mutator performance by Stephen M. Blackburn and Kathryn S. McKinley, in PLDI 2008.

Thu Dec 2

Just-in-time compilation: A brief history of just-in-time by John Aycock, in ACM Computing Surveys, 2003.
A survey of adaptive optimization in virtual machines by Matthew Arnold, Stephen Fink, David Grove, Michael Hind, and Peter F. Sweeney. In Proceedings of the IEEE, 92(2), 2005.

Tue Dec 7

Dynamically-typed languages: An efficient implementation of Self, a dynamically-typed object-oriented language based on prototypes by Craig Chambers, David Ungar, and Elgin Lee. In OOPSLA 1989.

Thu Dec 9

Trace compilation: Tracing for web 3.0: trace compilation for the next generation web applications by Mason Chang, Edwin Smith, Rick Reitmaier, Michael Bebenita, Andreas Gal, Christian Wimmer, Brendan Eich, and Michael Franz. In VEE 2009.
Optional: Trace-based just-in-time type specialization for dynamic languages by Andreas Gal, Brendan Eich, Mike Shaver, David Anderson, David Mandelin, Mohammad R. Haghighat, Blake Kaplan, Graydon Hoare, Boris Zbarsky, Jason Orendorff, Jesse Ruderman, Edwin W. Smith, Rick Reitmaier, Michael Bebenita, Mason Chang, and Michael Franz. In PLDI 2009.
Project final report due on December 10 at 4pm.

Tue Dec 14

No class. Final version of presentation slides due at 4pm.

Thu Dec 16 9:30-12:20, in room 403

final project presentations