Tue Mar 16 15:13:43 CET 2010

Compilation, Interpretation and Staging

I'm trying to build an intuition for the following diagram

          int      |
     stx ====> fun |
      :            |
 comp :            V
      :          data'

which represents the types:

    int  :: stx -> (data -> data')
    comp :: stx -> stx'

An interpreter maps syntax to function, while a compiler maps syntax
to syntax.  For a state machine representation, data=data'.

The difference between staging and compilation is then quite clear:

    - staging uses the range (data') of a target function domain as
      the input of a following interpretation step

    - multi-pass compilation is straightforward function composition

The big idea is that compilation is just computation (stx -> stx').
However, the connotation of compilation is usually that semantics of
the syntax is preserved in some way.  I.e. every intermediate syntax
will be related to some semantics (function domain) in such a way that
those function domains can be related.

     stx  ====> fun
      :          ^
 comp :          ;
      :          ; proj
      V    int'  ;
     stx' ====> fun'

I.e. for a definitional interpreter int, we know that comp is correct
if int = comp . int' . proj where int' is the target interpreter and
proj maps the target semantics (i.e. machine simulator) into the
original semantics.

Question: what happens if proj points in the other way?