Tue Nov 16 08:37:47 EST 2010

What is a Staapl macro? I :: m -> (t -> t)

Traditionally, a (Lisp/Scheme/...) macro perfoms only expansion while
the compiler can perform partial evaluation on the resulting
expression independently of the behaviour of the macro; working only
with the expansion results.

In Lisp/Scheme it is possible to inspect sub-forms at macro expansion
time to alter their behaviour originally specified as primitive forms
or other macro forms.  However, this isn't so well-behaved as the
meaning of forms is no longer defined in a single spot.

In Staapl, macros perform their own evaluation, but they don't modify
the structure of program text (with opaque, unknown semantics), but
instead operate on a well-defined lower-level representation language.

More formally, suppose t is a concatenative target language (syntax)
and m is a concatenative macro language (syntax).  Each token in m is
mapped (interpreted) to a function t->t or I :: m -> (t->t).  Each
non-primitive element in m consists of a concatenation of primitive
elements of m, which each map to a t->t function, thus each
non-primitive element of m also corresponds to a t->t function which
is the function composition of all the t->t functions associated to
each m token.  The t-meaning of m is then given by ((I m) t0) where t0
is the empty t program.

It doesn't seem that you can do this with an applicative language as
there is no relation between concatenation and composition and no
"natural" target language.  The Scheme above can be towered: in fact
in real life the target language t will be interpreted by a machine
execution unit E :: t -> (s->s) which maps each t token (machine
instruction) to a function transforming the machine state s.

One additional element is necessary: in order to get to a usable
programming language that supports modularity, the functions (t->t)
and (s->s) need to be ``local'' or ``small-dimensional'' in some way.
Staapl PIC18 currently uses stack machines where both t and s are
stacks of respectively PIC18 code and 8-bit machine words.