Interpreters

Interpret :: (Program, Data) --> Output

or (currying the inputs) Interpret :: Program --> Data --> Output

or (grouping the last two outputs) Interpret :: Program --> (Data --> Output)

or Interpret :: Program --> Executable (Futamura's first projection, discussed below)

"online"

Compilers

Compile :: Program --> Executable

Executable is in the language of the implementation of the Interpreter (e.g., assembly language for Java interpreter)

Executable :: Data --> Output

"offline"

Partial evaluation

A computer program can be seen as a mapping of input data to output data:

prog :: Istatic x Idynamic --> Output

The partial evaluator (also called specializer) transforms (prog, Istatic) into prog* :: Idynamic -> Output

prog* is called the residual program and should run more efficiently than the original program

Futamura Projections

Interesting case when prog is an interpreter for a programming language. Described in 1970s by Yoshihiko Futamura

If Istatic is source code designed to run inside an interpreter, then partial evaluation of the interpreter with respect to this data/program produces prog*, a version of the interpreter that only runs that source code.

This specialized version of the interpreter is written in the implementation language of the interpreter., i.e., the language in which the interpreter has been written (e.g., assembly language for the Java interpreter).

The source code does not need to be re-supplied to prog*

prog* is effectively a compiled version of Istatic

This is the first Futamura projection. There are three Futamura projections:

A specializer is a partial evaluator

  1. Futamura Projection 1: Specializing an interpreter for given source code, yields an executable
  2. Futamura Projection 2: Specializing the specializer for the interpreter (as applied in #1) yields a compiler
  3. Futamura Projection 3: Specializing the specializer for itself (as applied in #2), yields a tool that can convert any interpreter to an equivalent compiler.

Take-aways from Futamura's projections

Why study compilers? Can't I just take them for granted and forget about them?

If you ask me, compilers are the most exciting research area in computer systems (and perhaps in the whole of computer science) currently, and are likely to remain so for several years to come.

Two technology trends that show the rising importance of compilers in Computer Science:

  1. Moore's law is running out of steam
  2. Program complexity is increasing

Some more crazy ideas that seem to be going around these days

Some history