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

["Dimitre Novatchev" <dnovatchev@xxxxxxxxx>]

I want just to add something to this very interesting discussion.

In all cases when it is difficult to come up with a tail-recursive
transformation, or the XSLT processor in use happens not to recognize
the particular kind of tail recursion used (as happened with my
example that became the base for the thread in the saxon-help list),
then there is usually the possibility to use a DVC (DiVide and
Conquer) approach.

Very briefly described, a DVC algorithm typically processes two or
more (shorter) parts of the input list (recursively!) and then
combines the results.

Thus, processing a list of 1 000 000 (1M) elements with DVC will
require a maximum call-stack depth of only 19 (~ log2(1000000) ),

One can read more about DVC algorithms for example in Robert
Sedgewick's book "Algorithms in C++".

Most of the functions of FXSL, which are defined to process long
lists, have a DVC equivalent.

--
Cheers,
Dimitre Novatchev
---------------------------------------
Truly great madness cannot be achieved without significant intelligence.
---------------------------------------
To invent, you need a good imagination and a pile of junk
-------------------------------------
You've achieved success in your field when you don't know whether what
you're doing is work or play



On 5/2/07, Rashmi Rubdi <rashmi.sub@xxxxxxxxx> wrote:
> 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/recursion.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