Altova Mailing List Archives


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

From: Mike Brown <mike@-------->
To:
Date: 3/22/2003 8:28:00 PM
One thing Robert van Dalen said in his original post was

"Because most XSLT implementations out there still do not support
tail-recursion elimination, DVC is the way to go if you want to process a lot
of nodes."

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.

The problem that when the recursive template is a matching template instead of
a named template, it is hard for the processor to recognize that the
apply-templates at the end of the template will result in the same template
being applied. For example, Robert's second example has this:

  <xsl:template match="group">
    <xsl:copy>
      <xsl:copy-of select="@*"/>
      <xsl:copy-of select="./city"/>
    </xsl:copy>
    <xsl:apply-templates select="./group"/>
  </xsl:template>

I don't know if any processors can optimize this. It may seem obvious to you
and me that the apply-templates instruction will result in this same template
being applied, but there might be some other template that also matches
certain 'group' elements at a higher priority, so there's no easy way for the
processor to be sure (before runtime) that this template will be the one that
is invoked for every one of the selected nodes. Or at least, the analysis
required to be certain that this is tail-recursive is not simple enough that
anyone has bothered to figure it out yet. (Suggestions welcome...)

So for now, the way to tell a processor to use its tail recursion optimization
is to use a named template. It's OK to use xsl:if or xsl:choose/xsl:when, as
long as the recursive call is at the end (i.e. nothing else that could generate
output comes after it):

  <xsl:template match="group">
    <xsl:call-template name="process-group"> 
      <xsl:with-param name="group-node" select="."/>
    </xsl:call-template>
  </xsl:template>
  
  <xsl:template name="process-group">
    <xsl:param name="group-node"/>
    <xsl:if test="$group-node">
      <xsl:copy>
        <xsl:copy-of select="$group-node/@*"/>  
        <xsl:copy-of select="$group-node/city"/>
      </xsl:copy>
      <xsl:call-template name="process-group">
        <xsl:with-param name="group-node" select="$group-node/group"/>
      </xsl:call-template>
    </xsl:if>
  </xsl:template>


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

Disclaimer

These Archives are provided for informational purposes only and have been generated directly from the Altova mailing list archive system and are comprised of the lists set forth on www.altova.com/list/index.html. Therefore, Altova does not warrant or guarantee the accuracy, reliability, completeness, usefulness, non-infringement of intellectual property rights, or quality of any content on the Altova Mailing List Archive(s), regardless of who originates that content. You expressly understand and agree that you bear all risks associated with using or relying on that content. Altova will not be liable or responsible in any way for any content posted including, but not limited to, any errors or omissions in content, or for any losses or damage of any kind incurred as a result of the use of or reliance on any content. This disclaimer and limitation on liability is in addition to the disclaimers and limitations contained in the Website Terms of Use and elsewhere on the site.