Re: [xsl] tail recursion optimization (was How efficient is DVC?)

Subject: Re: [xsl] tail recursion optimization (was How efficient is DVC?)
From: Mike Brown <mike@xxxxxxxx>
Date: Sun, 23 Mar 2003 16:43:06 -0700 (MST)
Robbert van Dalen wrote:
> Mike wrote:
> > While DVC is the way to go for large amounts of data (as proven by Dimitre),
> > it's not accurate that XSLT implementations don't support tail-recursion
> > elimination. I can't speak for all of them, but many do.
> 
> Xalan doesn't seem to do tail-recursion (it doesn't claim anything about it)
>  I know SAXON does. Can you name any more implementation that support it?

4XSLT, from 4Suite 1.0a (current CVS snapshots) does.

After running the following stylesheet with various other processors, I see
that it seems you are right; no one else optimizes tail recursion. It's very
easy to cause a stack overflow in Xalan-J, xsltproc, Sablotron, oraxsl, XT,
and MSXML.

<?xml version="1.0" encoding="utf-8"?>
<xsl:stylesheet version="1.0"
  xmlns:xsl="http://www.w3.org/1999/XSL/Transform";>

  <xsl:output method="xml" indent="yes"/>

  <xsl:param name="limit" select="1000000"/>

  <xsl:template match="/">
    <result>
      <xsl:call-template name="recurse"/>
    </result>
  </xsl:template>

  <xsl:template name="recurse">
    <xsl:param name="iteration" select="$limit"/>
    <xsl:if test="$iteration div 1000 = floor($iteration div 1000)">
      <xsl:message terminate="no">
        <xsl:value-of select="concat($limit + 1 - $iteration,' ')"/>
      </xsl:message>
    </xsl:if>
    <xsl:if test="$iteration">
      <a/>
      <xsl:call-template name="recurse">
        <xsl:with-param name="iteration" select="$iteration - 1"/>
      </xsl:call-template>
    </xsl:if>
  </xsl:template>

</xsl:stylesheet>

Mike

-- 
  Mike J. Brown   |  http://skew.org/~mike/resume/
  Denver, CO, USA |  http://skew.org/xml/

 XSL-List info and archive:  http://www.mulberrytech.com/xsl/xsl-list


Current Thread