xsl-list
[Top] [All Lists]

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),'&#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(_at_)saxonica(_dot_)com>:
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(_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),'&#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
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>
--~--

<Prev in Thread] Current Thread [Next in Thread>