Re: [xsl] How can I achieve correct tail-recursion ?
2010-01-07 09:57:03
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(_at_)saxonica(_dot_)com>:
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(_at_)gmail(_dot_)com
[mailto:djidjoenator(_at_)gmail(_dot_)com]
On Behalf Of Frédéric 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
Frédéric Schwebel
http://sourceforge.net/projects/nat-braille/
--~------------------------------------------------------------------
XSL-List info and archive: http://www.mulberrytech.com/xsl/xsl-list
To unsubscribe, go to: http://lists.mulberrytech.com/xsl-list/
or e-mail:
<mailto:xsl-list-unsubscribe(_at_)lists(_dot_)mulberrytech(_dot_)com>
--~--
--~------------------------------------------------------------------
XSL-List info and archive: http://www.mulberrytech.com/xsl/xsl-list
To unsubscribe, go to: http://lists.mulberrytech.com/xsl-list/
or e-mail:
<mailto:xsl-list-unsubscribe(_at_)lists(_dot_)mulberrytech(_dot_)com>
--~--
--~------------------------------------------------------------------
XSL-List info and archive: http://www.mulberrytech.com/xsl/xsl-list
To unsubscribe, go to: http://lists.mulberrytech.com/xsl-list/
or e-mail: <mailto:xsl-list-unsubscribe(_at_)lists(_dot_)mulberrytech(_dot_)com>
--~--
|
|