Source Transformation for Fun and Profit (by alaric)
meta
meta is very, very simple.
All it is is an extra language construct, which affects the partial evaluation process. All the metas in your program should go away during partial evaluation; if any are left once partial evaluation is complete, something's wrong, and you get an error, since it's impossible to compile a meta construct. Well, the best you can do is to leave it to runtime and treat it as a kind of eval instead, but a meta that survives partial evaluation is probably an error, so had best be handled as such.
Basically, the rule for partial evaluation of a form of the form [meta x] is that we must first attempt to partially evaluate x until it becomes a literal value. If we can't, we move on - a later stage of partial application may make x fully reducable (perhaps we are in a function definition, and x depends on the function arguments, in which case it won't be reducible until we inline an application of the function to something).
But once the body of the meta has been partially evaluated all the way to a literal value, we just make good use of the Lispyness of our language, by replacing the whole [meta x] with just x; source code is just a literal value anyway.
And then we continue partial evaluation of x, which is now an expression - and a meta has been removed from the program. By the time there's nothing left to partially evaluate any more, all the metas should be gone, as mentioned earlier.
That's all there is to it. It's a very low-level macro system indeed. To create the effect of a more conventional macro system, you can do one of two things.
Firstly, you could define your macros as functions that map the source code of a macro invocation to the source code the macro should expand to, and then invoke them like [meta [my-macro [' body]]] - explicitly applying the macro-function to the body to get the expanded source, then using meta to treat that source code as if it had been written into your program at that point, rather than just being a literal value.
Secondly, you could define a new programming language that's like your existing language, but has macros. In other words, give it a macro special form that looks like a normal lambda, except that when 'applied', it is passed the literal source code for the list of arguments it is being applied to, and is expected to return source code to replace the macro application with. Now write a function that translates programs written in this language into ones written in your existing base language. This will involve some analysis very similar in nature to the partial evaluator; maybe the partial evaluator used by the base language can expose parts of itself in some abstract way so they can be shared. Basically, we must attempt to partially evaluate the program, including the substitution of symbols for their values where they are known. But unlike the usual partial evaluation, we must not attempt to reduce the arguments to a function application unless it is known that the function symbol will be bound to a function, and not to a macro.
Then when we do spot an application of a macro, we invoke the macro function, passing it the body of the macro application, and then replace the application with the result of the macro function. No macro applications should survive past this point; if the programmer writes code like [apply: [if: x then: my-macro else: my-func] to: (1 2 3)] without x being decidable one way or another during the macro-expansion partial evaluation, then they deserve the resulting error when the base language partial evaluator or compiler or runtime then finds itself trying to apply a macro object (about which it knows nothing).
Then we can write programs in our higher-level language with nice macros (which, you will note, are first class objects - as long as they are entirely computable at compile time), and then wrap the program in [meta [expand-macros ...]], where expand-macros is our macro expansion partial evaluator.
In fact, the potential for building a stack of more and more powerful languages by layering these translation functions is interesting. We can actually start off with a painfully primitive base language, plus meta, then build it up to something useful with a suite of translation functions. This is a nice architecture for a compiler, and to make it easier, I'd suggest that the base language (no matter how primitive) have some syntactic sugar in the form of a header for every source file that lists the names of files containing such translation functions, to be applied in order. The most commonly desired suite can be composed into a single function, for ease of use, but the programmer is free to use a totally unrelated suite of functions to build languages with perhaps totally different semantics, purely as a 'macro' on top of the base language.
I go on about this at length in the original STFFAP report, if you're interested.
Thu 19th Jul 2007 1:39 pm 
Subscribe