This course is a study of modern systems for expressing and executing computer programs. 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, Standard ML, 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.

We'll be using Scala, a language that enables a hybrid of object-oriented and functional programming, learning Scala in the first weeks, and using it all semester as our interpreter implementation language.

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; familiarity with an imperative programming language (e.g. Java, Python, C, C++, Ruby).

Meets: 2:10pm MWF in Library 389.
Course web: http://www.reed.edu/~jimfix/384
Instructor:Jim Fix
E-mail:jimfix@reed.edu
Office:Library 314
Office Hours: TBA, or by appointment.

• the Scala programming language
  • Lec 1.3: example function code
  • Lec 1.3: same, with cleaner case class syntax
  • Lec 2.1: example tree code, functional style
  • Lec 2.1: example tree code, object-oriented style
  • Lec 3.1: example mutable stack object
  • Lec 3.2: example mutable tree implementing an ordered sequence
• tokenizers and recursive-descent parsing
  • Lec 3.2: example expression term class
  • Lec 4.1: a recursive descent parser for MiniScheme
• programming language semantics and interpreters
• language-based models of computation; Church's untyped lambda calculus
• lazy, pure functional languages (Haskell)
• 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

• Homework 1: write labs 1 and 2 of MATH 121 using Scala
• Homework 2: stacks, queues, trees, and syntax terms; build from this sample source code.
• Homework 3: parsing Scheme.
• Homework 4: interpreting GUC w/ function definitions.

Programming in Scala by Odersky et al. This is a fast-moving introduction and overview of the features and syntax of Scala.

Scala web the official site for the language; includes installation download links, white papers, reference documents, tutorials, code examples, and full documentation of the language and its API.

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.

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.

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.