CS 590s: Programming Languages and Compilers Seminar

Instructor: Suresh Jagannathan

Hours: Tuesday, Thursday
3 - 4:15 pm
SC 102

Overview

This seminar will discuss intermediate representations used in modern and
classical compilers. Students will be exposed to historical approaches to
defining intermediate representations, and will review topical papers on the
subject. In addition, there will be detailed discussions based on case
studies of modern compilers that use intermediate representations in novel
ways. Continuation-passing style (CPS), static single assignment (SSA), and
program dependence graphs (PDG) will be the salient representations
discussed. Based on students' interests, we may also discuss other
intermediate forms or related topics.

Registered students are expected to participate heavily in class
discussions. Each student must present a critical analysis of a paper (or
set of related papers).

Grading

Grading for the class will be based on three components:

         Participation:        25%
    Scribe:               25%
    Paper Presentation:   50%

Class participation is self-explanatory. For the seminar to be successful, it is critical that all
students participate actively in discussions.

A scribe will be appointed at the beginning of each class. The role of the scribe is to take copious
notes of the lecture, and to translate these notes into html format for distribution on the course
web page. The scribe should feel free to talk to the lecturer about the class, and to clarify points
not clearly stated during the class. The notes should be presented cogently and cohesively, and should
be more than a simple rehash of the lecture.

Each student will be assigned a paper (or a set of related papers). The student will be expected to
present a synopsis of the paper, along with supporting reference material when warranted. For example,
a given paper may make assumptions presented in another paper. Students should present this other paper a
s a supporting reference. While it is not expected that students will need to do an in-depth study of all
related work, they should have a fairly deep grasp of the material, and be able to satisfactorily answer
reasonable questions posed by the class. Most importantly, the presentation should strive to be
an inquiry into the material, rather than a simple rehash of the paper's contents.

Students will be allowed to work in groups if they wish. The expectation on the quality of the
presentation will be correspondingly higher.

Papers

Assignments

Tentative Syllabus

Lecture 1: August 19,2002. Overview

Lecture 2:    August 22,2002: Lambda calculus and the SECD machine
                                                   Reference: The Mechanical Evaluation of Expresssions
                                                                        Peter Landin
                                                                        Computer Journal, vol. 6, pp 308-320, 1964

                                                                        The Next 700 Programming Languages
                                                                         Peter Landin
                                                                         Communications of the ACM, vol. 9, pp 157-166, 1966

Lecture 3:    August 27,2002: Introduction to combinators and the SKI machine
                                                  Reference: A New Implementation Technique for Applicative Languages
                                                                      David Turner
                                                                       Software Practice and Experience, vol. 9, pp 31-49, 1979

Lecture 4: August 29,2002: Minimal CPS algorithm and intro to Rabbit and Orbit

Lecture 5: September 3, 2002: Closure Passing and the Transformational Compiler

Lecture 6: September 5,2002: (cont)

Lecture 7: September 10,2002: Essence of Compiling with Continuations

Lecture 8: September 12,2002: (cont)

Lecture 9: September 17,2002: A systematic study of Functional Language Implementations

Lecture 10: September 19,2002: (cont)

Lecture 11: September 23,2002: Efficiently Computing SSA Form

Lecture 12: September 26,2002: Efficiently computing SSA form (cont)

Lecture 13: October 1,2002: Array SSA form and its use in Parallelization

Lecture 14: October 3,2002: A Simple Graph-based Intermediate Representation

Lecture 15: October 10,2002: A New Algorithm for Partial Redundancy Elimination based on SSA Form