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.

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 a modern imperative programming language (e.g. Java, Python, C, C++, Ruby). We may write Java code for some of the projects, but not from scratch, so some familiarity with either C++ or Java would be helpful.

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 315
Office Hours: TBA, or by appointment.

• the functional programming paradigm (in Scheme)
• tokenizers and recursive-descent parsing
• 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

• week 0:
  lecture 0 (overview)
  lecture 1 (intro scheme)
  lecture 2 (scheme syntax)
• homework 0: MATH 121's lab1, in Scheme
• week 1:
  lecture 0 (pairs lists)
  lecture 2 (lists lambda)
  
• homework 1: MATH 121's lab2, in Scheme; Also, define these terms and phrases:
   formal parameter
   actual parameter
   special form
   S-expression
   "higher-order functions"
   "functions are first class"
   lexical scope
  
• week 2:
  lecture 0 (exercise)
  lecture 1 (datatype)
  lecture 2 (syntax)
• homework 3: GNAL-U-CLAC interpreter due 2/20/9.
• week 3:
  lecture 0 (parsing)
  GUC recursive descent parser w/ solution to hw3
• week 4:
  lecture 0 (GUC semantics)
  
• homework 4: MiniML parser due 3/4/9.
• week 5:
  A MiniML interpreter using substitution
  
• week 6:
  description of MiniML, substitution
  
• week 7:
  
• homework 5: MiniML interpreter due 3/25/9. sample MiniML program Haskell code examples for BSTs and lazy lists
  
  
• week 8: break
  
• week 9:
  examples of HtDP Scheme boxes used for tree traversal and counting
  examples of C code illustrating C pointers
  
  
• week 10:
  
• homework 6: MiniMiniML reducer due 4/17/9. sample MiniMiniML program
• week 13:
  
• homework 7: typed MiniML due 5/12/9.

"Recursive Functions of Symbolic Expressions and Their Computation by Machine, Part I", John McCarthy, in Communications of the ACM, April 1960.
"LISP: Notes on its Past and Future", John McCarthy, in Proceedings of the ACM conference on LISP and functional programming, 1980.
"RABBIT: A Compiler for Scheme", Guy Steele, Master's Thesis, MIT AI Lab Technical Report 474, May 1978.
"The Evolution of Lisp", Guy Steele and Richard Gabriel, in Proceedings of the 2nd ACM Conference on the History of Programming Languages (HOPL II), 1993.

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 is also on library reserve.

Programming Languages: Application and Interpretation by Krishnamurthi. This is available on-line as a PDF. I will put copies of the text in Library 382 and also on library reserve. It can also be ordered from a just-in-time printing service. Once we learn Scheme and write a simple parser, we'll mostly follow the material of this text.

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:
The Scheme Programming Language (3rd ed.) a comprehensive reference for Scheme, with a mored advanced presentation than HtDP.

Teach Yourself Scheme in (Fixnum) Days a free on-line tutorial for Scheme, more compressed than HtDP.

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.