Rippling: Meta-level Guidance for Mathematical Reasoning

The implementation of rippling just sketched, although potentially effective, is rather inefficient. As in Section 1.4, we consider every possible rewrite step and then analyze the result to see if the givens are preserved and if progress has been made. This is inefficient, since we first generate a candidate rewriting result, and afterwards test the embedding of the givens in the result. If we add annotations to terms, it is possible to combine generation and testing. Term rewriting requires matching, and we can integrate the test for skeleton preservation (and progress) into matching by using annotations to mark what must be preserved, what may change, and how things may change.
To investigate this further, we need to address the question of how to represent annotations on terms. This question is open-ended, since the possibilities for hanging semantic information on terms are also open-ended: how we represent annotations depends on what the annotations should represent and how we intend to use them. This topic, and some of the complexities involved, are considered in detail in Chapter 6. For now, let us concentrate on using annotations to differentiate wave-fronts from skeletons, that is to mark what parts of terms should remain invariant during rewriting.
As observed in Section 1.3, a wave-front can be seen as a context , i.e. a term with one, or more, proper subterms deleted. Schematically, an outward-directed wave-front is of the form
, where n > 0 and the ?