Re: tail recursion optimization (was How efficient is

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?

> 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

I think implementations shouldn't bother to optimize the latter. Just sticking
with tail recursion is fine by me.
Trying to optimize complex templates is hard or even impossible for
implementations.
Also, the stylesheet creator will have a hard time *predicting* optimizations in
advance.

> 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):

I thought of this, writing the stylesheets in a tail-recursive style, but didn't
get it to work with Xalan - the processor I use daily ;-)

Cheers,

Robbert




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