Thu Jun 11 13:51:03 CEST 2009

Abstract interpretation ('eval in macros)

In Scheme low-level macro programming, most of the time 'syntax->datum
or 'syntax-case will be enough to allow for compile-time computations
necessary to construct output syntax.  However, sometimes you need to
actually "bring the input syntax to life" once before deciding how it
will be transformed finally.  In general this is called abstract
interpretation [1].

When this interpretation process is similar to interpreting Scheme
(i.e. it includes dealing with lexical variables to construct graphs)
it can be easier to just invoke 'eval directly, and encode the desired
alternative semantics as macros.

The dataflow pattern of such a syntax transformer is:

                            scheme code
  input syntax             ------------->  modified syntax

  modified syntax          ------------->  value

                            scheme code
  input syntax + value     ------------->  transformed syntax

In PLT Scheme this kind of trickery can be performed by using
(anchored) namespace objects passed to 'eval.

Namespace objects map identifiers to semantics.  In normal macro
programming you don't need to use explicit namespace objects since
everything has only one meaning.  When you want _alternative_
interpretations, you need to either perform interpretation manually
(i.e. using 'syntax-case or 'syntax->datum) or use the Scheme
interpreter as a whole by invoking 'eval in a specically constructed

This problem popped up when trying to compile a parallel program in a
dataflow language (DFL) to a staticly scheduled sequential Scheme
program.  In order to construct a properly sequenced code list, the
dataflow graph needs to be constructed and analysed for dependencies.
However, I implemented graph building on top of Scheme's lexical
scoping mechanism using macros, which means that the graph data
structure itself is only available _after_ expansion.  This allows me
to avoid having to construct the graph manually.  However, building a
sequential program from this requires a two pass algorithm: build the
graph and interpret it abstractly to find a serialized code sequence,
then compile everything to plain scheme in the right order.  The first
pass can then be performed using 'eval on an alternative
interpretation which yields the proper code sequence.  This can then
be used together with the original syntax to construct a compilation
to sequential Scheme code.

In Staapl I did run into this problem a couple of times before.  One
other case is the automatic wrapping of Scheme functions, which needs
information about their arity which is only available after executing
the functions.

Another occurance happened when trying to compile the dependency graph
of the cyclic forth bootstrapper, which involved several alternative
interpretations of the code: as code running on a threaded target
interpreter, and as code running inside the host compiler on a
different VM.

[1] http://en.wikipedia.org/wiki/Abstract_interpretation