RE: [xsl] How is memory allocated in recursive XSLT templates?

Subject: RE: [xsl] How is memory allocated in recursive XSLT templates?
From: "Michael Kay" <mike@xxxxxxxxxxxx>
Date: Wed, 2 May 2007 20:17:27 +0100
Well, clearly implementations may differ.

At first sight you are right: recursive template calls will consume an
amount of stack space proportional to the depth of recursion, and if you
code goes into infinite recursion you will hit some limit on the amount of
stack space available, which will cause execution to crash in some way.

However, there's a well-known optimization in functional programming
languages whereby recursive calls can sometimes be turned into iterations,
and if this happens then an infinite recursion can become an infinite
iteration, which won't terminate due to lack of resources. This applies to
functions that are "tail-recursive": basically, if the calling code doesn't
need to do anything with the result of the called code, then instead of the
sequence (make recursive call, then pop stack) it can do (pop stack, then
make recursive call). Saxon will do this for the template in your example.

Michael Kay
http://www.saxonica.com/



> -----Original Message-----
> From: Rashmi Rubdi [mailto:rashmi.sub@xxxxxxxxx] 
> Sent: 02 May 2007 19:34
> To: xsl-list@xxxxxxxxxxxxxxxxxxxxxx
> Subject: [xsl] How is memory allocated in recursive XSLT templates?
> 
> Hello Everyone,
> 
> Please treat this as a low priority, academic question.
> 
> I am interested in finding out what data structure is used 
> internally to represent each template's data in situations 
> where the template is called recursively, because I was 
> thinking that infinite recursion is not possible if memory is 
> allocated in the form of a stack.
> 
> I would like to think of templates as equivalent to a 
> function/ method in other programming languages for the 
> purpose of this post.
> 
> I was reading on recursive functions, and learned that each 
> function call's data is stored in a stack frame , and at the 
> end of the last function call, the data of each function call 
> is poped out of the stack frame and returned in reverse order 
> --- LIFO.
> 
> If a stack is used then, it poses memory constraints when 
> stack frames run out, this is why it is important to have a 
> termination condition.
> And when there's a termination condition it is not infinite recursion.
> 
> In case of XSLT the termination condition is the depth of an 
> XML structure (it cannot be infinite),  or it could be a 
> constraint specified by the author of the XSLT stylesheet.
> 
> There's an illustration which shows how memory is allocated 
> in a stack frame for each function call at the bottom of this page :
> http://www.oopweb.com/Algorithms/Documents/PLDS210/Volume/stacks.html
> 
> I made a naive attempt to calculate the factorial of a given 
> number recursively with XSL templates, but soon realized that 
> there's no return statement.
> 
> I know that XSLT has functions, I haven't read about them 
> yet, but I plan to soon.
> 
> Here's what I tried (it's incomplete):
> 
> <?xml version="1.0" encoding="UTF-8"?>
> <xsl:stylesheet version="2.0" 
> xmlns:xsl="http://www.w3.org/1999/XSL/Transform";>
> 
>  <xsl:template name="factorialTemplate">
>  	<xsl:param name="n"/>	
>  	<xsl:choose>
> 		<xsl:when test="$n=0">
>    	
> 		</xsl:when>
> 		<xsl:otherwise>
> 			<xsl:call-template name="factorialTemplate">
> 				<xsl:with-param name="n" select="$n-1"/>
> 			</xsl:call-template>
> 		</xsl:otherwise>
> 	</xsl:choose>
>  </xsl:template>
> 
> </xsl:stylesheet>
> 
> I was trying to achieve the equivalent of the recursive 
> Factorial function illustrated here with procedural programming:
> http://www.oopweb.com/Algorithms/Documents/PLDS210/Volume/recu
> rsion.html
> 
> Any thoughts on whether the memory is allocated in terms of 
> Stack with recursive template/ or recursive XLST functions is 
> appreciated.
> 
> edit: before I hit the send button, I realized that Google 
> has some info on this, I plan to read this 
> http://www.gca.org/papers/xmleurope2000/pdf/s35-03.pdf
> 
> -Thank you
> Rashmi

Current Thread