The Compiler Forest

TitleThe Compiler Forest
Publication TypeConference Paper
Year of Publication2012
AuthorsGalenson, J., Budiu M., & Plotkin G.

Compilers targeting complex execution environments, such as
computer clusters composed of machines with multi-core CPUs
and GPUs, are difficult to write. To address this problem, we introduce
partial compilers, which can pass subtasks to child compilers
and combine the various plans they create, as a generalization of
traditional compilers. We define a set of high-level polymorphic
operations that manipulate partial compilers as first-class values.
These mechanisms provide a software architecture for modular
compiler construction, which allows the building of a forest of
compilers. We explore the mathematical structure of partial compilers
and its ties to theorem proving and category theory. Motivated
by the problem of distributed computation, we demonstrate
the software engineering advantages of our approach by building
some complex compilers. We describe the complete implementation
of a large-scale query-processing system written as a modular
combination of many simple partial compilers.

The Compiler Forest.pdf715.88 KB