Term Rewriting

Definitions

1. A computation model in which expressions (terms) are transformed by repeatedly applying pattern-matching rules that replace subterms matching a left-hand side with the corresponding right-hand side, until no more rules apply (normal form). Used in symbolic algebra systems, compiler optimizers, and proof assistants.

   In plain English: A technique where a system repeatedly applies find-and-replace rules to mathematical expressions until they cannot be simplified further.

   Example: "The compiler's peephole optimizer uses term rewriting rules to replace `x * 1` with `x` and `x + 0` with `x` before codegen."

Related Terms

• Lambda Calculus
• Loop Unrolling
• Parser Combinator
• Persistent Data Structure
• Point-Free Style
• TLA+
• Transducer
• Type Constructor