Principles of Programming Languages: 2013-2014
Lecturer | |
Degrees | Schedule B2 — Computer Science |
Term | Michaelmas Term 2013 (16 lectures) |
Overview
This course use interpreters written in Haskell as a vehicle for exploring various kinds of programming languages.PRACTICALS
- Translation between recursive and iterative algorithms in a simple functional language.
- 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
- Introducing Fun, with familiar examples rewritten in the language.
- The concrete and abstract syntax of Fun.
- A metacircular interpreter for Fun. Examples of evaluation.
- Changing the interpreter to support assignable variables, with references as expressible values (like ML).
- Implementing while by recursion.
- Changing the interpreter to support output; extracting common features of memory and output.
- Interpreters in monadic form.
- Review: a language with exceptions.
- A purely functional language with call by name and lazy data structures.
- The language Fungol, where identifiers are bound to assignable variables, and derefencing is implicit.
- Call by value and call by reference.
- Nondeterministic programs for bactracking search.
- Logical variables and logic programming.
- Introducing continuations
- Continuations and abstract machines
- First-class continuations
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.
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.
Feedback
Students are formally asked for feedback at the end of the course. Students can also submit feedback at any point here. Feedback received here will go to the Head of Academic Administration, and will be dealt with confidentially when being passed on further. All feedback is welcome.
Taking our courses
Matriculated University of Oxford students who are interested in taking this course, or others in the Department of Computer Science, must complete this online form by 17.00 on Friday of 0th week of term in which the course is taught. Late requests, and requests sent by email, will not be considered. All requests must be approved by the relevant Computer Science departmental committee and can only be submitted using this form. Priority will be given to students studying for degrees in the Department of Computer Science.