Skip to main content

Tip: Loop with recursion in XSLT

Technique allows you extend XSLT's capabilities

Elliotte Rusty Harold (elharo@metalab.unc.edu), Adjunct Professor, Polytechnic University
Photo of Elliot Rusty Harold
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.

Summary:  XSLT is a functional programming language like Haskell or Scheme, and unlike C or Fortran. Thus it has no loops and no mutable variables. Instead, you must replace these constructs with recursion and parameters. This tip demonstrates how to provide this functionality using named templates and the xsl:call-template, xsl:with-param, and xsl:param elements.

View more content in this series

Date:  28 Jul 2006 (Published 29 Jun 2005)
Level:  Intermediate
Activity:  13701 views
Comments:  

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.

Functional programming

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.


Recursion

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>


Summary

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.


Resources

About the author

Photo of Elliot Rusty Harold

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.

Comments



Trademarks  |  My developerWorks terms and conditions

Help: Update or add to My dW interests

What's this?

This little timesaver lets you update your My developerWorks profile with just one click! The general subject of this content (AIX and UNIX, Information Management, Lotus, Rational, Tivoli, WebSphere, Java, Linux, Open source, SOA and Web services, Web development, or XML) will be added to the interests section of your profile, if it's not there already. You only need to be logged in to My developerWorks.

And what's the point of adding your interests to your profile? That's how you find other users with the same interests as yours, and see what they're reading and contributing to the community. Your interests also help us recommend relevant developerWorks content to you.

View your My developerWorks profile

Return from help

Help: Remove from My dW interests

What's this?

Removing this interest does not alter your profile, but rather removes this piece of content from a list of all content for which you've indicated interest. In a future enhancement to My developerWorks, you'll be able to see a record of that content.

View your My developerWorks profile

Return from help

static.content.url=http://www.ibm.com/developerworks/js/artrating/
SITE_ID=1
Zone=XML
ArticleID=87289
ArticleTitle=Tip: Loop with recursion in XSLT
publish-date=07282006
author1-email=elharo@metalab.unc.edu
author1-email-cc=dwxed@us.ibm.com

My developerWorks community

Tags

Help
Use the search field to find all types of content in My developerWorks with that tag.

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).

Use the search field to find all types of content in My developerWorks with that tag. 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).

Special offers