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

Subject: Re: [xsl] How is memory allocated in recursive XSLT templates?
From: Abel Braaksma <abel.online@xxxxxxxxx>
Date: Wed, 02 May 2007 20:56:26 +0200
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 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.



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



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.


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



Cheers, -- Abel

Current Thread