Tail call optimization
Added by Anonymous about 16 years ago
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.
Replies (1)
RE: Tail call optimization
-
Added by Anonymous about 16 years ago
Legacy ID: #5073129 Legacy Poster: Michael Kay (mhkay)
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/
Please register to reply