COMP 311 Principles of Programming Languages (Fall 2008)
Professor Robert "Corky" Cartwright
Department of Computer Science
Rice University
Houston, Texas, USA
Fall 2008: Room 1046, Duncan Hall, Monday, Wednesday, Friday, 1:00pm–1:50pm

Course News

Summary

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

  • identifying the conceptual building blocks from which lanugages are assembled and
  • specifying the semantics of programming languages using interpreters.
    • A secondary theme is software engineering. All of the programming assignments in this course are conducted using test-driven development and pair-programming, two of the major tenets of Extreme Programming.

    COMP 311 consists of three parts:

  • The first part focuses on specifying the syntax and the semantics of programming languages. The former is introduced via simple parsing (translations) of program text into abstract syntax. Topics like lexical analysis and advanced parsing methods are left to COMP 412, a course on compilers. The semantics of a comprehensive collection of programming language constructs is specified using interpreters and reduction systems. The constructs include arithmetical and conditional expressions, lexical binding of variables, blocks, first-class functions, assignment and mutuation, simple control constructs (loop exits, first-class continuations, simple threads), and dynamic dispatch.

  • The second part illustrates how interpreters and reduction semantics can be used to analyze the behaviorial properties of programming languages. Two examples are covered: type safety and memory safety. Type safety guarantees that programs respect syntactically defined type abstraction boundaries and never raise certain classes of error signals. Memory safety guarantees that programs release memory if it is provably useless for the remainder of the evaluation. Type safety typically depends on memory safety.

  • The third part shows how interpreters can systematically be transformed so that they use fewer and fewer language facilties. The key transformations are the explicit representation of closures as records and the conversion of program control flow to continuation-passing style. Using these transformations, a recursive interpreter can quickly be be re-written in a low-level language like C/C++ or assembly language. These transformations can be applied both to interpreters and to arbitrary programs. if we apply these transformations to an interpreter, the result is a low-level interpreter that is easily implemented in machine code. The process of applying these transformations to arbitrary input programs yields a high-level description of program compilation, a process which is explored in more detail in COMP 412.

    • The course enables students to ask relevant technical questions about 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.

    Notes in the notation we use in class.

    Course Information

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

    Assignments

    Please refer to the assignments column in the below.

    Lectures

    #

    		Date

    		Day

    		Topic

    		Reference

    		Assignments

    1

    		 8/25

    M

    		 Introduction & Motivation

    2

    		 8/27

    W

    		 Parsing Project 1 assigned, 8/27

    3

    		 8/29

    F

     

    		 9/1

    M

    		 Labor Day - No Classes  

    4

    9/3

    W

    		 The Scope of Variables Essentials, ch. 1

    5

    		 9/5

    F

    		 A Syntactic Interpreter for LC Review 1 

    6

    		 9/8

    M

    7

    		 9/10

    W

    		 A Syntactic Interpreter for LC (cont'd)   Project 1 due 12 noon, 9/10
    Project 2 assigned, 9/10

    8

    		 9/12

    F

    		 A Meta Interpreter for LC Essentials, ch. 3.1-3.6, 3.8

    9

    		 9/15

    M

    10

    		 9/17

    W

    		 Eliminating Meta Errors  

    11

    		 9/19

    F

    12

    		 9/22

    M

    		 Data Domains Supporting Recursive Definitions The Why of Y
    Domain Theory: An Introduction
    Types as Intervals
    The Lambda Calculus as a Model of Computation    		 Project 2 due 12 noon, 9/22
    Project 3 assigned, 9/22

    13

    		 9/24

    W

    14

    		 9/26

    F

    		 Recursive Definitions and Environments  

    15

    		 9/29

    M

    16

    		 10/1

    W

    17

    		 10/3

    F

    		 Review Supplemental Material Hand Evaluation Exercises,
    Solution to Hand Evaluation Exercises

    18

    		 10/6

    M

    		 Assignment and Mutability Essentials, ch. 3.7, 3.9

    19

    		 10/8

    W

    20

    		 10/10

    F

    		 Environment Representation and Control Essentials, ch. 7, 8

    		10/13

    M

    		 Midterm Recess - No Classes

    21

    		 10/15

    W

    		 Environment Representation and Control Essentials, ch. 7, 8

    22

    		 10/17

    F

    		 Object-Oriented Languages, Featherweight Java Essentials, ch. 5 Project 3 due 12 noon, 10/17
    Project 4 and 4xc assigned, 10/17

    23

    		 10/20

    M

    24

    		 10/22

    W

    25

    		 10/24

    F

    		 Review

    26

    		 10/27

    M

    		 What Is a Type?, Types and Safety Essentials, ch. 4

    Project 4 and 4xc due 12 noon, 10/27
    Project 5 assigned, 10/27
    Sample Exam 1 posted, 10/27
    Solutions to Sample Exam 1 posted, 10/27

    27

    		 10/29

    W

    		 Types and datatype  

    Exam 1 distributed in class, 10/29

    28

    		 10/31

    F

    29

    		 11/3

    M

    		 Polymorphism Essentials, ch. 6

    30

    		 11/5

    W

    		 Exam Discussion

    		Exam 1 due in class, 11/5

    31

    		 11/7

    F

    		 Implicit Polymorphism Type Inference Study Guide

    32

    		 11/10

    M

    		 Final Words on Types   Project 5 due 12 noon, 11/10
    Project 6 (PDF) assigned, 11/10

    33

    		 11/12

    W

    		 The Meaning of Function Calls Essentials, ch. 8

    34

    		 11/14

    F

    		 Continuation-Passing Style  

    35

    		 11/17

    M

    		 Type Inference Study Guide

    36

    		 11/19

    W

    		 Explaining letcc and error & The True Meaning of Function Calls  

    37

    		 11/22

    F

    		 Garbage Collection Uniprocessor Garbage Collection Techniques Project 6 due noon, 11/26
    Project 7 assigned, 11/22

    38

    		 11/24

    M

    39

    		 11/26

    W

    		 OO Code Optimization Sample Exam 2 Exam 2 handed out in class, 11/28

     

    		 11/28

    F

    		 Thanksgiving Recess - No Classes  

    40

    		 12/3

    M

    		 TBA    

    41

    		 12/3

    W

    		 TBA    

    42

    		 12/5

    F

    		 TBA   Project 7 due at 11:59 PM, 12/5
    Exam 2 due at 11:59 PM, 12/5

    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. Robert "Corky" Cartwright (pdf)
    2. Scheme
      1. How to Design Programs
      2. DrScheme Programming Environment
    3. O'Caml
      1. O'Caml 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. Scheme code from Class Lectures
    7. Uniprocessor Garbage Collection Techniques by Paul Wilson
    8. Space Efficient Conservative Garbage Collection by Hans Boehm (local file, PDF)
    9. Hans Boehm's Conservative GC Webpage
    10. The Java Virtual Machine. The most basic expository articles appear at the end of the index. Read it from bottom up.
    11. Java Memory Model
    12. 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.
    13. 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.
    14. Concurrency in Swing Text
    15. The Last Word in Swing Threads
    16. Old Course Website
    17. Advertisement for COMP 312: 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.