Tue May 26 09:51:27 CEST 2009

MetaML and future of Staapl

Removing this from the introduction page:

  Related Work

  Compared to MetaML, which seems to be the current reference point
  for staged programming systems, Staapl contains functionality
  related to MetaML combined with abstract interpretation. However,
  Staapl is quite different as it is a non-homogenous two-stage system
  based on flat combinators and dynamic typing, while MetaML is a
  homogeneous multi-stage system based on the lambda calculus and
  static ML-style typing.

It's not so clear..  The real difference is that Staapl is a bridge
between something that behaves as a Forth macro system and the scheme
procedure/macro system.  The concatenative macros are special in that
they do not deal with names, so they could be compared to the
constrained code manipulation that's possible in MetaML.  But, Staapl
also contains a complete scheme-like macro system that can abstract
over names (the prefix parsers) bringing it far outside the reach of
the static analysis allowed by MetaML.

It would be nice to get some discussion going with Walid Taha or one
of his students about this.  I tried contacting him in an informal way
but got no reply.

Anyways, I'd like to be able to understand the real differences
between macro systems and staging but as far as I can see in the
literature, the bridge between them is still being built.  Dave
Herman's work is interesting in this respect, as is the Ziggurat

Now, my goals are humble.  As arrogance and achiever mentality start
to fade, I see what I did in perspective.  It's not really rocket
science.  I'm glad I've got the bridge to PLT Scheme worked out, but
there are still things that I don't really like that much:

  * Inability to integrate true partial evaluation.  The basis is
    there I just don't see the light yet.  What I do understand is
    that PE is more of an art than a science, since it is mainly about
    avoiding code explosion due to inlined recursive calls.  That
    problem is related to the halting problem.  The field seems to be
    mostly about "bags of tricks" requiring a lot of study to get a
    good idea about what people have tried and what works and what

  * Separate machine peephole optimizations and generic ones.
    I.e. the behaviour of '+' should be extendable, to be handled by
    the main compiler if both arguments are available, and by the
    target compiler for 1 and 0 available compile time arguments.

  * A type system.  A lot is to be gained by a proper type system that
    would enable processing of concatenative macro code _before_
    handing it over to the eager evaluator.  I.e. trying different
    permutations that are possible due to commutativity of operations.
    This requires building an algebraic system of combinators that can
    perform simplifications at compile time.  It would probably also
    help with lifting the language semantics to a bit higher level,
    and simplifying the peeophole optimizer.

  * Run-time and compile-time stack interaction.  If pops and pushes
    are made lazy, it is possible to perform data-flow analysis on
    words with fixed stack effect.  However, I currently don't know
    how to mix the side effects of pushing/popping with re-arranging
    machine instructions.  I'm already using something like this in
    the live simulator where it is clear how it should work.