Can you recommend full-fledged, actively maintained programming languages—other than Prolog—that support term rewriting as a core feature or are designed primarily around it? I'm looking for a standalone language rather than a library, DSL, compiler extension, or macro system. Pure seems close to what I want, but it has not been updated in several years. The main idea is a formal rewriting system where users define rules that transform values or terms.
2 Answers
Maude is probably the closest match. It is a complete language and environment built around rewriting logic, with algebraic specifications and rules that transform terms. It is much more directly focused on formal term rewriting than ordinary macro systems.
Macros can sometimes be used to transform program syntax, but that is a different use of the word “rewriting.” Macro systems generally rewrite source code during compilation, while term-rewriting languages define rules that operate on values or symbolic terms. For the latter, you’ll want to look at languages based on rewriting logic rather than languages with metaprogramming features.
Right, I’m specifically interested in the formal term-rewriting model: defining rules that transform terms or values, not source-to-source macros.