Rippling: Meta-level Guidance for Mathematical Reasoning

4.4: Term Annotation

4.4 Term Annotation

4.4.1 The role of annotation

The implementation of rippling just sketched, although potentially effective, is rather inefficient. As in Section 1.4, we consider every possible rewrite step and then analyze the result to see if the givens are preserved and if progress has been made. This is inefficient, since we first generate a candidate rewriting result, and afterwards test the embedding of the givens in the result. If we add annotations to terms, it is possible to combine generation and testing. Term rewriting requires matching, and we can integrate the test for skeleton preservation (and progress) into matching by using annotations to mark what must be preserved, what may change, and how things may change.

To investigate this further, we need to address the question of how to represent annotations on terms. This question is open-ended, since the possibilities for hanging semantic information on terms are also open-ended: how we represent annotations depends on what the annotations should represent and how we intend to use them. This topic, and some of the complexities involved, are considered in detail in Chapter 6. For now, let us concentrate on using annotations to differentiate wave-fronts from skeletons, that is to mark what parts of terms should remain invariant during rewriting.

As observed in Section 1.3, a wave-front can be seen as a context , i.e. a term with one, or more, proper subterms deleted. Schematically, an outward-directed wave-front is of the form , where n > 0 and the ?

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: Color Meters and Appearance Instruments
Finish!
Privacy Policy

This is embarrasing...

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