Background

Term rewriting is omnipresent in computer science. It has been used to formalize the notion of computability, to study computational procedures, to implement functional languages, to analyze and implement abstract data types, to decide word problems, to proof theorems, and so on [40]. In the early eighties an ESPRIT project was started to support the generation of interactive programming environments from language specifications using term rewriting as one of the basic implementation paradigms [29]. This research has resulted in the design of the ASF+SDF formalism and its support environment, the ASF+SDF Meta-Environment. ASF stands for Algebraic Specification Formalism [6]. It is an implementation of conditional term rewriting [36,8] possibly containing negative premises [37,45,46,26]. It also uses a form of prioritized rewriting [3,44]: there are default rewrite rules that apply if other rewrite rules do not match. SDF stands for Syntax Definition Formalism [28]. In fact, SDF is the part to conveniently define the signature $\Sigma$ of a term rewriting system and in ASF this signature is used to specify the rewrite rules $R$. Terms are many-sorted and varyadic constructor functions are available for defining lists.

The formalism ASF+SDF and the ASF+SDF Meta-Environment have been described in a variety of papers and books [5,38,21]. In the context of this paper, the most significant properties of the ASF+SDF technology are:

$\bullet$

ASF+SDF is based on algebraic specifications and term rewriting is used for its implementation. Specifications consist of modules with conditional equations.

$\bullet$

Concrete syntax and abstract syntax are closely integrated: there is a standard mapping between the textual (concrete) representation of terms and their (abstract) representation as trees.

$\bullet$

The definition of concrete syntax is based on unrestricted context-free grammars, thus permitting modular composition of grammars. This is possible because of the parsing technology we are using, namely Generalized LR parsing [42,55,49,56].

$\bullet$

The ASF+SDF Meta-Environment is highly incremental and supports the rapid development and prototyping of specifications.

$\bullet$

The data exchange format between components is based on terms. The format is called ATF (Annotated Term Format) [12]. Its implementation is called ATerms [11]. The data exchange between components of the ASF+SDF Meta-Environment is called AsFix.

The ASF+SDF view on the world is grammar-centric and can be characterized by the slogan

Every expression has a grammar, so it can be represented as a term.

All languages are treated equal, be it the language of truth values or the programming language COBOL. Simple Boolean expressions and COBOL programs are all treated as terms. The major surprise is that this paradigm scales up so well to large industrial applications, like:

$\bullet$

analysis and transformation tools for the renovation of COBOL programs [16,17,15,51,54,22,23];

$\bullet$

tools for the migration between COBOL dialects [15];

$\bullet$

reengineering tools for a proprietary (telecommunications) language [52];

$\bullet$

design of and tool support for a new, domain-specific language, called Risla, for financial applications [2,20];

$\bullet$

a code generator for the UML design notation;

$\bullet$

tool support for a specification language for railway safety [27,25].

An overview of industrial applications of the ASF+SDF Meta-Environment can be found in [9]. Other large, non-commercial, applications of the ASF+SDF technology are:

$\bullet$

specification, prototyping and final implementation of various components of the ASF+SDF Meta-Environment itself, such as, a compiler [14], parser generator [56], and pretty printer generator [19];

$\bullet$

specification and prototyping of the TOOLBUS coordination architecture [7];

$\bullet$

tool support for action semantics [24];

$\bullet$

tool support for the CASL formalism [10].

In Section 2 we briefly discuss issues that have to be taken into account when cooperating with IT industry. Next, we sketch the global approach we use for the automatic generation of tools and applications (Section 3). Then, we highlight two major applications: the construction of analysis and transformation tools for COBOL (Section 4) and the ASF+SDF compiler, which is written in ASF+SDF (Section 5). Based on these experiences we suggest in Section 6 the study of topics that could further advance the use of term rewriting in industrial applications: persistent term databases, generalized LR parsing versus parallel term rewriting, and coordination languages versus strategy languages. It will turn out that we have an ``alien'' view on research in term rewriting: properties like confluence and termination are of very limited use when selling term rewriting to industry.