Jumping through loops with XSL
Posted by Ronnie Holm on June 13th, 2009
I was recently faced with the need to express a loop in XSL. Not the build-in for-each that iterates over nodes matching an XPath, but one with a counter. In C# this kind of loop is easily expressed as
for (int i = 0; i < 5; i++)
// do something
No such for-construct exists in XSL. In fact there’re no looping constructs of any kind in XSL, except for the one used to iterate nodes. However, since XSL and C# are both Turing complete languages, and since anything that can be expressed in one Turing complete language can be expressed in another, it follows that it must be possible to express a loop with a counter in XSL.
But as Alan Parlis puts it in Epigrams on Programming:
Beware of the Turing tar-pit in which everything is possible but nothing of interest is easy.
Although XSL and C# are both Turing complete languages, XSL is a functional programming language and therefore belongs to a strain of languages that forgo build-in looping constructs. Instead, looping is accomplished through recursion.
We can turn the iterative C# loop into a recursive one like so:
void Loop(int i) {
if (i > 0) {
// do something
Loop(i - 1);
}
}
and transform the recursive solution into an XSL template:
<xsl:template name="Loop">
<xsl:param name="i" select="5"/>
<xsl:if test="$i > 0">
<!-- do something -->
<xsl:call-template name="Loop">
<xsl:with-param name="i" select="$i - 1"/>
</xsl:call-template>
</xsl:if>
</xsl:template>
Okay, but what about nested loops then:
for (int i = 0; i < 5; i++)
for (int j = 0; j < 5; j++)
// do something
Giving it some thought, the nested loops (of any nesting level) can be expressed using recursion following a pattern of nested if-statements:
void NestedLoops(int i, int j, int k) {
if (i > 0) {
// do something
if (j == 1)
NestedLoops(i - 1, k, k);
else
NestedLoops(i, j - 1, k);
}
}
Again, performing a one-to-one transformation to XSL:
<xsl:template name="NestedLoops">
<xsl:param name="i"/>
<xsl:param name="j"/>
<xsl:param name="k"/>
<xsl:if test="$i > 0">
<!-- do something -->
<xsl:choose>
<xsl:when test="$j = 1">
<xsl:call-template name="NestedLoops">
<xsl:with-param name="i" select="$i - 1"/>
<xsl:with-param name="j" select="$k"/>
<xsl:with-param name="k" select="$k"/>
</xsl:call-template>
</xsl:when>
<xsl:otherwise>
<xsl:call-template name="NestedLoops">
<xsl:with-param name="i" select="$i"/>
<xsl:with-param name="j" select="$j - 1"/>
<xsl:with-param name="k" select="$k"/>
</xsl:call-template>
</xsl:otherwise>
</xsl:choose>
</xsl:if>
</xsl:template>
Wordy, but seeing through the angle brackets I find solution quite elegant.
June 14th, 2009 at 11:22 am
Functional languages do use recursion in stead of build-in looping constructs, but mostly only at the basic level. Typically, recursion will be used to build functions such as fold, map, scan, … and thus hide the “dangerous” recursion. I say dangerous as it is easy to get wrong and end in a eternal recursion (just like eternal loops in imperative language are all too easy to make). Fold, map, and friends protect against accidentally making eternal recursion, and they make for more concise and understandable programs.
If (and I mean ‘if’, as I do not know XSL very well) do not support building map, fold, … from basic recursion it is only functional in a negative sense. That is, it is functional as it do _not_ support destructive updates and as the programmer do not specify evaluation order. A positive definition would include things such as higher order functions, which would allow you to build fold, map, …
If a programming language is only functional in the negative sense, I really would not want to make big and complex programs in it. It still may be very useful, but it will have it limits that it will be quite painful to cross. For example, a spreadsheet is functional in the negative sense, but not in the positive sense. And a spreadsheet is immensely useful for certain tasks, but you do not want to write the next Linux kernel in Excel. A similar argument could be made for SQL, except various extension do contain functional / imperative aspects.
The point of my rant, is that you may want to consider if XSL is really up to the task of complex processing. Of cause, as I do not know the task, nor XSL, well enough, I can have no opinion on your exact problem.
June 14th, 2009 at 11:36 am
I just googled a little and in this post http://fxsl.sourceforge.net/articles/FuncProg/2.html some guy builds up fold and map in XSL. He uses it to compute sum and product. I have not read it thoroughly, as all this XSL hurts my brain.
June 14th, 2009 at 5:32 pm
Recursion is not the only way to implement a “loop” in XSLT.
In XSLT 2.0 one simply writes:
In XSLT 1.0 in most cases it is possible to use an elegant and efficient non-recursive technique, as described at:
http://www.topxml.com/code/cod-422_10050_avoiding-an-xslt-processor-crash-due-to-deep-recursive-processing.aspx
The FXSL library implements Higher Order Functions in XSLT (both in XSLT 1.0 and XSLT 2.0) and has nice functions/templates for folding, iteration, zipping, partial applications, … etc.
Mads Lindstrøm, who commented on the code of FXSL hurting his brain, has to look at the code of FXSL 2.x (for XSLT 2.0), which is orders of magnitude simpler, because it is XSLT 2.0. For example, this is the implementation of the f:foldl() function ():
1]
)”/>
The conclusion is: Before trying to re-invent the wheel, make an earnest attempt to read :)
June 14th, 2009 at 5:34 pm
Sorry, I tried twice in a row to enter some code in my comment — how do you do it?
June 14th, 2009 at 6:13 pm
@Dimitre Novatchev:
Unfortunately, WordPress isn’t too fund of code in comments.
Although I didn’t mention it explicitly, I’m relying on the .Net XslCompiledTransform class to do the actual transform. It only supports XSL/XPath 1.0.
But the FXSL library is definitely worth looking into.
June 14th, 2009 at 6:17 pm
Hi Dimitre Novatchev,
For code in comments, I have given up on WordPress. I use http://pastebin.com/ in stead and link to the code.
June 14th, 2009 at 9:19 pm
Not trying anymore to write code, here is a link to the code of f:foldl() — the code of the function is only a few lines:
http://fxsl.cvs.sourceforge.net/viewvc/fxsl/fxsl-xslt2/f/func-foldl.xsl?revision=1.3&view=markup
June 14th, 2009 at 9:22 pm
This is my last comment.
In order to see how powerful is XSLT 2.0 when Higher Order Functions are added to it, read this 2006 Extreme Markup Conference presentation:
http://www.idealliance.org/papers/extreme/proceedings/xslfo-pdf/2006/Novatchev01/EML2006Novatchev01.pdf
July 17th, 2009 at 2:50 pm
If you know your input document has enough nodes you can also just do <xsl:for-each select=”//node()[position() < 10]“><xsl:value-of select=”position()”/>,</xsl:for-each> which can be nested as much as you want (just use xsl:variables for each level).
December 28th, 2009 at 1:29 pm
[...] Jumping through loops with XSL [...]