Abstract
One of the directions of algebraic programming is the use of rewriting rules technique. This direction formalizes the transformational aspects of programming, which allows us to describe transformations of some formal objects and research properties of such transformations. The rewriting rules technique is both a powerful formal tool for transformation of formal systems and a practical tool for programming that allows implementing transformations of complex objects. In this chapter, the main definitions associated with algebraic programming based on rewriting rules are given, term rewriting systems are overviewed, and applications of these systems for processing and transformation of programs are considered.
TopThe Main Features Of Rewriting: Definitions And Examples
Many formal systems using rewriting technique have been proposed (Baader & Nipkow, 1999). Further, several such systems are considered demonstrating various rewriting aspects.
Key Terms in this Chapter
Rewriting Rules System: A software system which contains a language for description of rules, a program for their application, and also, probably, sets of ready-made rules or rewriting strategies.
Rewriting Strategy: A function selecting a unique result term from the set of results of application of a rewriting rule system to a term.
Abstract Rewriting System (ARS): A set of objects with a binary relation called the rewrite relation defined on it.
Optimization: The transformation which preserves a program behavior (a result for a given input data) and increases program performance, for example, in regard to execution time.
Term Rewriting Rule: A pair of terms (left-hand side and right-hand side) divided by an arrow. The left-hand side is replaced by the right-hand side.
Rewriting Rules Technique: A formal tool for transformation of formal systems based on term rewriting and a practical tool for programming, which allows implementing transformations of complex objects. Rewriting covers a wide range of methods of replacing sub-terms of a formula with other terms.
TermWare: An open-source implementation of rewriting rules engine written in Java. It provides a language for describing rewriting rules that operate on data structures called terms and also a rule engine that interprets rules to transform terms.