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 news group rice.owlnews.comp311.

    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

    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   Project 3 Due 12 noon, 9/19
    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

    		Data in the lambda calculus   Project 3 Due 12 noon, 10/8
    Homework 1 Assigned

    18

    10/4

    M

    		    

    19

    10/6

    W

    		    

    20

    10/8

    F

    		 Data in the lambda calculus   Due: Project 3, 12 noon, 10/8
    Homework 1

     

    10/11

    M

    		 Midterm Recess - No Classes    

    21

    10/13

    W

    		 Assignment and Mutability Essentials, ch. 3.7, 3.9 Project 4 

    22

    10/15

    F

    		   Due: Homework 1, 10/15 in class

    23

    10/18

    M

    		 Environment Representation and Control Essentials, ch. 7, 8  

    24

    10/20

    W

    		 Review   Due: Project 4, 12 noon, 10/20
    Exam 1 handed out in class, 10/20

    25

    10/22

    F

    		 Environment Representation and Control (cont'd)   Project 5

    26

    10/25

    M

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

    27

    10/27

    W

    		 Object-Oriented Languages, Featherweight Java

    		Due: Exam 1, in class, 10/27

    28

    10/29

    F

    		 Object-Oriented Languages, Featherweight Java

     

    29

    11/1

    M

    		 What Is a Type?, Types and Safety

    Essentials, ch. 4

    30

    11/3

    W

    		 Types and datatype

    31

    11/5

    F

    		 Exam Discussion    

    32

    11/8

    M

    		 Exam Discussion    

    33

    11/10

    W

    		 Types and datatype (cont'd)   Due: Project 5, 12 noon, 11/10

    34

    11/12

    F

    		 Polymorphism Essentials, ch. 6 Project 6

    35

    11/15

    M

    		 Implicit Polymorphism

    Type Inference Study Guide

    36

    11/17

    W

    		 Final Words on Types  

    37

    11/19

    F

    		 The Meaning of Function Calls

    Essentials, ch. 8

    38

    11/22

    M

    		 Continuation-Passing Style

    		 

    39

    11/24

    W

    		Exam 2 handed out in class, 11/24
    Project 7 (extra credit)

     

    11/26

    F

    		 Thanksgiving Recess - No Classes

    40

    11/29

    M

    		 Garbage Collection

    41

    12/1

    W

    		 Garbage Collection

    		 

    42

    12/3

    F

    		 Garbage Collection

    Extra Material:
    Explaining letcc and error
    The True Meaning of Function Calls

    		Due: Exam 2, beginning of class, 12/3 (Note: Turn in your exam on or before 12/10. If you have any questions, please email us.).
    Due: Project 6 , 11:59 PM, 12/3
    Due: Project 7 (extra credit), 11:59 PM, 12/3

    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

    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. Lecture Notes on Types I
    4. Lecture Notes on Types II
    5. Scheme code from Class Lectures
    6. Uniprocessor Garbage Collection Techniques by Paul Wilson
    7. Space Efficient Conservative Garbage Collection by Hans Boehm
    8. Hans Boehm's Conservative GC Webpage
    9. The Java Virtual Machine. The most basic expository articles appear at the end of the index. Read it from bottom up.
    10. Old Course Website
    11. 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.