Saxon

Legacy ID: #5072828 Legacy Poster: Vladimir Nesterovsky (vnesterovsky)

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