BYU - Spring 2013 - CS 630 - 6/4 - Review
Matthew Ashcraft
Debugging Hygienic Macros
This paper starts off discussing the power of macros and ideally how they should be used. The ideal language would allow for the “development, encapsulation, and reuse of entire sub-languages.” Macros give programmers the ability to define new expressions and definitions with custom behaviors. Some macro languages can also share information, and detect and report errors at compile-time. They also allow for extensions such as modules and local bindings to be mixed without the help of preprocessors or specialized compilers. Additionally, macros can take advantage of pattern matching, loop constructs, class systems, and component systems. To provide these abilities, the macro systems have had to evolve and have become much more complex. True syntactic abstractions must be indistinguishable from features that are provided by the core language. To try and aid this implementation, macro researchers have introduced the concepts of hygiene, referential transparency, and phase separation. These all add scoping properties to variables and identifiers. As these properties plus many more have been implemented into macro languages, they have become much more complex, making them harder to read and even harder to debug. For these reasons, this paper proposed a debugger that is build into the macro expander to aid programmers.
A debugger should not simple point to an error, but should try and explain it in a way that the user can understand. In order to provide this ability, their debugger relies upon three principles of macros:macros are rewriting tools, macros respect lexical scoping, and macros define layered abstractions. These principles are then discussed in further detail. Macro expansion is the process of applying repeatedly rewriting rules until the program only uses primitive forms provided by the core language. There are two ways to write the macro rewriting rules: syntax-rules, and syntax-case. Examples for each of these is given. It does mention that a single define-syntax equation can actually recognize multiple patterns, and use a different template for each. Does this mean that a large set of different macros could just be written in one macro with many different patterns? The paper then gives a small example of their graphical interface, of which many ideas have been borrowed from the run-time stepper for Racket. The interface allows the user to go back and forth in time to view the expansion as it occurs step by step.
The next principle this debugger is based off of revolves around the hygiene condition. They explain the hygiene requirements as “macros act 'like closures' at compile-time.” The bindings of the hygiene condition are gradually discovered during the compile-time expansion, meaning the entire program it not known until all of the expansions have been completed. As each step of the macro expansion, their debugger updates scope information for the user to see. Their debugger uses different types of arrows to differentiate between tentative bindings and definite bindings. This binding information is very important to the user because many of the bugs introduced by programmers come from incorrect bindings. Without scope information the program may look correct but still be producing the wrong values due to incorrect bindings. The last principle their debugger is based upon is that macros define layered abstractions. This is kind of like the idea of language towers that we discussed previously. Macros are built upon macros which are built upon macros, and so forth, until the core language is actually reached. I think it was stated in a previous class that some macros in the Racket language consist of language towers 30 macros deep. In this case the user would probably not want to see every macro all the way to the core language, especially since those languages have already been thoroughly tested. Their debugger provides as macro hiding option that allows the user to state which macros they don't want to see the expansion of, or in other words, which macros it wants to make opaque. Previous attempts at debugging macros was very limited, and relied upon expand, expand-once, and expand-only operations. These are explained further in the paper.
The implementation of the paper is then explained. The information in their debugger flows from the back end to the front end, opposite that of the compiler. The back end monitors the execution of the program, the middle optimizes the IR for user comprehension, and the front end displays the symbolic steps to the user. The back end is connected to the macro expander, and monitors the progress, intermediate terms, and unique names (fresh names and marks). The middle end traverses the tree, hiding extraneous details along the way. The front end shows all of this information to the user as a sequence of writing steps. The details of how these are implemented are then described in further detail, following which the formal model is given and proven. From their experiments they have found their debugger to work exceptionally well, and I believe this is what became the macro stepper used in the Racket program from class. I felt like I understood everything up to the formal model fairly well, so that is what I will primarily be reviewing before class tomorrow. The only question I have now is the one I gave in paragraph 2.
Fortifying Macros
This paper is about a new macro system for Racket that is robust and easy-to-understand language extensions that can detect when misuses of the macros. Macro writers are often satisfied once they simply get something to work. This is why more macro writers write sloppy macros. Work has been done in the past to make it easier for macro writers to write robust macros. The main work that this research was built off of was the Macro-By-Example (MBE) by Kohlbecker and Wand. MBE replaces the procedural code with a set of clauses, each of which is made up of patterns and templates. The patterns represent a macro's syntax, and the template is the definition. They also implemented the notion of using ellipses add expressive power to the patterns. Guards are then used to ensure that the macros accept valid syntax. These guards can require excessive overhead, and don't indicate where the errors occurred. There have been various way to overcome this problem, but they are too time consuming and difficult for most macro writers to implement. This is where their work comes in. They propose a DSL for macros called syntax-parse. It provides three advancements over MBE: an expressive language of syntax patterns, facilities for using these syntax patterns, and a matching algorithm that tracks the progress of the expansion to rank and report failures, which failures contain information about the errors that occurred. The syntax-parse uses the declarative specification to determine what error should be reported. Matching is done to determine which of all the errors that occurred is the actual error that should be reported. The paper then talks about how the error messages are generated. The syntax and semantics are then discussed, which would take too long to explain here. Their code was implemented using a two-continuation representation of a backtracking monad. (What is a monad?) Syntax-parse is the main contribution of this paper. It makes it easier to write easy-to-understand and robust macros. It is easier to use than previous work, such as MBE, and it comprehensively validates all constraints at the proper level of abstraction. The head patterns along with the semantics were the parts I had more trouble understanding, which I'm sure we will discuss tomorrow. This paper was less clear to me than the previous, but I still felt like I understood most of the concepts presented. I understood sections 1-5 fairly well, though there were many small parts here and there that were not clear to me. Additionally I had trouble understanding all of the semantics in section 6.
Jay McCarthy
share a common head, the name of the macro.
> Syntax-parse is the main contribution
> of this paper. It makes it easier to write easy-to-understand and robust
> macros. It is easier to use than previous work, such as MBE, and it
> comprehensively validates all constraints at the proper level of
> abstraction. The head patterns along with the semantics were the parts I had
> more trouble understanding, which I'm sure we will discuss tomorrow. This
> paper was less clear to me than the previous, but I still felt like I
> understood most of the concepts presented. I understood sections 1-5 fairly
> well, though there were many small parts here and there that were not clear
> to me. Additionally I had trouble understanding all of the semantics in
> section 6.
Jay McCarthy <j...@cs.byu.edu>
Assistant Professor / Brigham Young University
http://faculty.cs.byu.edu/~jay
"The glory of God is Intelligence" - D&C 93