A program as a list of replacements
A rewriting system works on a piece of text, often called the working string. A program is a list of rules, each of the form “find this pattern, replace it with that.” To run it, you look for a place where a rule applies, replace the matched part, and repeat. When no rule applies, the program halts and the current text is the result.
There are no variables in the usual sense, no explicit sequence of statements and no loops. Repetition happens because applying one rule can create text that a rule matches again.
This idea is old. Variants appear in formal grammars, in Markov algorithms, in Post’s systems of the early twentieth century and in tag systems. Several hobby languages package them as playable programming languages, where a source file is mostly rules and some starting text.
Two tiny examples
The first is a sorting rule. Take a single rule: replace “ba” with “ab”. Start with the text bbaa and always apply the rule at the leftmost match:
- bbaa has “ba” at positions 2 and 3 (counting from 1). Replace it: baba.
- baba has “ba” at the start. Replace it: abba.
- abba has “ba” in the middle-right. Replace it: abab.
- abab has “ba” in the middle. Replace it: aabb.
Now no “ba” remains, so the process halts with aabb. Every a has moved ahead of every b. The rule never mentions sorting, but sorting is what repeated local swaps produce.
The second example is addition in unary, where a number n is written as n copies of 1. To add 3 and 2, write 111+11 and use a single rule that deletes the plus sign. The result is 11111, which is five. The program is trivial because unary notation makes addition into concatenation. It is a good reminder that the choice of representation does a lot of the work.
Rule order and strategy
Real systems must say what happens when more than one rule applies, or one rule applies in several places. Common choices include:
- First rule that matches. Rules are tried in the order listed, and the first one that fits is used. Reordering the list can change behavior.
- Leftmost match. Among several matches, the leftmost wins, as in the example above.
- Any match, chosen freely. The system is nondeterministic: any applicable rule may fire. This is the style of formal grammars and of some esoteric languages, and it connects to the topic of nondeterministic programs.
Markov algorithms use ordered rules and often a way to mark some rules as terminating, meaning that applying them stops the run. Because the strategy is part of the language definition, two systems with the same rules but different strategies can behave differently.
Programming habits that carry over
Programming in a rewriting language feels different from conventional work.
- Marker symbols. Since there is no pointer, you place special symbols in the text to mark a position, such as a cursor that moves along the string as rules fire.
- Phases. A program is often organized as stages: first rules that convert input to an internal form, then rules that do the work, then rules that clean up markers. Order or distinct alphabets keep the stages from interfering.
- Termination is on you. A set of rules can easily loop forever. Whether a given rule set always halts is, in general, undecidable, in line with the halting problem.
How powerful is it
With the right rules, rewriting is capable of universal computation. Markov algorithms are equivalent in power to Turing machines, and tag systems, a very restricted rewriting form, are universal too, which is part of why they interest people looking for tiny universal machines. That result is also an intuition-builder: if a system can append and remove symbols according to a few simple conditions, it may already be enough.
The connection with other models is close. A reduction step in combinator calculus or lambda calculus is also a pattern replacement. A cellular automaton rewrites its whole grid at once. A Turing machine’s step can be phrased as a local rewrite of its tape and head position. Viewed this way, rewriting is a lingua franca for many models.
Where you will meet it in practice
Outside esoteric languages, rewriting appears in compilers, which apply transformation rules to code, in text tools with search-and-replace, and in computer algebra, where simplification rules transform expressions. Esoteric rewriting languages take the same machinery and strip away everything else, which makes it a cheap way to experiment.
If you want to try writing one, an interpreter is short: store the string, scan rules in order, find the first match, replace it, and loop until nothing matches. Add a step limit so runaway rule sets do not hang your program.