RE: tail-recursion

It's a rather strange stylesheet because as well as using recursion to
tokenize the string, it also calls xalan:tokenize() - I can't see why!

I-Lin Kuo, Ann Arbor, MI
Macromedia Certified ColdFusion 5.0 Advanced Developer
Sun Certified Java 2 Programmer
Ann Arbor Java Users Group (www.aajug.org) SUN Top 25 JUG

From: "Michael Kay" <mhk@xxxxxxxxx>
Reply-To: xsl-list@xxxxxxxxxxxxxxxxxxxxxx
To: <xsl-list@xxxxxxxxxxxxxxxxxxxxxx>
Subject: RE:  tail-recursion
Date: Thu, 28 Aug 2003 15:48:14 +0100

Your template parseRows is intrinsically tail-recursive - basically this
means that after calling itself, it does nothing else before returning.

It's a rather strange stylesheet because as well as using recursion to
tokenize the string, it also calls xalan:tokenize() - I can't see why!

Saxon and jd.xslt are known to use tail recursion.

To test whether your engine uses tail recursion (on a particular
stylesheet), generate some test data that will cause about 2000 nested
recursive calls. Most processors without tail recursion will fail at
around 500.

Michael Kay

> -----Original Message-----
> From: owner-xsl-list@xxxxxxxxxxxxxxxxxxxxxx
> [mailto:owner-xsl-list@xxxxxxxxxxxxxxxxxxxxxx] On Behalf Of I-Lin Kuo
> Sent: 28 August 2003 14:44
> To: xsl-list@xxxxxxxxxxxxxxxxxxxxxx
> Subject:  tail-recursion
>
>
> I have to do some string manipulation. The following takes a
> string such as
> "1~2~a~!~f~4~5~!~1~2~3" and parses it as a list delimited by
> "~!~" and then
> processes each list element "1~2~a", "f~4~5", and "1~2~3" as a list
> delimited by "~" in order to display as an html table
>
>
> <xsl:template name="parseRows">
> 	<xsl:param name="catContents"/>
> 	<xsl:param name="font-size" select="'-1'"/>
> 	<xsl:choose>
> 		<xsl:when test="contains($catContents,'~!~')">
> 			<xsl:call-template name="parseRow">
> 				<xsl:with-param name="rowContents"
> select="substring-before($catContents,'~!~')"/>
> 				<xsl:with-param
> name="font-size" select="$font-size"/>
> 			</xsl:call-template>
> 			<xsl:call-template name="parseRows">
> 				<xsl:with-param name="catContents"
> select="substring-after($catContents,'~!~')"/>
> 				<xsl:with-param
> name="font-size" select="$font-size"/>
> 			</xsl:call-template>
> 		</xsl:when>
> 		<xsl:otherwise>
> 			<xsl:value-of select="$catContents"/>
> 		</xsl:otherwise>
> 	</xsl:choose>
> </xsl:template>
>
> <xsl:template name="parseRow">
> 	<xsl:param name="rowContents"/>
> 	<xsl:param name="font-size" select="'-1'"/>
> 	<tr>
> 		<xsl:for-each select="xalan:tokenize($rowContents,'~')">
> 			<td><font
> size="{$font-size}"><xsl:value-of select="."/></font></td>
> 		</xsl:for-each>
> 	</tr>
> </xsl:template>
>
> This code works, but I'm thinking of modifying it. I know
> that some xslt
> engines use tail recursion to optimise their processing and
> I'm worried
> about breaking that.
>
> 1. Which xslt engines use tail recursion?
> 2. I'm not exactly sure about tail recursion. Does my xslt
> above already
> violate that? If not, what should I be careful about.
> 3. Is there a way for me to empirically test whether an xslt
> engine uses
> tail recursion?
>
> I-Lin Kuo, Ann Arbor, MI
> Macromedia Certified ColdFusion 5.0 Advanced Developer
> Sun Certified Java 2 Programmer
> Ann Arbor Java Users Group (www.aajug.org) SUN Top 25 JUG
>
> _________________________________________________________________
> Get MSN 8 and help protect your children with advanced
> parental controls.
> http://join.msn.com/?page=features/parental
>
>
>  XSL-List info and archive:  http://www.mulberrytech.com/xsl/xsl-list
>

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