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

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 rich variety of programming language constructs is specified using interpreters and reduction systems. The constructs include arithmetical and conditional expressions, blocks, lexically-scoped first-class functions, simple modules and objects, and control constructs (loop exits, first-class continuations, simple threads).

  • The second part illustrates how interpreters 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.

  • 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. The process of applying these transformations to arbitrary input programs is 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 simple interpreters for new languages or for "special-purpose" languages embeded in software applications.

    Students are encouraged to discuss the material covered in class and in assignments on the mailing list comp311-l@mailman.rice.edu. Please subscribe so you will also receive messages sent to the mailing list.

    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/22

    M

    		Introduction & Motivation

    2

    		 8/24

    W

    		 Parsing Parsing Project 1 Assigned  

    3

    		 8/26

    F

    4

    		 8/29

    M

    		 The Scope of Variables Essentials, ch. 1

    5

    		 8/31

    W

    		 A Syntactic Interpreter for LC   Review 1 

    6

    		 9/2

    F

    		9/5

    M

    		 Labor Day - No Classes    

    7

    		 9/7

    W

    		 A Syntactic Interpreter for LC (cont'd)   Project 1 Due 12 noon, 9/7
    Project 2 Assigned

    8

    		 9/9

    F

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

    9

    		 9/12

    M

    10

    		 9/14

    W

    		 Eliminating Meta Errors  

    11

    		 9/16

    F

    12

    		 9/19

    M

    		 Data Domains Supporting Recursive Definitions The Why of Y Project 2 Due 12 noon, 9/20 (ppd 1 day)
    Project 3 Assigned

    13

    		 9/21

    W

    14

    		 9/23

    F

    		 Recursive Definitions and Environments  

    15

    		 9/26

    M

    16

    		 9/28

    W

    17

    		 9/30

    F

    		 The lambda calculus as a model of computation   Optional Homework Exercises
     Review 2

    18

    		 10/3

    M

    		 Assignment and Mutability Essentials, ch. 3.7, 3.9  

    19

    		 10/5

    W

    20

    		 10/7

    F

    		 Environment Representation and Control Essentials, ch. 7, 8

    		10/10

    M

    		 Midterm Recess - No Classes    

    21

    		 10/12

    W

    		 Environment Representation and Control II Essentials, ch. 7, 8 Project 3 Due 12 noon, 10/12
    Project 4 Assigned
    Project 4xc (extra credit) Offered

    22

    		 10/14

    F

    		 Object-Oriented Languages, Featherweight Java Essentials, ch. 5

    23

    		 10/17

    M

    24

    		 10/19

    W

    25

    		 10/21

    F

    		 Review   Project 4 Due 12 noon, 10/21
    Exam 1 handed out in class, 10/21
    Sample mid-term
    Sample evaluations of Jam programs
    Project 5 Assigned, 10/21

    26

    		 10/24

    M

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

    27

    		 10/26

    W

    		 Types and datatype  

    28

    		 10/28

    F

    		 Exam 1 Due in class, 10/31

    29

    		 10/31

    M

    		 Polymorphism Essentials, ch. 6  

    30

    		 11/2

    W

    		 Exam Discussion

    		 

    31

    		 11/4

    F

    		 Implicit Polymorphism Type Inference Study Guide

    		Project 5 Due 12 noon, 11/4
    Project 6 (PDF) assigned

    32

    		 11/7

    M

    		 Final Words on Types  

    33

    		 11/9

    W

    		 The Meaning of Function Calls Essentials, ch. 8

    34

    		 11/11

    F

    		 Continuation-Passing Style  

    35

    		 11/14

    M

    		 Type Inference Study Guide

    36

    		 11/16

    W

    		 Explaining letcc and error & The True Meaning of Function Calls

    37

    		 11/18

    F

    		 Garbage Collection Uniprocessor Garbage Collection Techniques Project 6 Due noon, Monday 11/21
    Project 7 assigned

    38

    		 11/21

    M

    39

    		 11/23

    W

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

    F

    		 Thanksgiving Recess - No Classes

    40

    		 11/28

    M

    		 TBA

    41

    		 11/30

    W

    		 TBA  

    42

    		 12/2

    F

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

    Language Resources

    1. Java
      1. SDK Download
      2. Generic Java Documentation
      3. API Reference
      4. DrJava Programming Environment
    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
      2. Types and Type Inference
    2. Evaluation rules for functional Scheme
    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
    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. Old Course Website
    12. 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.