CMSC 22610
Implementation of Computer Languages - I
Winter 2009



Schedule

Date:  Topic:  Homework:  Project: 
Jan. 6, Tu Course introduction and overview;
Introduction to Standard ML (I)
Homework 1 out
Jan. 8, Th LangF project discussion;
Introduction to Standard ML (II)
Project 1 out
Jan. 13, Tu Specification vs. derivation vs. implementation;
Introduction to scanning and regular expressions;
Theory of regular expressions
Homework 1 due
Jan. 15, Th Non-deterministic and deterministic finite automata;
Implementation of regular expressions and FSMs;
Scanning with REs and DFAs
Jan. 20, Tu (Fluet away; Shaw lecturing);
Implementation of DFAs in SML;
Lexical analyzer generators (ml-ulex)
Jan. 22, Th (Fluet away; Shaw lecturing);
Introduction to parsing and context-free grammars
Project 2 out;
Project 1 due (Fri.)
Jan. 27, Tu Theory of context-free grammars;
Grammar transformations
Homework 2 out
Jan. 29, Th Recusive descent and predictive parsing
Feb. 3, Tu LR parsing (LR(0); SLR; LR(1); LALR(1)) Homework 2 due
Feb. 5, Th Parsing and semantic actions;
Parser generators (ml-yacc and ml-antlr);
Error recovery;
Other parsing techniques (parser combinators; GLR; PEG)
Homework 3 out Project 2 due (Mon.)
Feb. 10, Tu Introduction to static analysis;
Binding analysis;
Introduction to inference rules
Feb. 12, Th Midterm exam (in class) Project 3 out
Feb. 17, Tu Inference rules and type checking
Feb. 19, Th (Fluet away; Blume lecturing);
Implementation of type checker in SML
Homework 3 due
Feb. 24, Tu Midterm review;
Polymorphic type equality
Feb. 26, Th Tree interpreters Project 4
out;
Project 3 due (Fri.)
Mar. 3, Tu Variable locations;
Virtual machines (stack, heap);
Higher-order functions (calling conventions)
Mar. 5, Th Virtual machines (instruction encodings);
Bytecode generation.
Mar. 10, Tu Garbage collectors (mark-sweep and Cheney-copy);
Course conclusion
... Reading Period ...
Mar. 17, Tu Final Exam (1:30pm – 3:30pm; Ryerson 251)
Mar. 20, Fr Project 4 due

Possible Future Topics

regular-expression derivatives; attribute grammars; derived forms; semantic analysis (overview); semantic analysis (polymorphic type checking and Algorithm W); real-world type checking (error messages); intermediate representations (typed intermediate representations, direct style, A-normal form); elaboration into intermediate representation; rewrite rules.


Last modified: Sun Mar 15 19:20:04 CDT 2009