12
$\begingroup$

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:

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).

$\endgroup$
1
  • 1
    $\begingroup$ It shows up a lot in compilers, e.g. the selection dag to instruction dag pass in llvm. $\endgroup$ Commented May 18, 2023 at 21:30

3 Answers 3

7
$\begingroup$

The PURE programming language is based on term rewriting and its Web site refers to some additional use cases.

My own experimental Digital Scientific Notation 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.

$\endgroup$
3
  • 1
    $\begingroup$ 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. Have you? $\endgroup$
    – Ben Kovitz
    Commented May 18, 2023 at 18:33
  • $\begingroup$ 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. $\endgroup$
    – khinsen
    Commented May 19, 2023 at 7:07
  • $\begingroup$ What is the difference between term-rewriting and graph-rewriting or they are same things? $\endgroup$
    – RandomB
    Commented Oct 13, 2023 at 10:15
3
$\begingroup$

Term-rewriting as a model of execution is closely related to call by macro expansion. This gives you languages like TeX which use macro expansion exclusively, as well as the 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 here too. Languages in this paradigm include MarkovJunior, and my own language MJr which is heavily inspired by MarkovJunior.

$\endgroup$
1
  • $\begingroup$ 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? $\endgroup$
    – Ben Kovitz
    Commented May 18, 2023 at 18:44
3
$\begingroup$

I'm not sure it passes as a "little DSL" but very related to compiler implementation is the Stratego language (from the Spoofax framework) that works by term-rewriting.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .