For instance, one might choose to enhance all occurrences of certain keywords in an HTML file with links to Web sites about these keywords. If such transformation queries span over a flexible structure, considerable expertise is required to solve them in traditional query languages such as SQL. For XML (and its predecessor SGML), the need for expressive transformation languages has been obvious leading to the invention of XSLT (and DSSSL before). XSLT is quite well suited for such transformation tasks, mostly due to (a) its rule-based nature in combination with (b) an inherent structural recursion over the document. In Xcerpt,  the first advantage of XSLT is also present, but we have chosen to give the programmer the flexibility to program different kinds of recursion. The drawback is that in case of transformation queries as above the programmer also needs to specify the structural recursion that is implicit in the case of XSLT.

At http://svn.amachos.com/xcerpt/applications/2005/recursive-transformation/ you find an example of a recursive tree transformation in Xcerpt. The shown transformation is rather simple, it just wraps every element in an additional element tag recursively. I.e., a[ b[] ] is transformed to element[ a[ element[ b[] ] ] ]. Even in this simple example one can already observe the core pattern of tree transformations in Xcerpt:

1. It consists of several rules with common and usually otherwise unique root label of arity two. The first child of the root label represents the original data, the second the transformed data.
   

2. The rules are grounded (and therefore range restricted) by an explicit access to the original data in each rule.
   

3. There are at least two rules: one for the recursive case of an inner node in the original data, one for the case of a leaf node in the original data. Actually it is possible to merge these two rules into one using optional.
   

4. Often (but not in this example) there are also additional rules handling "exceptions", e.g., to omit elements with a certain label from the transformed data.
   

We have just started an activity together with Jakob Henriksson and Uwe Assmann, colleagues from Dresden University, on reuse techologies for Xcerpt. In this work we are investigating a general pattern for recursive transformation as one example. Details are forthcoming until then please take a look in our Subversion repository for the work in progress (to get access please contact Tim Furche).