CMSC 221: Programming Languages
Fall Quarter, 2005
TTh, 1:30 pm - 2:50 pm
Instructor Contact Info
Course Mailing List
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,
given by Prof. Umut Acar of TTI-C.
Instructor Contact Info
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.
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).
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.
Grading will be based on the following:
Homework exercises: 40%
Midterm exam: 25%
Final exam: 35%
Assigments: Homework assignments will normally be given on Tuesdays and
will be due at the beginning of class the following Tuesday. Late
homework can be handed in the class following the due date with a 30% penalty.
Collaboration: As in most courses, we encourage students to discuss
course material among themselves. Discussions of assignment problems is
also permitted to an extent, but submitted assignments should be your
own work, and collaborative discussions should be acknowledged.
Final Examination: The final examination will be a two hour in-class
exam given at 1:30pm on Dec 6 (time/date to be confirmed).
Course Mailing List
A mailing list has been created for the course. The address
The web page for the mailing list is at
Here is a tenative schedule of the lectures. This is subject to
midcourse adjustment, of course.
||Introduction and admin; inductive defs and transition systems
||Ch. 1 & 2
||Specifying language syntax
||Abstract binding trees; Static semantics
||Ch. 6 & 7
||Dynamic semantics; intro to MiniML
||Imperative functional programming
||Aggregate Data Structures
||Polymorphism and Data Abstraction
||Ch. 20 & 21
||Final review (Reading Period)
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).
Here are links to PDF files of the handouts.
Rule Induction for Arith+Let
Alternate E-machine description.
Description of Landin's SECD machine.
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
arith-ENV.sml: environment-based evaluator for arithmetic
arith-EV.sml: EV-style evaluator for arithmetic using
arith.scm: environment-based evaluator for arithmetic
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
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
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.
Last modified: Thu Sep 27 13:53:12 CDT 2007