Chapter Generic Traversal Strategies

Introduction

In the previous chapters we saw how strategies can be used to control transformations and how rules can be broken down into the primitive actions match, build and scope. Together, these combinators allow us to define any transformation. However, the definition of traversals using congruence operators is specific for a data-type. Although a one step traversal can be factored out of the definition of full tree traversals, there are no generic definitions of traversals. This entails, that traversals should be defined for each data type.

In this chapter we introduce combinators for generic term traversal, that support data type independent definition of traversals, which can be reused for any data type. Furthermore, the strategies that we have inspected so far are geared to transform terms while preserving types, i.e., rephrasings according to the taxonomy in Chapter Program Transformation. There is also a class of transformations, in which terms are translated to a different type. In this chapter we introduce a generic term construction and decomposition operator, which allows us to define generic translation or type unifying strategies.

Preprint

• Chapter-10.pdf
• Chapter-10.ps

Remarks

Very draft