grammar book

macros

Oh by the way, I implemented macro's pretty much exactly as Petrofsky had explained. The macro rewriting bit was fairly straightforward. I put in support for the most basic syntax-rules construct. Basically, it looks like this,

pattern variables must be just symbols that act as the parameters for the macro. template is an S-expression that is expanded by the macro transformer. The empty list right after syntax-rules is for literals, but I didn't bother implementing it.

Also notice that I didn't have the macro keyword appear in the macro itself. I could have, but I don't quite see the point of doing so. I ignored the whole pattern matching aspect of macros and just focusing on the transcription side.

So, when a macro is used its template is expanded and pushed onto the expression stack to get evaluated. Expansion is done by first creating map from pattern variables to the macro arguments. Then the expansion S-expression is built by recursively walking the template S-expression. If a number is encountered then it is put directly into the expansion (since numbers are immutable). A new list is created if a list is encountered and its contents are the expanded contents of the template's list. Finally, if a symbol is encountered which is mapped to an argument then the argument is put into the expansion, otherwise a new symbol with the same name is created and put into the expansion.

Actually, this isn't the whole story. The new symbol that is created is labelled in such a way that it can be distinguished as coming from that particular template transcription. This is the basis for the hygenic resolution of variable bindings. I introduced the class Label to capture the concept of a unique identifing mark on a symbol which makes it unique to that transcription AND provides enough information to look up the symbol in the environment of the macro transcription.

A new Label object is created each time a macro template is expanded, and it is applied to each generated symbol by the transformer. When the transformer emits a new symbol (it only does this, remember, when the template symbol is not a pattern variable) it labels the new symbol with all of the labels already applied to the template symbol plus the label for the current template expansion. To handle this, I modified Symbol objects to contain a list of Labels. Applying a Label to a Symbol means adding it to the end of this list.

The list of Labels then describes the history of macro expansions a symbol has undergone, in the order in which they happened. A Label itself contains two things, a unique integer across all instances, and an Environment. The unique integer per Label allows us to describe a Symbol as the symbol's name and the list of Label integers (just like Petrofsky's notation (ex. cons#1#2). In fact, this is exactly the sort of string I used to get the hash code for a Symbol so that symbols with different template expansion histories are treated as distinct symbols (the meaning of 'hygenic').

The only other change to the interpreter I made was to how a Symbol resolves its binding. Previously a Symbol.evaluate() would check with the VM's current environment for a binding. If one couldn't be found then it the symbol would be unbound. But the lexical scoping introduced by hygenic macros meant that symbol lookup should happen for each of the template transcription environments, from the most recent back. Furthermore, the symbol at the time of each macro template transcription, if it was in the environment at the time, wouldn't have label of that transcription. The upshot is that evaluating a Symbol involves first looking in the current environment, and then looking in each Label's environment, from the list of that Symbol's Labels, each time stripping off a label from the symbol.