CMSC 336: Type Systems for Programming Languages

Winter Quarter, 2003 
Tuesdays and Thursdays, 12:00 - 1:20 pm
Ryerson 277


Instructor Contact Info
Course Description
Course Textbook
Course Policies
Course Schedule
Course Homework Exercises
Additional Useful Links
Programming in SML


Instructor Contact Info

Name Role Office Office hours Phone Email
David MacQueen Professor Ryerson 256 Tue, Thu: 3:30-5:00pm (773) 702-4980

Course Description

Type systems are formal systems or languages for describing the structure of data and program interfaces. They are of immense practical utility because they provide a valuable though weak form of program specification that can be automatically checked by compilers. Extensive research in the area of type systems has also contributed to our basic understanding of the architecture and meaning of programming languages.

The use of type systems in the design and analysis of languages has been particularly successful for functional and object-oriented languages, so most of the language examples will be taken from these families of languages.

This course will cover the basic ideas of type systems, their formal properties, their role in programming language design and their implementation. Exercises involving design and implementation will explore the various options and issues.

Course Textbook

We will use the following textbook: Types and Programming Languages by Benjamin C. Pierce.

The textbook may be purchased at the Seminary COOP Bookstore on University.

Almost all the material covered in the course is included in this text book. The lecture slides will also be made available as PowerPoint and postscript or pdf documents.

Course Policies

Course Schedule

Here is a tenative, and probably overly ambitious, schedule of the lectures. This is subject to continual adjustment, of course.

Lecture Date Topic Reading Slides Code
0 1/07 Introduction, overview, history, administration 1, (2) ppt,pdf  
1 1/09 Preliminaries: syntax, operational semantics 3,4 ppt,pdf arith.tgz, source.tgz
2 1/14 Introduction to the lambda-calculus 5.1,5.2 ppt,pdf  
3 1/19 Formalizing the lambda-calculus 5.3, 6, 7 ppt,pdf untyped.tgz
4 1/21 Types; the simply typed lambda-calculus 8,9,10 ppt,pdf tyarith.tgz
5 1/23 Simple extensions; derived forms 11 ppt,pdf letexercise.tgz
6 1/28 More extensions 11    
7 1/30 References 13    
8 2/4 Subtyping 15    
9 2/6 Metatheory of subtyping 16,17    
10 2/11 Imperative objects 18 ppt,pdf  
11 2/13 Recursive types 20    
12 2/18 Metatheory of recursive types 21 ppt,pdf  
13 2/20 Type reconstruction 22 ppt,pdf  
14 2/25 Universal polymorphism 23 ppt,pdf  
15 2/27 Existential polymorphism; ADTs 24, (25) ppt,pdf  
16 3/4 Bounded quantification; objects 26, 27    
17 3/6 Type operators; F-omega 29,30    
  3/18 Final Exam      

Additional Useful Links