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:
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.
Notes on the common mathematical notation
used in operational semantics, some of which will be used in class.
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
#
|
Date
|
Day
|
Topic
|
Reference
|
Assignment
|
Language Resources
- Scala
- Getting started
- Quick References
- Online books
- Free Online course on Functional Programming in Scala by Martin Odersky
- Java
-
SDK Download
-
API Reference
-
DrJava Programming Environment
-
Elements of Object-Oriented Program Design by Prof. Cartwright
- Scheme
-
How to Design Programs
-
DrScheme Programming Environment
- OCaml
-
OCaml Book
-
O'Caml Language
-
MetaOCaml
-
OCamlLex
-
Using "Ledit" to make Ocaml recognize arrow keys
-
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:
-
Parameter Passing ( local file, PDF)
-
Types and Type Inference ( local file, PDF)
-
Evaluation rules for functional Scheme ( PDF)
-
References on evaluating Jam programs
-
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.