Index
Announcements
Instructor Contact Info
Course Description
Course Textbooks
Programming Exercises
Course Policies
Course Mailing List
Course Schedule
Homework Assignments
Homework Solutions
Handouts
Sample Code
Additional Useful Links
Programming in SML
SML/NJ FAQ
Announcements/Updates
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
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
-
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
is cmsc22100@cs.uchicago.edu.
The web page for the mailing list is at
http://mailman.cs.uchicago.edu/mailman/listinfo/cmsc22100.
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
Handouts
Here are links to PDF files of the handouts.
Rule Induction for Arith+Let
(cs221-style.tex)
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.