Thu May 7 09:30:31 CEST 2009


Maybe it is better to see the macros as specializers.  Take the
definition for '+ for example:

 (([qw a ] [qw b] +)         ([qw (tscat: a b +)]))
 (([addlw a] [qw b] +)       ([addlw (tscat: a b +)]))
 (([qw a] +)                 ([addlw a]))
 (([save] [movf a 0 0] +)    ([addwf a 0 0]))
 ((+)                        ([addwf POSTDEC0 0 0])))

This is defined as a function that combines original syntax 'qw with
specialized syntax 'addlw 'movf 'addwf.

The advantage is that it can be example-based: if you see some pattern
in target code that you didn't expect, it can usually just be added to
the rules of some specializer.

The problem is that this is quite lowlevel and difficult to understand
because it mixes 2 conceptual levels: real machine code and pseudocode
directly representing a trivial compilation of concatenative/Forth

Another problem is that this is eager: always reduce in the same
place: at the top of the code stack.  There is no "reduction under
lambda".  What I wonder is if this actually is a limitation.

So.  Next task: figure out a way to compile highlevel rewrite rules
(which operate only on macro syntax) into eager lowlevel ones.

I.e. the commutative law:

     (swap +) = (+)

Something related to Luke Palmer's post: what if it is possible to
keep functions that return a single value wrapped as promises?

The idea is that concatenative code (a b +) can be replaced with (b a
+) as long as 'a and 'b return a single value.  Using some kind of
type system it is possible to identify "pseudoconstants" that will
make moving code around a lot easier.

I.e.  Suppose there is some occurance of (a b +) where 'a will not
recombine with the code before it, but 'b will, then it is better to
swap them and evaluate the whole bunch into a value.

Actually, the type system could be _implemented_ as something that
wraps into 'qw.  I.e. macro results should be left as quotations as
long as possible, and when finally evaluated should be memoized.

This requires a representation of "pop the runtime stack" as a quoted
macro.  More specifically: reference into the runtime stack.  The
stack could then be pushed/popped on every call.

Bottom line: more lazyness -> better partial evaluation.

To organize this it might be best to keep the eager and lazy parts
separate.  I.e. the current PIC18 macros could implement the final
eager specializer (the optimizing compiler) while a lazy specializer
is written on top of it.

Some examples:

     @  always should bind directly
        [m1 a] -> [m1 (macro: a @)]

     +  binds lazily with a check for its two arguments
        [m2 ab]       -> [m1 (best (macro: ab +) (macro: ab swap +))]
        [m1 a] [m1 b] -> [m1 (best (macro: a b +) (macro b a +))]

Now this 'best thing in there.. That's the reason the compiler needs
to be purely functional - so we can easily fork 2 different states and
pick the best one to continue.

One thing about this scheme: it's not clear when to actually force the
expression.  I think this is the same as Luke means with "I am still
not totally sure when to introduce an abs" in [1].

It looks like a good time is whenever there are more items packed
together in a single macro return than the next macro takes as input.

Michael Thyer's lamba animator [2] contains examples of both eager and
lazy specialization.

[1] http://lukepalmer.wordpress.com/2009/05/04/lazy-partial-evaluation/
[2] http://thyer.name/lambda-animator/