(For the current offering of 5535 click here).

Fundamentals of Programming Languages
CSCI 5535

Administrivia

Instructor:          Amer Diwan
Office:                  ECOT 743
Office hours:         MWF 2:00 to 3:30 and by appointment
Class times:           MWF 1:00 to 1:50 p.m.
Class location:       CATECS studio ECCS 1B28
Class web page:    www.cs.colorado.edu/~diwan/5535-00
Grader:                  Shah Bhatti
 

Exams

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, polymorphism, dynamic memory management, and control flow constructs.
  2. The second level will discuss how languages such as Java, Modula-3, SML, Smalltalk, and C++ 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 50%
Class participation 10%
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.

The class participation component applies only to in-class students.   It involves the following:

I would like this to be a very interactive class--they are much more fun that way!

Text

For the most part we will not be using any text for this course.  However, occasionally I will want you to read up background material in an introductory programming languages text.  For this I will list sections from three programming languages texts: Programming Language Pragmatics by Michael Scott (Scott),  Concepts of Programming Langauges 4th Edition (Sebesta) by Robert W. Sebesta, and Programming Language Concepts 3rd Edition by Carlo Ghezzi (Ghezzi).  You need to read any one of the three.  If any one of them provides a particularly good treatment of the topic then I will underline that choice  The engineering library has copies of all three texts on reserve.

As mentioned above, most readings will be from papers and language specifications.  These readings are always compulsory.  When the reading is available on-line, I have a link to its on-line location.  However, some of these readings are not available on-line: I will distribute hard copies of these readings.

Class policies

You may discuss topics covered in this class with your fellow students, but all assignments that you hand in must be your own work (unless the assignment explicitly allows you to work in groups).  If you include any text or figures from any source in your submitted work you must clearly indicate it in your submission and include a citation to the original source.

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

All archives of the mailing list are available here

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 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 and overview.   Lecture in pdf
TYPES
2 What are types? Typed and untyped languages, type safety, type equality, static and dynamic typing, strong and weak typing.   Lecture in pdf (Updated 8/30/00) Ghezzi (3.4 upto and including 3.4.5) or
Scott (Sections 7.2.1, 7.2.2, 7.2.3)
1 Types and their implications in languages: Modula 3.   Lecture in pdf (Updated 9/11/00) Modula-3 type system (POPL 90)
1 Types and their implications in languages: Java,  Java lecture in pdf. Java type system chapters 4 and 5
1 Types and their implications in languages: Smalltalk  Lecture in pdf The Smalltalk-80 system (Byte) and

[Sebesta (Sections 11.4, 11.5, 11.6) or
  Scott (Sections 10.6.1) or
   Ghezzi (Section 6.3.4)]
1 Types discussion  Discussion slides in pdf How the language got its spots, from Systems Programming in Modula-3, editor Greg Nelson
POLYMORPHISM
4 Polymorphism, data abstraction. Lecture slides in pdf-1 Lecture slides in pdf-2 (updated 9/26/00)  Cardelli and Wegner
Sections 1 and 2 for first lecture 
Sections 3, 4, and 5 for second lecture
Sections 6, 7, 8, and 9 for third lecture
2 Polymorphism in languages and its implications(Modula-3, C++, Java, Smalltalk).Lecture slides in pdf
additional example		 Stroustrup, "Multiple inheritance in C++" 
Optional but worthwhile: Chapter 12 of "The design and evolution of C++", Bjarne Stroustrup (on reserve)
1 Polymorphism in languages and its implications (SML). Lecture slides in pdf  SML tutorial, Harper upto and including page 40
1 Interaction of inheritance with encapsulation. Lecture slides in pdf Snyder (OOPSLA 86)
1  Type inference: what, why, and how? Lecture slides in pdf Scott 7.2.5
1  Richer type systems: pointer analysis.  Lecture slides in pdf Steensgaard upto and including section 5.2
1 Richer type systems: finding bugs in programs Lecture slides in pdf Callahan and Jackson
2 Using types to improve program performance. Lecture slides in pdf  Diwan, McKinley, and Moss
CONTROL STRUCTURES
1 Closures. Lecture slides in pdf Scott: 3.3 or
Ghezzi: 2.7.1 to 2.7.4 inclusive or
Sebesta: 9.3
1 Exceptions including Java and Modula-3 case studies. Lecture slides in pdf Exceptions in Java chapters 11, 14.16, and 14.18
M-3 Discussion, Threads
1 Implementation implications of exceptions  Lecture slides in pdf  
1-2 Continuations including case studies. Lecture slides in pdf  Notes from Hodas ,  Notes from Harper's tutorial
1 Implications of continuations. Lecture slides in pdf Hieb, Dybvig, Bruggeman PLDI 90
1 Language design discussion.   Guy Steele's OOPSLA talk
MEMORY MANAGEMENT
2 Automatic versus manual allocation and deallocation.  Algorithms for memory management: accurate or conservative, copying, mark-and-sweep, and reference counting  Lecture slides in pdf Wilson survey
1 Implications of language features for memory management implementation. Lecture slides in pdf  Detlefs, Agesen, and Moss, 1998
NEW TRENDS
2 Persistent programming languages.  Lecture slides in pdf  Atkinson and Morrison, 1995 Upto and including section 4
1 Introduction to language semantics Ghezzi 2.1 (handout)
1 Delegation.  Lecture slides in pdf  Self paper
1 Discussion  Aspect oriented programming
1 Review.  Lecture slides in pdf

Homeworks

You may substitute one of the homeworks in the term with a project. The project can be on any topic of your choosing (as long as it is relevant to the class), must be no longer than 2 typed pages using reasonable font and spacing, and must involve reading one or more papers and discussing them.  If you are planning to substitute a project for a homework assignment, your project must be submitted on the deadline for the homework assignment.  You don't need to notify me in advance that you will be submitting a project instead of a particular assignment.  The front page of your submission should indicate that it is a project and not a homework assignment.  Before you embark on a project you must get my approval on the topic.
  1. Homework 1
  2. Homework 2
  3. Homework 3
  4. Homework 4
  5. Homework 5
  6. Homework 6   Sample solution in pdf

Interesting links

 C++ language definition
 Modula-3 language definition
 Using opaque types for Modula-3 I/O library
 Java language definition
 Full SML tutorial
 Ada reference manual
Eiffel