From Vertical to Horizontal Compilation?

The Stratego compiler is a pipeline applying over 40 components (some of which are applied more than once) to transform a sugared and modular source program to an implementation in C. This is an example of vertical compilation in the sense that one stage of compilation is applied to the entire program, before the next stage is applied. The alternative, horizontal compilation, is to apply the entire pipeline, or at least a considerable part of it to a single unit of the program, before considering the next unit. This is of course done in separate compilation, where 'compilation units' are compiled separately from other units. But it can be done to smaller units as long as the transformations are compositional, don't need information from other parts of the program.

After getting rid of nested functions, the next issue on my agenda is to refactor the Stratego compiler to provide a compilation library that offers translation strategies that can be applied to single definitions and that can be composed to form both horizontal and vertical compilers. The first goal of the operation is to improve the performance of the Stratego compiler by eliminating intermediate ATerm files and by increasing the locality of the operations; instead of traversing the entire program for each stage, apply all stages to a single definition, before moving to the next. In the longer term, this refactoring should enable the combination of interpreted, statically compiled, and run-time compiled code. Furthermore, it should facilitate the creation of an open compiler for Stratego that supports languages extension libraries.

The catch of course is in the compositionality of the compilation process. While many stages of the compiler can easily be applied per definition, or are even based on local rewriting, there are several stages that require the whole program. One example, is the stage that combines definitions with the same name into a single definition. A compositional compilation will require a scheme that allows the union of such definitions at link time. Another example, is the 'lifting of dynamic rules', which requires awares of all dynamic rule definition sites in a program to prevent generation of duplicate definition. Turning these operations into 'horizontal' ones may require some new (intermediate) language constructs or meta-data that can be consulted when joining program fragments. Such considerations will no doubt guide the design of a better module system for Stratego. More later.