Prerequisites:

The following prerequisites, although not at all mandatory, are recommended: basic practice of programming in any high-level programming language (like CSCI-GA.2110-001 or CSCI-GA.2110-003), basic course on translation and compiler construction (like CSCI-GA.2130-001), and basic knowledge of logic for computer science (like CSCI-GA.2390-001).

Course Description:

Courses on programming language translation and compiler constructions

Although all compiler construction courses cover essentially the same material (including lexical analysis, grammars and parsing, semantic analysis and typing, declaration and storage management, static analysis, register allocation, code generation, fontend and backend optimization techniques), they may have very different scopes depending on the considered languages (imperative, object-oriented, functional, logical, domain-specific, etc), the considered machines (virtual machines, specialized hardware such as GPU or parallel machines, etc), the considered analysis, allocation and transformation methods (including supporting tools), the considered pedagogical objectives (from teaching of a well-established technology to explaining the scientific bases of this technology), and the teaching strategies (e.g. applied programming project to application of theory to software design).

A complete compiler is a large program for a student project which, unfortunately, often ends up in a mishmash of techniques for solving very specific problems posed by a particular source language and target machine, which is not propitious for a coherent view of the subject. Moreover very few students are likely to have to develop a compiler in their professional carrier, which does not mean that the understanding of compilers, at an appropriate level of abstraction, is not essential to all computer scientists, e.g. to grasp the impact of compilers on how computers are used or to apprehend computer safety and security.

Formal concepts of compilation

The bias of this advanced compiler construction course is to view advanced compilation as an application of formal methods so that students will learn, beyond the basic ideas and concepts of compilation, rigorous mathematical concepts, abstractions, and methodologies that are useful in many areas of computer science where mathematical foundations and correctness is a major concern. Examples are abstract interpretation, languages, grammars, lattices, fixpoints, inductive definitions, parsing, semantics, bisimulations, program transformation and equivalence, abstract machines, correctness, proof methods, verifying compilers, proof assistants, theorem provers, etc.

Class Hours:

Tuesday and Thursday, 3:30PM—4:45PM, WWH 312

First class:

Tuesday, January 29^th, 2013

Office Hours:

By email appointment on Thursday, 2:00PM—3:15PM, CIWW 405

Textbook:

None, all information (including course notes) is provided online by the instructor.

Many books are available for the personal use of students such as

Andrew W. Appel and Jens Palsberg. Modern Compiler Implementation in Java, Cambridge University Press, 1998 (also in ML and C).
Reinhard Wilhelm and Helmut Seidl. Compiler Design: Virtual Machines. Springer, 2010
Reinhard Wilhelm, Dieter Maurer, and Stephen S. Wilson (Translator). Compiler Design. Addison-Wesley, 1995.

Trends in compilation can be tracked by looking at the proceedings of the annual International Conference on Compiler Construction (CC), see CC 2013 and previous proceedings at DBLP

Homework:

The reading of the course notes, including auxiliary material, when explicitly mentionned, is mandatory. The homework exercices are facultative and given for encouraging the improvement of one's knowledge and self-training in the perspective of the exams.

Personal project:

The project will consists in reading a research paper on compilation followed by the production of a comprehensive summary in 1200 words (about 4 pages) and an oral presentation of the paper in 25mn plus 5mn of questions (which is the standard format of most computer science conferences) The papers will be distributed randomly.
The oral presentation and summary will be evaluated on the understanding of the background material, the clarity of the presentation, the insights and opinions beyond what was in the paper, and, for the oral presentation, the quality of the answers to questions.

Midterm exam:

Thursday, March 14^th, 2013. Questions on all previous classes.

Spring recess:

Monday, March 18^th — Sunday, March 24^th, 2013.

Last day of class:

Thursday, May 9^th, 2013.

Final exam:

Thursday, May 16^th, 2013. Questions on all previous classes.

Course requirements:

Personal project, midterm and final exams. Class attendance and facultative homework highly recommended.

Academic integrity:

See the NYU computer science department commitment to academic integrity and the Academic Integrity of the College of Arts and Science

Grading:

Personnal project (25%), midterm exam (25%), and final exam (50%).

The course content is online