RSS 2.0
Sign In
# Wednesday, February 20, 2008

Building jxom stylesheets I've learned what is a "good" and "bad" recursion from the saxon's perspective.

I'm using control tokens $t:indent and $t:unindent to control indentation in the sequence of tokens defining java output. To build output lines I need to calculate total indentation for each line. This can be done using cummulative sum, considering $t:indent as +1 and $t:unindent as -1.

This task can be formalized as "calculate cummulative integer sum".

The first approach I've tested is non recursive: "for $i in 1 to count($items) return sum(subsequence($items, 1, $i))".
It is incredibly slow.

The next try was recurrent: calculate and spew results as they are calculated.
This is "crash fast" method. Saxon, indeed, implements this as recursion and arrives to a stack limit early.

The last approach, employes saxon's ability to detect some particular flavour of tail calls. When function contains a tail call, and the output on a tail call code path consists of this tail call only, then saxon transforms such construction into a cycle. Thus I need to accumulate result and pass it down to a tail call chain and output it on the last opportunity only.

The following sample shows this technique:

<?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"
  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"/>

    <result>
      <sum>
        <xsl:value-of select="t:cumulative-integer-sum($values)"/>

        <!-- This call crashes with stack overflow. -->
        <!-- <xsl:value-of select="t:bad-cumulative-integer-sum($values)"/> -->

        <!-- To compare speed uncomment following lines. -->
        <!--<xsl:value-of select="sum(t:cumulative-integer-sum($values))"/>-->
        <!--<xsl:value-of select="sum(t:slow-cumulative-integer-sum($values))"/>-->
      </sum>
    </result>
  </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*"/>

    <xsl:sequence select="t:cumulative-integer-sum-impl($items, 1, 0, ())"/>
  </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*"/>

    <xsl:variable name="item" as="xs:integer?" select="$items[$index]"/>

    <xsl:choose>
      <xsl:when test="empty($item)">
        <xsl:sequence select="$result"/>
      </xsl:when>
      <xsl:otherwise>
        <xsl:variable name="value" as="xs:integer" select="$item + $sum"/>
        <xsl:variable name="next" as="xs:integer+" select="$result, $value"/>

        <xsl:sequence select="
          t:cumulative-integer-sum-impl($items, $index + 1, $value, $next)"/>
      </xsl:otherwise>
    </xsl:choose>
  </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*"/>

    <xsl:sequence select="t:bad-cumulative-integer-sum-impl($items, 1, 0)"/>
  </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"/>

    <xsl:variable name="item" as="xs:integer?" select="$items[$index]"/>

    <xsl:if test="exists($item)">
      <xsl:variable name="value" as="xs:integer" select="$item + $sum"/>
 
      <xsl:sequence select="$value"/>
      <xsl:sequence select="
        t:bad-cumulative-integer-sum-impl($items, $index + 1, $value)"/>
    </xsl:if>
  </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>

Wednesday, February 20, 2008 8:59:22 AM UTC  #    Comments [0] -
xslt
Archive
<December 2024>
SunMonTueWedThuFriSat
24252627282930
1234567
891011121314
15161718192021
22232425262728
2930311234
Statistics
Total Posts: 387
This Year: 3
This Month: 0
This Week: 0
Comments: 1984
Locations of visitors to this page
Disclaimer
The opinions expressed herein are our own personal opinions and do not represent our employer's view in anyway.

© 2024, Nesterovsky bros
All Content © 2024, Nesterovsky bros
DasBlog theme 'Business' created by Christoph De Baene (delarou)