CMSC 221: Programming Languages

Fall Quarter, 2005 
TTh, 1:30 pm - 2:50 pm
Ryerson 276


Instructor Contact Info
Course Description
Course Textbooks
Programming Exercises
Course Policies
Course Mailing List
Course Schedule
Homework Assignments
Homework Solutions
Sample Code
Additional Useful Links
Programming in SML


The first class will be on Tuesday, Sept. 27, 2005 at 1:30pm in Ry 276. Prof. MacQueen will be away the first week of the term, so the first two lectures will be given by Adam Shaw as guest lecturer.

This year for the first time, there will be a separate graduate Programming Languages course, CMSC32100, given by Prof. Umut Acar of TTI-C.

Instructor Contact Info

Name Role Office Office hours Phone Email
David MacQueen Professor Ryerson 256 By appointment 2-4980
George Kuan TA Hinds 030 3:00pm - 5:00pm Friday 5-0160 gkuan [at] cs [dot] uchicago [dot] edu

Course Description

Programming languages are the most fundamental tools involved in the creation of software, and thus play a key role in computing. This is a foundational course exploring the principles and concepts underlying the design of programming languages. We use a formal approach based on operational semantics to give clear and precise descriptions of language concepts, such as flow of control, data structures and types, modularity and abstraction, and concurrency. The major paradigms of imperative, functional, and object-oriented paradigms will be discussed.

Students should have experience programming in one or more programming languages, and some familiarity with basic concepts of naive set theory and logic would be helpful.

Course Textbook

The main textbook for the course is Programming Languages: Theory and Practice by Robert Harper. There are two versions: online.pdf for reading online using a PDF reading like Adobe Reader, and offline.pdf for printing (these links are for local copies on the department web server).

Programming Exercises

This is not a course centered on programming projects, but programming examples and exercises that show how to implement the ideas expressed in operational semantics will be given using the language Standard ML. There are several good sources of documentation and tutorials for SML/NJ available online, and some of these are given in the course SML/NJ page.

Course Policies

Course Mailing List

A mailing list has been created for the course. The address is The web page for the mailing list is at

Course Schedule

Here is a tenative schedule of the lectures. This is subject to midcourse adjustment, of course.

Date Topic Reading
9/27 Introduction and admin; inductive defs and transition systems Ch. 1 & 2
9/29 Specifying language syntax Ch. 3--4
10/4 Abstract binding trees; Static semantics Ch. 6 & 7
10/6 Dynamic semantics; intro to MiniML Ch. 8
10/11 MiniML continued Ch. 9
10/13 Type safety Ch. 10
10/18 Abstract machines Ch. 11
10/20 Continuations Ch. 12
10/25 Exceptions Ch. 13
10/27 Imperative functional programming Ch. 14
11/1 Midterm review
11/3 Midterm exam
11/8 Aggregate Data Structures Ch. 19
11/10 Polymorphism and Data Abstraction Ch. 20 & 21
11/15 Dynamic Typing Ch. 24
11/17 Featherweight Java Ch. 25
11/22 Subtyping Ch. 26
11/24 Thanksgiving
11/29 Inheritance Ch. 29
12/1 Final review (Reading Period)

Homework Assignments

Here are links to PDF files of the homework assignments.
Homework 1 (due Oct 4); Homework 2 (due Oct 13); Homework 3 (due Oct 18); lambda-subst.sml (code for problem 4); Homework 4 (due Oct 25); Homework 5 (due Nov 1); minml-SOS.sml (code for problem 4); Homework 6 (due Nov 15); minml-C.sml (code for problem 3); Homework 7 (due Nov 22); Homework 8 (due Thursday, Dec 1).

Midterm Solutions

Midterm Solutions


Here are links to PDF files of the handouts.
Rule Induction for Arith+Let
Alternate E-machine description.
Description of Landin's SECD machine.

Sample Code

Here are links to sample code.

arith.sml: arithmetic with let, calculating free variables
arith-interp.sml: simple interpreter for arithmetic with let (single variable substitutions)
arith-SOS.sml: SOS-style evaluator for arithmetic using substitutions
arith-ENV.sml: environment-based evaluator for arithmetic
arith-EV.sml: EV-style evaluator for arithmetic using substitutions
arith.scm: environment-based evaluator for arithmetic (scheme version)
Type checker and evaluator for MiniML
Big-step evaluator for pure lambda calculus
Evaluator for lambda calculus using environments
Tarball of code for Reynolds "Definitional Interpreters" paper
E-machine evaluator for MinML
SECD machine evaluator for MinML
SECD compiler for MinML
E-machine evaluator for MinML with products
Type checker and evaluator for MinML with recursive types
Interactive interpreter for extended MinML (tarball)

Papers and Presentations

Definitional Interpreters for Higher-Order Progamming Languages by John Reynolds (1972)
A Structural Approach to Operational Semantics by Gordon Plotkin.
The Discoveries of Continuations by John Reynolds.
Structure and Abstraction in HOT Languages (Marktoberdorf Summer School Notes, 2000).

Additional Useful Links

Frank Pfenning at CMU has a web site for his version of a course 15-312 Foundations of Programming Languages based on Harpers draft book. This web site has some very useful supplementary lecture notes, as well as assignments, software, and other resources. You may find it useful to browse through this site and download some of the material.

Dave MacQueen
Last modified: Thu Sep 27 13:53:12 CDT 2007