Department of Computer Science and Technology

Course pages 2018–19

Subsections


Unit: Metaprogramming

This course is only taken by Part II 75% students.

Lecturers: Dr N. Amin and Dr J. Yallop

No. of lectures and practical classes: 12+4

Prerequisite courses: Foundations of Computer Science, Prolog, Semantics of Programming Languages, Concepts in Programming Languages, Compiler Construction.

Capacity: 50

Aims

This course surveys principled approaches to metaprogramming; writing programs that manipulate programs. Topics include evaluators, reflection, writing programs that write programs, designing domain specific languages and meta-linguistic abstractions, synthesis.

Lectures

  • Week 1. Programs as data, data as programs. Interpreters. Meta-interpreters in Lisp and Prolog.
  • Week 2. Reification / reflection, reflective towers of interpreters, meta-object protocols.
  • Week 3. Partial evaluation including Futamura projections, multi-stage programming. Turning interpreters into compilers, collapsing towers of interpreters.
  • Week 4. Domain-specific languages, finally-tagless. Non-determinism, relational and probabilistic languages.
  • Week 5. Synthesis.
  • Week 6. Unconventional models of computation. Relaxing from symbolic to neural. Reversible computing.

Objectives

By the end of the course students should be able to:

  • Mechanically turn an interpreter into a compiler;
  • design meta-linguistic abstractions to deal with a complex problem;
  • think beyond traditional paradigms for programming.

Recommended reading

Detailed suggestions for reading will be given in the lecture notes. The Scala programming language will be used for assignments, and the following books are useful reference for that, although neither is required:

Odersky, M. (2014) Scala by example. EPFL Programming Methods Laboratory. Available online: https://www.scala-lang.org/docu/files/ScalaByExample.pdf
Odersky, M., Spoon, L. & Venners, B. (2016) Programming in Scala. Artima (3rd ed.).

Additional background reading includes:

Pierce, B.C. (2002) Types and programming languages. MIT Press.
Abelson, H. & Sussman, G.J. Structure and interpretation of computer programs. MIT Press (2nd ed.).
Norvig, P. (1992) Paradigms of artificial intelligence programming. Morgan Kaufmann.


75=75