CMSC 22610
Implementation of Computer Languages I
Winter 2011

Schedule

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