BYU - Spring 2013 - CS 630 - 5/28 - Discussion
Andrew Kent
We began our discussion as we have several times now, by looking at what the paper is “really” about, as opposed to what the title and perhaps the abstract highlights. This paper (“A Few Principles of Macro Design”) really highlights some realities about macros that have come to light that seem to show that macro hygiene does not mean what people think it means. Perhaps also it shows how in some cases we don’t really want the strict definition of hygiene to be in force, if perhaps there is a compelling reason to break it to accomplish some reasonable task.
This turn of events was not entirely unforeseeable (at least in hindsight...). As we discussed when we read the initial Kholbecker paper the definition of what hygiene was had some vague descriptions and Kholbecker himself didn’t formally prove anything about it (even so, it was a compelling leap forward for macros!). In this paper, Herman tries to argue that what we really want when we are trying to describe how a macro should behave is alpha-equivalence... as well as a logical structure (such that the user of a macro need not see the implementation to fully use and understand it).
To articulate cases where strict hygiene is not wanted (or at least where its exclusion is interesting) we see the puzzle of how to tell if two S-expressions are identical. The simple first solution is to merely use quoting, which is one simple way to allow the program to inspect its own code. The other way is using syntax-rules to create macros that behave (expand) differently based on the program source text. The problem is that doing this inhibits the ability for a program to be automatically optimized (or similar) because the program could be inspected and changed without the optimizer considering how this might affect the computations.
Another problem with hygiene that is brought up is that the whole idea that hygiene cannot bind things the user introduces just doesn’t make sense in some cases (the mylet and loop examples). In fact, when you think about it as the macro is working with, and in this case, binding, the things you specifically gave it, it doesn’t sound as if it should be verboten in all cases. Thus hygiene is not only vague in what it is specifying, but it is not universally agreed that it is the ‘cure all’ and should be universally applied.
We then discussed the 3 key things he argued should be kept in mind when designing macros: design the macro with alpha-equivalence in mind, do not use identifiers in 2 different ways, and do not quote things (or avoid observing variable names). This led to highlighting what Dybvig included in his “macro-writer’s bill of rights,” that a compiler can and should make optimizations whenever reasonably possible, and the use of manual optimizations should exclude cases where the aforementioned automated case could apply. In other words, you should focus on clear, correct macros and the optimizer should do the rest (within reason).
The second paper we dug into was as Jay described an “evil” paper because it showed interesting, previously undiscovered exploitations in the existing Scheme language specification. In fact, these exploitations are so powerful (and confusing...) that they basically allow a Schemacist to create a general purpose macro system that behaves like the Lisp macro system, which means that after all this effort to create sound, structured macros in Scheme we ended up with a macro system that really wasn’t different at all to begin with (although, reflecting on this more now, I’m not sure I understand how it outright makes it the same... it seemed like it took a lot of work to break it down to this level - doesn’t that count for something?)
In our discussion and review of how this worked it was pointed out that one of the key ideas behind this was the difference between keywords and symbols. If a macro can decide when something is an actual keyword and not merely a symbol in a pattern to match then attacks that could take advantage of this can be prevented. In other words, or by example, if we’re defining our own if/then/else the ‘then’ and ‘else’ should be able to be specified clearly as keywords and not merely place holding symbols which separate the true and false expressions.
Another important thing that was brought up during our discussion of this paper (and something we’ve been hinting at or mentioning all along) is the reality that hygiene does not have an actual technical meaning. I feel like this conclusion begs the cliched question of how can we get somewhere if we don’t even know where we’re going? If hygiene isn’t an actual technical specification and more just a mushy idea, how are we confident we’re moving in the right direction with where macros are headed? That’s a little harsh, I mean, of course there are clear examples and areas where we can say “yes, a macro should do this” or “no, a macro should not do that,” but I can’t help but be slightly bothered that macro development is reaching for something that it’s not quite even sure of. Perhaps, however, many of the bleeding edge innovations in areas like this are done in this manner at times and that’s just the reality of scientific study and exploration into the unknown.
Matthew Ashcraft
The whole point of these papers was that the hygiene condition does not mean what we thought it meant. Additionally they show us how to approach hygienic macros in way to break informal assertions regarding them, and how to programs better with them. The first paper we discussed was A Few Principles of Macro Design by the Davids. The paper is based off the idea that if you can’t show that two s-exprs are can be the same, then they must all be different. The paper uses the quote operator in their example. We shortly discussed the quote operator, in that it turns all code into data, and quote is the same as ‘, which would have made this clearer if I knew that when reading it. The example which was demonstrated compared the add and + operations. Though these produce the same result (possibly not always), they are implemented in different ways. When the two were compared with the quote operator, then they were shown to be different. I also learned about the check-true and check-false operators, which test results of macros or functions to see if they are true or false.
One of the problems we discussed was that macros violate your ability to understand macros. This is a big problem in optimizations because a macro that sums constants cannot be replaced by the sum of the constants. This is because the macro could be quoted, turning the code into data. The example that was used in class was a new macro which was looking for a list was placed around the original macro. With the original code the macro returned true, but with the substitution the list was replaced with a single element, so the macro returned false. I was surprised when I first understood this, as I never thought that optimizations such as that would have been a problem, but now it is so obvious now why they are. The next topic of our discussion was the continuation passing style. The main issue with this was that macros cannot communicate outwards. In the example the macro called itself as one of the parameters, and as a result, the wrong I value was assigned. As the macros expanded within one another, the hygienic renaming chose the wrong values to rename together. I think this was because in syntax-rules the patterns are matched in order.
The next bit of code that we discussed was the ident? operator which returns true when a pattern variable is given. Then we talked about the ident=? operator. It was also mentioned regarding these that operators can rely on literals in which case everything, including else, must be explicitly stated. These literals are the source of all of these problems with hygienic macros. The loop macro from the text was discussed next, which truly did break the hygiene condition. In the loop macro, the break statement is extracted using the find operator that the author wrote, and is then plugged into the loop macro to exit the loop when the break is found.
Following that discussion we went off on a tangent on continuations. Continuations let you jump back to an earlier state of the rest of the program. The example that was given looked for a pair of numbers that could be used to satisfy an equation. The neat thing about the implicit continuations is they allow you to specify the answer you want, along with all of the possible input parameters, and the macro can solve the problem for you. I have only heard of one other language that can do that so easily (I don’t however remember its name). It was also mentioned in class that the example we were dealing with is sometimes called the double barrel continuation. These continuations used to find solutions to desired answers use features similar to depth first searches.
Alpha renaming was then discussed as part of the hygienic condition. This process renames all variables while keeping the equivalent program. The variables are renamed where they are bound, and all variables that use that binding are then replaced with the same name. This is popular because it makes every variable globally unique. It was also mentioned that macros should never break alpha equivalence. The jletwreck example was then discussed, which used free and bound identifiers together. This is something that shouldn’t be done. Additionally we discussed the negative effects of the quote operation, and that it should basically never be used in good macros. An example of why the quote operator might be needed was given regarding the mangled names for structs. Apparently there is even another way of doing this without the quote operator. Lastly for this paper we talked about how subterms should be atomic, meaning we shouldn’t look inside them.
The next paper was only discussed for the last 30-40 minutes of class. This paper used a lot of the same work that was used in the first paper, like that of Petrofsky. Referential opaqueness, in contrast to referential transparency, was discussed. In order to achieve referential opaqueness the author created a new version of let called mylet, and as he expanded macros, he re-defined them to know about their predecessor. This was so that nested macros could know which variables were local to each macro. The redefining of mylet pushed the bindings down to used variables. The last section showed how R5RS could be taken over and treated as the lisp macro system. The discussion was pretty clear to me except for some of the examples that were written in class. If the code from class could be posted that would be appreciated.