Compilation Strategy

The translation of ASF+SDF specifications to C code is mainly influenced by the above four aspects of ASF+SDF. For instance, the fact that ASF+SDF is based on innermost rewriting is a pleasant convenience because of the call-by-value mechanism of C. This enables us to translate the right-hand side of rewrite rules directly to C function calls. The first aspect (modular structure) on the other hand implies extra work when generating C code. For each ASF+SDF function a separate C function will be generated. The corresponding equations are translated to conditional statements in this C function. This means that all equations have to be available before the C function can be generated and thus a reshuffling of equations is needed. One consequence of the distribution of equations over several modules is that modules can not serve as incremental compilation units. We have chosen functions as the incremental compilation unit. The C code generated for the default equations should always be executed after the code that is generated for the ordinary equations. List matching patterns are either transformed into ordinary term matching, if the pattern contains no or exactly one list variable, or the patterns are translated to (nested) while-statements in which all elements of the list are inspected until either a successful match is found or no elements are left. See [48] for a general treatment of this topic.

The global compilation strategy is as follows. An ASF+SDF specification is parsed and for each function with its equations a new ASF+SDF module is generated containing this function and all corresponding equations. We call this flattening of the specification followed by reshuffling of the equations. All constructor functions defined in one module are kept together. These modules are initially used by the compiler for the actual code generation but also when the specification is recompiled to decide for which functions new code should be generated. This phase is entirely independent of the code generation phase. Each new created module is fed to the compiler to generate the actual C code.

The generation of C code is performed in a number of (small) steps. We start with the ASFIX representation of each module, essentially the full parse tree of the module still containing layout, comments, keywords and the like. After reshuffling the ASF+SDF module, it is transformed into another intermediate representation that has been designed to simplify the compilation process. This intermediate formalism $\mu$ASF is a simplified prefix representation of ASF+SDF, see Figure 6 for the $\mu$ASF representation of the Booleans. Given this $\mu$ASF code, a number of transformations is performed to simplify the actual code generation phase and to increase the performance of the resulting code, e.g., list matching patterns containing at most one list variable are transformed into ordinary term matching. From the resulting transformed $\mu$ASF code the C code is generated. The left-hand sides of the $\mu$ASF equations are transformed into a matching automaton which is directly included in the C function. The right-hand sides of the equations are directly translated to function calls. See Figure 7 for an example of generated code from the Booleans of Figure 6.

Figure 6: $\mu$ASF specification of the Booleans.

Figure 7: Generated C code for the and function of the Booleans.

The generated code depends heavily on a general term library (see Section 6.1), which ensures efficient manipulation of terms as well as maximal sharing subterms. The term library provides the basic functionality to construct normal forms, functionality to check the outermost function symbols of terms, and functionality to manipulate the list data structure. Note that the function calls check_sym and make_nf2 in Figure 7 are provided by this library.

Figure: Simplified architecture of the new ASF+SDF Meta-Environment.