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(_dot_)sub(_at_)gmail(_dot_)com]
Sent: 02 May 2007 19:34
To: xsl-list(_at_)lists(_dot_)mulberrytech(_dot_)com
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
--~------------------------------------------------------------------
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>
--~--