<p>I'm in the process of designing a simple domain-specific language and I think that a term-rewriting system may provide the simplest way to specify and implement it. However, I have only seen a few examples of term-rewriting systems, so I don't have much sense for the possibilities of how you can design a language with one. Aside from the standard examples and topics:</p>
<ul>
<li>symbolic differentiation</li>
<li>computer algebra</li>
<li>the Fibonacci sequence</li>
<li>subexpression optimization in a code generator</li>
<li>theorems about confluence and termination in general</li>
</ul>
<p>which inspired me to look further into term-rewriting systems, I have only seen a few examples of term-rewriting systems designed for some specific, narrow purpose:</p>
<ul>
<li><a href="https://youtu.be/0G76N11_x1w" rel="noreferrer">this talk</a> by Brian Beckman about how to track units of measure via a term-rewriting DSL in Javascript</li>
<li>Mathematica (not exactly a narrow purpose)</li>
<li><a href="http://maude.cs.uiuc.edu/maude1/casestudies/crypto/" rel="noreferrer">checking a cryptographic protocol for flaws</a> with Maude</li>
</ul>
<p>What are some little DSLs that people have made from term-rewriting systems? I am particularly interested in seeing the rewrite rules for a given &quot;language&quot; (not a generic language for making term-rewriting systems).</p>

<term-rewriting-system><domain-specific-languages>
What are some practical examples of domain-specific term-rewriting systems?
CC BY-SA 4.0
2023-05-18T21:30:36.780Z
It shows up a lot in compilers, e.g. the selection dag to instruction dag pass in llvm.
Jon Chesterfield
<p>I'm not sure it passes as a &quot;little DSL&quot; but very related to compiler implementation is the <a href="https://www.spoofax.dev/references/stratego/" rel="nofollow noreferrer">Stratego</a> language (from the Spoofax framework) that works by term-rewriting.</p>

CC BY-SA 4.0
2023-05-26T15:42:03.077Z
2023-05-26T15:42:03.077Z
Alex Chichigin
<p>Term-rewriting as a model of execution is closely related to <a href="https://en.wikipedia.org/wiki/Evaluation_strategy#Call_by_macro_expansion" rel="nofollow noreferrer">call by macro expansion</a>. This gives you languages like <a href="https://en.wikipedia.org/wiki/TeX" rel="nofollow noreferrer">TeX</a> which use macro expansion exclusively, as well as the <a href="https://en.wikipedia.org/wiki/C_preprocessor" rel="nofollow noreferrer">C preprocessor</a> which uses macro expansion within files otherwise written in C.</p>
<p>Term-rewriting is also related to string-rewriting, so it's worth mentioning <a href="https://en.wikipedia.org/wiki/Markov_algorithm" rel="nofollow noreferrer">Markov algorithms</a> here too. Languages in this paradigm include <a href="https://github.com/mxgmn/MarkovJunior" rel="nofollow noreferrer">MarkovJunior</a>, and my own language <a href="https://kaya3.github.io/MJr/" rel="nofollow noreferrer">MJr</a> which is heavily inspired by MarkovJunior.</p>

CC BY-SA 4.0
2023-05-18T04:01:40.437Z
2023-05-18T04:01:40.437Z
kaya3
CC BY-SA 4.0
2023-05-18T18:44:45.577Z
Ah, I'd forgotten that macro expansion is just another form of term-rewriting. M*Jr looks quite interesting—maybe relevant to my project, even. Have you come across any small sets of reduction rules that illustrate the power of term-rewriting as programming technique?
Ben Kovitz
<p>The <a href="https://agraef.github.io/pure-lang/" rel="noreferrer">PURE programming language</a> is based on term rewriting and its Web site refers to some additional use cases.</p>
<p>My own experimental Digital Scientific Notation <a href="https://science-in-the-digital-era.khinsen.net/#Leibniz" rel="noreferrer">Leibniz</a> is also based on term rewriting. It may seem similar to computer algebra at first sight, but has a different focus: being a notation for use in books and papers, rather than a tool for performing computations.</p>
<p>A relevant question in this context is: why use term rewriting rather than a purely functional language? There are many similarities between the two. The main difference is that a term rewriting system permits the complete separation of function declarations from their implementation(s). You can declare that <code>sin</code> is a function from real numbers to real numbers and stop there. If you never provide an implementation, you can still write <code>sin(x)</code> and it will stay <code>sin(x)</code> during rewriting. You can then write code that imports such a declaration and provides different ways to implement the function.</p>

CC BY-SA 4.0
2023-05-18T08:38:40.397Z
2023-05-18T08:38:40.397Z
khinsen
CC BY-SA 4.0
2023-05-18T18:33:27.993Z
Here are some of what attract me to term-rewriting for my project: the simplicity, non-linear pattern matching, keeping the rules tightly constrained, and generating rules programmatically. I'm mainly looking for examples of term-rewriting systems to inform and stimulate my imagination—i.e. sets of rules that define a simple language that does something useful. Beyond those listed in the question, I haven't found any examples to illustrate "This is why term-rewriting is great!" (not even [on the Pure web site](https://agraef.github.io/pure-docs/pure.html#examples). Have you?
Ben Kovitz
CC BY-SA 4.0
2023-05-19T07:07:08.363Z
I don't know such examples either. It's perhaps not easy to demonstrate the advantages of term rewriting in a single example.

For my own project, I chose term rewriting because standard programming languages didn't provide the modularity and notational flexiblity I needed. In my digital scientific notation, declarations (for the term algebra and its rules) are small units that can be written in any order. That is very important for inserting them into the flow of a narrative, much like traditional mathematics notation.
khinsen
CC BY-SA 4.0
2023-10-13T10:15:55.390Z
What is the difference between term-rewriting and graph-rewriting or they are same things?
RandomB
# What are some practical examples of domain-specific term-rewriting systems?
Posted by: username_0 on 2023-05-17
I'm in the process of designing a simple domain-specific language and I think that a term-rewriting system may provide the simplest way to specify and implement it. However, I have only seen a few examples of term-rewriting systems, so I don't have much sense for the possibilities of how you can design a language with one. Aside from the standard examples and topics:

* symbolic differentiation
* computer algebra
* the Fibonacci sequence
* subexpression optimization in a code generator
* theorems about confluence and termination in general

which inspired me to look further into term-rewriting systems, I have only seen a few examples of term-rewriting systems designed for some specific, narrow purpose:

* [this talk](https://youtu.be/0G76N11_x1w) by Brian Beckman about how to track units of measure via a term-rewriting DSL in Javascript
* Mathematica (not exactly a narrow purpose)
* [checking a cryptographic protocol for flaws](http://maude.cs.uiuc.edu/maude1/casestudies/crypto/) with Maude

What are some little DSLs that people have made from term-rewriting systems? I am particularly interested in seeing the rewrite rules for a given "language" (not a generic language for making term-rewriting systems).
**Tags:** term-rewriting-system domain-specific-languages
> **Comments:**
> **username_1**: It shows up a lot in compilers, e.g. the selection dag to instruction dag pass in llvm.  
---
## 3 answers
### Answer by username_4 on 2023-05-18. Score: 7
The [PURE programming language](https://agraef.github.io/pure-lang/) is based on term rewriting and its Web site refers to some additional use cases.

My own experimental Digital Scientific Notation [Leibniz](https://science-in-the-digital-era.khinsen.net/#Leibniz) is also based on term rewriting. It may seem similar to computer algebra at first sight, but has a different focus: being a notation for use in books and papers, rather than a tool for performing computations.

A relevant question in this context is: why use term rewriting rather than a purely functional language? There are many similarities between the two. The main difference is that a term rewriting system permits the complete separation of function declarations from their implementation(s). You can declare that `sin` is a function from real numbers to real numbers and stop there. If you never provide an implementation, you can still write `sin(x)` and it will stay `sin(x)` during rewriting. You can then write code that imports such a declaration and provides different ways to implement the function.
> **Comments:**
> **username_0** (2023-05-18): Here are some of what attract me to term-rewriting for my project: the simplicity, non-linear pattern matching, keeping the rules tightly constrained, and generating rules programmatically. I'm mainly looking for examples of term-rewriting systems to inform and stimulate my imagination—i.e. sets of rules that define a simple language that does something useful. Beyond those listed in the question, I haven't found any examples to illustrate "This is why term-rewriting is great!" (not even [on the Pure web site](https://agraef.github.io/pure-docs/pure.html#examples). Have you?  
> **username_4** (2023-05-19): I don't know such examples either. It's perhaps not easy to demonstrate the advantages of term rewriting in a single example.

For my own project, I chose term rewriting because standard programming languages didn't provide the modularity and notational flexiblity I needed. In my digital scientific notation, declarations (for the term algebra and its rules) are small units that can be written in any order. That is very important for inserting them into the flow of a narrative, much like traditional mathematics notation.  
> **username_5** (2023-10-13): What is the difference between term-rewriting and graph-rewriting or they are same things?  
---
### Answer by username_2 on 2023-05-26. Score: 3
I'm not sure it passes as a "little DSL" but very related to compiler implementation is the [Stratego](https://www.spoofax.dev/references/stratego/) language (from the Spoofax framework) that works by term-rewriting.
---
### Answer by username_3 on 2023-05-18. Score: 3
Term-rewriting as a model of execution is closely related to [call by macro expansion](https://en.wikipedia.org/wiki/Evaluation_strategy#Call_by_macro_expansion). This gives you languages like [TeX](https://en.wikipedia.org/wiki/TeX) which use macro expansion exclusively, as well as the [C preprocessor](https://en.wikipedia.org/wiki/C_preprocessor) which uses macro expansion within files otherwise written in C.

Term-rewriting is also related to string-rewriting, so it's worth mentioning [Markov algorithms](https://en.wikipedia.org/wiki/Markov_algorithm) here too. Languages in this paradigm include [MarkovJunior](https://github.com/mxgmn/MarkovJunior), and my own language [MJr](https://kaya3.github.io/MJr/) which is heavily inspired by MarkovJunior.
> **Comments:**
> **username_0** (2023-05-18): Ah, I'd forgotten that macro expansion is just another form of term-rewriting. M*Jr looks quite interesting—maybe relevant to my project, even. Have you come across any small sets of reduction rules that illustrate the power of term-rewriting as programming technique?  
---
