Domain-Specific Languages (DSL) are programming languages specialized to a particular application domain. A possible framework for constructing compiled DSLs can comprise creating a DSL by an author, implementing the DSL and using the DSL by an application developer to obtain an application program. This allows consumers of DSLs such as application developers to program at a very high level, while producing optimized code.
To produce and optimize compiled programs, program transformation can be used, which takes an abstract syntax tree (AST) of the program as input and produces another AST. A rewrite rule is a specific kind of such transformation, which describes a pattern of tree fragments and transforms every fragment which matches this pattern into an output fragment, keeping everything else in place. The rewrite rules are important for program optimization, and some DSLs may include up to tens or hundreds of rules.
However, the known systems for describing rewrite rules do not support programs creating new rules or transforming existing rules. Moreover, often separate languages are used for describing the language being developed and the rewrite rules. Therefore, it is desirable to enable the DSL or application developer to easily add or change rewrite rules.