RE: How can I achieve correct tail-recursion ?

Your recursion isn't a tail recursion because the recursive call is not the
last instruction:

	<xsl:if test="$numNoeud &lt; count(*)">
		<xsl:call-template name="miseEnPage">
			<xsl:with-param name="numNoeud" select="$numNoeud+1"
/>
			<xsl:with-param name="numPage" select="$nouvPage" />
			<xsl:with-param name="numLigne" select="$nouvLigne"
/>
		</xsl:call-template>
	</xsl:if>
	<xsl:if test="$mise_en_page and ($numNoeud = count(*))"> <!-- appel
final pour num de page et saut de page -->
		<!-- THIS COMES AFTER THE RECURSIVE CALL -->
	</xsl:if>

Tail recursion means that the recursive call is the last thing that the
template/function does.

Regards,

Michael Kay
http://www.saxonica.com/
http://twitter.com/michaelhkay


> -----Original Message-----
> From: djidjoenator@xxxxxxxxx [mailto:djidjoenator@xxxxxxxxx]
> On Behalf Of Fridiric Schwebel
> Sent: 07 January 2010 15:03
> To: xsl-list
> Subject:  How can I achieve correct tail-recursion ?
>
> Hello, I'm using SaxonHE 9.2 with a layout sheet for braille
> output. I need to process every child of node "doc" while
> remembering line and page numbers for each child I process.
> Here's the sub-part of the sheet ("doc" is the root of my document) :
> ----------------
> [...]
> <xsl:template match="doc">
> 	<xsl:apply-templates select="@*" />
> 	<xsl:call-template name="miseEnPage"/>
> </xsl:template>
>
> <!-- TEMPLATE PRINCIPAL DE MISE EN PAGE --> <xsl:template
> name="miseEnPage">
> 	<xsl:param name="numNoeud" as="xs:integer" select="1" />
> 	<xsl:param name="numPage" as="xs:integer" select="1" />
> 	<xsl:param name="numLigne" as="xs:integer" select="1" />
>
> 	<xsl:variable name="texteMisEnPage" as="xs:string*">
> 		<xsl:choose>
> 			<!-- saut de page -->
> 			<xsl:when test="*[$numNoeud][self::page-break]">
> 				<xsl:value-of
> select="translate(doc:sautePage(true(),$numLigne,$numPage),con
> cat($sautAGenerer,$espace),'&#10;&pt;')"/>
> 			</xsl:when>
> 			<xsl:when
> test="not(string(*[$numNoeud]))"><!-- le fils est vide -->
> 				<xsl:call-template
> name="gestionLignesVides">
> 					<xsl:with-param
> name="numNoeud" select="$numNoeud" />
> 					<xsl:with-param
> name="numLigne" select="$numLigne" />
> 					<xsl:with-param
> name="numPage" select="$numPage" />
> 				</xsl:call-template>
> 			</xsl:when>
> 			<xsl:when test="*[$numNoeud][self::ul
> or self::ol]"> <!-- liste ` puces -->
> 				<xsl:call-template name="MEPliste">
> 					<xsl:with-param
> name="noeud" select="*[$numNoeud]" />
> 					<xsl:with-param
> name="numPage" select="$numPage" tunnel="yes"/>
> 					<xsl:with-param
> name="numLigne" select="$numLigne" tunnel="yes" />
> 				</xsl:call-template>
> 			</xsl:when>
> [... other xsl:when ...]
>
> <xsl:otherwise><xsl:text></xsl:text></xsl:otherwise>
> 		</xsl:choose>
> 	</xsl:variable>
>
> 	<!-- ******** affichage du texte ********* -->
> 	<xsl:variable name="texteMisEnPageJoint"
> select="string-join($texteMisEnPage,'')" as="xs:string" />
> 	<xsl:value-of select="$texteMisEnPageJoint" />
>
> 	<xsl:variable name="nouvPage" as="xs:integer"
> select="doc:nouvellePage($texteMisEnPageJoint,$numPage)" />
> 	<xsl:variable name="nouvLigne" as="xs:integer"
> select="doc:nouvelleLigne($texteMisEnPageJoint,$numLigne)" />
>
> <!-- here comes the tail recursion -->
> 	<xsl:if test="$numNoeud &lt; count(*)">
> 		<xsl:call-template name="miseEnPage">
> 			<xsl:with-param name="numNoeud"
> select="$numNoeud+1" />
> 			<xsl:with-param name="numPage"
> select="$nouvPage" />
> 			<xsl:with-param name="numLigne"
> select="$nouvLigne" />
> 		</xsl:call-template>
> 	</xsl:if>
> 	<xsl:if test="$mise_en_page and ($numNoeud =
> count(*))"> <!-- appel final pour num de page et saut de page -->
> 		<xsl:variable name="completeLastPage" as="xs:string"
> select="doc:sautePage(true(),$nouvLigne,$nouvPage)" />
> 		<xsl:value-of
> select="translate($completeLastPage,concat($sautAGenerer,$espa
> ce),'&#10;&pt;')"
> />
> 	</xsl:if>
> </xsl:template>
>
> ----------------------------------
> I've read Saxon optimizes tail recursion as an iterating
> function, this would mean no stack overflow.
> I switched back to Saxon 9.1 and tried to achieve this with
> saxon:iterate and parameters :
> ---------------------------------
> <xsl:template name="miseEnPage">
>
> 	<saxon:iterate select="*" xmlns:saxon="http://saxon.sf.net/"
> xsl:extension-element-prefixes="saxon">
> 		<xsl:param name="numPage" as="xs:integer" select="1" />
> 		<xsl:param name="numLigne" as="xs:integer" select="1" />
>
> 		<xsl:variable name="texteMisEnPage" as="xs:string*">
> 			<xsl:choose>
> 				<!-- saut de page -->
> 				<xsl:when test="self::page-break">
> 					<!--<xsl:message
> select="OUI"/>-->
> 					<xsl:value-of
> select="translate(doc:sautePage(true(),$numLigne,$numPage),con
> cat($sautAGenerer,$espace),'&#10;&pt;')"/>
> 				</xsl:when>
> 				<xsl:when
> test="not(string(.))"><!-- le fils est vide -->
> 					<xsl:call-template
> name="gestionLignesVides">
> 						<xsl:with-param
> name="numLigne" select="$numLigne" />
> 						<xsl:with-param
> name="numPage" select="$numPage" />
> 					</xsl:call-template>
> 				</xsl:when>
> 				<xsl:when test="self::ul or
> self::ol"> <!-- liste ` puces -->
> 					<xsl:call-template
> name="MEPliste">
> 						<xsl:with-param
> name="numPage" select="$numPage" tunnel="yes"/>
> 						<xsl:with-param
> name="numLigne" select="$numLigne" tunnel="yes" />
> 					</xsl:call-template>
> 				</xsl:when>
> [... other xsl:when ...]
>
> <xsl:otherwise><xsl:text></xsl:text></xsl:otherwise>
> 			</xsl:choose>
> 		</xsl:variable>
>
> 		<!-- ******** affichage du texte ********* -->
> 		<xsl:variable name="texteMisEnPageJoint"
> select="string-join($texteMisEnPage,'')" as="xs:string" />
> 		<xsl:value-of select="$texteMisEnPageJoint" />
>
> 		<saxon:continue>
> 			<xsl:with-param name="numPage" as="xs:integer"
> select="doc:nouvellePage($texteMisEnPageJoint,$numPage)" />
> 			<xsl:with-param name="numLigne" as="xs:integer"
> select="doc:nouvelleLigne($texteMisEnPageJoint,$numLigne)" />
> 		</saxon:continue>
> 	</saxon:iterate>
> 	<!-- <xsl:value-of
> select="concat('nouvpage',$nouvPage,'nouvligne',$nouvLigne,'ma
> tches ', string($pagesEnPlus),' ',string($lignesEnPlus))" />
> --> </xsl:template>
>
> -----------------------------------
>
> With saxon:iterate , no more stack overflow and processing is
> about 10x faster ! I suppose I would get a nearby result if
> my first sheet did correct tail recursion. How can I modify
> it to do correct tail recursion ? I couldn't find any doc
> about it on the W3C website, nor on saxonica.com, nor on
> http://saxon.markmail.org/.
>
> Thanks for any help,
> Regards
> Fridiric Schwebel
> http://sourceforge.net/projects/nat-braille/