Compilation of ASF+SDF to C

Our second example of a generated tool is the ASF+SDF compiler itself.

The first goal of the ASF+SDF compiler is to provide a flexible compilation scheme for the incremental compilation of large modular specifications. The second goal is to generate C code which can process large terms in an efficient way regarding both execution time and memory usage. A third goal is the generation of stand-alone tools (generated C code) that can be shipped to IT industry, without having to ship the ASF+SDF Meta-Environment as well (see the example of the Risla flattener at the end of this section). We have used our own tools, techniques and formalism while developing the ASF+SDF compiler. This approach helps achieving the first goal mentioned above, since it makes us the first guinea pigs of our own compiler, The ASF+SDF specification of the compiler is circa 150 pages (1748 rewrite rules, see Table 1).

There are four aspects of ASF+SDF that have to be taken into account during compilation:

$\bullet$

ASF+SDF is a modular algebraic specification formalism. For each module we can define functions and corresponding equations. A complicating factor is the possibility to define a function with some equations in module $M$ and to add extra equations in module $N$ which must of course (in)directly import module $M$ ($M\neq N$).

$\bullet$

The ASF+SDF formalism provides a default mechanism for the equations, this means that during the rewriting of a term $F(t_1, \ldots, t_n)$ with $n\geq~0$ all non-default equations for function $F$ are tried before the default equations. Note that this is a form of prioritized rewriting [44,3].

$\bullet$

ASF+SDF provides list matching (also known as associative matching) this mechanism allows a concise style of specification and involves backtracking. Note that associative matching is NP-complete [4] so optimizations for special cases have to be considered in the compiler.

$\bullet$

ASF+SDF uses innermost rewriting as execution model.