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

The first two assignments (Assignments 0 and 0.5) must be done individually; they are warm-up exercises solely designed to help you learn the fundamentals of Scala. The first assignment covering course material (the principles of programming languages) is Project 1. Project 1 and all subsequent assignments should ideally be done in pairs. So you should think about identifying a programming partner starting September 5.
Please join the course mailing list by subscribing.
If you haven't found a partner by September 5, send an email to the comp411-l mailing list.
Students looking for Project 1 partners:
- None yet listed.
Please get in touch with each other. Issues to keep in mind:
- Make sure you have the time to work on the project together.
- Make sure that you team has some functional programming experience (e.g., Scheme, ML, writing in Java in a functional style) and some Java programming experience.
- Try to find a permanent partner for the rest of the class; it's a lot easier to work with the same student than to switch.
- You may choose to work alone. The work load is significant but manageable if you understand how to write mostly functional programs in Scala. We do not allow groups of more than two students, even if there is an odd number of students in the class.
- If you haven't found a partner and are not on this list, send an email to the comp411 mailing list.
- If you are on this list but have already found a partner, email the same list comp411 mailing list to remove you from this list.

Summary

COMP 411 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, including common type systems, of programming languages.

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:

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. More detailed aspects of parsing (such as 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 (textual rewriting) 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 important 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 (using graph reachability [pointer-chasing] and perhaps more powerful techniques) for the remainder of the evaluation. Type safety typically implies on memory safety.
The third part shows how interpreters can systematically be transformed so that they use fewer and fewer language facilities. 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 readily be be re-written in a low-level language like C/C++ or even 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

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	Program 0 assigned, 8/21
0.5	8/24	F	Scala vs. Java		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		Project 1 due 12 noon, 9/17 Project 2 assigned, 9/17
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			Project 2 due 12 noon, 10/1
	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		Essentials, ch. 5, 6	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	Project 7 assigned, 11/18	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

Scala
Java
Scheme
1. How to Design Programs
2. DrScheme Programming Environment
OCaml
Haskell

Additional References

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.
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)
Evaluation rules for functional Scheme ( PDF)
References on evaluating Jam programs
Notes defining various syntactic (operational) semantics for LC. In class, we use "small step" syntactic semantics and "big step" environment (denotational) semantics.
Lecture Notes on Types I
Lecture Notes on Types II
Introduction to System F (Polymorphic Lambda-Calculus)
Scheme code from Class Lectures
The Essence of Compiling with Continuations by Flanagan et al.
Uniprocessor Garbage Collection Techniques by Paul Wilson
Garbage Collection [canonical textbook] by Jones and Lins
Space Efficient Conservative Garbage Collection by Hans Boehm ( local file, PDF)
Hans Boehm's Conservative GC Webpage
The Java Virtual Machine. The most basic expository articles appear at the end of the index. Read it from bottom up.
Java Memory Model
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.
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.
Concurrency in Swing Text
The Last Word in Swing Threads
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.

COMP 411 Principles of Programming Languages Fall 2012