For 2011, the course number has changed to COMP 411.

COMP 311 Principles of Programming Languages (Fall 2010)

Professor Robert "Corky" Cartwright

Department of Computer Science

Rice University

Houston, Texas, USA

Fall 2010: Room 117, Herzstein Hall, Monday, Wednesday, Friday, 1:00pm–1:50pm

Course News


COMP 311 is an introduction to the principles of programming languages. It focuses on:

In the lecture materials, interpreters are written in concise functional notation using Scheme. In some cases, supplementary material showing how the same interpreters can be written in OCaml (using explicit typing) are provided. While Java is a very good vehicle for implementing these interpreters, it is not a good conceptual representation because it is much too wordy and the OO structure obscures the simple algebraic structure of abstract syntax and structural recursion used to defin interpretation.

A secondary theme is software engineering. All of the programming assignments in this course are conducted in Java using test-driven development and pair-programming, two of the major tenets of Extreme Programming.

COMP 311 consists of three parts:

The course enables students to analyze the semantics and pragmatics of the old, new, and future programming languages that they are likely to encounter in the workplace (e.g., Fortran, C, C++, Java, Visual Basic, C#, Perl). They will also be able to build efficient interpreters for new languages or for "special-purpose" languages embeded in software applications. Finally, they will be much be equipped as software developers because they will understand how to define and implement whatever linguistic extensions are appropriate for simplifying the construction a particular software system.

Notes on the common mathematifcal notation used in operational semantics, some of which will be used in class.

Course Information

Please take a look at the course information discussed on the first day of classes


Please refer to the assignments column in the below.


Powerpoint slides for selected lectures are available in this directory.

# Date Day Topic Reference Assignment
1 8/23 M Information & Motivation
2 8/25 W Parsing Component Pascal Syntax Diagrams Project 1 assigned, 8/25
Reference: Notes on Object-Oriented Program Design
3 8/27 F
4 8/30 M The Scope of Variables Essentials, ch. 1
5 9/1 W Syntactic Interpreters Brief Review of Lectures 1-6
6 9/3 F
9/6 M Labor Day Holiday
7 9/8 W A Syntactic Interpreter for LC (cont'd) Essentials, ch. 3.1–3.6, 3.8 Project 1 due 12 noon, 9/8
Project 2 assigned, 9/8
8 9/10 F A Meta Interpreter for LC
9 9/13 M
10 9/15 W Eliminating Meta Errors
11 9/17 F
12 9/20 M Data Domains Supporting Recursive Definitions The Why of Y
Recursive Programs as Definitions in First-Order Logic
Domain Theory: An Introduction
Types as Intervals
The Lambda Calculus as a Model of Computation

13 9/22 W
14 & 15 9/24 F Recursive Definitions and Environments Supplemental Material Project 2 due 12 noon, 9/24
Project 3 assigned, 9/24
14 & 15 9/27 M
16 9/29 W
16 (continued) 10/1 F Review Hand Evaluation Exercises Solution to Hand Evaluation Exercises
17 10/4 M Assignment and Mutability Essentials, ch. 3.7, 3.9
18 10/6 W
18 (continued) 10/8 F
10/11 M Midterm Recess — No Classes
X10 10/13 W Guest Lecture on X10 by Vivek Sarkar
Project 3 due 12 noon, 10/13
Project 4 and 4xc assigned, 10/13
Sample Exam 1
Solutions to Sample Exam 1

19,20 10/15 F Run-time Environment Representation and Control
Essentials, ch. 7, 8
Powerpoint slides taken from Sebesta's book Concepts of Programming Languages
Exam 1 Review 10/18 M Sample Exam 1 Essentials, ch. 5 Exam 1 distributed in class, 10/18
Binding/bound occurrences, Problem 3
Call-by-name hand evaluation, Problem 5(i)
Call-by-value hand evaluation, Problem 5(ii)
21 10/20 W Object-Oriented Languages Featherweight Java (Optional) Project 4 due 12 noon, 10/22
Project 5 and 5xc assigned, 10/22
4xc due 12 noon, 10/26
21 (continued) 10/22 F
22 10/25 M What Is a Type?, Types and Safety Essentials, ch. 4 Exam 1 due in class, 10/25
22 10/27 W Exam Discussion
22 10/29 F Types and datatype
23 11/1 M Essentials, ch. 6
23 11/3 W Polymorphism Project 5 and 5xc due 12 noon, Monday, 11/8
Project 6 (PDF) assigned, Monday, 11/8
24 11/5 F Implicit Polymorphism Type Inference Study Guide
25 11/8 M Final Words on Types
26 11/10 W The Meaning of Function Calls Essentials, ch. 8
27 11/12 F Continuation-Passing Style
28 11/15 M
29 11/17 W Explaining letcc and error & The True Meaning of Function Calls
30 11/19 F Garbage Collection Uniprocessor Garbage Collection Techniques Dynamic Storage Allocation Survey Project 7 assigned, 11/19
31 11/22 M Project 6 due noon, 11/22
31 11/24 W Copying Collection Sample Exam 2

Sample Exam 2 With Solutions
Exam 2 handed out in class, 11/24
11/26 F Thanksgiving Recess — No Classes
32 11/29 M Generational Collection
41 12/1 W Review
42 12/3 F OO Optimization; Java Concurrency Project 7 due at 11:59 PM, 12/3
Exam 2 due at 11:59 PM, 12/3

Language Resources

  1. Java
    1. SDK Download
    2. Generic Java Documentation
    3. API Reference
    4. DrJava Programming Environment
    5. Elements of Object-Oriented Program Design by Prof. Cartwright
  2. Scheme
    1. How to Design Programs
    2. DrScheme Programming Environment
  3. OCaml
    1. OCaml Book
    2. O'Caml Language
    3. MetaOCaml
    4. OCamlLex
    5. Using "Ledit" to make Ocaml recognize arrow keys

Additional References

  1. Friedman, Wand, and Haynes, Essentials of Programming Languages, 2nd ed. (MIT Press, 2001)
    You should take a look at the following two new chapters, which the authors prepared for the second edition:
    1. Parameter Passing ( local file, PDF)
    2. Types and Type Inference ( local file, PDF)
  2. Evaluation rules for functional Scheme ( PDF)
  3. References on evaluating Jam programs
  4. Lecture Notes on Types I
  5. Lecture Notes on Types II
  6. Introduction to System F (Polymorphic Lambda-Calculus)
  7. Scheme code from Class Lectures
  8. The Essence of Compiling with Continuations by Flanagan et al.
  9. Uniprocessor Garbage Collection Techniques by Paul Wilson
  10. Garbage Collection [canonical textbook] by Jones and Lins
  11. Space Efficient Conservative Garbage Collection by Hans Boehm ( local file, PDF)
  12. Hans Boehm's Conservative GC Webpage
  13. The Java Virtual Machine. The most basic expository articles appear at the end of the index. Read it from bottom up.
  14. Java Memory Model
  15. Revised Thread Synchronization Policies in DrJava (doc) ( pdf). Since DrJava is built using the Java Swing library, it must conform to the synchronization policies for Swing. Unfortunately, the official Swing documentation is sparse and misleading in places, so this document includes a discussion of the Swing synchronization policies.
  16. Lesson: Concurrency in Swing. This lesson discusses concurrency as it applies to Swing programming. It assumes that you are already familiar with the content of the Concurrency lesson in the Essential Classes trail.
  17. Concurrency in Swing Text
  18. The Last Word in Swing Threads
  19. Old Course Website
  20. Advertisement for COMP 402: Production Programming

Accomodations for Students with Special Needs

Students with disabilities are encouraged to contact me during the first two weeks of class regarding any special needs. Students with disabilities should also contact Disabled Student Services in the Ley Student Center and the Rice Disability Support Services.