Rippling: Meta-level Guidance for Mathematical Reasoning

In this section we present a very simple realization of rippling that has the simulation and skeleton-preservation properties and suffices to carry out the kinds of proofs considered in Chapters 1 and 2. We shall delay the issue of termination until Section 4.7. Our presentation here is somewhat artificial in that it leads to an implementation of rippling that is too inefficient for practical use. However, it illustrates the main ideas, and is related to other, more realistic, implementations.
In Section 1.3 we informally motivated annotation as a way of marking parts of terms. This marking indicates which parts of a term correspond to the givens (skeletons) and which parts do not (wave-fronts). These markings guide rippling by highlighting the parts of the term that can be transformed; so under this view, adding annotations adds semantic information that guides rippling. In this section we will take a different view where annotations serve not as a guide, but rather as a check. This leads to a s imple implementation based on generate-and-test. Afterwards, we will show how this can be made more efficient, essentially by interleaving the generation with the testing.
Consider the example given in Section 1.4 where we have the given a + b = 42 and the goal (( c + d) + a) + b = ( c + d) + 42. We can apply the rewrite rule for the associativity of plus in three...