I’ve just finished reading “Xoc, an Extension-Oriented Compiler for
Systems Programming”, by Russ Cox, Tom Bergany, Austin
T. Clements, Frans Kaashoek, and Eddie Kohlery. It’s a description of
an interesting approach to extensible compilation, for C in this case,
that refines a lot of ideas that have been explored previously,
bringing them together in a more compositional style than previous
extensible compilers have managed to achieve.
One of the key themes in the paper is how to control extension
visibility. They describe a couple of approaches they take: one, a
type system used to ensure that extensions to abstract syntax are only
visible to other extensions when those extensions explicitly declare
knowledge of them; and two, an approach from Warth et al.’s
“Statically scoped object adaptation with expanders” paper for
controlling visibility of extensions to core data structures. I wonder
if the latter is used to underpin the former at all.
Regarding the type system approach they take, it’s interesting how it
lets the extension writer provide analyses directly in terms of
extension abstract syntax, rather than forcing translation to a core
language before performing any analysis. We did the latter in
Highwire, and the error messages referred to core-language constructs
which didn’t map well to source-language syntax: the user was forced
to unexpand the macro in their heads to make sense of the output of
the compiler. The paper refers to this problem in section 5.2, where
the authors write “Since macros cannot access compiler internals, they
typically do not even type check their arguments, producing cryptic
errors when invoked incorrectly.”
Their compiler, xoc, is a source-to-source translator at the moment,
which means it’s not integrated with code generation and backend
optimisations and rewrites. It’d be fascinating to build a complete
compiler in this style. It’d also be neat to relate this approach to
extensible semantics. At the moment the extensions look quite
ad-hoc. How could this framework be used, for example, to extend
Scheme or ML, where there’s a real semantics underneath it?
One nice feature of xoc is that it tries to preserve hygiene during
rewriting. I’m curious as to whether it preserves hygiene to the
degree that, say, syntax-case does; their description of the feature
was a bit terse for me to be able to tell. In particular I’m
interested in how it treats keywords, and where “fresh names” come in
to the picture; the paper speaks simply of the code emitter renaming
variables “when two distinct variables share a name”.
They use a GLR parser for converting concrete syntax to abstract
syntax. One of the benefits of this is its ability to deal with
ambiguity, which they exploit in a couple of ways, most ingeniously in
their approach to type inference (if you like) for syntax pattern
variables. I’d like to learn more about how xoc computes the type of a
syntax pattern variable; I wonder if a similar system could be ginned
up for use with OMeta?
The laziness of most of xoc’s attribute computations is rather
nifty. Code generated relatively late in a compilation, when earlier
passes are complete for the rest of the code, can have necessary
information filled in lazily on demand, running just those parts of
the previous analyses that are required.
I’d like to see some of the pattern-matching and reconstruction
features of xoc employed in the context of general purpose
computing. It seems to me that using a GLR parser the way they do
could effectively provide concrete domain-specific syntax for
algebraic data types, not just abstract syntax trees. (The question
arises: when is an AST an ADT? Always?) Being able to cons up syntax
for new types as easily as Haskell and ML cons up the types themselves
seems like a win it’s worth experimenting with. OMeta goes a step in
this direction; I hope to explore it myself sometime soon.
