A _rewrite rule_ is a rule of the form

 lhs -> rhs

where lhs and rhs are term patterns. It declares that any instance of lhs rewrites to the corresponding instance of rhs. The application of a rule to a term succeeds if the term matches (PatternMatching) with the lhs pattern. The result is the instantiation of the rhs pattern.