XSLT is Turing complete. This means that given sufficient memory, XSLT can calculate anything any other Turing-complete language (such as C++) can calculate. This comes as a bit of a surprise to programmers who are accustomed to more traditional languages. After all, XSLT is missing some features that are important to a lot of algorithms, including loops and mutable variables.
Note: What XSLT calls variables are called constants in most other languages. They're more like algebraic variables than traditional programming variables.
The omissions just mentioned aren't oversights. XSLT is a functional language rather than a procedural one. In a procedural language such as C or Pascal, a program is defined as a sequence of steps, the execution of which in the specified order produces the final result as the last step in the sequence. In a functional language, a program is defined as a function composed of other functions, the evaluation of which leads to the final result. The big advantage of functional languages is that the order of execution doesn't matter. As a simple example, consider these two (algebraic) functions:
f(x) = 2*x g(x) = x - 3 |
Now consider the function h(x) to be the composition of
f and g:
h(x) = f(g(x)) |
You can evaluate this function either g first:
h(x) = f(x - 3) = 2 * (x - 3) = 2x - 6 |
or f first:
h(x) = 2 * g(x) = 2 * (x - 3) = 2x - 6 |
Both produce the same answer. The functional nature of a language makes it more amenable to parallel processing because multiple parts of a program can be evaluated simultaneously with no concern for which parts need to be evaluated before other parts. Thread safety is automatic.
Functional languages, including XSLT, can't include traditional loops because loops are ordered in
time. That is, a typical loop is written and compiled such that i==1 has to happen before i==2. Of
course, you can run loops backward instead of forward, or increment the loop counter by something
other than 1, or even eliminate the loop counter completely as you do in a
while statement. However, regardless of the loop's type, the order of
execution matters, and this is antithetical to functional programming.
In functional languages, most tasks that are accomplished with loops in traditional languages are instead accomplished with recursion. Parameters take the place of variables. For example, recently I was asked how to print a certain number of dots (periods) where the number to print wasn't known at compile time. This might be useful when formatting a restaurant menu, for example, which often requires a different number of dots between the entree name and the price:
Crawfish Etoufee.......$9.95 Fried Chicken..........$6.95 |
In C, you'd write a simple function like this:
void printDots(int n) {
int i;
for (i = 0; i < n; i++) {
printf(".");
}
} |
However, this isn't the only way to solve the problem. Instead of a loop, you can use recursion, like so:
void printDotsRecursively(int n) {
if (n > 0) {
printf(".");
printDotsRecursively(n-1);
}
} |
This would be unusual in C. However, in XSLT, recursion is the only option.
The following template generates the precise number of dots passed in as the value of the
count param. The logic is straightforward: If the value of
$count is greater than zero, output a period and call the function again
with a count param decremented by one. Otherwise, do nothing. This
is essentially the same algorithm that's used by the printDotsRecursively
function, only it's implemented in XSLT rather than C:
<xsl:template name="dots">
<xsl:param name="count" select="1"/>
<xsl:if test="$count > 0">
<xsl:text>.</xsl:text>
<xsl:call-template name="dots">
<xsl:with-param name="count" select="$count - 1"/>
</xsl:call-template>
</xsl:if>
</xsl:template> |
For example, to print 100 dots, you call the template with 100 as the value of the
count param:
<xsl:call-template name="dots">
<xsl:with-param name="count" select="100"/>
</xsl:call-template> |
Instead of passing a constant value, you can calculate the number of dots to print based on some
other value. For example, the following instruction prints as many dots as are needed to pad a menu
line to 80
characters, after accounting for the length of the price and the entree name (more specifically, the length
of the string-values of the price and entree child elements of the context node):
<xsl:call-template name="dots">
<xsl:with-param name="count"
select="80 - string-length(entree) - string-length(price)"/>
</xsl:call-template> |
Replacing loops with recursion, whether in C, XSLT, or Scheme, takes some getting used to. However, this technique has a certain elegance. You don't need to use it often in XSLT, but it lets you accomplish tricky tasks that you can't do any other way in standard XSLT.
- Read this article on functional programming on Wikipedia. While you're there, find out more about Turing completeness.
- Check out Michael Kay's
XSLT Programmer's Reference
, the standard introduction to XSLT.
He has also authored two XSLT articles on developerWorks: "What kind of language is XSLT?" (April 2005) and "Saxon: Anatomy of an XSLT processor" (April 2005).
- Find out more about recursion in
Chapter 17 of Elliotte Harold's book
Processing XML with Java
, which covers the basics of XSL templates.
- Learn several simpler ways of accomplishing the same task performed here with recursion in XSLT 1.0 by reading the W3C's XSLT 2.0 specification. However, XSLT 2.0 doesn't change the basic functional nature of XSLT, so many tasks still require recursion to complete.
- Try to solve the menu problem discussed here with the padding function in EXSLT. However, it's a one-trick pony, and it doesn't address many of the other problems that can also be solved by recursion. The pure XSLT implementation of the EXSLT padding function uses a slightly more efficient version of the recursive algorithm shown here.
- Find more XML resources on the developerWorks XML zone. For a complete list of XML tips to date, check out the tips summary page.
- Learn how you can become an IBM Certified Developer in XML and related technologies.
-
IBM trial software: Build your next development project with trial software available for download directly from developerWorks.
Elliotte Rusty Harold is originally from New Orleans, to which he returns periodically in search of a decent bowl of gumbo. However, he resides in the Prospect Heights neighborhood of Brooklyn with his wife Beth and cats Charm (named after the quark) and Marjorie (named after his mother-in-law). He's an adjunct professor of computer science at Polytechnic University, where he teaches Java technology and object-oriented programming. His Cafe au Lait Web site has become one of the most popular independent Java sites on the Internet, and his spin-off site, Cafe con Leche, has become one of the most popular XML sites. His books include Effective XML , Processing XML with Java , Java Network Programming , and The XML 1.1 Bible . He's currently working on the XOM API for processing XML and the Jaxen XPath engine.
Next steps from IBM
With the no-charge DB2 Express-C, pureXML, Zend Core PHP, and Java you can develope advanced Web 2.0 applications quickly that matter.
- Try: Download a free trial version of DB2 Express-C, which includes Zend Core PHP and pureXML technology that is ideally suited for managing both XML and relational data.
- Article: See how DB2 pureXML schema capabilities can evolve schemas without making any changes to your applications.
- Tutorial: This tutorial shows you how to use DB2's pureXML to expose the native XML capabilities of DB2.
- Buy: DB2 9 for Linux, UNIX and Windows
My developerWorks community
Tags
Use the slider bar to see more or fewer tags.
Popular tags shows the top tags for this particular content zone (for example, Java technology, Linux, WebSphere).
My tags shows your tags for this particular content zone (for example, Java technology, Linux, WebSphere).
Popular article tags |
My article tagsSkip to tags list
Popular article tags |
My article tags
