XSLT/Saxon 中的尾调用优化？
Tail Call Optimization in XSLT/Saxon?
谁能解释为什么下面的代码会发生堆栈溢出？我曾希望 Saxon 将模板识别为尾递归，并对其进行优化，从而允许进行大量迭代——实际上，它会在大约 1000 次迭代后发生堆栈溢出。我按照以下执行：
me@server:~/dev$ java -classpath /usr/local/share/java/saxon9ee.jar net.sf.saxon.Transform -it -xsl:recurse.xslt
437
Exception in thread "main" java.lang.WhosebugError
at net.sf.saxon.expr.instruct.ParameterSet.getIndex(ParameterSet.java:127)
at net.sf.saxon.expr.XPathContextMajor.useLocalParameter(XPathContextMajor.java:561)
at EE_sequence_02125238280.process(file:/home/me/dev/recurse.xslt:23)
at com.saxonica.ee.bytecode.CompiledExpression.process(CompiledExpression.java:84)
at com.saxonica.ee.bytecode.ByteCodeCandidate.process(ByteCodeCandidate.java:143)
at com.saxonica.ee.bytecode.ByteCodeCandidate.processLeavingTail(ByteCodeCandidate.java:178)
at net.sf.saxon.expr.instruct.NamedTemplate.expand(NamedTemplate.java:263)
at EE_sequence_02125238280.process(file:/home/me/dev/recurse.xslt:23)
and so on.....
我正在使用 Saxon-EE 9.8.0.15J。
我已经尝试使用 <xsl:if>、XPATH 和函数，在几个变体中代替 <xsl:choose> - 但我遇到了同样的问题。
使用 call-templates 我实际上可以在网上找到建议这应该有效的评论，下面的示例与我的类似。我不是 100% 清楚 XPATH 表达式中的函数或递归调用是否受支持，因此我在这个例子中坚持使用 call-templates。
例如：Recursive Loop XSLT
我想我错过了一个技巧 - 有什么想法吗？
<?xml version="1.0" encoding="UTF-8"?>
<xsl:stylesheet version="3.0" xmlns:xsl="http://www.w3.org/1999/XSL/Transform" xmlns:xs="http://www.w3.org/2001/XMLSchema" xmlns:map="http://www.w3.org/2005/xpath-functions/map" exclude-result-prefixes="xs map">
<xsl:output method="text" version="1.0" encoding="UTF-8" indent="yes"/>
<xsl:template name="xsl:initial-template">
<xsl:variable name="freqs" select="unparsed-text-lines('input.txt', 'UTF-8')!xs:integer(.)"/>
<xsl:message select="sum($freqs)"/>
<xsl:variable name="hash" select="map{}" as="map(xs:integer, xs:boolean)"/>
<xsl:call-template name="find-repeated-cs">
<xsl:with-param name="freqs" select="$freqs"/>
<xsl:with-param name="cs-hash" select="$hash"/>
</xsl:call-template>
</xsl:template>
<xsl:template name="find-repeated-cs">
<xsl:param name="freqs" as="xs:integer*"/>
<xsl:param name="cs-hash" as="map(xs:integer, xs:boolean)"/>
<xsl:param name="cs" select="0" as="xs:integer"/>
<xsl:param name="i" select="1" as="xs:integer"/>
<xsl:variable name="new-cs" select="$cs + $freqs[$i]" as="xs:integer"/>
<xsl:variable name="new-i" select="if ($i >= count($freqs)) then 1 else $i + 1" as="xs:integer"/>
<xsl:choose>
<xsl:when test="map:contains($cs-hash, $new-cs)">
<xsl:value-of select="$new-cs"/>
</xsl:when>
<xsl:otherwise>
<xsl:call-template name="find-repeated-cs">
<xsl:with-param name="freqs" select="$freqs"/>
<xsl:with-param name="cs-hash" select="map:put($cs-hash,$new-cs,true())"/>
<xsl:with-param name="cs" select="$new-cs"/>
<xsl:with-param name="i" select="$new-i"/>
</xsl:call-template>
</xsl:otherwise>
</xsl:choose>
</xsl:template>
</xsl:stylesheet>
编辑
对于一些上下文，代码在累积和序列中找到第 2 次出现的数字，该序列是通过重复循环一组固定整数 freqs 生成的。最新的累计和是cs，在cs-hash中建立了过去看到的累计和的字典。 i 索引 freq 作为循环 index/counter。
如果我的方法很愚蠢，我也对其他方法感兴趣，但我仍然想了解为什么无法优化此代码 - 即使有更好的方法。
编辑 2
为了完整性，函数实现使用 xsl:choose:
<?xml version="1.0" encoding="UTF-8"?>
<xsl:stylesheet version="3.0" xmlns:xsl="http://www.w3.org/1999/XSL/Transform" xmlns:xs="http://www.w3.org/2001/XMLSchema" xmlns:map="http://www.w3.org/2005/xpath-functions/map" xmlns:aoc2018="\
http://www.blah.co.uk/aoc2018" exclude-result-prefixes="xs map aoc2018">
<!-- hint: java -classpath /usr/local/share/java/saxon9ee.jar net.sf.saxon.Transform -it -xsl:01.xslt -->
<xsl:function name="aoc2018:find-repeated-cs">
<xsl:param name="freqs" as="xs:integer*"/>
<xsl:param name="cs-hash" as="map(xs:integer, xs:boolean)"/>
<xsl:param name="cs" as="xs:integer"/>
<xsl:param name="i" as="xs:integer"/>
<xsl:variable name="new-cs" select="$cs + $freqs[$i]" as="xs:integer"/>
<xsl:choose>
<xsl:when test="map:contains($cs-hash, $new-cs)">
<xsl:value-of select="$new-cs"/>
</xsl:when>
<xsl:otherwise>
<xsl:variable name="new-i" select="if ($i >= count($freqs))
then 1
else $i + 1" as="xs:integer"/>
<xsl:value-of select="aoc2018:find-repeated-cs($freqs, map:put($cs-hash,$new-cs,true()), $new-cs, $new-i)"/>
</xsl:otherwise>
</xsl:choose>
</xsl:function>
<xsl:output method="text" version="1.0" encoding="UTF-8" indent="yes"/>
<xsl:template name="xsl:initial-template">
<xsl:variable name="freqs" select="unparsed-text-lines('input.txt', 'UTF-8')!xs:integer(.)"/>
<xsl:message select="sum($freqs)"/>
<xsl:variable name="hash" select="map{}" as="map(xs:integer, xs:boolean)"/>
<xsl:message select="aoc2018:find-repeated-cs($freqs, $hash, 0, 1)"/>
</xsl:template>
</xsl:stylesheet>
以及使用 XPATH 的函数实现：
<?xml version="1.0" encoding="UTF-8"?>
<xsl:stylesheet version="3.0" xmlns:xsl="http://www.w3.org/1999/XSL/Transform" xmlns:xs="http://www.w3.org/2001/XMLSchema" xmlns:map="http://www.w3.org/2005/xpath-functions/map" xmlns:aoc2018="\
http://www.blah.co.uk/aoc2018" exclude-result-prefixes="xs map aoc2018">
<!-- hint: java -classpath /usr/local/share/java/saxon9ee.jar net.sf.saxon.Transform -it -xsl:01.xslt -->
<xsl:function name="aoc2018:find-repeated-cs">
<xsl:param name="freqs" as="xs:integer*"/>
<xsl:param name="cs-hash" as="map(xs:integer, xs:boolean)"/>
<xsl:param name="cs" as="xs:integer"/>
<xsl:param name="i" as="xs:integer"/>
<xsl:variable name="new-cs" select="$cs + $freqs[$i]" as="xs:integer"/>
<xsl:variable name="new-i" select="if ($i >= count($freqs))
then 1
else $i + 1" as="xs:integer"/>
<xsl:value-of select="if (map:contains($cs-hash, $new-cs))
then $new-cs
else aoc2018:find-repeated-cs($freqs, map:put($cs-hash,$new-cs,true()), $new-cs, $new-i)"/>
</xsl:function>
<xsl:output method="text" version="1.0" encoding="UTF-8" indent="yes"/>
<xsl:template name="xsl:initial-template">
<xsl:variable name="freqs" select="unparsed-text-lines('input.txt', 'UTF-8')!xs:integer(.)"/>
<xsl:message select="sum($freqs)"/>
<xsl:variable name="hash" select="map{}" as="map(xs:integer, xs:boolean)"/>
<xsl:message select="aoc2018:find-repeated-cs($freqs, $hash, 0, 1)"/>
</xsl:template>
</xsl:stylesheet>
已确认这在 9.9 下有效（使用尾递归），无论是否启用字节码生成，但在 9.8 下，只有关闭字节码生成才能成功。我认为这些版本之间的区别在于 9.9 在决定不使用字节码生成时会更聪明，因为它会干扰尾递归。
要了解为什么在使用函数调用而不是模板时失败，我需要查看代码。这两种情况在内部使用不同的机制。特别是函数默认在 "pull" 模式下求值（它们 return 是结果的迭代器），模板在 "push" 模式下（它们将结果写入结果树）。最显着的区别是 returning 包含递归调用结果的序列（例如 select="$x, f:myself($x - 1)）可以使用模板以尾递归方式完成，但不能使用函数。但这似乎不适用于您的情况。此外，对于模板，我们处理两个或多个模板的相互递归，而对于函数，我们只处理自递归。
以下版本似乎可以使用尾递归使用 9.8 或 9.9，无论是否生成字节码。 （虽然在 9.8 下，有一个我没有时间研究的奇怪之处：在产生输出值之后，进程实际上并没有退出。）
<?xml version="1.0" encoding="UTF-8"?>
<xsl:stylesheet version="3.0" xmlns:xsl="http://www.w3.org/1999/XSL/Transform" xmlns:xs="http://www.w3.org/2001/XMLSchema"
xmlns:map="http://www.w3.org/2005/xpath-functions/map" xmlns:f="f" exclude-result-prefixes="#all">
<xsl:output method="text" version="1.0" encoding="UTF-8" indent="yes"/>
<xsl:param name="limit" select="2000"/>
<xsl:template name="xsl:initial-template">
<xsl:variable name="freqs" select="1 to $limit"/>
<xsl:message select="sum($freqs)"/>
<xsl:variable name="hash" select="map{}" as="map(xs:integer, xs:boolean)"/>
<xsl:sequence select="f:find-repeated-cs($freqs, $hash, 0, 1)"/>
</xsl:template>
<xsl:function name="f:find-repeated-cs">
<xsl:param name="freqs" as="xs:integer*"/>
<xsl:param name="cs-hash" as="map(xs:integer, xs:boolean)"/>
<xsl:param name="cs" as="xs:integer"/>
<xsl:param name="i" as="xs:integer"/>
<xsl:variable name="new-cs" select="$cs + $freqs[$i]" as="xs:integer"/>
<xsl:variable name="new-i" select="if ($i >= count($freqs)) then 1 else $i + 1" as="xs:integer"/>
<xsl:choose>
<xsl:when test="map:contains($cs-hash, $new-cs)">
<xsl:value-of select="$new-cs"/>
</xsl:when>
<xsl:otherwise>
<xsl:sequence select="f:find-repeated-cs($freqs, map:put($cs-hash,$new-cs,true()), $new-cs, $new-i)"/>
</xsl:otherwise>
</xsl:choose>
</xsl:function>
</xsl:stylesheet>
更新
实际上，当我说它有效时，我的意思是它不会因堆栈溢出而失败。进一步检查表明它实际上并没有终止——似乎终止条件永远不会为真。我还没有尝试找出原因。
在您的代码中，您使用 <xsl:value-of> 来 return 函数结果，而不是 xsl:sequence。 xsl:value-of 传递一个文本节点，它需要从递归调用的结果中构建：你可以在 -explain 输出中看到：
<function name="Q{http://www.blah.co.uk/aoc2018}find-repeated-cs"
line="5"
module="file:/Users/mike/Desktop/temp/test.xsl"
eval="9"
flags="pU"
as="item()*"
slots="6">
<arg name="Q{}freqs" as="xs:integer*"/>
<arg name="Q{}cs-hash" as="map(xs:integer, xs:boolean)"/>
<arg name="Q{}cs" as="xs:integer"/>
<arg name="Q{}i" as="xs:integer"/>
<let role="body"
baseUri="file:/Users/mike/Desktop/temp/test.xsl"
ns="xsl=~ aoc2018=http://www.blah.co.uk/aoc2018 xs=~ map=~"
line="10"
var="Q{}new-cs"
as="xs:integer"
slot="4"
eval="16">
<check card="1" diag="3|0|XTTE0570|new-cs">
<arith op="+" calc="i+i">
<varRef name="Q{}cs" slot="2"/>
<subscript>
<varRef name="Q{}freqs" slot="0"/>
<varRef name="Q{}i" slot="3"/>
</subscript>
</arith>
</check>
<let line="13" var="Q{}new-i" as="xs:integer" slot="5" eval="16">
<choose>
<vc op="ge" onEmpty="0" comp="CAVC">
<varRef name="Q{}i" slot="3"/>
<fn name="count">
<varRef name="Q{}freqs" slot="0"/>
</fn>
</vc>
<int val="1"/>
<true/>
<arith op="+" calc="i+i">
<varRef name="Q{}i" slot="3"/>
<int val="1"/>
</arith>
</choose>
<valueOf line="16">
<fn name="string-join">
<convert from="xs:anyAtomicType" to="xs:string">
<choose>
<ifCall name="Q{http://www.w3.org/2005/xpath-functions/map}contains"
type="xs:boolean">
<varRef name="Q{}cs-hash" slot="1"/>
<varRef name="Q{}new-cs" slot="4"/>
</ifCall>
<varRef name="Q{}new-cs" slot="4"/>
<true/>
<data>
<mergeAdj>
<ufCall name="Q{http://www.blah.co.uk/aoc2018}find-repeated-cs"
tailCall="false"
bSlot="0"
eval="6 16 6 6">
<varRef name="Q{}freqs" slot="0"/>
<treat as="map(xs:integer, xs:boolean)" diag="0|1||aoc2018:find-repeated-cs">
<ifCall name="Q{http://www.w3.org/2005/xpath-functions/map}put" type="map(*)">
<varRef name="Q{}cs-hash" slot="1"/>
<varRef name="Q{}new-cs" slot="4"/>
<true/>
</ifCall>
</treat>
<varRef name="Q{}new-cs" slot="4"/>
<varRef name="Q{}new-i" slot="5"/>
</ufCall>
</mergeAdj>
</data>
</choose>
</convert>
<str val=" "/>
</fn>
</valueOf>
</let>
</let>
</function>
因为函数结果还需要做进一步的操作（即转为文本节点，需要将结果原子化，将结果中的项转为字符串，并用空格分隔）所以函数为不是尾递归的。始终使用 xsl:sequence 到 return 函数结果，并始终声明函数的结果类型和参数类型。
谁能解释为什么下面的代码会发生堆栈溢出？我曾希望 Saxon 将模板识别为尾递归，并对其进行优化，从而允许进行大量迭代——实际上，它会在大约 1000 次迭代后发生堆栈溢出。我按照以下执行：
me@server:~/dev$ java -classpath /usr/local/share/java/saxon9ee.jar net.sf.saxon.Transform -it -xsl:recurse.xslt
437
Exception in thread "main" java.lang.WhosebugError
at net.sf.saxon.expr.instruct.ParameterSet.getIndex(ParameterSet.java:127)
at net.sf.saxon.expr.XPathContextMajor.useLocalParameter(XPathContextMajor.java:561)
at EE_sequence_02125238280.process(file:/home/me/dev/recurse.xslt:23)
at com.saxonica.ee.bytecode.CompiledExpression.process(CompiledExpression.java:84)
at com.saxonica.ee.bytecode.ByteCodeCandidate.process(ByteCodeCandidate.java:143)
at com.saxonica.ee.bytecode.ByteCodeCandidate.processLeavingTail(ByteCodeCandidate.java:178)
at net.sf.saxon.expr.instruct.NamedTemplate.expand(NamedTemplate.java:263)
at EE_sequence_02125238280.process(file:/home/me/dev/recurse.xslt:23)
and so on.....
我正在使用 Saxon-EE 9.8.0.15J。
我已经尝试使用 <xsl:if>、XPATH 和函数，在几个变体中代替 <xsl:choose> - 但我遇到了同样的问题。
使用 call-templates 我实际上可以在网上找到建议这应该有效的评论，下面的示例与我的类似。我不是 100% 清楚 XPATH 表达式中的函数或递归调用是否受支持，因此我在这个例子中坚持使用 call-templates。
例如：Recursive Loop XSLT
我想我错过了一个技巧 - 有什么想法吗？
<?xml version="1.0" encoding="UTF-8"?>
<xsl:stylesheet version="3.0" xmlns:xsl="http://www.w3.org/1999/XSL/Transform" xmlns:xs="http://www.w3.org/2001/XMLSchema" xmlns:map="http://www.w3.org/2005/xpath-functions/map" exclude-result-prefixes="xs map">
<xsl:output method="text" version="1.0" encoding="UTF-8" indent="yes"/>
<xsl:template name="xsl:initial-template">
<xsl:variable name="freqs" select="unparsed-text-lines('input.txt', 'UTF-8')!xs:integer(.)"/>
<xsl:message select="sum($freqs)"/>
<xsl:variable name="hash" select="map{}" as="map(xs:integer, xs:boolean)"/>
<xsl:call-template name="find-repeated-cs">
<xsl:with-param name="freqs" select="$freqs"/>
<xsl:with-param name="cs-hash" select="$hash"/>
</xsl:call-template>
</xsl:template>
<xsl:template name="find-repeated-cs">
<xsl:param name="freqs" as="xs:integer*"/>
<xsl:param name="cs-hash" as="map(xs:integer, xs:boolean)"/>
<xsl:param name="cs" select="0" as="xs:integer"/>
<xsl:param name="i" select="1" as="xs:integer"/>
<xsl:variable name="new-cs" select="$cs + $freqs[$i]" as="xs:integer"/>
<xsl:variable name="new-i" select="if ($i >= count($freqs)) then 1 else $i + 1" as="xs:integer"/>
<xsl:choose>
<xsl:when test="map:contains($cs-hash, $new-cs)">
<xsl:value-of select="$new-cs"/>
</xsl:when>
<xsl:otherwise>
<xsl:call-template name="find-repeated-cs">
<xsl:with-param name="freqs" select="$freqs"/>
<xsl:with-param name="cs-hash" select="map:put($cs-hash,$new-cs,true())"/>
<xsl:with-param name="cs" select="$new-cs"/>
<xsl:with-param name="i" select="$new-i"/>
</xsl:call-template>
</xsl:otherwise>
</xsl:choose>
</xsl:template>
</xsl:stylesheet>
编辑
对于一些上下文，代码在累积和序列中找到第 2 次出现的数字，该序列是通过重复循环一组固定整数 freqs 生成的。最新的累计和是cs，在cs-hash中建立了过去看到的累计和的字典。 i 索引 freq 作为循环 index/counter。
如果我的方法很愚蠢，我也对其他方法感兴趣，但我仍然想了解为什么无法优化此代码 - 即使有更好的方法。
编辑 2
为了完整性，函数实现使用 xsl:choose:
<?xml version="1.0" encoding="UTF-8"?>
<xsl:stylesheet version="3.0" xmlns:xsl="http://www.w3.org/1999/XSL/Transform" xmlns:xs="http://www.w3.org/2001/XMLSchema" xmlns:map="http://www.w3.org/2005/xpath-functions/map" xmlns:aoc2018="\
http://www.blah.co.uk/aoc2018" exclude-result-prefixes="xs map aoc2018">
<!-- hint: java -classpath /usr/local/share/java/saxon9ee.jar net.sf.saxon.Transform -it -xsl:01.xslt -->
<xsl:function name="aoc2018:find-repeated-cs">
<xsl:param name="freqs" as="xs:integer*"/>
<xsl:param name="cs-hash" as="map(xs:integer, xs:boolean)"/>
<xsl:param name="cs" as="xs:integer"/>
<xsl:param name="i" as="xs:integer"/>
<xsl:variable name="new-cs" select="$cs + $freqs[$i]" as="xs:integer"/>
<xsl:choose>
<xsl:when test="map:contains($cs-hash, $new-cs)">
<xsl:value-of select="$new-cs"/>
</xsl:when>
<xsl:otherwise>
<xsl:variable name="new-i" select="if ($i >= count($freqs))
then 1
else $i + 1" as="xs:integer"/>
<xsl:value-of select="aoc2018:find-repeated-cs($freqs, map:put($cs-hash,$new-cs,true()), $new-cs, $new-i)"/>
</xsl:otherwise>
</xsl:choose>
</xsl:function>
<xsl:output method="text" version="1.0" encoding="UTF-8" indent="yes"/>
<xsl:template name="xsl:initial-template">
<xsl:variable name="freqs" select="unparsed-text-lines('input.txt', 'UTF-8')!xs:integer(.)"/>
<xsl:message select="sum($freqs)"/>
<xsl:variable name="hash" select="map{}" as="map(xs:integer, xs:boolean)"/>
<xsl:message select="aoc2018:find-repeated-cs($freqs, $hash, 0, 1)"/>
</xsl:template>
</xsl:stylesheet>
以及使用 XPATH 的函数实现：
<?xml version="1.0" encoding="UTF-8"?>
<xsl:stylesheet version="3.0" xmlns:xsl="http://www.w3.org/1999/XSL/Transform" xmlns:xs="http://www.w3.org/2001/XMLSchema" xmlns:map="http://www.w3.org/2005/xpath-functions/map" xmlns:aoc2018="\
http://www.blah.co.uk/aoc2018" exclude-result-prefixes="xs map aoc2018">
<!-- hint: java -classpath /usr/local/share/java/saxon9ee.jar net.sf.saxon.Transform -it -xsl:01.xslt -->
<xsl:function name="aoc2018:find-repeated-cs">
<xsl:param name="freqs" as="xs:integer*"/>
<xsl:param name="cs-hash" as="map(xs:integer, xs:boolean)"/>
<xsl:param name="cs" as="xs:integer"/>
<xsl:param name="i" as="xs:integer"/>
<xsl:variable name="new-cs" select="$cs + $freqs[$i]" as="xs:integer"/>
<xsl:variable name="new-i" select="if ($i >= count($freqs))
then 1
else $i + 1" as="xs:integer"/>
<xsl:value-of select="if (map:contains($cs-hash, $new-cs))
then $new-cs
else aoc2018:find-repeated-cs($freqs, map:put($cs-hash,$new-cs,true()), $new-cs, $new-i)"/>
</xsl:function>
<xsl:output method="text" version="1.0" encoding="UTF-8" indent="yes"/>
<xsl:template name="xsl:initial-template">
<xsl:variable name="freqs" select="unparsed-text-lines('input.txt', 'UTF-8')!xs:integer(.)"/>
<xsl:message select="sum($freqs)"/>
<xsl:variable name="hash" select="map{}" as="map(xs:integer, xs:boolean)"/>
<xsl:message select="aoc2018:find-repeated-cs($freqs, $hash, 0, 1)"/>
</xsl:template>
</xsl:stylesheet>
已确认这在 9.9 下有效（使用尾递归），无论是否启用字节码生成，但在 9.8 下，只有关闭字节码生成才能成功。我认为这些版本之间的区别在于 9.9 在决定不使用字节码生成时会更聪明，因为它会干扰尾递归。
要了解为什么在使用函数调用而不是模板时失败，我需要查看代码。这两种情况在内部使用不同的机制。特别是函数默认在 "pull" 模式下求值（它们 return 是结果的迭代器），模板在 "push" 模式下（它们将结果写入结果树）。最显着的区别是 returning 包含递归调用结果的序列（例如 select="$x, f:myself($x - 1)）可以使用模板以尾递归方式完成，但不能使用函数。但这似乎不适用于您的情况。此外，对于模板，我们处理两个或多个模板的相互递归，而对于函数，我们只处理自递归。
以下版本似乎可以使用尾递归使用 9.8 或 9.9，无论是否生成字节码。 （虽然在 9.8 下，有一个我没有时间研究的奇怪之处：在产生输出值之后，进程实际上并没有退出。）
<?xml version="1.0" encoding="UTF-8"?>
<xsl:stylesheet version="3.0" xmlns:xsl="http://www.w3.org/1999/XSL/Transform" xmlns:xs="http://www.w3.org/2001/XMLSchema"
xmlns:map="http://www.w3.org/2005/xpath-functions/map" xmlns:f="f" exclude-result-prefixes="#all">
<xsl:output method="text" version="1.0" encoding="UTF-8" indent="yes"/>
<xsl:param name="limit" select="2000"/>
<xsl:template name="xsl:initial-template">
<xsl:variable name="freqs" select="1 to $limit"/>
<xsl:message select="sum($freqs)"/>
<xsl:variable name="hash" select="map{}" as="map(xs:integer, xs:boolean)"/>
<xsl:sequence select="f:find-repeated-cs($freqs, $hash, 0, 1)"/>
</xsl:template>
<xsl:function name="f:find-repeated-cs">
<xsl:param name="freqs" as="xs:integer*"/>
<xsl:param name="cs-hash" as="map(xs:integer, xs:boolean)"/>
<xsl:param name="cs" as="xs:integer"/>
<xsl:param name="i" as="xs:integer"/>
<xsl:variable name="new-cs" select="$cs + $freqs[$i]" as="xs:integer"/>
<xsl:variable name="new-i" select="if ($i >= count($freqs)) then 1 else $i + 1" as="xs:integer"/>
<xsl:choose>
<xsl:when test="map:contains($cs-hash, $new-cs)">
<xsl:value-of select="$new-cs"/>
</xsl:when>
<xsl:otherwise>
<xsl:sequence select="f:find-repeated-cs($freqs, map:put($cs-hash,$new-cs,true()), $new-cs, $new-i)"/>
</xsl:otherwise>
</xsl:choose>
</xsl:function>
</xsl:stylesheet>
更新
实际上，当我说它有效时，我的意思是它不会因堆栈溢出而失败。进一步检查表明它实际上并没有终止——似乎终止条件永远不会为真。我还没有尝试找出原因。
在您的代码中，您使用 <xsl:value-of> 来 return 函数结果，而不是 xsl:sequence。 xsl:value-of 传递一个文本节点，它需要从递归调用的结果中构建：你可以在 -explain 输出中看到：
<function name="Q{http://www.blah.co.uk/aoc2018}find-repeated-cs"
line="5"
module="file:/Users/mike/Desktop/temp/test.xsl"
eval="9"
flags="pU"
as="item()*"
slots="6">
<arg name="Q{}freqs" as="xs:integer*"/>
<arg name="Q{}cs-hash" as="map(xs:integer, xs:boolean)"/>
<arg name="Q{}cs" as="xs:integer"/>
<arg name="Q{}i" as="xs:integer"/>
<let role="body"
baseUri="file:/Users/mike/Desktop/temp/test.xsl"
ns="xsl=~ aoc2018=http://www.blah.co.uk/aoc2018 xs=~ map=~"
line="10"
var="Q{}new-cs"
as="xs:integer"
slot="4"
eval="16">
<check card="1" diag="3|0|XTTE0570|new-cs">
<arith op="+" calc="i+i">
<varRef name="Q{}cs" slot="2"/>
<subscript>
<varRef name="Q{}freqs" slot="0"/>
<varRef name="Q{}i" slot="3"/>
</subscript>
</arith>
</check>
<let line="13" var="Q{}new-i" as="xs:integer" slot="5" eval="16">
<choose>
<vc op="ge" onEmpty="0" comp="CAVC">
<varRef name="Q{}i" slot="3"/>
<fn name="count">
<varRef name="Q{}freqs" slot="0"/>
</fn>
</vc>
<int val="1"/>
<true/>
<arith op="+" calc="i+i">
<varRef name="Q{}i" slot="3"/>
<int val="1"/>
</arith>
</choose>
<valueOf line="16">
<fn name="string-join">
<convert from="xs:anyAtomicType" to="xs:string">
<choose>
<ifCall name="Q{http://www.w3.org/2005/xpath-functions/map}contains"
type="xs:boolean">
<varRef name="Q{}cs-hash" slot="1"/>
<varRef name="Q{}new-cs" slot="4"/>
</ifCall>
<varRef name="Q{}new-cs" slot="4"/>
<true/>
<data>
<mergeAdj>
<ufCall name="Q{http://www.blah.co.uk/aoc2018}find-repeated-cs"
tailCall="false"
bSlot="0"
eval="6 16 6 6">
<varRef name="Q{}freqs" slot="0"/>
<treat as="map(xs:integer, xs:boolean)" diag="0|1||aoc2018:find-repeated-cs">
<ifCall name="Q{http://www.w3.org/2005/xpath-functions/map}put" type="map(*)">
<varRef name="Q{}cs-hash" slot="1"/>
<varRef name="Q{}new-cs" slot="4"/>
<true/>
</ifCall>
</treat>
<varRef name="Q{}new-cs" slot="4"/>
<varRef name="Q{}new-i" slot="5"/>
</ufCall>
</mergeAdj>
</data>
</choose>
</convert>
<str val=" "/>
</fn>
</valueOf>
</let>
</let>
</function>
因为函数结果还需要做进一步的操作（即转为文本节点，需要将结果原子化，将结果中的项转为字符串，并用空格分隔）所以函数为不是尾递归的。始终使用 xsl:sequence 到 return 函数结果，并始终声明函数的结果类型和参数类型。