Sat Sep 13 09:31:58 CEST 2008
Staapl vs. MetaML / MetaScheme
This post is an attempt to list the differences between the kind of
metaprogramming Staapl uses, and the approach used in (untyped)
Scheme's hygienic macros:
Allow manipulation of arbitrary expression trees, but provide both
referential transparency (all identifiers take semantics from the
definition site) and avoid variable capture (identifiers introduced
by a macro never bind variable references that were already present
in the code.)
Scheme's approach is about IDENTIFIERS, not about abstract syntax
trees. The bindings of these identifiers (syntax or values) drives
the expansion. Lexical structure comes from extending the
expander's local identifier environment whenever new binding forms
are encountered. Binding information from the local environment is
available through functions like 'bound-identifier=?.
Lisp macros and quasiquotation:
A simpler templating mechanism that does not interpret names in any
way, and thus has problems with hygiene when manipulating or
generating code with lexical structure.
Ignoring the type system details, this becomes MetaScheme. It is
based on the operations: Bracket, Escape, Lift, and Run. These
operations are performed on a code data structure.
Such a system needs a more highlevel representation of code as
lambda terms. Care needs to be taken to ensure proper renaming when
manipulating binding forms and providing cross-stage-persistence.
The comparison to MetaML is a bit difficult because Staapl doesn't
have a clear concept of ``code object'' in the sense that MetaML
does. Staapl's metaprogramming is function-oriented instead of
data-oriented. The central object in Staapl is a ``code
transformer'' which operates on primitive stack machine code.
Metaprogramming in Staapl is established by two mechanisms. The
first one is similar to MetaML's 4 operations on code objects, but
operates on compositions of code transformers instead of a code data
structure, and is no longer a true staging operation in the MetaML
sense. The second is the definition of primitive transformers
operating on stack machine code (the data-oriented part).
Due to the absence of a binding mechanism in Coma code, the
equivalents of Bracket and Escape are simply quasiquote and unquote.
Bracket corresponds to the concatenative composition form 'macro:
while escape is an 'unquote operation which allows interpolation
from the Scheme lexical environment.
There is an analog for MetaML's cross-stage persistence (Lift), but
this is usually better made more explicit in Staapl: Unquote
operations are usually preferred over automatic lifting:
(let ((square (macro: dup *))
(macro: ,square ,square ',one +)) ;; 4th power + 1
This is for two reasons: Scheme and Coma have different name spaces
to support different language semantics side-by-side and unquoting
explicitly chooses between them. By default 'macro: takes from the
'(macro) namespace, i.e. the '+ 'dup and '* identifiers in the
example above. Moreover, Coma code handles values and functions
differently, which requires a choice of how Scheme identifiers
should be interpreted. This is reflected in the two unquote forms ,
and ', which insert functions and literals from the Scheme name
space in the Coma code respectively.
However, when it's clear whether identifiers should represent
functions or values, automatic cross-stage lifting is easily added.
It is used in the 'tscat: composition operation where Scheme lexical
names can be referenced as values:
(let ((one 1))
(tscat: one +)) ;; increment
Similarly, one could choose to use default function semantics, where
Scheme lexical identifiers are dereferenced as Coma functions. This
is used in a language extension that allows the introduction of
Note that the code generator closes over identifiers in the
currently visible '(macro) namespace also. These identifiers behave
exactly as Scheme identifiers; they are implemented as prefixed
identifiers. There's a corresponding let form:
(let-ns (macro) ((inc (macro: 1 +)))
(macro: inc inc)) ;; add 2
The analog for MetaML's Run operation is more difficult to identify,
since this requires on-target stack machine code execution. While
it is possible in Staapl, compilation is usually kept separate from
on-target code exection.
However, the different model used in Staapl does present an
``instantiate'' operation which produces stack machine code from a
code generator. A generator is a code transformer that accepts the
Upto now we ignored the other metaprogramming mechanism that uses
pattern matching to define machine code transformer primitives.
This is an essential part of Staapl, and is in some sense
complementary to the Scheme->Coma bracketing operations in that it
can be used to represent Partial Evaluation rules which
_deconstruct_ code. They have no equivalent in MetaML, but resemble
abstract interpretation techniques that have been used in
conjunction with MetaOcaml code construction. In Staapl this is an
integral part, and it's the interplay between quasiquotation and
deconstruction that gives the system its expressiveness.