Computer Science CS411

Introduction to Compiler Construction

Winter Session 2005/2006 Term 2

Course Description
Student Questionnaire <<< PLEASE FILL THIS OUT AND BRING IT TO LECTURE
Text
Other Useful Documentation
Instructors
Communication about the Course
Grading
Lecture
Homework
Downloads <<< HERE!!!
Schedule

PRACTICE FINAL EXAMS:

Course Description

In this course you will learn how compilers work, how to build a compiler, and how knowing how to build a compiler can make you a better software developer. Some of the things you learn and work on this semester include:

Key concepts and practices of compiler construction.
Working through the range of times at which language semantics can be bound to implementation.
Practical ways to take advantage of understanding compilers in software development, design and management.
The deeper insights into the nature of programming languages, software and computation that understanding compilers provide.

This year the course will involve two problem sets, followed by the main project. The main project this year will be to build an AspectJ compiler that accepts Java source code, and does weaving (a key operation in the implementation of AspectJ) after compilation. We will also do our work in Java 1.5 (aka Java 5), which will give us the challenge of working through the generic types in 1.5. This will be an exciting and challenging project. In exchange for your hard work, you will learn a lot about languages, compilers, software development and how to use programming language expertise to make a large project work better. This project will also give you an opportunity to work with aspect-oriented programming, which is a hot new area in programming languages.

You are expected to have a good knowledge of programming languages (CPSC 311 is the prerequisite), and you should also be able to write programs in Java.

Student Questionnaire

So that we can get to know each of you better, please fill out the Student Information Sheet and bring a hardcopy to lecture. You can take this HTML page, and edit it to have the information and your picture, and then print that. Or you can just print it, write in the information by hand and staple a photo to it. Either way is fine.

Text Book

The course text provides background reading for our work this semester.

Programming Language Processors in Java, Compilers and Interpreters, David A. Watt and Deryck F. Brown. (ISBN 0 130 35786 9)

Several copies are available in the reading room. The bookstore also has some. Not everyone needs to buy a copy, but everyone should plan to read through the book, as shown on the schedule below.

You may also find it helpful to consult the notes from last year's class, or the year before. In addition, there are numerous other courses around the world from which we have drawn ideas, one such set of notes was prepared by Laurie Hendren and Michael Schwartzbach, and is used in the McGill 520A compiler course.

Instructors

Gregor Kiczales (email: gregor)

Teaching Assistant

Andrew Carbonetto (email: acarbo)

Communication about the Course

There are four primary means for communicating between those involved in this course. These are:

Lecture.
Lecture in this course will be conducted in an interactive style. Come prepared to ask questions there.
Office hours.

The instructor and TAs have regularly scheduled hours when they are available to discuss questions and course material. The schedule is:
- TA: Andrew Carbonetto
  - Meeting Time: 2:00 to 3:30 Tuesdays, 12:30 to 1:30 Thursdays
  - Location: Learning Center
- Instructor: Gregor Kiczales
  - Meeting Time: Wednesday 1:30 - 3:00
  - Location : CICSR 311
  - Other times available by appointment.
News
The course newsgroup ubc.courses.cpsc.411. The instructor, TAs, and all students are expected to read the news on a regular basis. Late breaking information about assignments, the project, lectures etc will be communicated through the newsgroup. You are responsible for reading the newsgroup.
The newsgroup is also a very effective means of communication if used correctly. Questions about the assignments and project should be posted to the newsgroup rather than being emailed to the instructor or a TA, as everyone will see both the question and its answer. All students are encouraged to post answers to questions posed on the newsgroup as well.
Email
Email to the instructor or TAs is appropriate in limited circumstances. It is the most effective means of scheduling a consulting time when the regular hours are impossible or insufficient. It is an appropriate means of asking questions concerning the grading of assignments and examinations. It is not an appropriate means of asking questions about the assignments or project - see the course newsgroup.

Grading

The following is a tentative grading scheme for the course, although it is subject to change at the instructor's discretion. No student will receive an A in the course without doing well on all four components of the course grading scheme.

Problem Sets and Project	50%
Quizzes	25%
Final Exam	25%

You will work on the project in groups. Group assignments will be discussed in lecture.

I am aware that this policy means that some students could try to hand in homework they did little of the work on. You should be aware that it will not be possible to pass the quizzes and the final unless you fully understand the problem sets and project you hand in. Be sure that you understand the complete design and code for everything you and your group hand in.

So that everyone has equals access to prior quizzes in the course, here are the quizzes from last year:

Spring 05 Quiz 1
Spring 05 Quiz 2

Lecture

The lecture in this course will be conducted in an interactive style. You are encouraged to ask and answer questions during lecture. This style is designed to help you bridge between the lecture and the technical discussions that you homework and project groups will be having.

Homework Assignments

Your homework in this course will consist of several problem sets as well as a larger project.

The problem sets will occur early in the semester. They will involve a combination of coding and write-up. The project itself will have intermediate hand-ins, designed to help you pace your work, and see how you are doing as you go along.

Problem Set 1, Eclipse Project for Problem Set 1
Problem Set 2
Project Description

Downloads

Important downloads to do the assignments and the project will be made available here as we go along.

Eclipse Project for Problem Set 1

NOTE:

Prior to using this, you have to be working with Eclipse 3.1 and you have to install the latest release of AJDT. Instructions for installing AJDT are at http://eclipse.org/ajdt.
Once you have done that, you should be able to load up the MJ Compiler by doing:
File>Import... Existing project...from archive file.
All the settings should default properly. But if you get strange errors about parametric types, then go into the settings for the project and make sure the Java compiler is set to 1.5 (aka 5).

Project Description:

This year's project will be to create a compiler for a subset of the AspectJ language. More details will be available later in the semester.

Handin Procedure:

You will be using handin to submit your completed project phases. The name of the course is cs411. See man handin if you need additional information on how to use handin.

Late Policy:

Late homework will not be accepted in this course.

Schedule

Because we are trying a new approach to this material, you should consider the following schedule to be somewhat fluid. Some topics may move as we go through the semester. You should check this schedule regularly for changes. In addition to being announced in lecture changes, assignments, quizzes and the like will be posted here.

In broad terms, the course has two parts:

In the first six weeks we will sprint through all the main topics of compiler design and implementation. By the end of this period you will have a solid basis for building a working and moderately sophisticated Java compiler.
In the remainder of the semester we will slow down noticeably. Lecture will meet less than the normal three times a week. We will use the time to visit several topics in greater depth. You will be using this time to develop your main course project.

Week 1 - Introduction and Overview

              January 2005
   S    M   Tu    W   Th    F    S
   1    2    3    4    5    6    7
                  L         L

Topics: What is a compiler? What is the value of understanding compilers? How can a chief architect use knowledge of compilers to guide a large project?

Common structure of compilers. Parsing, AST, analysis, code generation.

Bootstrapping a compiler.

NOTE: these slides are not complete lecture notes.

Reading: Read Chapter 1 for Friday.

Homework:

Legend:
L - Lecture, PS - Problem Set Due, Q - Quiz

Week 2 - Abstract Syntax Trees, AOP Introduction

              January 2005
   S    M   Tu    W   Th    F    S
   8    9   10    11  12    13   14
        L         L         L

Topics: Representing programs. Issues in AST design. Parse trees vs. ASTs. Size of core language. De-sugaring. Code walking, code walking with visitors, generating visitor infrastructure.

AOP, AspectJ, crosscutting structure, how AOP affects software design.

Reading: Read Chapter 2 for Monday, and Chapter 3 for Wednesday. (The reading will slow down after this.)

Homework:

Week 3 - Intro to AOP, Name Binding

              January 2005
   S    M   Tu    W   Th    F    S
  15   16   17   18   19   20   21
        L         L         L

Topics: AOP continued.

Binding names to declarations, scopes, symbol tables.

Reading: Chapter 4 of textbook.
The following are useful AspectJ documentation:

The Programming Guide introduces AOP and the AspectJ.
The Quick Reference summarizes syntax.
The Semantics appendix is the best reference.

Homework:

Week 4 - Name Binding

          January/February 2005
   S    M   Tu    W   Th    F    S
  22   23   24   25   26   27    28   
     L, PS1       L         L

Topics:

Reading: Chapter 4 of textbook.

Homework:

Week 5 - Type Checking

              February 2005
  S    M   Tu    W   Th    F    S
 29   30   31    1    2    3    4    
       L         -         -

Topics: Types, type expressions, computing types, checking types, higher-order types.

Reading: Chapter 5 of textbook

Homework:

Week 6 - Type Checking, Project, Quiz 1

              February 2005
   S    M   Tu    W   Th    F    S
   5    6    7    8    9   10   11   
        L         L        Q

Topics:

Type checking

First description of this year's project.

Reading: Chapter 5 of textbook.

Homework:

Week 7 - MIDTERM BREAK

              February 2005
   S    M   Tu    W   Th    F    S
  12   13   14   15   16   17   18
       ----------------------

Week 8 - Virtual Machines and Code Generation

           February/March 2005
   S    M   Tu    W   Th    F    S
  19   20   21   22   23   24   25
        L         L         L

Topics:

Runtime organization, stack machines, register machines, instruction sets, target models...schemes for generating code.

Reading: Chapter 6 of textbook.

Runtime Lecture Notes

Homework:

Week 9 - AOP, AspectJ, AOP Target Model

             March 2005
   S    M   Tu    W   Th    F    S
  26   27   28    1    2    3    4
        L         L         L

Topics: Detailed semantics of key AspectJ language mechanisms, with an eye towards implementing them in your compiler.

Target model for advice, join point shadows and pointcuts.

Reading:

Gregor Kiczales, Erik Hilsdale, Jim Hugunin, Mik Kersten, Jeffrey Palm and William G. Griswold. An Overview of AspectJ. In Proc. of ECOOP, Springer-Verlag (2001).

Erik Hilsdale, Jim Hugunin. Advice Weaving in AspectJ. In Proc. of AOSD, ACM Press (2004).

Homework:

Week 10 -

             March 2005
   S    M   Tu    W   Th    F    S
   5    6    7    8    9   10   11
        L         L         L

Topics: Project Issues, Parsing

Reading:

Homework:

Week 11 - TBD

             March 2005
   S    M   Tu    W   Th    F    S
  12   13   14   15   16   17   18
        L        CR         -

Topics: Finish Parsing, Code Reviews

Reading:

Homework:

Week 12 - AOSD Conference Week (No Lecture)

               March 2005
   S    M   Tu    W   Th    F    S
  19   20   21   22   23   24   25
        -         -         -

Topics:

Reading:

Homework:

Week 13 -

            March/April 2005
   S    M   Tu    W   Th    F    S
  26    27   28   29   30   31   1 
       --         L         Q2

Topics: ABC Compiler, Quiz 2

Reading: abc:An Extensible AspectJ Compiler, abc Technical Report abc-2004-4

Homework:

Week 14 -

            April 2005
   S    M   Tu    W   Th    F    S
   2    3    4    5    6    7
        L         L         L

Topics:

Reading:
Expressive Pointcuts for Increased Modularity, Ostermann et. al., ECOOP 2005

Doxpects: Aspects Supporting XML Transformation Interfaces

Homework:

CS 411 course material

Computer Science CS411

Introduction to Compiler Construction

Winter Session 2005/2006 Term 2

Course Description

Student Questionnaire

Text Book

Other Useful Documentation

Instructors

Teaching Assistant

Communication about the Course

Grading

Lecture

Homework Assignments

Downloads

Project Description:

Handin Procedure:

Late Policy:

Schedule