Syllabus and synopsis (Programming Languages)

PRINCIPLES OF PROGRAMMING LANGUAGES

(also known as Functional Programming Made Difficult)

Overview

This course uses interpreters written in Haskell as a vehicle for exploring the meaning of various kinds of programming languages.

Learning Outcomes

After taking this course, students will be able to:

• define the semantics of a programming language using a definitional interpreter.
• investigate semantic issues in programming languages by studying implementations in an interpreter.
• solve problems using a range of programming paradigms and assess the effectiveness of each paradigm for a particular problem.

Prerequisites

Students will need a good knowledge of Functional programming.

This course fits well with Compilers but can be studied either before or after that course.

Syllabus

Abstract and concrete syntax. Definitional interpreters in direct and monadic form. Functional, imperative, and logic programming. Expressible and denotable values; call by value and call by name. Continuations and abstract machines.

Synopsis

1. Introducing Fun, with familiar examples rewritten in the language.
2. The concrete and abstract syntax of Fun.
3. A metacircular interpreter for Fun. Examples of evaluation.
4. Changing the interpreter to support assignable variables, with references as expressible values (like ML).
5. Implementing while by recursion.
6. Changing the interpreter to support output; extracting common features of memory and output.
7. Interpreters in monadic form.
8. Review: a language with exceptions.
9. The language Fungol, where identifiers are bound to assignable variables, and derefencing is implicit.
10. Call by value and call by reference.
11. Nondeterministic programs for backtracking search.
12. Logical variables and logic programming.
13. Introducing continuations
14. Interpreters in continuation-passing style
15. Continuations and abstract machines
16. First-class continuations

Practicals

1. Translation between recursive and iterative algorithms in a simple functional language.
2. Semantics of a language with call-by-name and assignable variables.
3. Semantics of loops with exit statements, combined with local functions.

Reading list

The course explores many of the same themes that are covered in

Friedman, Wand and Haynes, Essentials of Programming Languages, 2nd or 3rd ed., MIT Press.

However, that book contains interpreters written in Scheme, and we will use Haskell.

Full notes for the course (in the form of a draft book) will be handed out in lectures and put on the web.