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.

MetaML's staging:

  Ignoring the type system details, this becomes MetaScheme[1].  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.

Staapl's staging:

  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 *))
          (one 1))
       (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
  local functions.

  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
  empty program.

  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.

[1] http://okmij.org/ftp/Computation/Generative.html#meta-scheme