Lecturer: Neil D. Jones

Interpreters, compilers, program specialisers.

Lecture Notes:

• Datalogi V - Programming Languages, Chapter 3: Programs as data objects, by N. D. Jones. University of Copenhagen, 2007.
• Datalogi V - Programming Languages, Chapter 4: Partial Evaluation, Compiling, and Compiler Generation, by N. D. Jones.University of Copenhagen, 2007.
• Partial Evaluation and Automatic Program Generation, Chapter 16.2: Types for interpreters, compilers, and program specialisers, by N. D. Jones, C.K. Gomard, P. Sestoft. Prentice Hall, 1993.

SLIDES: (may be updated)

• LECTURE 1 slides.
• LECTURE 2 first slides.
• LECTURE 2 second slides.
• LECTURE 3 slides.

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:

• Datalogi V - Programming Languages, Chapter 3: Programs as data objects, by N. D. Jones. University of Copenhagen, 2007.
• Datalogi V - Programming Languages, Chapter 4: Partial Evaluation, Compiling, and Compiler Generation, by N. D. Jones.University of Copenhagen, 2007.
• Partial Evaluation and Automatic Program Generation, Chapter 16.2: Types for interpreters, compilers, and program specialisers, by N. D. Jones, C.K. Gomard, P. Sestoft. Prentice Hall, 1993.
• On Jones-optimal specialization for strongly typed languages, volume 1924 of Lecture Notes in Computer Science, by Henning Makholm. Springer-Verlag, 2000.