[XSL-LIST Mailing List Archive Home] [By Thread] [By Date] [Recent Entries] [Reply To This Message]

How can I achieve correct tail-recursion ?

Subject: How can I achieve correct tail-recursion ?
From: Frédéric Schwebel <Fred.Schwebel@xxxxxxxxxxx>
Date: Thu, 7 Jan 2010 16:02:45 +0100
 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),concat($sautAGener
er,$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,$espace),'&#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),concat($sautAGener
er,$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,'matches ',
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

PURCHASE STYLUS STUDIO ONLINE TODAY!

Purchasing Stylus Studio from our online shop is Easy, Secure and Value Priced!

Buy Stylus Studio Now

Download The World's Best XML IDE!

Accelerate XML development with our award-winning XML IDE - Download a free trial today!

Don't miss another message! Subscribe to this list today.
Email
First Name
Last Name
Company
Subscribe in XML format
RSS 2.0
Atom 0.3
Site Map | Privacy Policy | Terms of Use | Trademarks
Free Stylus Studio XML Training:
W3C Member
Stylus Studio® and DataDirect XQuery ™are products from DataDirect Technologies, is a registered trademark of Progress Software Corporation, in the U.S. and other countries. © 2004-2013 All Rights Reserved.