COMP 411
Principles of Programming Languages
Fall 2012

Professor Robert "Corky" Cartwright

Department of Computer Science

Rice University

Houston, Texas, USA

Lecture: Room 1042, Duncan Hall, Monday, Wednesday, Friday, 1:00pm–1:50pm

For more information on the course staff including office hours, see course information.


Course News

Summary

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

In the lecture materials, interpreters will be written in concise functional notation using Scala. (Past versions of the course materials used Scheme.) This Scala code is subject to revision as the instructor's understanding of Scala coding idioms improves.

A secondary theme is software engineering. All of the programming assignments in this course are conducted in Scala using test-driven development and pair-programming, two of the major tenets of Extreme Programming. Scala is a putative successor to Java and runs on the Java Virtual Machine. Scala is fully compatible with compiled Java code. The Scala core libraries are an extension of the Java core libraries. In fact, it is possible to develop projects written partly in Scala and partly in Java, although we do not recommend using Java instead of Scala unless there is a strong external reason such as a project that extends an existing Java code base.

COMP 411 consists of three parts:

Students who complete this course will be able 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, Clojure, Groovy). 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.

Course Information

Please take a look at the course information some of which was discussed during the first few class lectures.

Assignments

Please refer to the assignments column in the below.

Lectures

Syntactic Interpretation -->
# Date Day Topic References Assignment
1 8/20 M Motivation for Studying Programming Languages Information
Notes on Object-Oriented Program Design
Slides on how OOP can be cast as an enrichment of FP
Program 0 assigned, 8/21
0 8/22 W Scala vs. Java
Good online textbook on Scala
Scala Syntax Summary
Scala Quick Reference
0.5 8/24 F Program 0.5 assigned, 8/24
Program 0 Solutions including a pattern-matching version
2 8/27 M Syntax Syntax and Simple Parsing
Component Pascal Syntax Diagrams
3 8/29 W Parsing PLAI, ch. 3-4
8/31 F Parsing cont.
9/3 M Labor Day Holiday
4 9/5 W Scope of Variables The Scope of Variables
Syntactic Interpreters (including code in Scheme)
5 9/5 W
6 9/7 F Syntactic Interpretation cont. Brief Review of Lectures 1-6
Syntactic Interpreter Scala Code
Overview of the SKI Combinator Calculus"
7 9/10 M Semantic Interpretation A Meta Interpreter for LC Eliminating Meta-errors PLAI, Ch. 4-6
8 9/12 W Semantic Intrerpetation cont.
9 9/14 F Semantics of Recursion: Overview Data Domains Supporting Recursive Definitions
Recursive Definitions and Environments
Domain Theory: An Introduction
The Why of Y
Recursive Programs as Definitions in First-Order Logic
Types as Intervals
The Lambda Calculus as a Model of Computation
Review of the Pure Lambda-Calculus
10 9/17 M Semantics of Recursion I Project 1 due 12 noon, 9/17
Project 2 assigned, 9/17
11 9/19 W Semantics of Recursion II
12 9/21 F Recursive Binding Essentials, ch. 3.7, 3.9
Hand Evaluation Exercises
Solution to Hand Evaluation Exercises
Project 2 due 12 noon, 10/1
9/24 M
9/26 W
13 9/28 F Eliminating Binding
14 10/1 M Mutation Assignment and Mutability
10/3 W
10/5 F Project 3 assigned, 9/28
15 10/8 M Essentials, ch. 5, 6
16 10/10 W Powerpoint slides taken from Sebesta's book Concepts of Programming Languages
Run-time Environment Representation and Control
Midterm Recess — No Classes 10/12 F
10/15 M Essentials, ch. 5
Project 3 due 12 noon, 10/15
Project 4 assigned, 10/17

10/17 W
10/19 F Sample Exam 1
Solutions to Sample Exam 1
Binding/bound occurrences, Problem 3
Call-by-name hand evaluation, Problem 5(i)
Call-by-value hand evaluation, Problem 5(ii)
10/22 M
10/24 W
17 10/26 F Object-oriented languages Essentials, Ch. 7.
18, 19 10/29 M What is a type?
Extending the Typed Lambda Calculus
What Is a Type?, Types and Safety
Types and datatype
Project 4 due 12 noon, 10/29
Project 5 assigned
20 10/31 W Polymorphism Polymorphism
Implicit Polymorphism
Type Inference Study Guide
21 11/2 F Types for Imperative Languages Final Words on Types
11/5 M
11/7 W Essentials, ch. 8
22 11/9 F The Low-level Meaning of Function Calls The True Meaning of Function Calls
11/12 M Continuation-Passing Style Continuation-Passing Style Project 6 assigned, due: 11/23
23 11/14 W Explaining letcc and error Explaining letcc and error
24 11/16 F Lambda Lifting and Closure Conversion Project 7 assigned, 11/18
25 11/19 M Storage Management Uniprocessor Garbage Collection Techniques
Dynamic Storage Allocation Survey
26 11/21 W Garbage Collection I Garbage Collection Sample Exam 2
Sample Exam 2 With Solutions
Project 6 due noon, 11/23
Exam 2 handed out in class, 11/23
11/23 F Thanksgiving Recess — No Classes
27 11/26 M Garbage Collection II
28 11/28 W Project 7 due at 11:59 PM, 12/2 A Glimpse of Concurrency
11/30 F Semantic Building Blocks Embedded in Scala
Exam 2 due at 11:59 PM, 12/2

Language Resources

  1. Scala
    1. Getting started
    2. Quick References
    3. Online books
    4. Free Online course on Functional Programming in Scala by Martin Odersky
  2. Java
    1. SDK Download
    2. API Reference
    3. DrJava Programming Environment
    4. Elements of Object-Oriented Program Design by Prof. Cartwright
  3. Scheme
    1. How to Design Programs
    2. DrScheme Programming Environment
  4. OCaml
    1. OCaml Book
    2. O'Caml Language
    3. MetaOCaml
    4. OCamlLex
  5. Haskell

Additional References

  1. Krishamurthi, Shriram. Programming Languages: Application and Interpretation. Online at http://www.cs.brown.edu/~sk/Publications/Books/ProgLangs/. This book is a descendant of lecture notes created by Shriram for a version of this course when Shriram was a teaching assistant over a decade ago.
  2. Friedman, Wand, and Haynes, Essentials of Programming Languages, 2nd ed. (MIT Press, 2001)
    You can take a look at the following two chapters, which the authors prepared for the second edition, without buying the book:
    1. Parameter Passing ( local file, PDF)
    2. Types and Type Inference ( local file, PDF)
  3. Evaluation rules for functional Scheme ( PDF)
  4. References on evaluating Jam programs
  5. Notes defining various syntactic (operational) semantics for LC. In class, we use "small step" syntactic semantics and "big step" environment (denotational) semantics.
  6. Lecture Notes on Types I
  7. Lecture Notes on Types II
  8. Introduction to System F (Polymorphic Lambda-Calculus)
  9. Scheme code from Class Lectures
  10. The Essence of Compiling with Continuations by Flanagan et al.
  11. Uniprocessor Garbage Collection Techniques by Paul Wilson
  12. Garbage Collection [canonical textbook] by Jones and Lins
  13. Space Efficient Conservative Garbage Collection by Hans Boehm ( local file, PDF)
  14. Hans Boehm's Conservative GC Webpage
  15. The Java Virtual Machine. The most basic expository articles appear at the end of the index. Read it from bottom up.
  16. Java Memory Model
  17. 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.
  18. 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.
  19. Concurrency in Swing Text
  20. The Last Word in Swing Threads
  21. Old Course Website

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.