It is wellknown that recursion is one of the main techniques associated with the functional programming style and this goes hand-in-hand with the principles that variables are immutable and once defined their values cannot be reassigned.  

Using recursion is elegant and beautiful most of the time, but it can have its drawbacks, too. One is that processing a long (with length N) list of items  the system may crash due to call-stack overflow. Depending on the available amount of memory and the specific language/runtime parameters this may happen at different recursion depths, but as a rule on a typical computer call-stack overflow is most often observed when N >= 1000.  

Thus, for any practical functional programming applications it is of paramount importance to be able to avoid call-stack overflows. There are two main ways of solving this problem: tail-recursion optimization and the DVC (Divide and Conquer) principle. Today I’d discuss tail-recursion optimization and the state of this technique in some existing and wellknown XSLT (2.0 or 1.0) processors.

Definition(Wikipedia): "Tail recursion (or tail-end recursion) is a special case of recursion that can be easily transformed into an iteration. Such a transformation is possible if the recursive call is the last thing that happens in a function".  

Transforming recursion into iteration (similar to a C-like "for" or "while" loop) not only completely eliminates the possibility of call-stack overflow, but also often leads to lightning-fast resulting code.  

This month I have been playing with an XSLT 2.0 implementation of a simple general LR parser as described in the Wikipedia. The implementation was straightforward and simple enough and the code was very short and compact. What was best, I had a tail-recursive variant of my code! Tested with Saxon 8.7.3 it also ran extremely fast, dispelling any doubts that XSLT Might not be the best language to use for such kind of processing.

Before starting to implement my XSLT 2.0 and XPath 2.0 parsers written in XSLT 2.0 (  :oO)  ) I needed to run a simple experiment just to be sure I was on the safe side from the very start. I needed to verify that Saxon will indeed recognize the tail-recursion and optimize it, so that it would always be possible to parse very long "sentences" described by a particular grammar. I started doubling the length (number of terminal symbols) of the input and unfortunately! and completely to my horror Saxon crashed with the dreaded "stack overflow" exception when the length reached 1600.  

Imagine my ("mixed" to put it mildly) feelings.  

I reported the issue to the saxon-help mailing list. Got assurances from Dr. Kay that he would look into the issue. Sent him the tail-recursive variant of my code. Then waited. As of today, the issue is not listed in the tracker for the Saxon project. I know that Dr. Kay is a busy person and during this time period he had been involved in the final stages of making the XSLT 2.0 spec an official W3C Recommendation — something really a lot more important.  I believe that sooner or later this issue will be fixed in Saxon.

Anyway, I did try the other two known XSLT 2.0 implementations — Altova and Gexslt. Both failed the same way as Saxon.  

Then I decided to test a much more simple XSLT tail-recursive application — both on available XSLT 1.0 and XSLT 2.0 processors. The code to produce the sum of the numbers 1,2,3,…, N

where N=1000000 (one million) is listed below:

<xsl:stylesheet version="2.0" 
 xmlns:xsl="http://www.w3.org/1999/XSL/Transform"                
 xmlns:xs="http://www.w3.org/2001/XMLSchema" 
 xmlns:f="http://fxsl.sf.net/" 
 > 
 <xsl:output method="text"/>

      <xsl:template match="/"> 
        <xsl:sequence select="f:sum(0, 1, 1000000)"/> 
      </xsl:template>      

      <xsl:function name="f:sum"> 
        <xsl:param name="pAccumulated" as="xs:integer"/> 
        <xsl:param name="pFrom" as="xs:integer"/> 
        <xsl:param name="pTo" as="xs:integer"/>        

        <xsl:sequence select= 
         "if($pFrom gt $pTo) 
            then $pAccumulated 
            else                                            
              f:sum($pAccumulated + $pFrom, $pFrom + 1, $pTo) 
         " 
         /> 
      </xsl:function>
</xsl:stylesheet>

This transformation runs with Saxon 8.7.3 (J) for about 2.5 to 3 seconds. Altova crashes with stack overflow again.

The case with Gexslt was more complicated — it was processing this transformation for a very long time (more than 2 minutes CPU) and was gradually consuming all the memory of the computer.

I tried a similar, template-based transformation with a number of XSLT 1.0 processors. As it happens, .NET 2.0 XslCompiledTransform is the champion in this group, producing the correct result almost instantaneously.

I want to finish this story in an optimistic tone.

I contacted Colin-Paul Adams — the author/developer of Gexslt and he responded very quickly. Both the LR-parsing tail-recursion and the sum() tail recursion problem were fixed in a couple of days.

So, it appears that right at this moment Gexslt handles correctly and much better some kinds of tail-recursive transformations (such as of the LR-parsing type) than any other available XSLT 2.0 processor.

This is the beauty of having more than one competing products. Many thanks to Colin!