Learn how easy it is to sync an existing GitHub or Google Code repo to a SourceForge project! See Demo

Close

Tail call optimization

2008-07-04
2012-10-08
  • Hello Mr Kay!

    Would you please share you thoughts on logic behind of decision to make tail call optimization using the following example, showing two implementations of a same algorithms. For the t:cumulative-integer-sum-impl() tail call is used, for the t:bad-cumulative-integer-sum-impl() - no.

    <?xml version="1.0" encoding="utf-8"?>
    <xsl:stylesheet version="2.0"
    xmlns:xsl="http://www.w3.org/1999/XSL/Transform"
    xmlns:xs="http://www.w3.org/2001/XMLSchema"
    xmlns:t="http://www.nesterovsky-bros.com/weblog/2008/02/20/EfficientXslt20RecursionInSaxon9.aspx"
    exclude-result-prefixes="xs t">

    <xsl:output method="xml" indent="yes"/>

    <xsl:template match="/">
    <xsl:variable name="values" as="xs:integer*" select="1 to 10000"/>

    &lt;result&gt;
      &lt;sum&gt;
        &lt;xsl:value-of select=&quot;t:cumulative-integer-sum($values)&quot;/&gt;
    
        &lt;!-- This call crashes with stack overflow. --&gt;
        &lt;!--
        &lt;xsl:value-of select=&quot;t:bad-cumulative-integer-sum($values)&quot;/&gt;
        --&gt;
    
        &lt;!-- To compare speed uncomment following lines. --&gt;
        &lt;!--&lt;xsl:value-of select=&quot;sum(t:cumulative-integer-sum($values))&quot;/&gt;--&gt;
        &lt;!--&lt;xsl:value-of select=&quot;sum(t:slow-cumulative-integer-sum($values))&quot;/&gt;--&gt;
      &lt;/sum&gt;
    &lt;/result&gt;
    

    </xsl:template>

    <!--
    Calculates cumulative sum of integer sequence.
    $items - input integer sequence.
    Returns an integer sequence that is a cumulative sum of original sequence.
    -->
    <xsl:function name="t:cumulative-integer-sum" as="xs:integer">
    <xsl:param name="items" as="xs:integer
    "/>

    &lt;xsl:sequence select=&quot;t:cumulative-integer-sum-impl($items, 1, 0, ())&quot;/&gt;
    

    </xsl:function>

    <!--
    Implementation of the t:cumulative-integer-sum.
    $items - input integer sequence.
    $index - current iteration index.
    $sum - base sum.
    $result - collected result.
    Returns an integer sequence that is a cumulative sum of original sequence.
    -->
    <xsl:function name="t:cumulative-integer-sum-impl" as="xs:integer">
    <xsl:param name="items" as="xs:integer
    "/>
    <xsl:param name="index" as="xs:integer"/>
    <xsl:param name="sum" as="xs:integer"/>
    <xsl:param name="result" as="xs:integer*"/>

    &lt;xsl:variable name=&quot;item&quot; as=&quot;xs:integer?&quot; select=&quot;$items[$index]&quot;/&gt;
    
    &lt;xsl:choose&gt;
      &lt;xsl:when test=&quot;empty($item)&quot;&gt;
        &lt;xsl:sequence select=&quot;$result&quot;/&gt;
      &lt;/xsl:when&gt;
      &lt;xsl:otherwise&gt;
        &lt;xsl:variable name=&quot;value&quot; as=&quot;xs:integer&quot; select=&quot;$item + $sum&quot;/&gt;
        &lt;xsl:variable name=&quot;next&quot; as=&quot;xs:integer+&quot; select=&quot;$result, $value&quot;/&gt;
    
        &lt;xsl:sequence select=&quot;
          t:cumulative-integer-sum-impl($items, $index + 1, $value, $next)&quot;/&gt;
      &lt;/xsl:otherwise&gt;
    &lt;/xsl:choose&gt;
    

    </xsl:function>

    <!-- "Bad" implementation of the cumulative-integer-sum. -->
    <xsl:function name="t:bad-cumulative-integer-sum" as="xs:integer">
    <xsl:param name="items" as="xs:integer
    "/>

    &lt;xsl:sequence select=&quot;t:bad-cumulative-integer-sum-impl($items, 1, 0)&quot;/&gt;
    

    </xsl:function>

    <!-- "Bad" implementation of the cumulative-integer-sum. -->
    <xsl:function name="t:bad-cumulative-integer-sum-impl" as="xs:integer">
    <xsl:param name="items" as="xs:integer
    "/>
    <xsl:param name="index" as="xs:integer"/>
    <xsl:param name="sum" as="xs:integer"/>

    &lt;xsl:variable name=&quot;item&quot; as=&quot;xs:integer?&quot; select=&quot;$items[$index]&quot;/&gt;
    
    &lt;xsl:if test=&quot;exists($item)&quot;&gt;
      &lt;xsl:variable name=&quot;value&quot; as=&quot;xs:integer&quot; select=&quot;$item + $sum&quot;/&gt;
    
      &lt;xsl:sequence select=&quot;$value&quot;/&gt;
      &lt;xsl:sequence select=&quot;
        t:bad-cumulative-integer-sum-impl($items, $index + 1, $value)&quot;/&gt;
    &lt;/xsl:if&gt;
    

    </xsl:function>

    <!-- Non recursive implementation of the cumulative-integer-sum. -->
    <xsl:function name="t:slow-cumulative-integer-sum" as="xs:integer">
    <xsl:param name="items" as="xs:integer
    "/>

    <xsl:sequence select="
    for $i in 1 to count($items) return
    sum(subsequence($items, 1, $i))"/>
    </xsl:function>

    </xsl:stylesheet>

    I hoped t:bad-cumulative-integer-sum-impl() to be optimized in version 9.1, as it looks like it could stream results immediately, in contrast to t:cumulative-integer-sum-impl(), which collects result.

    Thanks.

     
    • Michael Kay
      Michael Kay
      2008-07-04

      Currently functions are not marked tail-recursive if there is any kind of operation performed on the result of the recursive call. In this case there is a sequence-concatenation operation (implicit in the use of two xsl:sequence calls).

      Intrinsically it would be quite possible to do tail-call optimization in this case (there's a TODO in net.sf.saxon.instruct.Block suggesting this); it's just work that needs to be done.

      In fact tail-call optimization on templates will handle this case. That case is slightly different because templates are always evaluated in push mode (using the process() method), and tail call optimization there is entirely a run-time matter, whereas for functions there is a compile-time rewrite into a loop. Another effect of this difference is that mutual recursion (t->s->t) is optimized for templates but not for functions.

      Michael Kay
      http://www.saxonica.com/