Rippling: Meta-level Guidance for Mathematical Reasoning

In this section we shall finish our formalization of rippling by explaining how wave-rules are applied, and showing that the resulting rippling relation has the desired properties.
The reader may wonder whether it is necessary to reinvent the wheel here. Our present formalism represents annotated terms as a subset of terms built from an extended signature. Perhaps we can treat these as conventional terms and manipulate these using conventional rewriting? Unfortunately this is not possible. As we have already observed, annotated terms have a special structure, and one cannot directly carry over conventional definitions and results from rewriting.
We consider below the problems involved as they motivate our formalization.
As an example of the problems that can arise, consider applying the wave-rule associated with the recursive definition of times,
| (4.10) | |
to the annotated term
. Using conventional rewriting, we match the left-hand side of (4.10) with this term, and this generates the substitutions { x/ U} and
. Performing these replacements in the right-hand side yields

Here we have used a darkened wave-front to indicate an improper nesting; the result is perhaps easier to understand if we desugar the syntax, i.e.
| (4.11) | |
The problem is that the (second occurrence of the) subterm wf up ( s( wh( y))) is improperly nested within a wave-front: there are two nested wave-fronts without an intermediate wave-hole. Hence, the result of conventional rewriting is a term with...