This course is a study of modern systems for expressing and executing algorithms. We will explore a number of advanced computer language features, beyond those available in imperative languages such as C. We will survey key programming language paradigms--- functional (Scheme, Haskell), object-oriented (Smalltalk), and logic (Prolog). We will take a formal approach to understanding the concepts underlying these paradigms, considering their concrete and abstract syntax, their semantics, and their type systems, and also the lambda calculus of Church. We will also cover selected topics in the implementation of language systems such as interpreters, compilers, and memory managers.

Your practical goal is to go beyond C 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, familiarity with a modern imperative programming language (e.g. Java, Pascal, C, C++). We will be writing Java code for some of the projects, but not from scratch, so some familiarity with either C++ or Java should suffice.

Meets: 9am MWF in Library 387.
Course web: http://www.reed.edu/~jimfix/384
Instructor:Jim Fix
E-mail:jimfix@reed.edu
Office:Library 315
Office Hours: TBA, or by appointment.

• programming language semantics and interpreters
• high-level, functional programming (in Scheme)
• lazy, pure functional languages (Haskell_
• language-based models of computation; Church's untyped lambda calculus
• type systems and type inference
• pattern matching and unification
• logic programming (in PROLOG)
• object-oriented programming (in Smalltalk)
• run-time systems and garbage collection
• topics in language design and PL history

How to Design Programs by Fellesian et al. This is a clear methodical introduction to the features and syntax of Scheme. We'll be using Scheme all semsester as our interpreter implementation language, and learning Scheme from this text in the first three weeks. The text is available on-line and also in the bookstore.

Programming Languages: Application and Interpretation by Krishnamurthi. This is also available on-line as a PDF. It can be ordered Once we learn scheme, this will be the main text we will follow in the course.

General:
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.

Programming Languages Concepts and Constructs by Sethi. Standard undergraduate text for a programming language survey course.

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

Theory:
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.

Scheme supplements:
coming soon

Haskell:
coming soon

Standard ML:
ML for the Working Programmer by Paulson. A good introduction to the language Standard ML that also includes some general programming language discussions and some interesting and illustrative functional programming examples.

Programming in Standard ML by Bob Harper at CMU. These are on-line notes for a draft of an ML tutorial.