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.
Instructor: Greg Cooper (firstname.lastname@example.org)
Greg received a Ph.D. in computer science from Brown University in 2008, advised by Shriram Krishnamurthi. In real life he works as a software engineer at Google.
Late Policy: Credit for late homework will be discounted by 10% per day for up to three days after the due date. After that, no credit will be given, unless arrangements were made in advance to accommodate an exceptional hardship.
The course will use the Haskell programming language, which is freely available for recent versions of Windows, Mac OS, and Linux. The instructor uses haskell-mode for Emacs, but many other options are available for non-Emacs users.
haskell.org – the language’s homepage (docs, extensive wiki)
Learn You a Haskell – a free, popular online guide to Haskell
Real World Haskell – a free online book about Haskell focusing on real applications
The Haskell wikibook – very complete (and of course it’s free and online)
Approximate Schedule of Lecture Topics
- Course intro. Programming in Haskell. Syntax; parsing; evaluation.
- Variables; substitution; scope and environments. Functions. Evaluation strategies. (slides)
- Mutation. Monads. (slides)
- Untyped lambda calculus. Church encodings. Y-combinator. (slides)
- Continuations. (slides)
- Continuations, part 2; formal semantics (big-step). (slides)
- Small-step operational semantics. Simply-typed lambda calculus. (slides)
- Explicit parametric polymorphism (System F). Unification, Hindley-Milner type inference. Type soundness. (slides)
- Curry-Howard Correspondence. Recursive types. Subtyping. (slides)
- Something fun. (slides)