Simple tail call optimisation in Saxon/XSLT

Question

I'm running Saxon-EE 11.4 (I'm running inside Oxygen with saxon optimisations on - that may be relevant)

<xsl:stylesheet xmlns:xsl="http://www.w3.org/1999/XSL/Transform"
    xmlns:xs="http://www.w3.org/2001/XMLSchema"
    exclude-result-prefixes="xs"
    version="3.0"
    xmlns:kooks="http://www.kookerella.com">
    
    <xsl:function name="kooks:pointlessLoop" as="xs:integer">
        <xsl:param name="n" as="xs:integer"/>
        <xsl:choose>
            <xsl:when test="$n = 0">
                <xsl:sequence select="$n"/>
            </xsl:when>
            <xsl:otherwise>
                <xsl:sequence select="kooks:pointlessLoop($n - 1)"/>
            </xsl:otherwise>
        </xsl:choose>
    </xsl:function>
    
    <xsl:template match="/">
        <xsl:sequence select="kooks:pointlessLoop(10000)"/>
    </xsl:template>    
</xsl:stylesheet>

this errors out with

System ID: Severity: error
Description: class java.lang.StackOverflowError

Its not clear to me if Saxon does or doesn't do tail call optimisation (there are various things published online, and a previous SO conversation about something that isn't tail recursive, so doesn't work, but I havent found anything to say it definitively does currently).

Assuming it does, what am I doing wrong? (I noted on a previous SO question that templates and functions can behave slightly differently, but I've tried this with a named template, and it also fails, it also fails with an 'apply-template' scenario recursively selecting the root node, though with a different error)

---

an update is that running this on the command line with saxon 11.4 does seem to work tail recursively, so my assumption is the issue is related to the integration between Saxon/Oxygen, presumably the saxon opimisation setting isnt being set.

Answer 1

I've tried in various Saxon 11.x and 12.x versions, both -HE and -EE, and tail call optimization is working just fine for this example. It may be something Oxygen is doing. But it also worked for me in Oxygen.

I did get a StackOverflow error in Oxygen if I switched Saxon optimizations off.

Answer 2

I can run the following code fine with Saxon HE 12.4:

<xsl:stylesheet xmlns:xsl="http://www.w3.org/1999/XSL/Transform"
    xmlns:xs="http://www.w3.org/2001/XMLSchema"
    exclude-result-prefixes="#all"
    version="3.0"
    xmlns:mf="http://example.com/mf">
    
    <xsl:function name="mf:pointlessLoop" as="xs:integer">
        <xsl:param name="n" as="xs:integer"/>
        <xsl:choose>
            <xsl:when test="$n = 0">
                <xsl:sequence select="$n"/>
            </xsl:when>
            <xsl:otherwise>
                <xsl:sequence select="mf:pointlessLoop($n - 1)"/>
            </xsl:otherwise>
        </xsl:choose>
    </xsl:function>
    
    <xsl:template match="/" name="xsl:initial-template">
        <xsl:sequence select="mf:pointlessLoop(100000)"/>
    </xsl:template>
    
</xsl:stylesheet>

The -explain output from Saxon HE 12.4 is

<stylesheet xmlns:fn="http://www.w3.org/2005/xpath-functions"
            xmlns:xs="http://www.w3.org/2001/XMLSchema">
   <globalVariables/>
   <mode onNo="TC" flags="dW" patternSlots="0">
      <ruleSet type="document-node()">
         <templateRule prec="0"
                       prio="-0.5"
                       seq="0"
                       rank="0"
                       minImp="0"
                       slots="0"
                       matches="ND"
                       flags="s"
                       line="19"
                       module="file:/C:/Users/marti/OneDrive/Documents/xslt/blog-xslt-3-by-example/tail-call-recursion/./simple-function1.xsl">
            <p.nodeTest role="match" test="ND"/>
            <ufCall role="action"
                    baseUri="file:/C:/Users/marti/OneDrive/Documents/xslt/blog-xslt-3-by-example/tail-call-recursion/./simple-function1.xsl"
                    ns="mf=http://example.com/mf xs=~ xsl=~"
                    line="20"
                    name="Q{http://example.com/mf}pointlessLoop"
                    tailCall="false"
                    bSlot="0">
               <int val="100000"/>
            </ufCall>
         </templateRule>
      </ruleSet>
   </mode>
   <namedTemplates>
      <template name="xsl:initial-template"
                line="19"
                module="file:/C:/Users/marti/OneDrive/Documents/xslt/blog-xslt-3-by-example/tail-call-recursion/./simple-function1.xsl">
         <ufCall baseUri="file:/C:/Users/marti/OneDrive/Documents/xslt/blog-xslt-3-by-example/tail-call-recursion/./simple-function1.xsl"
                 ns="mf=http://example.com/mf xs=~ xsl=~"
                 line="20"
                 name="Q{http://example.com/mf}pointlessLoop"
                 tailCall="false"
                 bSlot="0">
            <int val="100000"/>
         </ufCall>
      </template>
   </namedTemplates>
   <accumulators/>
   <functions>
      <function name="Q{http://example.com/mf}pointlessLoop"
                line="7"
                module="file:/C:/Users/marti/OneDrive/Documents/xslt/blog-xslt-3-by-example/tail-call-recursion/./simple-function1.xsl"
                flags="pU"
                as="1ADI"
                slots="1">
         <arg name="Q{}n" as="1ADI"/>
         <tailCallLoop role="body"
                       baseUri="file:/C:/Users/marti/OneDrive/Documents/xslt/blog-xslt-3-by-example/tail-call-recursion/./simple-function1.xsl"
                       ns="mf=http://example.com/mf xs=~ xsl=~"
                       line="9">
            <choose>
               <vc line="10" op="eq" onEmpty="0">
                  <varRef name="Q{}n" slot="0"/>
                  <int val="0"/>
               </vc>
               <varRef line="11" name="Q{}n" slot="0"/>
               <true/>
               <ufCall line="14"
                       name="Q{http://example.com/mf}pointlessLoop"
                       tailCall="self"
                       bSlot="0">
                  <arith op="-" calc="i-i">
                     <varRef name="Q{}n" slot="0"/>
                     <int val="1"/>
                  </arith>
               </ufCall>
            </choose>
         </tailCallLoop>
      </function>
   </functions>
</stylesheet>

Note the "tailCallLoop".

Online fiddle even working with CheerpJ 3.0 Java 8 to JavaScript/Webassembly runtime in the browser.

Also runs fine through SaxonCHE Python at the online test.

Based on that I would say tail call optimization happens.

Will need to check later with Saxon EE.

You do know that XSLT 3 has xsl:iterate? SaxonJS 2.6 doesn't seem to do tail call optimization for above example but fails with some "Maximum call stack size exceeded" while it runs an xsl:iterate example fine:

<xsl:stylesheet xmlns:xsl="http://www.w3.org/1999/XSL/Transform"
    xmlns:xs="http://www.w3.org/2001/XMLSchema"
    exclude-result-prefixes="#all"
    version="3.0"
    xmlns:mf="http://example.com/mf">
    
    <xsl:function name="mf:pointlessLoop" as="xs:integer">
        <xsl:param name="n" as="xs:integer"/>
        <xsl:iterate select="(0 to $n) => reverse()">
          <xsl:choose>
            <xsl:when test=". > 0">
              <xsl:next-iteration/>
            </xsl:when>
            <xsl:otherwise>
              <xsl:sequence select="."/>
            </xsl:otherwise>
          </xsl:choose>
        </xsl:iterate>
    </xsl:function>
    
    <xsl:template match="/" name="xsl:initial-template">
        <xsl:sequence select="mf:pointlessLoop(100000)"/>
    </xsl:template>
    
</xsl:stylesheet>