Department of Computer Science and Technology

Course pages 2018–19

Metaprogramming

Principal lecturers: Dr Nada Amin, Dr Jeremy Yallop
Taken by: MPhil ACS, Part III
Code: L305
Hours: 16 (12 lectures and 4 hrs of practical)
Prerequisites: Foundations of CS (eg. see Part IA), Prolog, Semantics of Programming Languages, Concepts in Programming Languages, Compiler Construction (eg. see Part IB); More loosely-related: Denotational Semantics (eg. IB), Optimising Compilers, Types (eg. II)

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.

Assessment

  • Three programming problem sets 50%.
  • One open-ended assignment 50%.

The course is borrowed from Part II of the Computer Science Tripos Units of Assessment. As such, assessment will be adjusted to an appropriate level for those enrolled for Part III of the Tripos or the M.Phil in Advanced Computer Science. Further information about assessment and practicals will follow at the first lecture.

This course is borrowed from Part II of the Computer Science Tripos. As such, assessment will be adjusted to an appropriate level for those enrolled for Part III of the Tripos or the M.Phil in Advanced Computer Science. Further information about assessment and practicals will follow at the first lecture.