Description
OPTIMIX is a specification language for the specification of
optimizers based on graph rewriting developed by
UweAssman at the University of Karlsruhe [3]. A specification consists of a set of modules that each define a set of rewrite systems that consist of a list of graph rewrite rules. A rule matches a subgraph of the graph
and adds or deletes edges and nodes. In order to avoid
non-termination and non-confluence a transformation is defined in
several separate rewrite systems that are then consecutively applied.
Only a restricted set of rewrite systems is supported that can be
divided in two flavours. (1) Edge Addition Rewrite Systems (EARS)
consist only of rules that add edges. These are used for program
analysis; extra edges express relations between program nodes, e.g.,
is a subexpression of. (2) General Graph Rewrite Systems are used to
express transformations. However, only those systems are supported
that can be proven to be terminating according to a termination check.
This boils down to systems that do not create new redexes after
transformation steps.
In effect, an
OPTIMIX rewrite system specification appears to be an
abstraction of a certain class of while-programs that perform a loop
over the program tree/graph finding all applications of the rules and
then applying the transformations once.
A specification is translated to a C program in which each rewrite
system corresponds to a C function that performs a
transformation. These C functions have to be invoked from a C program
that implements the rest of the compiler. Data types are declared with
a data definition language (
CoSy-fSDL or AST from the Cocktail
package).
The specification method is related to Datalog.
OPTIMIX is an imperative specification language in the sense that
there is one tree/graph that is manipulated. Other paradigms are
usually functional, i.e., compute a new tree from an old one.
References
See Also
Other
TransformationSystems