MATH 384: "Giving lambda its legs since the year 2000."

Programming Languages

This course is a study of modern systems for expressing and executing computer programs. We will explore a number of advanced computer language features, focusing primarily on those developed under the functional paradigm--- Scheme, Standard ML, and Haskell, derivatives of Lisp. We take a mathematical approach that has ties to mathematical logic and the nature of mathematical proof. We survey topics related to programming language semantics: its foundations in the lambda calculus, "meta-programming" in Standard ML, the Hindley-Milner type system and the Curry-Howard correspondence, and (so-called) lazy evaluation. The course includes several significant programming projects (written in Python) where we build up a fully functional interpreter for a subset of Standard ML. We'll also survey (and practice writing programs) in Haskell, Prolog, and (if time permits) object-oriented languages like Smalltalk and Self. Finally, we'll look at "purely functional" language support for side-effects and interactivity, using monadic expressions, and survey concurrency and communication in the pi calculus.

Your practical goal is to go beyond languages like Python and Java, to gain insight into the connections between programming language design and mathematical logic, and to develop the skills and knowledge needed to build programming language systems.

Prerequisites: MATH 121

Meets: 3:10pm MWF in Physics 240A.
Course web:
Instructor:Jim Fix
Office:Library 314
Office Hours: 1-3pm MWF

Schedule of Topics and Lecture Materials:

Week 1
Lec 1.1: overview of course (via SML)
Reading: selected from Chs. 1, 2, and 3 of Ullman (see link below))
Lec 1.2 and 1.3: introduction to SML syntax
Note: we'll eventually cover a fuller version of SML
Lec 1.3: some SML examples

Week 2
Lec 2.1 recursive functions; lists.
Reading: Chs. 4 and 5 of Ullman.
Lec 2.2 classic list functions: map, fold, and filter.
Lec 2.3 patterns and case; datatypes.
Reading: Chs. 6, 12, and 13 of Ullman. (except Figure 13.4!!)

Week 3
Lec 3.1 example datatype use.
   > eval
   > bstree
Lec 3.2 interpreter pipeline overview.
Lec 3.3 PL syntactic specification

Week 4
Lec 4.1 derivation trees; ambiguity.
Lec 4.2 fixing ambiguity; recursive-descent parsing.
Lec 4.3 introduction to PL semantics.

Week 5 semantics of Calc++ and MiniML

Week 6 Church's lambda caclulus
   > old notes on lambda calculus

Week 7 MiniML assigned
   > MiniML in Python

Ongoing notes for this course
   > get them while they're toasty

There will be weekly short programming assignments and problem sets, and a take-home final. Throughout the semester we will be implementing the parser, interpreter, and type system for MiniML.

Homework 1: SML warm-up due 2/3.
Homework 2: SML datatypes due 2/10.
   > Exercise 1 sample code.
   > Exercise 2 sample code.
Homework 3: grammars due 2/15.
Homework 4: extending Calc due 2/22.
Homework 5: specifying Calc++ due 3/2.
Homework 6: Part 1 due 3/14
Homework 7: Part 2 due 3/18
Homework 8: Part 3 along with written exercises due 3/30
Homework 9: typed MiniML due 4/25.


Elements of ML Programming , Jeffrey D. Ullman. Since we will be building our own SML interactive interpreter, you will want to develop your understanding of the language. This book serves as a good introduction. I will put copies of the text in Library 382 and also on library reserve.

Other resources:

Programming Languages: Application and Interpretation by Krishnamurthi. This is available on-line as a PDF. This text is most like this semester's course; there is considerable overlap, except its use of the Scheme programming language. I will put copies of the text in Library 382 and also on library reserve.

Programming Language Pragmatics by Michael Scott. A comprehensive text on several aspects of programming languages and programming language systems. It includes in-depth coverage of parsing, beyond my plans for our course, and also runtime systems, architecture, compilers, and other aspects of PLs that are heavily related to implementation, beyond the goals of this course (see MATH 389). It does, however, survey some of the theoretical topics we cover under the major section heading "ALTERNATIVE PROGRAMMING MODELS." And its coverage of runtime constructs like binding environments is very solid.

Structure and Interpretation of Computer Programs by Abelson and Sussman. Used by some schools as an intro text, it introduces a lot of program design ideas that hint at many advanced language features. Uses the functional language Scheme, a clean dialect of LISP. Check out the "metacircular evaluator" project; we'll be doing something similar in the first weeks. Now free, on-line.

Concepts in Programming Languages by John Mitchell. Standard undergraduate text for a programming language survey course.

Programming Languages Concepts and Constructs by Sethi. Similar to the above.

Essentials of Programming Languages by Friedman et al. Similar to the above. Uses Scheme.

Functional Programming by Field and Harrison. Provides decent coverage of the theory behind functional languages, including reduction, advanced type systems, and the lambda caclulus.

Foundations for Programming Languages by John Mitchell. An advanced text covering the theory of programming languages using typed lambda calculi.

Programming Languages: Theory and Practice by Bob Harper. These are an on-line draft of a book that provides tighter, more accessible discussion of the topics in Mitchell's book. Some chapters are not complete. There are two PDF files, one a hyperlinked version ("online") and the other not ("offline").

Types and Programming Languages by Benjamin C. Pierce. a careful, comprehensive introduction to programming language type systems.