(For the current offering of 5535 click here).

Fundamentals of Programming Languages
CS 5535


Instructor:          Amer Diwan
Office:                  ECOT 743
Office hours:         MW 2:00 to 3:30, F 3:00 to 4:30, and by appointment
Class times:           MWF 1:00 to 1:50 p.m.
Class location:       ECCR 151
Class web page:    www.cs.colorado.edu/~diwan/5535
Grader:                  Fengxia Ma


Final project

Click  here  for information on the final project, including deadlines.

Course goals

This course will cover semantic foundations of advanced features found in modern programming languages such as Java and ML.  The course will present the material at three levels:
  1. The first level will introduce important fundamental concepts that are common across several programming languages.  These concepts include types, poly morphism, dynamic memory management, and control flow constructs.
  2. The second level will discuss how languages such as Java, Modula-3, SML, Smalltalk, C++, and Oberon implement these concepts.
  3. The third level will discuss the implications of how languages implement these concepts for compiler and run-time system.

Course requirements

Bi-weekly homework assignments 40%
Final project 20%
Midterm exams 20%
Final exam 20%
All assignments must be handed in on time except in the case of emergency.  There will be a penalty of 20% per day for late assignments.  Exams cannot be rescheduled except in the case of emergency.


We will use two texts in this course.  The first is a preprint of John Mitchell's new book, "Concepts in Programming Languages".  I'll be handing out copies of relevant chapters from this book.  The second text is John Mitchell's "Foundations for programming languages".  This book is available in the bookstore and on reserve in the Physics library.  We will be using only some chapters from this book so it is not necessary for you to buy it.  In addition to the texts, we will be reading several conference and journal papers.

Class policies

You may discuss topics covered in this class with your fellow students, but all assignments and projects that you hand in must be your own work (unless the assignment explicitly allows you to work in groups).

Mailing list

To join the class discussion list, send mail to majordomo@cs.colorado.edu, with the following as the body of your message:
  subscribe cs5535 <your email address>
Feel free to post any relevant question/opinions to this mailing list by sending mail to: cs5535@cs.colorado.edu

List of topics

The following table gives the topics we will cover in the class and the approximate number of lectures to be spent on each topic.  The "Reading" column (which will be filled in as the class progresses) lists the reading material for the class. You should do the reading for a class before attending the class.
Lectures Topics Readings
1 Course organization: types, polymorphism, memory management, control flow primitives, and exotics. Lectures in html , pdf
2 What are types? Typed and untyped languages, type safety, type equality, static and dynamic typing, strong and weak typing.   Lectures in html  pdf Mitchell handout, Sections 5.1, 5.2, 5.3
1 Types and their implications in languages: Modula 3.  Lectures in pdf Modula-3 type system (handout) 
1 Types and their implications in languages: Java.   Lectures in pdf Java type system chapters 4 and 5
1 Types and their implications in languages: Smalltalk.  Lectures in pdf The Smalltalk-80 system (handout) 
Mitchell (handout)
3 Polymorphism, data abstraction.   Lecture in pdf  Cardelli and Wegner
2 Polymorphism in languages and its implications(Modula-3, C++, Java, Smalltalk).   Lectures in pdf Stroustrup, "Multiple inheritance in C++" (avail. from Pat)
2 Polymorphism in languages and its implications (SML).  Lectures in pdf  SML tutorial, Harper upto and including page 40
1 Interaction of inheritance with encapsulation.  Lectures in pdf Updated 9/25/99 Snyder (from Pat)
1 Interaction of inheritance with concurrency (postponed)
Type inference: what, why, and how?  Lectures in pdf Mitchell handout, Sections 5.4 (you should already have this handout)
Richer type systems: pointer analysis.  Lectures in pdf Updated 9/25/99  Pointer analysis upto and including section 5.2
1 Review.  Review 2 in pdf
1 Richer type systems: finding bugs in programs  Lectures in pdf Bug detection
2 Using types to improve program performance.   Lectures in pdf  types for optimizations
1 Types discussion How the language got its spots, from Systems Programming in Modula-3, editor Greg Nelson
Types: the end   Lectures in pdf
1 Closures.   Lectures in pdf Read up on activation records, static links, and dynamic links in your favorite programming languages text
1 Exceptions including Java and Modula-3 case studies.  Updated 10/22/99  Lectures in pdf. Exceptions in Java chapters 11, 14.16, and 14.18
M-3 Discussion
1 Implementation implications of exceptions  Lectures in pdf.Updated 10/25/99   
1-2 Continuations including case studies.  Lectures in pdf.  Notes from Hodas ,  Notes from Harper's tutorial
1 Implications of continuations.   Lectures in pdf. Representing control in the presence of first-class continuations, Hieb, Dybvig, Bruggeman (handed out in class)
1 Automatic versus manual allocation and deallocation.  Lectures in pdf.Updated 11/03/99 Wilson survey
1 Algorithms for memory management: accurate or conservative, copying, mark-and-sweep, and reference counting
1 Review.   Review 2 in pdf.
1 Implications of language features for memory management implementation. Lectures in pdf. Updated 11/15/99  Detlefs, Agesen, and Moss, 1998
2 Persistent programming languages.  Lectures in pdf  Atkinson and Morrison, 1995 Upto and including section 4
1 Delegation.   Lectures in pdf  Self paper
1 Multiple dispatching.   Lectures in pdf  Cecil paper
Next Lecture
Review.   Lecture in pdf


 Homework 1
 Homework 2
 Homework 3 Solution in pdf
 Homework 4 Solution in pdf
 Homework 5   Solution in html.
 Homework 6   Solution in html

Interesting links

 C++ language definition
 Modula-3 language definition
Java language definition
 Full SML tutorial