Course Schedule

The course schedule is always open to change and revision.  The course will have weekly assignments, due at midnight, usually on Thursdays. 

Many of the lecture notes come from Professor David August, with only minor modifications by myself.  I really appreciate David's help making this a better course.

The overall course project requires that students compile the Fun language.  The definition of Fun is here.  In the second half of the term, we will be using the SPIM simulator.  Documentation for SPIM is here.

In order to prepare for exams, I recommend doing some exercises from Appel's textbook.  This document contains a list of recommended exercises from the textbook and some additional exercises I have made up myself.  These exercises are completely optional and will not be graded.  Their only purpose is to help you study.  Use them however you choose.  I recommend trying each problem first yourself before asking your friends about how to solve it.

Week Topics Notes Assignments: Due Date
1 (Feb 7) Intro; SML

A Guide to Using SML/NJ

Online SML Book

Appel Chap 1

Course & ML Intro, part 1; ML Intro part 2

notes on installing sml and emacs mode

A1:  Intro to SML

Due February 16

2 (Feb 14) Lexical Analysis; Parsing Intro

Appel Chap 2

Lexing notes

CFGs & LL(1) parsing

A2: Lexical Analysis

Due February 23

3 (Feb 21) Parsing;

Appel Chap 3

LL(1) continued & bottom-up beginning


A3:  MLYacc Parsing

Due March 7

4 (Feb 28) Parsing;

Type Checking

Appel Chap 4-5

Harper text Chap 12.1 and 12.2 (not the proofs)

LR parser table construction

judgments notes (.doc) (html)

5 (March 7) Type Checking

Harper text on Subtyping Chap 32, 33 (not the proofs)

typing and subtyping notes(.doc) A4:  Type Checking

Due (Friday) March 17

6 (March 14) Closure conversion

Garbage Collection

Appel Chap 13

gc notes  
Break (March 21) Bliss    
7 (March 28) Midterm Mar. 28 (see below for topics)

Stack Frames

Appel Chap 6.1

Activation Records & Stack Frames (.pdf) A5: Garbage Collection

Due April 6

8 (April 4)

Maximum munch & dynamic programming for instruction selection

mips and spim; Appel Chap 9.1,9.2

Class was on the blackboard (see text chap 9.1 and 9.2 for notes) A6: Code Generation

Due April 20

9 (April 11) Dataflow analysis

Appel Chap 10.1, 17.1-17.3

Some dataflow notes (class was on the blackboard)  
10 (April 18) Register Allocation

Appel Chap 11.1-11.4

Register Allocation via graph coloring (.ppt) A7: Liveness Analysis & Interference Graph Construction

Due May 2

11 (April 25) Loop Optimizations

Static Single Assignment

Appel Chap 18.1-18.3, 19.1, 19.3

See Appel text for notes A8: Register Allocation

Due May 9

12 (May 2) Advanced Language Features

Objects and Threads

Appel Chap 14.1-14.5

Objects Notes

Threads Notes

Final Exam (May 18, 7:30PM, CS Building 102) All topics    

  Midterm Topics
  • In general, everything discussed in class, assignments or text is fair game

Programming Interpreters

  • Assignment #1
  Lexical Analysis 
  • Regular expressions
  • ML-Lex
  • Assignment #2
  • Appel Chap 2, 2.1, 2.2, 2.5
  • Context-free grammars
  • Top-down parsing
  • Bottom-up parsing
  • Classifying grammars:  LL(k), LR(k), SLR, LALR, ambiguous
  • Semantic actions & generating abstract syntax
  • ML-Yacc
  • Error recovery techniques
  • Assignment #3
  • Appel Chap 3, 4
  Type checking
  • Inductive definitions and typing rules
  • MinML & Fun typing
  • Subtyping
  • Type checking algorithms
  • Assignment #4
  • Harper Chap 9, 26 (not the lemmas or proofs)

Closure conversion

  • definitions:  free variables, closed functions, closure data structures
  • formal definition of closure conversion algorithm using inference rules