Re: [xsl] How can I achieve correct tail-recursion ?

Subject: Re: [xsl] How can I achieve correct tail-recursion ?
From: Frédéric Schwebel <Frederic.Schwebel@xxxxxxxxxxxxxxxx>
Date: Thu, 7 Jan 2010 16:56:27 +0100
Thanks for your quick reply.
I figured what you said just after posting, for I found another
message of yours :
http://www.biglist.com/lists/lists.mulberrytech.com/xsl-list/archives/200912/
msg00149.html

so I switched the two lasts 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,$espace),'&#10;&pt;'
)"
/>
	</xsl:if>

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

But processing time is strictly the same... Didn't check if stack
problems disappear with it but shouldn't the optimization speed up the
process (maybe not so much as saxon:iterate but still a bit ?) ?

2010/1/7 Michael Kay <mike@xxxxxxxxxxxx>:
> 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: [xsl] 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/

Current Thread