Any good recommendations on Term Rewriting Systems...
# thinking-together
m
Any good recommendations on Term Rewriting Systems?
j
What are you wanting to get out of the system?
g
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
@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
@guitarvydas I usually am interested in parsing stuff, but today it's not the case 😄
j
Ah, so interested in theory rather than a particular system. “Term Rewriting and All That” is the big canonical text. Very theory heavy. https://kframework.org/ has quite a few publications on the latest work going on http://fmse.info.uaic.ro/publications/ PLTRedex is also a pretty good resource if you are looking for a system to define languages in. Check out Maude and Stratego and mathematica Of course I have my own stuff I’ve written in this area (not research) so I can’t help but link to it https://jimmyhmiller.github.io/meander-rewriting https://jimmyhmiller.github.io/building-meander-in-meander

https://www.youtube.com/watch?v=9fhnJpCgtUw

I have friend steeped in this stuff. So if you want something more specific, let me know.
👀 1
m
Great list of resources, thanks!
d
👀 1
k
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.
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.