Growing a Syntax
Eric Allen, Ryan Culpepper, Janus Dam Nielsen, Jon
Rafkind and Sukyoung Ryu
Abstract
In this paper we present a macro system for the Fortress programming
language. Fortress is a new programming language designed for
scientific and high-performance computing. Features include: implicit
parallelism, transactions, and concrete syntax that emulates
mathematical notation.
Fortress is intended to grow over time to accommodate the changing
needs of its users. Our goal is to design and implement a macro system
that allows for such growth. The main challenges are (1) to support
extensions to a core syntax rich enough to emulate mathematical
notation, (2) to support combinations of extensions from separately
compiled macros, and (3) to allow new syntax that it is
indistinguishable from core language constructs. To emulate
mathematical notation, Fortress syntax is specified as a parsing
expression grammar (PEG), supporting unlimited lookahead. Macro
definitions must be checked for well-formedness before they are
expanded and macro uses must be well encapsulated (hygienic,
composable, respecting referential transparency). Use sites must be
parsed along with the rest of the program and expanded directly into
abstract syntax trees. Syntax errors at use sites of a macro must refer
to the unexpanded program at use sites, never to definition sites.
Moreover, to allow for many common and important uses of macros,
mutually recursive definitions should be supported.
Our design meets these challenges. The result is a flexible system that
allows us not only to support new language extensions, but also to move
many constructs of the core language into libraries. New grammar
productions are tightly integrated with the Fortress parser, and use
sites expand into core abstract syntax trees. Our implementation is
integrated into the open-source Fortress reference interpreter. To our
knowledge, ours is the first implementation of a modular hygienic macro
system based on parsing expression grammars.
Presented at FOOL'09; Saturday, 24 January
2009, Savannah, Georgia, USA.