如何用尾递归函数创建无界序列？XSLT栈溢出问题咨询

问题重现 #

你用Saxon-EE 11.4写了个递归函数生成全是1的无界整数序列，但调用kooks:repeat()[5]取第5个元素时，直接触发了java.lang.StackOverflowError。你的XSLT代码如下：

<xsl:function name="kooks:repeat" as="xs:integer*">
    <xsl:sequence select="1"/>
    <xsl:sequence select="kooks:repeat()"/>
</xsl:function>

<xsl:template match="/">
    <xsl:sequence select="kooks:repeat()[5]"/>
</xsl:template>

错误提示：

Severity: error
Description: class java.lang.StackOverflowError

对比能正常运行的F#实现：

let rec ones () =
    seq {
        yield 1
        yield! ones ()
    }

let tenMillionthEntry = 
    ones ()
    |> Seq.skip 10000000
    |> Seq.take 1
    |> Seq.head

原因分析 #

你猜的没错：XSLT函数里两个<xsl:sequence>的拼接操作，让函数没法被识别成尾递归。Saxon处理这种序列拼接时，得保留当前函数的栈帧来完成后续的序列合并，根本做不了尾递归优化。而F#的seq是懒加载序列，yield!会推迟递归调用，只有迭代到对应元素时才触发，不会一次性把栈撑爆。

解决方案 #

方案1：用xsl:iterate实现无限懒序列 #

XSLT 3.0的<xsl:iterate>是循环式生成序列，从根源上避免栈溢出问题，不用依赖递归：

<xsl:function name="kooks:repeat" as="xs:integer*">
    <xsl:iterate>
        <!-- 每次迭代输出1 -->
        <xsl:sequence select="1"/>
        <!-- 无限循环下去 -->
        <xsl:next-iteration/>
    </xsl:iterate>
</xsl:function>

<xsl:template match="/">
    <xsl:sequence select="kooks:repeat()[5]"/>
</xsl:template>

<xsl:iterate>是懒加载生成序列的，你取第5个元素时，它只会跑5次迭代，不会累积栈帧。

方案2：调整递归函数为尾递归兼容形式 #

如果一定要用递归函数，得让函数最后一步直接调用自身，同时合并序列拼接为单个表达式，让Saxon能识别成懒加载：

<xsl:function name="kooks:repeat" as="xs:integer*">
    <xsl:sequence select="1, kooks:repeat()"/>
</xsl:function>

不过这种写法在部分Saxon版本里还是可能栈溢出，毕竟递归拼接序列本质还是靠栈处理调用链，更推荐用第一种xsl:iterate的方案。

内容的提问来源于stack exchange，提问作者MrD at KookerellaLtd