Rippling: Meta-level Guidance for Mathematical Reasoning

Theorem 4 was proven for an arbitrary reduction order > on annotated terms. In this section, we give a concrete example of a reduction ordering that is useful in practice. We build our ordering in steps, starting with simply annotated terms: those whose wave-fronts have a single wave-hole. We define a measure on such terms and a corresponding order. Afterwards, we generalize this to measures and orders for terms with general (multi-hole) annotations.
As we have seen in Figure 1.3 in Section 1.4, we can view annotated terms as decorated trees where the tree is the skeleton and the wave-fronts are boxes decorating the nodes. See, for example, the first tree in Figure 4.2, which represents
. Our orders are based on assigning measures to annotations in these trees. We define orders by progressively simplifying annotated trees to capture the notion of progress during rippling that we wish to measure.
To begin with, since rippling is skeleton preserving, we need not account for the contents of the skeleton in our orderings. That is, we can abstract away function symbols in the skeleton, for example, mapping each to a variadic function constant * . This gives, for example, the second tree in Figure 4.2.
A further abstraction is to ignore the names of function symbols within wave-fronts and instead assign a numeric weight to each wave-front. For example, we may tally up the values...