Rippling: Meta-level Guidance for Mathematical Reasoning

We have completed our formal account of rippling and termination orderings for annotated terms. We now turn to the more practical problem of mechanizing rippling. In particular, given an ordering, how do we recognize wave-rules and apply them? Below we describe an implementation of the above formalization of rippling that is part of the Edinburgh
system. To give the reader a feel for this, and the issues involved, we sketch briefly a couple of the core routines.
Much of the work in implementing rippling concerns turning unannotated rewrite rules into wave-rules; as noted in Section 4.5 we call this wave-rule parsing. A wave-rule parser takes a set of unannotated rewrite rules and returns a corresponding set of wave-rules. By definition, the wave-rules are annotated copies of the original rules that are skeleton preserving and measure decreasing. We can achieve these requirements separately. An annotation phase first annotates l and r with unoriented wave-fronts (i.e., making no commitment to whether the direction is up or dn) in a skeleton-preserving way. The annotation algorithm works by calculating the maximal skeletons that can be embedded in both sides of the wave-rule, and encloses the remaining expressions in wave-fronts. Afterwards, an orientation phase augments each wave-front with a direction so that l
r. The result is a wave-rule or, more accurately, a set of wave-rules, since there are choice-points in both phases.
As an example, consider parsing a rewrite rule such as