[XSL-LIST Mailing List Archive Home] [By Thread] [By Date]

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


Subject: Re: [xsl] How is memory allocated in recursive XSLT templates?
From: "Rashmi Rubdi" <rashmi.sub@xxxxxxxxx>
Date: Wed, 2 May 2007 15:19:08 -0400

Hi Abel,

Thank you for your valuable reply

On 5/2/07, Abel Braaksma <abel.online@xxxxxxxxx> wrote:
Rashmi Rubdi wrote:
> Hello Everyone,
>
> Please treat this as a low priority, academic question.

I believe these are treated with high-prio by many... but time will tell ;)

>
>
> I would like to think of templates as equivalent to a function/ method
> in other programming languages for the purpose of this post.

Not sure if you can. But a pretty close equivalent in C++ is the way
that C++ can use template programming which is said to be (close to /
the same?) as declarative programming. Or, one might use it for that
matter, which is probably precisely why so many computational algorithms
are placed in the STL.

I don't know C++ , but I was reading that SQL is declarative, but I don't mean to digress.


> > 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.

Yep, though the order of the stack is, I believe, different on different
CPUs. Virtual Machines, and most modern CPUs as well, can set the amount
of memory reserved for stack space. With Saxon, you can control the
stack space which may help when having deeply nested templates (or
recursion): java -Xss1024k will give you 1MB of stack space, for instance.

Thank you, it's useful to know this.


>
> 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.

True. But you presumably haven't yet read about tail recursion, which

You're right I haven't, I probably did a long time ago but now I'll read more about it. Thanks.

can be optimized to normal iteration and hence is favored in most
fuctional/declarative languages. Tail recursion, if optimized well, may
provide infinite recursion depth, because the stack is not used.
Normally, tail-recursion is done by having the recursive call at the end
of the function. In XSLT, this wouldn't make sense, but the optimizer
may choose to rewrite any recursive calls into tail recursion, if
possible. I'm not sure, but I believe this is an intricate and complex
optimization. Saxon-SA has this optimization build in to some extend.

>
> 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.

Yep, but read above: it *can* be infinite. And please note that XSLT by
definition does not limit the depth of the recursion, though the
available resources may (if time is not a part of your termination
condition, think Turing Complete, recursion can be really infinite).

Got it.


>
> 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.

Huh? What would you need a return statement for? You declare how you
want your result to look like. I.e., the 'equivalent' of a result
statement is your sequence instruction:

<xsl:function name="f:my-name" as="xs:string">abel</xsl:function>

will 'return' the string 'abel' when called.

Thanks it helps to know in advance, but I will be reading about functions at some point.

>
> Any thoughts on whether the memory is allocated in terms of Stack with
> recursive template/ or recursive XLST functions is appreciated.
>

Search the saxon list for "tail recursion", there has recently been some
discussion, I believe it was between Dimitre Novatchev and Michael Kay,
about how to optimize any recursive call to tail-recursion. You may find
some pointers there. Also, this is quite explanatory, though basic:
http://en.wikipedia.org/wiki/Tail_recursion

Thank you, I will.



Cheers, -- Abel

Your reply has answered all my questions.


-Regards
Rashmi


Current Thread
Keywords