CSE P 505: Programming Languages

Spring 2013

Course Overview

This course will offer an introduction to programming language semantics through implementation and formal models. It will emphasize functional programming and cover the key features of modern functional languages (including type systems and memory management), along with some ideas from object-oriented and other programming styles.

Course Staff

Instructor: Greg Cooper (ghc78[at]uw.edu)
Greg received a Ph.D. in computer science from Brown University in 2008, advised by Shriram Krishnamurthi. He is currently employed as a software engineer at Google.

TA: Zach Stein (steinz[at]uw.edu)

Course Tools

Disccusion Board Dropbox Gradebook

Textbook and Software

The course will draw on Programming Languages: Application and Interpretation for material. Examples and homework problems will use the plai-typed variant of the Racket programming language. The DrRacket programming environment is distributed freely under the LGPL license and runs on all major desktop platforms.

Homework

Homework 1 (done)
Homework 2 (done)
Homework 3 (done)
Homework 4 (done)

Lectures

  1. Course intro. Programming in Racket. Syntax. (notes; see also textbook chapters [1], [2], [3])
  2. Interpretation. Substitution, environments, functions. (see textbook chapters [5], [6], [7])
  3. State. (code/notes on monadic store-passing combinators; also textbook chapter [8]; [4] for discussion of desugaring and [12] for representations)
  4. Recursion. Lazy evaluation. (see textbook chapters [9] and [17.1])
  5. Continuations. (my notes and textbook chapter [14])
  6. Formal operational semantics. (scan of hand-written large-step and small-step rules and extended pdf version)
  7. Untyped lambda calculus. Simply-typed lambda calculus. System F. (code for Church encodings; textbook sections [15.2] and [15.3.1])
  8. Variants; recursive types. Type inference and let-polymorphism. Type soundness. (type rules, see textbook section [15.3.2] through the end of section 15)
  9. Memory management. (textbook chapter [11] and note external references at end of section)
  10. Macros, logic programming (nondeterminism and unification). (code from lecture and textbook chapter [13])