Re: Re: lookup-table thoughts (was Re: matching multip

At 06:30 PM 11/7/2001 +0000, Jeni Tennison wrote:
>Hi Tom,
>
> > However, I think making R tail-recursive is a success only if the
> > "cons" is constant-time.
>
>The proof of the pudding is in the eating, as they say. It seems
>you're right. .... ...
>As you can see, there's not much in it for low counts, but the time
>for the tail recursive template increases exponentially, the
>non-tail-recursive template increases more than the divide and conquer
>template, which stays roughly the same throughout....
>That's the last time I let David C. indoctrinate me ;)

umm, with regard to page 16 of _XSLT and XPath on the Edge_, an
excellent book which came in today's mail, I see 

   "If you can, you should make all your templates use tail recursion
  as this will increase the speed of your stylesheet."

Hmm. I don't mean to be rubbing it in -- on the contrary. David's
basically right that tail recursion is a big win, it's just not a free
lunch -- and I think the big win is not speed but runnability.
If you write a linear-recursive template to find the longest 
verse in Bosak's ot.xml, or just use M.Kay's length-of-longest sample
recursion template, it won't work in Xalan or MSXML but it will, I
think, work in Saxon provided that you make it tail-recursive. (I
haven't tried...but it Ought To Work. Feeling energetic? :-) ) If
you want to compute that kind of thing in Xalan I have to use a
divide-and-conquer recursion down books and chapters (or, of course, 
java or javascript or vb extensions); in a flat-list document, I
don't think pure XSLT in Xalan (or any non-tail-recursive processor)
could compute it at all. (I'm not sure of that; if I had to try, I'd
start by writing a stylesheet to break the flat-list doc into a
hierarchy.) Tail recursion is an increase in the actual expressive
power of XSLT. 

Tom Myers


 XSL-List info and archive:  http://www.mulberrytech.com/xsl/xsl-list