COMP 411 Principles of Programming Languages (Summer 2021)

Professor Robert "Corky" Cartwright

Department of Computer Science

Rice University

Summer 2021: Zoom Virtual classroom lectures provided in the Canvas link to Comp 411 Spring 21

TBA

Course News

This course uses Piazza for class discussion and questions about class material. The site is located at the following URL: https://piazza.com/rice/spring2021/comp411/home. The Comp 411 Piazza discussion board will be monitored by the instructor and should also appear on each student's Piazza home page. The Piazza website is designed to quickly provide you with course help from classmates, the TAs, and myself. The primary course web site is: https://www.cs.rice.edu/~javaplt/411.

Browser-based reference Jam interpreter developed by Nick Vrvilo

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 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, and they support the limited use of mutation (imperativity) as well. Haskell is a deviant member of the ML family because it does not support mutation but it includes support for an object-based approach to code-factoring call type classes and a functional alternative to mutation called a monad, which I am not convinced is semantically simpler than the judicious use of mutation. 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 requisite OO structure can obscure 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. Clojure is a Scheme variant implemented on top of the Java Virtual Machine.

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 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. In practice, most domain specific languages do not need a sophisticated parser; in fact, so-called "internal DSLs" rely on the parser and compiler of the host language. Scala, a putative successor to Java that compiles to Java byte code, is specfically designed to support the easy implementation of internal DSLs. In addition, "external DSLs" (which are implemented by interpreters akin to the interpreter projects assigned in this course) often rely on simple manually written parsers based on "recursive descent" which is the approach to writing parsers taught in this course. The other attractive option for parsing external DSLs is to use a parser generator like ANTLR which is based on a simple extension of recursive descent parsing.
In the course, you will implements the semantics of a comprehensive collection of programming language constructs using mostly functional interpreters derived from simple reduction (textual rewriting) semantics for the constructs. The constructs include arithmetical and conditional expressions, lexical binding of variables, blocks, first-class functions, assignment and mutuation, basic 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 for the remainder of the evaluation. The standard technique for ensuring memory safety is automatic storage management, which is typically implemented using reference counting or garbage collection. Automatic storage management (which is present in all high-level programming languages including Java, Python, Javascript, and Swift) never deletes data objects that are reachable in subsequent program execution. Type safety typically depends on memory safety. We will study the formal type-checking process incorporated in the ML family of languages, which has been adopted in part by sophisticated OO languages like Scala and Swift.

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.

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.

Course Schedule

Date a

#	Day	Topic	Reference	Assignment
1	5/24	M	Information & Motivation
2	5/26	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	5/28	F	Parsing		Project 1, assigned 5/28 and due at 11:59pm 6/7
4	5/31	M	The Scope of Variables	PLAI, ch. 3-4 Why Python is Broken [Python: The Full Monty]
5	6/2	W	Syntactic Interpreters
6	6/4	F	Syntactic Interpreters	Essentials, ch. 3.7, 3.9
7	6/7	M	A Meta Interpreter for LC Eliminating Meta-errors	Brief Review of Lectures 1-6 PLAI, Ch. 4-6	Project 1 due at 11:59pm, 6/7 Project 2 assigned 6/7 and due at 11:59pm 6/21 See: Notes on Object-Oriented Program Design
8	6/9	W
9	6/11	F
10	6/14	M	Data Domains Supporting Recursive Definitions Recursive Definitions and Environments	Domain Theory: An Introduction Chs. 1-4 The Why of Y Recursive Programs as Definitions in First-Order Logic Types as Intervals The Lambda Calculus as a Model of Computation The Pure Lambda Calculus as a Programming Language
12	6/16	W
12	6/28	F
13	6/21	M	Recursive Binding	Syntactic Evaluation of Core Jam Hand Evaluation Exercises Solution to Hand Evaluation Exercises	Project 2 due 11:59pm, 6/21 Project 3 assigned 6/21 Assignment 3 solution posted on Piazza
14	6/23	W	Eliminating Binding (lambda)
15	6/25	F	Assignment and Mutability
16	3/1	M			Monday, March 1, is another "sprinkle day". This week I will present three online lectures covering two slide decks (Lectures 15 and 16) at the usual time, MWF 11am. The material is not difficult. Your main concern is working on project 3.
16 cont.	3/3	W
17	3/5	F	Run-time Environment Representation and Control	Essentials, ch. 7, 8 Powerpoint slides taken from Sebesta's book Concepts of Programming Languages Note: Sebesta presents Fortran 77 as supporting value-result parameter passing in addition to refernce parameter passing. The Fortran 77 standard does NOT include value-result parameeter passing. Sebesta calls value-result parameters "copying parameters" and also refers to them as "result parameters" and parameters of "out mode". Sebesta's account of procedure linkage is accurate assuming Fortran 77 is extended by value-result parameter passing. His description of the Algol 60 run-time is very good. Essentially all modern compiled languages (e.g., Java, C++) use a variant of this run-time.
17 cont.	3/8	M			Project 4 and XC Project 4xc, assigned 3/8 511 Written Assignment 1, assigned 3/8 Project 3 due 10am, 3/8
18	3/10	W
18 cont.	3/12	F
Midterm Review	3/15	M	Sample Midterm Exam Solutions to Problems 1, 2, 4, 6 Solution to Problem 3 Solution to Problem 5(i) Solution to Problem 5(ii)	There is a brief description of how let, let*, and letrec are evaluated in Scheme/Racket in the HTDP book which matches the meanings that we use in Jam. See https://docs.racket-lang.org/reference/let.html.
19	3/17	W	Object-Oriented Languages	Essentials, ch. 5	Midterm Examination, 6-10pm, March 18 Administered as four 1-hour Canvas quizzes
19 cont.	3/19	F	Object-Oriented Languages	Essentials, ch. 5
20	3/22	M	What Is a Type? Types and Safety Types and Datatype	Essentials, ch. 4 Essentials, ch. 6 Type Inference Study Guide	Project 4 due 11:59pm, 3/22 Project 5 and and XC Project 5xc, assigned 3/22
21	3/24	W	What Is a Type? Types and Safety Types and Datatype
22	3/26	F	Polymorphism Implicit Polymorphism
23,	3/29	M	Unification	Survey of Unification Draft Racket program that performs unification inefficiently	XC Project 4xc, due 11:59pm, 3/29 511 Written Assignment 1, due 11:59pm, 3/29 511 Written Assignment 2, assigned 3/29
24	3/31	W	Typing Imperative Languages Final Words on Types
25	4/2	F	Continuation Passing Style (CPS) Meaning of Function Calls	Essentials, ch. 7-8
25	4/5	M	Continuation-Passing Style		Project 5 due 11:59pm 4/5
26	4/7	W	Explaining `letcc` and `error`		Project 5 due 11:59pm 4/5
27	4/9	F	Storage Management	Dynamic Storage Allocation Survey	XC Project 5xc due Sunday, 11:59pm 4/11.
28	4/12	M	Garbage Collection	Uniprocessor Garbage Collection Techniques
29	4/14	W
	4/16	F			511 Written Assignment 2, due 11:59pm, 4/16 511 Written Assignment 3, assigned 4/16 Project 6 due 11am, 4/16 Project 7 assigned 4/16
30	4/19	M	Retrospective on Software Engineering in Java
	4/21	W	Retrospective on Software Engineering in Java
	4/23	F	Review	Sample Final Exam Sample Final Exam With Solutions
Review	4/26	M	Review
31	4/28	W	Lambda-lifting and other optimizations for efficient low-level implementations
Review	4/30	F	Final Review		Project 7 due 11:59pm 4/30 511 Written Assignment 3, due 11:59pm, 4/30

Language Resources

Additional References

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.
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
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
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.
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.
Java concurrency (multi-threading): Tutorial. A tutorial on expressing concurrent computation in Java using threads.
The Last Word in Swing Threads. An article on the perils of accessing Swing components from outside the event dispatch thread.
Why Functional Programming Matters (as analyzed in 1990).
Why Functional Programming Mattered (gazing at programming technology in 2017).
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.