Partial Evaluation: Types, Binding Times and Optimal Specialisation

Lecturer: Neil D. Jones

Interpreters, compilers, program specialisers.

Course Materials

Lecture Notes:

SLIDES: (may be updated)


Functional programming.


Day 1. Programs as data objects(2 hours)

  • Interpreters, Compilers, and Program Specialisers
  • Specialisation
  • Interpretation overhead
  • Self-interpretation of a subset of SCHEME
  • Partial evaluation: efficient program specialisation

Day 2. Partial Evaluation, Compiling, and Compiler Generation (2 hours)

  • Specialisation
  • The Futamura projections
    • 1: a partial evaluator can compile
    • 2: a partial evaluator can generate a compiler
    • 3: a partial evaluator can generate a compiler generator
  • Speedups from specialisation
  • How specialisation can be done
  • The first Futamura projection with UNMIX
  • The second Futamura projection with UNMIX
  • Speedups from self-application
  • Metaprogramming without order-of-magnitude loss of efficiency
  • Desirable properties of a specialiser

Day 3. The Types Involved in Partial evaluation (2 hours)

  • Underbar types (types of program texts)
    • Types of interpreters
    • Types of compilers
    • Types of program specialisers
    • Types for program self-application
  • Optimal program specialisation
    • Inherited limits during specialisation
    • Optimality is harder for typed languages!
    • Makholm's solution


Some suggested reading:

partial-eval.txt · Last modified: 2008/06/26 22:27 by scm
Recent changes RSS feed Creative Commons License Donate Powered by PHP Valid XHTML 1.0 Valid CSS Driven by DokuWiki