[XSL-LIST Mailing List Archive Home]
[By Thread]
[By Date]
Hi Abel,
Thank you for your valuable reply
On 5/2/07, Abel Braaksma <abel.online@xxxxxxxxx> wrote:
Thank you, it's useful to know this.
Got it.
Thank you, I will.
Your reply has answered all my questions.
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 |
---|
|
<- Previous | Index | Next -> |
---|---|---|
Re: [xsl] How is memory allocated i, Abel Braaksma | Thread | Re: [xsl] How is memory allocated i, Abel Braaksma |
RE: [xsl] How is memory allocated i, Michael Kay | Date | [xsl] Enforcing element order, ms |
Month |