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),' &pt;' )" /> </xsl:if> <xsl:if test="$numNoeud < 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 < 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),' &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 < 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),' &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),' &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 |
---|
|
<- Previous | Index | Next -> |
---|---|---|
RE: [xsl] How can I achieve correct, Michael Kay | Thread | RE: [xsl] How can I achieve correct, Michael Kay |
RE: [xsl] How can I achieve correct, Michael Kay | Date | re: [xsl] How can I achieve correct, Vladimir Nesterovsky |
Month |