term-rewriting-rs
A Rust library for representing, parsing, and computing with first-order term rewriting systems.
Usage
To include as a dependency:
[]
= "0.3"
To actually make use of the library:
extern crate term_rewriting;
use ;
Term Rewriting Systems
Term Rewriting Systems (TRS) are a simple formalism from theoretical computer science used to model the behavior and evolution of tree-based structures like natural langauge parse trees or abstract syntax trees.
A TRS is defined as a pair (S, R). S is a set of symbols called the signature and together with a disjoint and countably infinite set of variables, defines the set of all possible trees, or terms, which the system can consider. R is a set of rewrite rules. A rewrite rule is an equation, s = t, and is interpreted as follows: any term matching the pattern described by s can be rewritten according to the pattern described by t. Together S and R define a TRS that describes a system of computation, which can be considered as a sort of programming language. term-rewriting-rs provides a way to describe arbitrary first-order TRSs (i.e. no λ-binding in rules).
Further Reading
- Baader & Nipkow (1999). Term rewriting and all that. Cambridge University Press.
- Bezem, Klop, & de Vrijer (Eds.) (2003). Term Rewriting Systems. Cambridge University Press.
- Rewriting. (2017). Wikipedia.