Any good recommendations on Term Rewriting Systems?
j
Jimmy Miller
05/23/2022, 2:04 PM
What are you wanting to get out of the system?
g
guitarvydas
05/23/2022, 3:05 PM
I jump to thinking of syntactic solutions:
1. TXL.ca (strongly-typed, functional, parse-based)
2. Ohm-JS (a DSL for pattern-matching based on PEG principles)
And then, there’s
3. Lisp
m
Mariano Guerra
05/23/2022, 3:08 PM
@Jimmy Miller thinking about evaluation as term rewriting and want to read an overview of concepts, sub areas, state of the art, where and how it's used
Mariano Guerra
05/23/2022, 3:09 PM
@guitarvydas I usually am interested in parsing stuff, but today it's not the case 😄
There's also Pure (https://agraef.github.io/pure-lang/), probably the closest to a general-purpose programming language based on term rewriting.
My own Leibniz project (https://science-in-the-digital-era.khinsen.net/#Leibniz) is based on term algebras and term rewriting as well. Its main inspiration is the OBJ family of algebraic specification languages, the latest of which (Maude) has already been mentioned. But the older papers on OBJ, mainly by Joseph Goguen and collaborators, are still worth reading.
Konrad Hinsen
05/24/2022, 8:28 AM
A technique that looks like a nice complement to term rewriting is equality saturation (https://arxiv.org/abs/1012.1802). I am currently playing with it in Leibniz. Instead of reducing a term to a normal form, equality saturation compactly represents all equivalent terms, so that you can pick the one that is "best" for your purposes. Of course this works only for rewriting systems implementing equivalence transformations.