COMP 411/511: Principles of Programming Languages

COMP 411/511 Principles of Programming Languages (Spring 2020)

Professor Robert "Corky" Cartwright

Department of Computer Science

Rice University

Houston, Texas, USA

Spring 2020: Room 1070, Duncan Hall, Monday, Wednesday, Friday, 11:00am–11:50am

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


Course News

Summary

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

In the lecture materials, interpreters are written in concise functional notation using Scheme (Racket). In some cases, supplementary material showing how the same interpreters can be written in Scala (using explicit typing) are provided. The functional subset of Scala and the ML family of languages (notably OCaml) are very well-suited to writing purely functional interpreters, yet they support the limited use of mutation (imperativity) as well. I personally dislike the ML family of languages for writing larger software systems because they do not support inheritance and object-oriented design. In conrast, Java is a very good vehicle for implementing these interpreters including the disciplined use of imperative code to greatly improve program efficiency. On the other hand, it is not a good representation for explaining abstract concepts because it is much too wordy and the OO structure obscures the simple algebraic structure of abstract syntax and structural recursion used in simple interpreters. For this reason, we will present sample code in lecture in mostly functional Scheme/Racket. If you have not seen Scheme/Racket before, you will need to learn the core constructs of this language family which is widely imitated in many domain specific languages (DSLs) embedded in applications, such as Emacs Lisp embedded in Gnu Emacs.

A secondary theme of this course is software engineering. All of the programming assignments in this course are conducted in Java using test-driven development and pair-programming, two of the major tenets of Extreme Programming. A compelling reason for using Java is that it is widely used for software development in industry and it supports low-level programming where appropriate. Java Virtual Machines are expensive to start (the Achilles heel of Java IMO) and Java applications are commpiled "Just In Time" (JIT) which has visible costs early in program execution. On the other hand, well-written Java code that has been "warmed up" (run on sufficient inputs to force the JIT compilation of all of the compute intensive parts of the application) is surprisingly fast.

COMP 411/511 consists of three parts:

This course material enables students 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., C, C++, Java, JavaScript, Swift, C#, Python). It also enables students to design and implement efficient interpreters for new languages or DSLs embeded in software applications. Most importantly, it equips students to become master software developers because they will be able to define and implement whatever linguistic extensions are appropriate for simplifying the construction of a particular software system.

My notes on object-oriented program design briefly describe the design patterns that I recommend using to express functional programming abstractions in Java. If you have little prior experience in writing functional programming code in Java, I highly recommend skimming them.

For students interested in operational (syntax-based) semantics, I recommend reading notes by Walid Taha (now at Halmstad University in Sweden) on big-step versus small-step semantics. I strongly prefer small-step semantics, so it is the only form of operational semantics that we will use in this class, but big-step semantics is often used in the programming languages literature.

Differences between COMP 411 and COMP 511

COMP 511 includes all of the material from COMP 411 plus a modest amount of supplemental material. Portions of projects 3 and 6 are mandatory for Comp 511 students but optional for 411 students, COMP 511 students are also required to complete 3 short written assignments over the course of the semester, discussing concepts from the lectures.

More Course Information

Please take a look at the course information/policies page, which is referenced in the first few class lectures.

Course Schedule

# Date Day Topic Reference Assignment
1 1/13 M Information & Motivation
2 1/15 W Parsing Web site describing Syntax Diagrams
Note: EBNF notation is explained in Project 1.
Component Pascal Syntax Diagrams
Tutorial on Context Free Grammars
The Java Language Specification
3 1/17 F Project 1, assigned 1/17
1/20 M Martin Luther King Holiday
4 1/22 W The Scope of Variables PLAI, ch. 3-4
5 1/24 F Syntactic Interpreters
6 1/27 M Brief Review of Lectures 1-6 Project 1 due at 10am, 1/27 Project 2 assigned 1/27
Reference: Notes on Object-Oriented Program Design
7 1/29 W A Meta Interpreter for LC Eliminating Meta-errors PLAI, Ch. 4-6
8 1/31 F
9 2/3 M
10 2/5 W 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
Supplemental Material
11 2/7 F
12 2/10 M Project 2 due 10am, 2/10
Project 3 assigned 2/10
13 2/12 W Recursive Binding
2/14 F Spring Recess
14 2/17 M Eliminating Binding (lambda) Essentials, ch. 3.7, 3.9
Hand Evaluation Exercises
Solution to Hand Evaluation Exercises
15 2/19 W Assignment and Mutability
16 2/21 F
16 (cont.) 2/24 M
Project 3 due 10am, 2/24
Project 4 and XC Project 4xc, assigned 2/24
Comp 511 Written Assignment 1, assigned 2/24
17 2/26 W Run-time Environment Representation and Control Essentials, ch. 7, 8
Powerpoint slides taken from Sebesta's book Concepts of Programming Languages
18 2/28 F
3/2 M
19 3/4 W Object-Oriented Languages Essentials, ch. 5
Midterm Review 3/6 F Sample Midterm Exam
Solutions to Problems 1, 2, 4, 6
Solution to Problem 3
Solution to Problem 5(i)
Solution to Problem 5(ii)

Essentials, ch. 3.8
3/9 M Project 4 due 10am, 3/9 [postponed]
Project 5 and XC Project 5xc, assigned 3/9
3/10 Tu Mid-term Examination 7-10pm in McMurtry Auditorium in Duncan Hall [cancelled]
20 3/11 W What Is a Type?
Types and Safety
Types and Datatype
Essentials, ch. 4
Essentials, ch. 6
Type Inference Study Guide
Comp 511 Written Assignment 1, due 11:59pm, 3/11 [postponed]
21 3/13 F XC Project 4xc due 10am, 3/13 [postponed].
3/16-3/20 M-F Spring Break — No Classes
22 3/23 M Polymorphism
Implicit Polymorphism
Survey of Unification
Draft Racket program that performs unification inefficiently
22a, 23 3/25 W Final Words on Types Comp 511 Written Assignment 1, due 3/25
Comp 511 Written Assignment 2, assigned 3/25
24 3/27 F Meaning of Function Calls Essentials, ch. 7-8 Project 4 and XC Project 4xc due 10am, 3/27
25 3/30 M Continuation-Passing Style Project 6 assigned 3/30
26 4/1 W Explaining letcc and error
27 4/3 F Project 5 due 10am 4/3.
28 4/6 M Dynamic Storage Allocation Survey Project 5xc, due 10:00am, 4/6
Comp 511 Written Assignment 2, due 11:59pm, 4/6
29 4/8 W Garbage Collection Uniprocessor Garbage Collection Techniques
4/10 F
4/13 M Comp 511 Written Assignment 3, assigned 4/13
Project 6 due 11am, 4/13
Project 7 assigned 4/13
30 4/15 W
4/17 F Sample Final Exam
Sample Final Exam With Solutions
4/20 M
4/22 W
4/24 F Project 7 due 11:59pm 4/24
Comp 511 Written Assignment 3, due 11:59pm, 4/24

Language Resources

  1. Java
    1. SDK Download
    2. API Reference
    3. DrJava Programming Environment
    4. Elements of Object-Oriented Program Design by Prof. Cartwright
  2. Scheme (Racket)
    1. How to Design Programs
    2. DrRacket Programming Environment
  3. Browser-based reference Jam interpreter

Additional References

  1. Krishamurthi, Shriram. Programming Languages: Application and Interpretation. 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. Lecture Notes on Types I
  6. Lecture Notes on Types II
  7. Introduction to System F (Polymorphic Lambda-Calculus)
  8. Scheme code from Class Lectures
  9. The Essence of Compiling with Continuations by Flanagan et al.
  10. Uniprocessor Garbage Collection Techniques by Paul Wilson
  11. Garbage Collection [canonical textbook] by Jones and Lins
  12. Space Efficient Conservative Garbage Collection by Hans Boehm ( local file, PDF)
  13. Hans Boehm's Conservative GC Webpage
  14. JVM Performance Optimization. The first article in a five part series (with the remaining four parts linked from the first article) on JVM internals and how to write Java source code to use them efficiently.
  15. Java Memory Model
  16. 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.
  17. 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.
  18. Java concurrency (multi-threading): Tutorial. A tutorial on expressing concurrent computation in Java using threads.
  19. The Last Word in Swing Threads. An article on the perils of accessing Swing components from outside the event dispatch thread.
  20. Why Functional Programming Matters (as analyzed in 1990).
  21. Why Functional Programming Mattered (gazing at programming technology in 2017).
  22. 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.