Type-Safe, Generative, Binding Macros
0Macros are powerful tools that can facilitate resuse. But, with few exceptions, macros have traditionally been viewed as operations on syntax trees or even on plain strings. This view makes macros seem ad hoc, and is at odds with two desirable features of contemporary programming languages: static typing and static scoping. At a deeper level, there is a need for a simple, usable semantics for macros. We argue that these problems can be addressed by formally viewing macros as multi-stage computation. This view eliminates the need for freshness conditions and tests on variable names, and provides a compositional interpretation that can serve as a basis for designing a sound type system for languages supporting macros, or even for compilation. To illustrate our approach, we develop and present a core language that supports inlining, recursive macros, and the definition of new binding constructs. The latter is subtle, and is the most novel addition in a statically typed setting. The semantics of the core language is given by an interpretation into a statically-typed multi-stage calculus. It is then easy to show that our macros are stage- and type-safe: macro expansion does not depend on runtime evaluation, and both stages do not ``go wrong''. Furthermore, these macros do not interfere with reasoning about the expanded program.