8.12

CS 4410/6410: Compiler Design🔗

Syllabus --Spring 2024


Meeting places & times🔗

Course staff & office hours🔗

Instructor

  

Benjamin Lerner

  

blerner@ccs

  

WVH 326

  

Monday 1:00–2:30pm,
after class (usually),
and by appointment

TA:

  

Federico Cassano

  

cassano.f@northeastern

  

Outside WVH 308

  

Tuesday 1:00–3:00pm,
Friday 1:35–3:35pm

Ben Lerner
Ben Lerner

Federico Cassano
Federico Cassano

General information🔗

CS 4410 covers the implementation of efficient compilers for programming languages. The course focuses on the connections between language features and the impact they have on the design of a compiler, including any associated algorithms and pragmatic issues, and practical applications including those outside of programming languages proper. Participants build a working compiler including lexical analysis, parsing, type checking, code generation, and register allocation. As a secondary emphasis, the course exposes students to run-time issues and optimization.

Prerequisites🔗

This course assumes familiarity with programming in the style of How to Design Programs, and basic knowledge of functional programming as introduced in CS 2510, and C programming as introduced in CS3650.

Exams🔗

At the moment, I am not planning on giving formal exams. However, we will likely have two or three written assignments (as opposed to the project assignments) that will serve a similar purpose. There is a final exam time scheduled for this course, but we probably will not use it. We will likely have project presentations due during exam week, so don’t assume the course is over before then.


Materials🔗

Software🔗

Programming assignments will use several pieces of software:

The first homework will guide you through setting up the software you’ll need.

There is no specific IDE for OCaml; I tend to use emacs, but you may use any editor you wish.

Books🔗

There is no required textbook, but you may find these books useful.


Andrew Appel, Modern Compiler Implementation in ML, Cambridge University Press, 1998.

  


Keith D. Cooper and Linda Torczon, Engineering a Compiler, 2nd Ed., Morgan Kaufmann, 2004.

  


Alfred V. Aho, Monica S. Lam, Ravi Sethi, and Jeffrey D. Ullman, Compilers: Principles, Techniques, and Tools, Pearson Education Inc, 2006.

Online resources🔗

OCaml Resources

X86 Resources

X64 Resources

(I will add to this list over the semester as I find useful guides. Email me if you have suggestions.)

Lectures🔗

The lecture schedule below is accurate to roughly-weekly resolution: last year the course met twice a week, while this year it’s three times a week, so each lecture note will take about 1.5 days this year.

Date

 

Topics (tentative and approximate)

 

Materials

1/08 M

 

Introduction, OCaml practice

 

notes

1/10 W

 

Tiny compiler: grammar, abstract syntax, and instructions

 

notes

1/15 M

 

No class: MLK Day

 

1/17 W

 

Names, scope and (simple) stacks

 

notes

1/22 M

 

A-Normal Form (part 1)

 

notes

1/24 W

 

A-Normal Form (part 2)

 

1/29 M

 

Multiple data types and tagging values

 

notes

1/31 W

 

Errors and calling functions

 

notes

2/05 M

 

Function declarations

 

notes

2/07 W

 

Overflow and Tail Calls

 

notes, notes and notes

2/12 M

 

Heap allocation and pairs

 

notes

2/14 W

 

Mutually-recursive declarations and types; mutable tuples

 

notes

2/19 M

 

No class: Presidents’ Day

 

2/21 W

 

Enrichment: Pyret runtime, printing values deeper than the stack depth

 

2/26 M

 

First-class functions

 

notes

2/29 W

 

Work on homework

 

3/04 M

 

No class: Spring Break

 

3/06 W

 

No class: Spring Break

 

3/07 T

 

No class: Spring Break

 

3/11 M

 

Closures

 

3/13 W

 

Memory management

 

notes

3/19 M

 

Automated memory management, Mark/compact

 

3/20 W

 

Intermediate representations, abstract locations, and register allocation; CSE

 

3/25 M

 

Register allocation

 

notes

3/28 T

 

Work on homework

 

4/01 M

 

Type inference

 

notes and notes

4/03 W

 

Enrichment: Pyret compilation and stack management

 

4/08 M

 

Objects

 

notes

4/10 W

 

Lexing

 

4/11 T

 

Parsing

 

4/15 M

 

No class: Patriots’ Day

 

4/17 W

 

Wrap-up

 

Testing🔗

Testing your code is sufficiently important that we’ve devoted an entire page to it. Please read these notes, for each and every assignment you work on.

Federico Cassano, a TA for the course, has also written up some helpful notes on how to debug the output of your compiler, to find what’s wrong.


Homework schedule🔗

Homework will usually be due at 8:59 PM; the day of the week varies, so you should check each individual assignment to be sure. General homework policies are here.

This homework schedule is tentative and subject to change at the instructor’s discretion.

Link

  

Assigned

  

Due

Assignment 0: OCaml warmup, part 1: basics

  

Wed 01/10

  

Sun 01/14

Assignment 1: OCaml warmup, part 2: trees

  

Wed 01/10

  

Tue 01/16

Assignment 2: Adder: A starter language

  

Wed 01/17

  

Tue 01/23

Assignment 3: Boa: Adding new operators

  

Wed 01/24

  

Thu 02/01

Assignment 4: Cobra: Multiple types of values

  

Fri 02/02

  

Fri 02/09
Sat 02/10

Assignment 5: Diamondback: Defining functions

  

Mon 02/12

  

Tue 02/20

Assignment 6: Egg-eater: Tuples

  

Wed 02/21

  

Fri 03/01

Assignment 7: Adding new data types

  

Wed 02/28

  

Fri 03/01

Assignment 8

  

Mon 03/11

  

Tue 03/19

Assignment 9

  

Wed 03/20

  

Fri 03/29

Assignment 10

  

Mon 04/01

  

Wed 04/10

Assignment 11

  

Wed 04/10

  

Fri 04/12

Assignment 12

  

Thu 04/11

  

Fri 04/26

Course policies🔗

Collaboration and academic integrity🔗

You may not collaborate with anyone on any of the exams. You may not use any electronic tools, including phones, tablets, netbooks, laptops, desktop computers, etc. If in doubt, ask a member of the course staff.

All homework assignments will be completed with a partner; some may involve a larger team (TBD). You must collaborate with your assigned partner or team, as specified, on homework assignments. You may request help from any staff member on homework. (When you are working with a partner, we strongly recommend that you request help with your partner, rather than solo.) You may use the Piazza bulletin board to ask questions regarding assignments, so long as your questions (and answers) do not reveal information regarding solutions. You may not get any help from anyone else on a homework assignment; all material submitted must be your own. If in doubt, ask a member of the course staff.

Providing illicit help to another student is also cheating, and will be punished the same as receiving illicit help. It is your responsibility to safeguard your own work.

Students who cheat will be reported to the university’s office on academic integrity and penalized by the course staff, at our discretion, up to and including failing the course.

If you are unclear on any of these policies, please ask a member of the course staff.

Homework🔗

In general, you should submit your homework according to the instructions on the web page for the individual assignments.

We have written a guide to using the handin server, which should answer most questions you have. If something is still unclear after reading that, please ask an instructor.

Submission troubles🔗

If you have trouble submitting to the server and you have time before the deadline, please wait few minutes and try again; it may also be worth checking on Piazza to find out whether other students are experiencing similar difficulties. If upon retrying you still cannot submit, email Dr. Lerner (blerner@ccs). Or if you don’t have time to try again then you should submit by email. In this (rare!) case, email your instructor with the subject line “HW N submission” (where N is the appropriate homework number). Attach your source files to the email individually; do not use a ZIP file or other kind of archive. Our email systems reject messages with archive attachments.

Late days & late work🔗

Each student gets four free, no-questions-asked late days for the term. The purpose of late days is make the extension process fair and transparent by getting the instructors out of the extension-granting business entirely. Instead, when you need an extension, you can take one — provided you have a late day remaining.

Using a late day is automatic: simply submit the homework up to one day late. The server will keep track of the number of used late days. Conserve your late days carefully.

No more than one late day may be used on any one homework. Late days cannot be divided fractionally, but must be used whole. Late days cannot be transferred to or shared with a partner, so in order to take an extension both you and your partner must have sufficient late days remaining. Choose your partners carefully.

Grades🔗

Your grade will be based on your performance on the problem sets, and the written assignments; exact weights TBD.

The grades will computed on an absolute basis: there will be no overall curving. The instructor may choose to curve an individual assignment, but please do not bank on such a chance.

The estimated mapping of raw point totals to letter grades is given below. Please note that these grade boundaries may move slightly in either direction at the discretion of the instructor: if a particular breakpoint falls in the middle of a tight cluster of numeric grades, we will attempt to move the breakpoint to give that whole cluster the same letter grade. If, near the end of the semester, you are concerned that your grade is hovering near a breakpoint, see me to discuss your concerns.

Cutoff

  

93%

  

90%

  

86%

  

83%

  

80%

  

76%

  

73%

  

70%

  

66%

  

63%

  

60%

  

else

Letter grade

  

A

  

A-

  

B+

  

B

  

B-

  

C+

  

C

  

C-

  

D+

  

D

  

D-

  

F