Rewriting

From Esolang

This article is a stub, which means that it is not detailed enough and needs to be expanded. Please help us by adding some more information.

Rewriting denotes a form of computation where a data structure is replaced by a modified form of itself, sometimes repeatedly. Prominent forms of rewriting include:

• String rewriting, where the data structure is a string of symbols. Examples are the languages Thue and ///, Post canonical systems, and regular expression substitution as found in several mainstream languages.
• Graph rewriting, where the data structure is a (usually labeled) graph of vertices with edges between them. This is frequently used as an implementation or formal semantics of languages, especially functional ones. Examples: Combinatory logic or Clean.
• Tree rewriting, the frequent special case of graph rewriting where the graph is a tree, at least conceptually. In implementations, identical sub-trees may be identified for efficiency, so that the underlying structure is nevertheless a more general graph (directed, without cycles).