Computational Stylesheets

Computational stylesheets are the most complex of the four design patterns. They arise when there is a need to generate nodes in the result tree that do not correspond directly to nodes in the source tree. With XSLT 1.0, this happened most commonly when dealing with structure in the source document that is not explicit in its markup. For example:

• A text field in the source might consist of a comma-separated list of items that is to be displayed as a bulleted list in the output.

• There might be a need to generate <section> elements in the output where a section is not explicit in the source, but is defined as comprising an <h1> element and all its following sibling elements up to the next <h1> element.

With XSLT 2.0, many of these problems can be tackled using new facilities built in to the language: the first of these examples can be handled using <xsl:analyze-string> , and the second using <xsl:for-each- group > . However, sooner or later you will exhaust the capabilities of these constructs, and need to write a stylesheet in the form of a general-purpose program. Examples of such problems include the following:

• Starting a new page (or other unit) when a running total has reached some threshold value

• Analyzing graph-structured data, for example to see if it contains any cycles

• Creating graphical representations of numeric data using the vector graphics standard SVG as the output format

When you write computational stylesheets you invariably run up against the fact that XSLT does not have an assignment statement, and that it is therefore not possible to write loops in the way you are probably used to in other languages. So you need to understand some of the concepts of functional programming, which the following section tries to explain.

Programming without Assignment Statements

Back in 1968, the renowned computer scientist Edsger Dijkstra published a paper under the title GoTo Statement Considered Harmful . His thesis, suggesting that programs should be written without goto statements, shattered the world as most programmers saw it. Until then they had been familiar with early dialects of Fortran and Cobol in which the vast majority of decisions in a program were implemented by using a construct that mapped directly to the conditional jump instruction in the hardware: ‰ if condition goto label ‰« . Even the design notation of the day, the ubiquitous flowchart drawn in pencil using a clear plastic template, represented control flow in this way.

Dijkstra argued that structured programs, written using if -then-else and while-do constructs instead of goto statements, were far less likely to contain bugs and were far more readable and therefore maintainable . The ideas were fiercely controversial at the time, especially among practicing programmers, and for years afterwards the opponents of the idea would challenge the structured programming enthusiasts with arguments of the form, "OK, so how do you do this without a goto statement?"

Today, however, the battle is won, and the goto statement has been consigned to history. Modern languages like Java don't provide a goto statement, and we no longer miss it.

But for just as long, there has been another group of enthusiasts telling us that assignment statements are considered harmful. Unlike Dijkstra, these evangelists have yet to convince a skeptical world that they are right, though there has always been a significant band of disciples who have seen the benefits of the approach.

This style of coding, without assignment statements, is called Functional Programming. The earliest and most famous functional programming language was Lisp (sometimes ridiculed as "Lots of Irritating Superfluous Parentheses"), while more modern examples include ML, Haskell, and Scheme. (See, for example, Simply Scheme: Introducing Computer Science by Brian Harvey and Matthew Wright, MIT Press, 1999.)

XSLT is a language without assignment statements, and although its syntax is very different from these languages, its philosophy is based on the concepts of functional programming. It is not a full-fledged functional programming language because you cannot manipulate functions in the same way as data; but in most other respects, it fits into this category of language. If you want to do anything complicated, you must get used to programming without assignment statements. At first, it probably won't be easy: just as early Fortran and Cobol programmers instinctively reached for the goto statement as the solution to every problem, if your background is in languages like C or Visual Basic or even Java you will just as naturally cherish the assignment statement as your favorite all-purpose tool.

So what's wrong with assignment statements, and why aren't they available in XSLT?

The crux of the argument is that it's the assignment statements that impose a particular order of execution on a program. Without assignment statements, we can do things in any order, because the result of one statement can no longer depend on what state the system was left in by the previous statement. Just as the goto statement mirrors the "jump" instruction in the hardware, so the assignment statement mirrors the "store" instruction, and the reason we have assignment statements in our programming languages today is that they were designed to take advantage of sequential von Neumann computers with jump and store instructions. If we want to free ourselves from sequential thinking modeled on sequential hardware architecture, we should find a way of describing what effect we want to achieve, rather than saying what sequence of steps the machine should take in order to achieve it.

The idea of a functional program is to describe the output as a function of the input. XSLT is a transformation language; it is designed to transform an input document into an output document. So, we can regard a stylesheet as a function that defines this transformation: a stylesheet is a function O = S (I) where I is the input document, S is the stylesheet, and O is the output document. Recall the statement made by James Clark at the 1995 Paris workshop, which I quoted in Chapter 1, page 28:

A DSSSL stylesheet very precisely describes a function from SGML to a flow object tree.

This concept clearly remained a key part of the XSLT vision throughout the development of the language. (And, indeed, the flow objects of DSSSL eventually became the Formatting Objects of XSL-FO.)

We're using the word function here in something close to its mathematical sense. Languages like Fortran and Visual Basic have borrowed the word to mean a subroutine that returns a result, but the mathematical concept of a function is not that of an algorithm or sequence of steps to be performed, rather it is a statement of a relationship. The square-root function defines a relationship between 3 and 9, namely 3=sqrt (9) . The essence of a function is that it is a fixed, constant, reliable relationship, and evaluating it doesn't change the world. When you ask me "what's the square root of 9 if you work it out?" I can honestly reply "exactly the same as if I don't." I can say this because square root is a pure function, it gives the same answer whoever calls it and however often they call it, and calling it once doesn't change the answer it gives next time; in fact, it doesn't change anything.

The nice property of pure functions is that they can be called any number of times, in any order, and produce the same result every time. If I want to calculate the square root of every integer between zero and a thousand, it doesn't matter whether I start at zero and work up, or start at a thousand and work down, or whether I buy a thousand and one computers and do them all at the same time; I know I will get the same answer. Pure functions have no side effects.

An assignment statement isn't like that. The effect of an assignment statement "if you work it out" is not the same as if you don't. When you write ‰ x=x+1; ‰« (a construct, incidentally, which most of us found completely absurd when we were first introduced to programming), the effect depends very much on how often the statement is executed. When you write several assignment statements, for example

 temp = x; x = y; y = temp; 

then the effect depends on executing them in the right order.

This means, of course, that a pure function can't update external variables . As soon as we allow assignment, we become dependent on doing things in sequence, one step at a time in the right order.

Don't object-oriented languages achieve the same thing, by preventing one object updating data held in another? No, because although they prevent direct writing to private data, they allow the same effect to be achieved by get() and set() methods . An update to a variable achieved indirectly through a defined interface creates exactly the same dependence on sequence of execution as an update done directly with an assignment statement. A pure function must have no side effects; its only output is the result it returns.

The main reason that functional languages are considered ideal for a stylesheet language (or a tree transformation language, if you prefer) is not so much the ability to do things in parallel or in any order, but rather the ability to do them incrementally. We want to get away from static pages; if you're showing a map of the traffic congestion hotspots in your area, then when the data for a particular road junction changes, you want the map updated in real time, and it should be possible to do this without recalculating and redrawing the whole map. This is only possible if there's a direct relationship-a function-between what's shown at a particular place on the map display and a particular data item in the underlying database. So if we can decompose our top-level stylesheet function, O = S ( I ) , into a set of smaller, independent functions, each relating one piece of the output to one piece of the input, then we have the potential to do this on-the-fly updating.

Another benefit of this incremental approach is that when a large page of XML is downloaded from the network, the browser can start displaying parts of the output as soon as the relevant parts of the input are available. Some XSLT processors already do this: Xalan, for example, runs the transformation in parallel with the XML parsing process. If the stylesheet were a conventional program with side effects, this wouldn't be possible, because the last bit of input to arrive could change everything.

The actual "functions" in XSLT take several forms. The most obvious functions in XSLT 2.0 are the stylesheet functions written using an <xsl:function> element. However, templates (both named templates and template rules) also act as functions: the only real difference between an <xsl:function> and an <xsl:template> is that the former is called from an XPath expression, and the latter from an XSLT instruction.

XSLT template rules and stylesheet functions act as small, independent functions relating one piece of the output to one piece of the input. Functions and template rules in XSLT have no side effects; their output is a pure function of their input. Stylesheet functions follow this model more strictly than templates, because the only input they have is the values of the parameters to the function (plus global variables and the results of functions such as document() , which access the context, which cannot vary from one function call to another within a given transformation). Templates are less pure, because they also take the current position in the input document, and other context information, as implicit input parameters. But the principle is the same.

Technically, functions in XSLT are not completely pure, because they can create nodes with distinct identity. If a function creates and returns a new node <a/> , then calling the function twice with the same arguments produces two elements with the same content but with different identity, which means that the expression ‰ f() is f() ‰« will return false . Fortunately, it's not too difficult for an optimizer to detect when a function has this characteristic.

It doesn't matter in what order the template rules are executed, so long as we assemble their individual outputs together in the right way to form the result tree. If part of the input changes, then we need to re-evaluate only those template rules that depend on that part of the input, slotting their outputs into the appropriate place in the output tree. In practice, of course, it's not as easy as that, and no one has yet implemented an incremental stylesheet processor that works like this. However, many XSLT processors do take advantage of the freedom to change the order of evaluation, by using a technique known as lazy evaluation.

Lazy evaluation means, in general, that expressions are not evaluated until their values are actually needed. This gives two benefits: firstly, it avoids allocating memory to hold the results. (Although modern machines have vast amounts of memory, processing large XSLT documents can be very memory intensive , and the overhead of allocating and de-allocating memory dynamically accounts for a lot of the cost of XSLT processing.) Secondly, lazy evaluation sometimes means that an expression doesn't need to be evaluated at all. To take a simple example, in a function call such as ‰ string-join ($sequence, $separator) ‰« , there is no need to evaluate the second argument unless the first argument is a sequence containing two or more items.

Meanwhile, while the researchers and product developers work out how to optimize XSLT execution using incremental and parallel evaluation, you as a user are left with a different problem: learning how to program without assignment statements. After this rather lengthy digression into computer science theory, in the next section I shall get my feet back on the ground and show you some examples of how to do this.

However, first let's try and separate this from another programming challenge that arose with XSLT 1.0, namely the limited number of data types available. This restriction has been greatly eased in XSLT 2.0, now that arbitrary sequences are available in the data model. In terms of language design principles, the lack of assignment statements and the absence of a rich type system are quite separate matters. With XSLT 1.0, you often hit the two issues together:

• The only effect a template could have was via the output it produced (because of the ban on side effects).

• And the only output it could produce, if you wanted to process it further, was a character string (because of the limited range of data types available).

However, in XSLT 2.0 it becomes possible for a template to construct an arbitrary sequence or a tree, which can be used as input to further stages of processing. These data structures are about as versatile as you can get, so the second problem is really a thing of the past. With XSLT 1.0, you could often get around the problem by representing complex data in the form of character strings (or by using the exslt:node-set() function available in many processors), but the introduction of temporary trees and sequences in XSLT 2.0 greatly reduces the contortions that are necessary to implement complex algorithms in your transformations.

So Why are They Called Variables?

XSLT, as we have seen, does have variables that can hold values. You can initialize a variable to a value, but what you can't do is change the value of an existing variable once it has been initialized .

People sometimes ask, why call it a variable if you can't vary it? The answer lies in the traditional mathematical use of the word variable : a variable is a symbol that can be used to denote different values on different occasions. When I say "area = length — breadth," then area, length, and breadth are names or symbols used to denote values: here, they denote properties of a rectangle. They are variables because these values are different every time 1 apply the formula, not because a given rectangle is changing size as I watch.

Cheating

Just occasionally, you may feel that programming without assignment statements is too mind-boggling, or too slow. In these cases you may be tempted to cheat.

Most XSLT processors actually allow user-written extension functions to have side effects, and some even describe in their documentation how to exploit this feature to implement a substitute for updateable variables.

The Saxon product goes one step further, and provides an extension element <saxon:assign> that allows you to update a variable directly.

Since I've just spent several pages explaining why side-effect-free languages are a "good thing," you might find it surprising that I should put a feature in my own product that destroys the principle at a stroke. I have several excuses:

1. At the time I did it, XSLT was far less advanced as a functional programming language than it finally became.

2. I thought that although side-effect-free programming is a good thing in theory, many users wouldn't be ready for it.

3. I wanted to experiment to see whether the costs (in performance and usability) of the pure functional approach exceeded the benefits, and the best way to do this was to launch a genetically modified variant of the language into the wild and see whether the mutation thrived.

In fact, I hardly ever use <saxon:assign> , and the same goes for the vast majority of Saxon users. It has proved a difficult feature to maintain because it prevents certain optimizations, and it probably won't survive in the product much longer. The fact that the feature hasn't been copied in any other XSLT processor (as far as I know) is pretty convincing proof that you can live without it.

These features are a last resort. Most XSLT processors actually do their processing in a predictable way, so you can usually get away with such cheating. If you use a processor that does more optimization, however, then using such extensions might have different side effects from the ones you wanted. You can find yourself, for example, closing a file before you've written to it, because the order of execution of different instructions is not predictable. These facilities are like the PEEK and POKE of early Basic dialects, a messy escape into a lower level of programming, that you should use only if you are desperate. Having said that, there are occasional situations where they can give a dramatic boost to the speed of a stylesheet with performance problems.

Avoiding Assignment Statements

In the following sections I'll look at some of the common situations where assignment statements appear to be needed, and show how to achieve the required effect without them.

Conditional Initialization

This problem has an easy solution, so I shall get it out of the way quickly.

In conventional languages you might want to initialize a variable to zero in some circumstances and to a value of one in others. You might write:

  int x;   if (zeroBased) {   x=0;   } else {   x=1;   }  

How can you do the equivalent in XSLT without an assignment statement? The answer is simple. Think of the equivalent:

  int x = (zeroBased ? 0 : 1 );  

which has its parallel in XSLT 2.0 as:

  <xsl:variable name="x" select="if ($zeroBased) then 0 else 1">  

This has become much easier in XSLT 2.0 with the introduction of a conditional expression in XPath. In XSLT 1.0 the nearest equivalent was:

  <xsl:variable name="x">   <xsl:choose>   <xsl:when test="$zeroBased">0</xsl:when>   <xsl:otherwise>1</xsl:otherwise>   </xsl:choose>   </xsl:variable>  

The disadvantage of this, apart from its verbosity , is that when you use the content of <xsl:variable> to set its value, rather than the select attribute, the value of the variable will always be a tree. This doesn't matter if, as here, you want a string or number, because a tree can easily be converted to a string or number, but it's a problem when what you want is a sequence of nodes from the source document. Using XPath conditional expressions is much more flexible.

Avoid Doing Two Things at Once

Another common requirement for variables arises when you are trying to do two things at once. For example, you are trying to copy text to the output destination, and at the same time to keep a note of how much text you have copied. You might feel that the natural way of doing this is to keep the running total in a variable, and update it as a side effect of the template that does the copying. Similarly, you might want to maintain a counter as you output nodes, so that you can start a new table row after every ten nodes.

Or perhaps you want to scan a set of numbers calculating both the minimum and the maximum value; or while outputting a list of employees , to set a flag for later use if any salary greater than $100,000 was found.

You have to think differently about these problems in XSLT. Think about each part of the output you want to produce separately, and write a function (or template rule) that generates this piece of the output from the input data it needs. Don't think about calculating other things at the same time.

So you need to write one function to produce the output, and another to calculate the total. Write one template to find the minimum, and another to find the maximum.

This might mean writing a little more code, and it might take a little longer because work is being repeated-but it is usually the right approach. The problem of repeated processing can often be solved by using variables for the sequences used as input to both calculations: if you need to use a particular set of nodes as input to more than one process, save that sequence in a variable, which can then be supplied as a parameter to the two separate templates or functions.

An alternative that may occasionally give better performance is to write a template or function that returns a composite result. With XSLT 2.0, it is possible to return a composite result structured either as a sequence or as a tree. The calling code is then able to access the individual items of this sequence, or the individual nodes of the tree, using an XPath expression. For example, the following recursive template, when supplied with a sequence of nodes as a parameter, constructs a tree containing two elements, <min> and <max>, set to the minimum and maximum value of the nodes, respectively. A working stylesheet based on this example can be found in the download file as minimax.xsl: it acts as its own source document.

  <xsl:template name="get-min-and-max">   <xsl:param name="nodes"/>   <xsl:param names"best-so-far">   <min><xsl:value-of select="999999999"/></min>   <max><xsl:value-of select="-999999999"/></max>   </xsl:param>   <xsl:choose>   <xsl:when test="$nodes">   <xsl:variable name="new-best-so-far">   <min>   <xsl:choose>   <xsl:when test="$nodes[1] &lt; $best-so-far/min">   <xsl:value-of select="$nodes[1]"/>   </xsl:when>   <xsl:otherwise>   <xsl:value-of select="$best-so-far/min"/>   </xsl:otherwise>   </xsl:choose>   </min>   <max>   <xsl:choose>   <xsl:when test="$nodes[1] &gt; $best-so-far/max">   <xsl:value-of select="$nodes[1]"/>   </xsl:when>   <xsl:otherwise>   <xsl:value-of select="$best-so-far/max"/>   </xsl:otherwise>   </xsl:choose>   </max>   </xsl:variable>   <xsl:call-template name="get-min-and-max">   <xsl:with-param name="nodes" select="$nodes[position() &gt; 1]"/>   <xsl:with-param name="best-so-far" select="$new-best-so-far"/>   </xsl:call-template>   </xsl:when>   <xsl:otherwise>   <xsl:copy-of select="$best-so-far"/>   </xsl:otherwise>   </xsl:choose>   </xsl:template>  

When you call this template you can let the second parameter, $best-so-far , take its default value:

  <xsl:variable name="min-and-max">   <xsl:call-template name="get-min-and-max">   <xsl:with-param name="nodes" select="//item/price"/>   </xsl:call-template>   </xsl:variable>   Minimum price is: <xsl:value-of select="$min-and-max/min"/>.   Maximum price is: <xsl:value-of select="$min-and-max/max"/>.  

One particular situation where it is a good idea to save intermediate results in a variable, and then use them as input to more than one process, is where the intermediate results are sorted. If you've got a large set of nodes to sort, the last thing you want to do is to sort it more than once. The answer to this is to do the transformation in two passes : the first pass creates a sorted sequence, and the second does a transformation on this sorted sequence. If the first pass does nothing other than sorting, then the data passed between the two phases can simply be a sequence of nodes in sorted order. If it does other tasks as well as sorting (perhaps numbering or grouping), then it might be more appropriate for the first phase to construct a temporary tree.

There are actually two ways you can achieve a multistage transformation in XSLT:

• Create a temporary tree in which the nodes appear in sorted order. Then use <xsl:for-each> or <xsl:apply-templates> to process the nodes on this tree in their sorted order. This is similar to the min-and-max example above; it relies on having either XSLT 2.0, or an XSLT 1.0 processor with the exslt:node-set() extension function.

• Use a sequence of stylesheets (sometimes called a chain or pipeline ): the first stylesheet creates a document in which the nodes are sorted in the right order, and subsequent stylesheets take this document as their input. Such a chain of stylesheets can be conveniently manipulated using the JAXP interface described in Appendix D. The advantage of this approach compared with a single stylesheet is that the individual stylesheets in the chain are easier to split apart and reuse in different combinations for different applications.

Note that neither of these techniques violates the XSLT design principle of "no side effects."

Don't Iterate, Recurse

One of the most common uses of variables in conventional programming is to keep track of where you are in a loop. Whether this is done using an integer counter in a ‰ for ‰« loop, or using an Iterator object to process a list, the principle is the same: we have a variable that represents how far we have got and that tells us when we are finished.

In a functional program, you can't do this, because you can't update variables. So instead of writing a loop, you need to write a recursive function.

In a conventional program a common way to process a list of items is as follows .

 iterator = list.iterator(); while (iterator.hasNext()) {    item = iterator.next();    item.doSomething(); } 

The killer assignment statement is ‰ item = iterator.getNextItem() ‰« . This assigns a different value to the item each time, and what's more, it relies on the iterator containing some sort of updateable variable that keeps track of how far it's got.

In a functional program we handle this by recursion rather than iteration. The pseudocode becomes:

 function process(list) {    if (!isEmpty(list)) {       doSomething(getFirst(list));       process(getRemainder(list));    } } 

This function is called to process a list of objects. It does whatever is necessary with the first object in the list, and then calls itself to handle the rest of the list. (I'm assuming that getFirst() gets the first item in the list and getRemainder() gets a list containing all items except the first). The list gets smaller each time the function is called, and when it finally becomes empty, the function exits, and unwinds through all the recursive calls.

It's important to make sure there is a terminating condition such as the list becoming empty. Otherwise, the function will keep calling itself forever-the recursive equivalent of an infinite loop.

So, the first lesson in programming without variables is to use recursion rather than iteration to process a list. With XSLT, this technique isn't necessary to handle every kind of loop, because XSLT and XPath collectively provide built-in facilities, such as <xsl:apply-templates> and <xsl:for-each> and the ‰ for ‰« expression, that process all the members of a sequence, as well as functions like sum() and count() to do some common operations on sequences; but whenever you need to process a set of things that can't be handled with these constructs, you need to use recursion.

Is recursion expensive? The answer is, not necessarily . Generally , a recursive scan of a sequence using the head/tail method illustrated above has O(n) performance, which means that the time it takes is directly proportional to the size of the list-exactly the same as with a conventional loop. In fact, it's quite possible for a reasonably smart compiler to generate exactly the same code for a recursive procedure as for an iterative one. For example, a common compilation technique with functional programming languages is that of tail call optimization, which recognizes that when a function calls itself as the last thing it does (as in the proforma code above) there's no need to allocate a new stack frame or new variables; you can just loop back to the beginning.

Unfortunately, not all XSLT processors implement tail call optimization, which means that a recursive scan of a list can run out of memory, typically after processing 500 or 1,000 items. Among the better-known XSLT 1.0 processors, Saxon and jd.xslt implement tail call optimization, while Xalan and MSXML do not. A programming technique that is often useful in such cases is called divide-and-conquer recursion. With head-tail recursion, the function processes one item, and then calls itself to process the rest of the sequence, which means that the maximum depth of recursive calls is equal to the number of items in the sequence. With divide-and-conquer recursion, by contrast, the function calls itself to process the first half of the sequence, and then calls itself again to process the second half. Although the number of function calls is the same, the maximum depth of recursion is now the logarithm of the size of the sequence: for example, to process a sequence of 1,000 items the maximum depth of recursion will be 10. With a little ingenuity, many recursive algorithms that process a sequence of items can be written using this divide-and-conquer approach.

Aggregating a List of Numbers

The following example uses a recursive template to process a whitespace-separated list of numbers.

Input

Suppose, you have a string that holds a white-space -separated list of numbers, for example (12, 34.5, 18.2, 5), and you want to replace this with a cumulative sequence (12, 46.5, 64.7, 69.7) in which each number is the sum of the previous values. An example of an application that might need to do this is a billing application, where the input sequence contains the values of individual transactions, and the output sequence shows a running balance.

This could be done with an XPath expression such as follows:

  for $i in 1 to count($seq)   return sum($seq[position() = 1 to $i])  

However, this involves n ² /2 additions, which gets more and more expensive as the size of the sequence increases . It's reasonable to look for a solution that is more scaleable than this.

For the sake of an example, this is the entire content of the document, number-list .xml.

  <numbers> 12 34. 5 18. 2 5 </numbers>  

We'll suppose that there is a schema that validates this as a sequence of xs:decimal values, so (unlike XSLT 1.0) we don't need to be concerned with the parsing of the string; we can simply access the typed value of the element as a sequence.

Schema

The schema used to validate this trivial source document is number-list.xsd .

  <xs:schema xmlns:xs="http://www.w3.org/2001/XMLSchema">   <xs:element name="numbers" type="number-list"/>   <xs:simpleType name="number-list"> -'   <xs:list itemType="xs:decimal"/>   </xs:simpleType>   </xs:schema>  

Stylesheet

Here's the recursive stylesheet (in file number-total.xsl ):

  <xsl:stylesheet   xmlns:xsl="http://www.w3.org/1999/XSL/Transform"   xmlns:xs="http://www.w3.org/2001/XMLSchema"   xmlns:f="local-functions.uri"   exclude-result-prefixes="xs f"   version="2.0">   <xsl:import-schema schema-location="number-list.xsd"/>   <xsl:function name="f:total-numbers" as="xs:decimal*">   <xsl:param name="input" as="xs:decimal*"/>   <xsl:param name="total" as="xs:decimal"/>   <xsl:if test="exists($input)">   <xsl:variable name="x" as="xs:decimal"   select="$input[1] + $total"/>   <xsl:sequence select="$x"/>   <xsl:sequence select="f:total-numbers($input[position()!=1],$x)"/>   </xsl:if>   </xsl:function>   <xsl:template match="/">   <total values="{f:total-numbers(numbers, 0)}"/>   </xsl:template>   </xsl:stylesheet>  

To run this with Saxon, you need the schema-aware version of the product. You can execute the transformation as:

 java com.saxonica.Transform-val number-list.xml number-total.xsl 

Notice how closely the function f:total-numbers mirrors the pseudocode structure given earlier.

If the supplied list is empty, the function returns nothing (an empty sequence).

The first time the function is called, it returns the value of the first item in the sequence (obtained by adding the value of this item to the running total, which is initialized to zero). It then calls itself to process the rest of the list, and returns the result of this processing.

Each subsequent time the function is called, it processes the first value in what's left of the input sequence, adds this to the running total that was supplied as a parameter, outputs this value, and then calls itself to process the tail of the sequence.

Eventually, the function will call itself with an empty sequence as the argument, at which point it returns, unwinding the entire stack of function calls.

Output

  <?xml version="1.0" encoding="UTF-8"?>   <total values="12 46.5 64.7 69.7"/>  

 

Here's another example, this time processing a sequence of nodes. XPath provides built-in functions for counting nodes and for totaling their values, but they aren't always flexible enough: sometimes you need to walk round the nodes yourself.

Using Interleaved Structures

XML makes it very easy to represent hierarchic structures, such as the chapters, sections, and paragraphs of a book. But what do you do when there are structures that are nonhierarchic? An example is the text of a play: one way of splitting the text is according to who is speaking, and another way is to follow the meter of the verse. The problem is that lines of verse aren't neatly nested inside speeches, and speeches aren't nested inside lines of verse: the two structures are interleaved. The usual solution to this problem is to use the hierarchic XML tagging to represent one of the structures (say the speeches) and to use empty element tags to mark the boundaries in the other structure.

(Another design approach is referred to as parallel markup: the markup for either or both of the structures is held separately from the text itself, using XPointer references to identify the text to which it relates .)

Input

This example ( scene4-3.xml ) is an extract from Shakespeare's Othello, Act IV, Scene 3.1 have departed from Jon Bosak's markup to show the line endings as they are given in the Arden Shakespeare edition.

  <?xml version="1.0" encoding="iso-8859-1"?>   <SCENE REF="4.3">   <STAGEDIR>Enter OTHELLO, LODOVICO, DESDEMONA, EMILIA and   attendants</STAGEDIR>   <SPEECH>   <SPEAKER>LODOVICO</SPEAKER>   I do beseech you, sir, trouble yourself no further.<NL/>   </SPEECH>   <SPEECH>   <SPEAKER>OTHELLO</SPEAKER>   0, pardon me: 'twill do me good to walk.<NL/>   </SPEECH>   <SPEECH>   <SPEAKER>LQDOVICO</SPEAKER>   Madam, good night; I humbly thank your ladyship.<NL/>   </SPEECH>   <SPEECH>   <SPEAKER>DESDEMONA</SPEAKER>   Your honour is most welcome. </SPEECH>   <SPEECH>   <SPEECH>   <SPEAKER>OTHELLO</SPEAKER>   Will you walk, sir?<NL/>   0, Desdemona, --   </SPEECH>   <SPEECH>   <SPEAKER>DESDEMQNA</SPEAKER>   My lord?   </SPEECH>   <SPEECH>   <SPEAKER>OTHELLO</SPEAKER>   Get you to bed<NL/>   on th' instant; I will be returned forthwith<NL/>   dismiss your attendant there: look't be done.<NL/>   </SPEECH>   <SPEECH>   <SPEAKER>DESDEMONA</SPEAKER>   I will, my lord.<NL/>   </SPEECH>   <STAGEDIR>Exeunt Othello, Lodovico, and attendants</STAGEDIR>   </SCENE>  

Output

Typically, a printed edition of this play is formatted with the kind of layout shown in Figure 9-3, in which lines that are split across multiple speeches are indented to show their relationship.

DESDEMONA
Your honour is most welcome.
OTHELLO		Will you walk, sir?
O, Desdemona-
DESDEMONA	My Lord?
OTHELLO		Get you to bed
On th'instant, I will be returned forthwith dismiss your attendant there: look't be done.

Figure 9-3

Achieving this format is not easy (especially details such as the omission of a new line if the indented text fits on the same line as the speaker's name), and it certainly requires a computational stylesheet to achieve it. Rather than attempt this, I will tackle a simpler problem, which is to invert the structure so that the primary XML hierarchy shows the lines, and the start of each speech is tagged by an empty element.

  <?xml version="1.0" encoding="UTF-8"?>   <scene><title>SCENE III. Another room In the castle.</title>   <stagedir>Enter OTHELLO, LODOVICO, DESDEMONA, EMILIA and   attendants</stagedir>   <speech speaker="LODOVICO"/>   <line>I do beseech you, sir, trouble yourself no further.</line>   <speech speaker="OTHELLO"/>   <line>O, pardon me: 'twill do me good to walk.</line>   <speech speaker="LODOVICO"/>   <line>Madam, good night; I humbly thank your ladyship.</line>   <speech speaker="DESDEMONA"/>   <line>Your honour is most welcome.   <speech speaker="OTHELLO"/>   Will you walk, sir?</line>   <line>o Desdemona, --   <speech speaker="DESDEMONA"/>   My lord?   <speech speaker="OTHELLO"/>   Get you to bed</line>   <line>on th' instant; I will be returned forthwith</line>   <line>dismiss your attendant there: look't be done.</line>   <speech speaker="DESDEMONA"/>   <line>I will, my lord.</line>   <stagedir>Exeunt Othello, Lodovico, and attendants</stagedir>   </scene>  

Stylesheet

I tackle this by processing the text sequentially, using a recursive template. The structure I have followed below is a two-phase approach. The first phase flattens the structure so that both the speech boundaries and the line boundaries are represented by empty elements, appearing as siblings of the text nodes. The result of the first phase is held in the variable $flat . This variable holds a sequence of (parentless) element and text nodes. The second phase then adds the hierarchic structure of <line> elements containing the text and <speech> nodes.

Here is the top-level logic of the stylesheet invert.xsl . Note how the second phase starts by processing only the first node in the sequence $flat .

  <xsl:stylesheet   xmlns:xsl="http://www.w3 .org/1999/XSL/Transform"   versions"2.0">   <xsl:template match="SPEECH">   <xsl:variable name="flat" as="node()*">   <xsl:apply-templates mode="phase"/>   </xsl:variable>   <xsl:apply-templates select="$flat[l]" mode="phase2"/>   </xsl:template>  

Now the template rules for the first phase, the flattening phase. The important template rule is the first one, which in effect takes the children of the old <SPEECH> element and makes them into following siblings of the new <speech> element.

  <xsl:template match="SPEECH" mode="phase1">   <speech speakers"{SPEAKER}"/>   <xsl:apply-templates/>   </xsl:template>   <xsl:template match="NL" mode="phase1">   <NL/>   </xsl:template>   <xsl:template match="STAGEDIR" mode="phase1">   <stagedir>   <xsl:apply-templates/>   </stagedir>   </xsl:template>  

We now have a flat structure containing empty <speech> elements, empty <NL> elements, text nodes, and <stagedir> elements. Phase 2 is structured so a template rule is called once for each node in the sequence $flat. In each case, this template rule calls <xsl:apply-templates> to process the next node in the sequence (and thus, by implication , the rest of the sequence beyond). When an <NL> element is encountered , a new <line> element is written to the result tree, and the following elements generate children of this <line> element. When any other kind of node is encountered, it is simply copied to the result tree at the current level.

  <xsl:template match="NL" mode="phase2">   <line>   <xsl:apply-templates   selects"following-sibling::node()[1][not(self::NL)]"/>   mode="phase2"/>   </line>   <xsl:apply-templates select="following-sibling::node() ['1]"/>   </xsl:template>   <xsl:template match="node()" mode="phase2">   <xsl:copy-of select="."/>   <xsl:apply-templates   select=",following-sibling::node() [1] [not(self::NL)]"/>   </xsl:template>   </xsl:stylesleet>  

The expression ‰ following-sibling::node() [1] [not(self::NL)] ‰« selects the next sibling node, provided it is not an <NL> element; if the next sibling is an <NL> element, it selects an empty sequence.

There is very little that is specific to XSLT 2.0 in this stylesheet, with the exception of the sequence of nodes used as an intermediate variable. The second phase could have been written, without explicit recursion, using <xsl:for-each-group> , but in my view the recursive solution in this case is not really any more difficult.

This stylesheet also demonstrates that recursive processing of a sequence can often be carried out very elegantly, using <xsl:apply-templates> . I find that there is a tendency when writing recursive code to reach straight for <xsl:call-template> (or, in XSLT 2.0, <xsl:function> ) when <xsl:apply-templates> can often do the job far better.

Superficially, the logic of this stylesheet doesn't bear much resemblance to the prototypical head/tail recursive structure described earlier. But in fact, this is precisely the underlying structure. There are actually two nested sequences being processed here, each of them using a head/tail recursion. The first sequence is the sequence of lines, where each line is represented in the input by an <NL> element and its following siblings up to the next <NL> . The ‰ match="NL" ‰« template processes the first line of text (which consists of multiple nodes), and then calls itself via <xsl:apply-templates> to process the remaining lines. The second, nested, sequence is the sequence of nodes that follow each <NL> element. In both cases, the test for the terminating condition is implicit, because <xsl:apply-templates> does nothing when the selected node sequence is empty.

 

Recursion: Summary

By now the principle should be clear. Whenever you need to find something out by processing a sequence of items, write a recursive template that is given the sequence as a parameter. If the sequence isn't empty, deal with the first item, and make a recursive call to deal with the rest of the sequence that follows the first item.

As I mentioned, with XSLT1.0 there was another problem when doing this, which had nothing to do with the lack of an assignment statement, but was a consequence of the limited range of data types available. The result of a template in XSLT 1.0 was always a temporary tree, and with XSLT 1.0 (without the widely implemented exslt:node-set() extension) there were only two things you could do with the tree: you could copy it to the final result tree, or you could convert it to a string.

With XSLT 2.0, this becomes much easier because a template (or a function) can return an arbitrary sequence, which you can manipulate in any way you like. You can also choose to construct a temporary tree, which can now be manipulated just like an original source document.

For another example that takes advantage of this, see the Knight's Tour in Chapter 12.

Grouping

A common processing task that appears at first sight to need updateable variables is the splitting of data into groups.

Suppose that your source logged cities and their respective countries in the following format:

 <cities>    <city name=   "    CityName    "   country  ="   CountryName    "    />   ... etc ...  </cities> 

However, you want to list together all cities found in a particular country.

 <countries>    <country name="  CountryName">  <city>  CityName1  </city>       <city>  CityName2<  /city>    </country  ...  etc...  </countries> 

In other languages, we've probably all written code that achieved similar effects using pseudocode such as this:

 sortedCities = cities.sortBy("country"); previousCountry = null; write("<country>") for each city in sortedCities {    thisCountry = city.getAttribute("country");    if (thisCountry != previousCountry)       write("</country>\n<country>");    }    write("<city>" + city.getAttribute("city") + "</city>");    previousCountry = thisCountry; } write("</country>") 

In XSLT, of course, this is a nonstarter, for two reasons. Firstly, you need to output a tree, not a text file containing markup tags: this means you can't write the end tag for an element as a separate operation from writing the start tag. Secondly, you can't use assignment statements to spot the change of country as you go through the data.

This kind of problem can nearly always be tackled in XSLT 2.0, using the <xsl:for-each-group> construct. In many cases, it can also be handled by writing two nested <xsl:for-each> loops (one to execute once per group, the other to execute once per item within each group), using the distinct-values () function to select the grouping key values that identify the groups. These problems can therefore be tackled using navigational stylesheets alone.

However, the <xsl:for-each-group> construct is a stereotype, a high-level construct designed to tackle a particular class of commonly encountered programming problems. The trouble with stereotype constructs is that there always comes a point where they break down, where the problem falls outside the domain that the stereotype was designed to tackle. The XSL Working Group designed the construct after surveying quite a range of use cases, which means that it's quite hard to come up with examples of things that it won't do, but they are bound to arise.

In addition, even though this book is designed to describe XSLT 2.0, there may well be cases where you want to design a solution that also works under XSLT 1.0. I think it's useful therefore to retain a description of the two principal techniques used for grouping in XSLT 1.0. But I will keep it brief.

All grouping techniques essentially consist of two nested loops, with the structure:

  <xsl:for-each select=group-representative>   <group>   <xsl:for-each member-of-group>   <item>   item information   </item>   </xsl:for-each>   </group>   </xsl:for-each>  

Of course, either of the loops might equally be coded using <xsl:apply-templates> or perhaps an XPath ‰ for ‰« expression, and sometimes the inner loop will not be a real loop at all, but a call on an aggregation function such as count() or sum() .

But in all cases, the tricky part in the outer loop, is to select one item that serves to identify the group, and in the inner loop, is to select the remaining items that participate in the same group.

Very often, a call on distinct-values() can be used in the outer loop, to select one instance of each distinct value that appears in the input sequence. In XSLT 1.0, there are two ways of achieving the same effect:

• The expression ‰ x[ not (@y = preceding -sibling::x/@y) ] ‰« selects all the <x> children of the context node whose @y attribute is different from that of any preceding <x> child.

• The expression ‰ x[.is key ('k',@y)[1]] ‰« selects an <x> element if, of all the elements retrieved by the call on ‰ key('k',@y) ‰« , this is the first one. Unfortunately, the ‰ is ‰« operator was not available in XPath 1.0, so instead of writing ‰ A is B ‰« to test whether two expressions return the same node, you can write ‰ generate-id (A) = generate-id (B) ‰« , or ‰ count (A B) =1 ‰« .

Selecting the remaining elements in the group is generally easier:

• In the first case, you can write ‰ select=" .. /x[@y = current() /@y] " ‰« .

• In the second case, you can use the same key again, by writing ‰ select="key ( 'k' , @y) " ‰« .

Of these two techniques, the second is generally more efficient because it takes advantage of the index or hash table built to support the key() function. This technique, using keys for grouping, is known as the Muenchian grouping technique, after its inventor , Steve Muench of Oracle. A comprehensive guide to Muenchian grouping, including many variants to handle problems such as multilevel grouping, has been produced by Jeni Tennison at http://www.jenitennison.com/xslt/grouping .

Another advantage of Muenchian grouping is that it can be used where the grouping expression (the common value that determines whether two nodes belong in the same group) is something other than the string value of a node, as it was in the above example. A typical example is where you want to create alphabetical groups, one for each letter of the alphabet. For example, if you wanted to list the cities alphabetically , with a heading for each initial letter of the alphabet, you could simply use the following key definition.

  <key name="alpha-group" match="city" use="substring(@name, 1, 1)"/>  

and apart from this change, the logic of the stylesheet would be much the same.