Loop with recursion in XSLT

Technique allows you extend XSLT's capabilities

Comments

Content series:

This content is part # of # in the series: Tip

Stay tuned for additional content in this series.

This content is part of the series:Tip

Stay tuned for additional content in this series.

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.


Downloadable resources


Related topics


Comments

Sign in or register to add and subscribe to comments.

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