Print numbers from one to one million

Question

Assume you have a highly synthetic task to print numbers from 1 to 1.000.000 without appropriate input XML. Of course, straight-forward recursion will fail due to, ironic enough, stack overflow.

I came up with the solution listed below:

<?xml version="1.0" encoding="UTF-8"?>
<xsl:stylesheet version="1.0" xmlns:xsl="http://www.w3.org/1999/XSL/Transform">
<xsl:output method="text"/>

<xsl:variable name="end" select="number(1000000)"/>

<xsl:template match="/">    
    <xsl:call-template name="batches"/>
</xsl:template>

<xsl:template name="batches">
    <xsl:param name="start" select="number(1)"/>
    <xsl:param name="stop" select="$end"/>
    <xsl:param name="ololo"/>

    <xsl:if test="$start &lt;= ($end)">
        <xsl:choose>
            <xsl:when test="$stop = 0">
                <xsl:value-of select="$start"/>:<xsl:value-of select="$ololo"/>
                <xsl:text>&#xa;</xsl:text>
            </xsl:when>
            <xsl:otherwise>
                <xsl:call-template name="batches">
                    <xsl:with-param name="start" select="$start"/> 
                    <xsl:with-param name="stop" select="floor($stop div 2)"/>
                    <xsl:with-param name="ololo" select=" 'A' "/>
                </xsl:call-template>
                <xsl:call-template name="batches">
                    <xsl:with-param name="start" select="floor($stop div 2) + $start + 1"/>
                    <xsl:with-param name="stop" select="floor($stop div 2)"/>
                    <xsl:with-param name="ololo" select=" 'B' "/>
                </xsl:call-template>
            </xsl:otherwise>
        </xsl:choose>
    </xsl:if>
</xsl:template>

</xsl:stylesheet>

It works both in libxslt and MSXML. But it prints some duplicate numbers and looks quite awkward in terms of efficiency. Can this be improved somehow?

Answer 1

Here is a generic "iterate" template that performs an action on an initial input and then on its result, until a given condition is specified.

This transformation is tail-recursive and works without stack overflow with an intelligent XSLT processor:

<xsl:stylesheet version="1.0"
 xmlns:xsl="http://www.w3.org/1999/XSL/Transform"
 xmlns:my="my:my">
 <xsl:output method="text"/>

 <my:action>
   <end>1000000</end>
 </my:action>

 <xsl:variable name="vAction"
      select="document('')/*/my:action"/>

 <xsl:template match="/">
  <xsl:call-template name="iterate">
   <xsl:with-param name="pAction" select="$vAction"/>
   <xsl:with-param name="pInput" select="0"/>
  </xsl:call-template>
 </xsl:template>

 <xsl:template name="iterate">
   <xsl:param name="pAction"/>
   <xsl:param name="pInput"/>

   <xsl:if test="string-length($pInput)">
       <xsl:variable name="vResult">
         <xsl:apply-templates select="$pAction">
           <xsl:with-param name="pInput" select="$pInput"/>
         </xsl:apply-templates>
       </xsl:variable>

       <xsl:copy-of select="$vResult"/>

       <xsl:call-template name="iterate">
         <xsl:with-param name="pAction"
              select="$pAction"/>
         <xsl:with-param name="pInput" select="$vResult"/>
       </xsl:call-template>
   </xsl:if>
 </xsl:template>

 <xsl:template match="my:action">
  <xsl:param name="pInput" select="0"/>

  <xsl:if test="not($pInput >= end)">
   <xsl:value-of select="concat($pInput+1,'&#xA;')"/>
  </xsl:if>
 </xsl:template>
</xsl:stylesheet>

when this transformation is applied on any XML document (not used), an intelligent XSLT processor that optimizes tail recursion into iteration produces the wanted result without stack overflow. This is the case with Saxon 6.5.4, which I used to produce the result.

Your problem is that not all XSLT processors recognize and optimize tail-recursion.

For such processors, one can use DVC - style recursion:

<xsl:stylesheet version="1.0"
 xmlns:xsl="http://www.w3.org/1999/XSL/Transform">
 <xsl:output method="text"/>

 <xsl:template match="/">
  <xsl:call-template name="displayNumbers">
    <xsl:with-param name="pStart" select="1"/>
    <xsl:with-param name="pEnd" select="1000000"/>
  </xsl:call-template>
 </xsl:template>

 <xsl:template name="displayNumbers">
  <xsl:param name="pStart"/>
  <xsl:param name="pEnd"/>

  <xsl:if test="not($pStart > $pEnd)">
   <xsl:choose>
    <xsl:when test="$pStart = $pEnd">
      <xsl:value-of select="$pStart"/>
      <xsl:text>&#xA;</xsl:text>
    </xsl:when>
    <xsl:otherwise>
      <xsl:variable name="vMid" select=
       "floor(($pStart + $pEnd) div 2)"/>
      <xsl:call-template name="displayNumbers">
       <xsl:with-param name="pStart" select="$pStart"/>
       <xsl:with-param name="pEnd" select="$vMid"/>
      </xsl:call-template>
      <xsl:call-template name="displayNumbers">
       <xsl:with-param name="pStart" select="$vMid+1"/>
       <xsl:with-param name="pEnd" select="$pEnd"/>
      </xsl:call-template>
    </xsl:otherwise>
   </xsl:choose>
  </xsl:if>
 </xsl:template>
</xsl:stylesheet>

this transformation produces the correct result without any crash using MSXML4.

With this DVC transformation the maximum recursion-depth is only Log2(N) -- in this case 19.

I would recommend using the FXSL library. It provides DVC variants of commonly used higher-order functions, such as foldl() and map() making it possible to produce the DVC variant of almost any recursive algorithm.

Of course, in XSLT2.0 one would simply write:

<xsl:sequence select="1 to 1000000"/>