Rippling: Meta-level Guidance for Mathematical Reasoning

4.6: Rippling using wave-rules

4.6 Rippling using wave-rules

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.

4.6.1 Why ordinary rewriting is not enough

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...

UNLIMITED FREE
ACCESS
TO THE WORLD'S BEST IDEAS

SUBMIT
Already a GlobalSpec user? Log in.

This is embarrasing...

An error occurred while processing the form. Please try again in a few minutes.

Customize Your GlobalSpec Experience

Category: DC-AC Inverters
Finish!
Privacy Policy

This is embarrasing...

An error occurred while processing the form. Please try again in a few minutes.