Skip to main content

Principles of Programming Languages:  2017-2018

Lecturer

Degrees

Schedule S1(CS&P)Computer Science and Philosophy

Schedule B2 (CS&P)Computer Science and Philosophy

Schedule S1Computer Science

Schedule B2Computer Science

Schedule S1(M&CS)Mathematics and Computer Science

Schedule B2Mathematics and Computer Science

Schedule BMSc in Computer Science

Term

Overview

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

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.

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

Functional programming.

Synopsis

(Sample)
  • Introducing Fun, with familiar examples rewritten in the language.
  • The concrete and abstract syntax of Fun.
  • A definitional interpreter for Fun. Examples of evaluation.
  • Changing the interpreter to support assignable variables, with references as expressible values (like ML).
  • Changing the interpreter to support output; extracting common features of memory and output.
  • Interpreters in monadic form.
  • Exceptions.
  • Call by name and call by value.
  • Nondeterministic programs for bactracking search.
  • Continuations.
  • Abstract types.
  • Simple types.
  • First theorems relating types, the abstract machine and the definitional interpreter.

Syllabus

Abstract and concrete syntax. Definitional interpreters in direct and monadic form. Functional and imperative programming. Simple types and basic denotational semantics. Call by value and call by name. Continuations and abstract machines.

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.