The Semantics of Syntax Applying Denotational Semantics to Hygienic Macro Systems
Neelakantan R. Krishnaswami · 2015
Typically, when semanticists hear the words “Scheme” or “Lisp”, what comes to mind is “untyped lambda calculus plus higher-order state and first-class control”. Given our typical concerns, this seems to be the essence of Scheme: it is a dynamically typed applied lambda calculus that supports mutable data and exposes first-class continuations to the programmer. These features expose a complete computational substrate to programmers so elegant that it can even be characterized mathematically; every monadicallyrepresentable effect can be implemented with state and firstclass control [4]. However, these days even mundane languages like Java support higher-order functions and state. So from the point of view of a working programmer, the most distinctive feature of Scheme is something quite different – its support for macros. The intuitive explanation is that a macro is a way of defining rewrites on abstract syntax trees. However, Scheme programmers typically pair this explanation with the advice that getting macros right is rather subtle, and that one should avoid macros unless the usual abstraction mechanisms of the language have been tried first and have failed. Because of this subtlety, macros remain a distinctive feature of the Lisp family, and have so far failed to make the jump to other functional languages; neither ML nor Haskell have formal macro systems. (GHC Haskell offers programmatic access to the AST via Template Haskell, though many users seemingly hate this feature. Ocaml used to have a macro system — CamlP4 — but this macro system has actually been removed from recent versions of the language!) This, despite the fact that most functional languages have features, such as pattern matching and do-notation, which have compositional, local desugarings that would lend themselves to being defined and implemented as macros. This gap arises for surprising and deep reasons, which the description of a macro as an AST rewriting glosses over. Without a deeper understanding of these reasons, the technology developed for Scheme does not immediately transfer to typed languages, because it is not obvious how to report errors in terms of the the source rather than the expansion.