Learn how easy it is to sync an existing GitHub or Google Code repo to a SourceForge project!

## Re: [saxon] Problems with Tail Recursion again

 Re: [saxon] Problems with Tail Recursion again From: Michael Kay - 2007-05-05 09:26:37 ```> One is to recognize that when \$thisRow has cardinality > one-or-more, then \$thisRow[last()] (and indeed \$thisRow[1]) > will have cardinality exactly-one. That's something of a > special case and one expects it won't come up that often. I've added this special case to the cardinality computation for filter expressions and it solves the problem. Pushing cardinality (and item type) checks into the branches of a choose is a bit more difficult, but should also have more widespread benefits. Michael Kay http://www.saxonica.com/ ```

 [saxon] Problems with Tail Recursion again From: Dimitre Novatchev - 2007-05-04 19:47:20 ```Please, do have a look at the comments on Jeni's "Levenstein's Distance" article, and this one in particlar: http://www.jenitennison.com/blog/node/11#comment-54 What should one do in order for tail recursion (TR) in functions to be recognised by Saxon? -- 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 ```
 Re: [saxon] Problems with Tail Recursion again From: David Carlisle - 2007-05-04 21:30:47 ``` > Please, do have a look at the comments on Jeni's "Levenstein's > Distance" article, and this one in particlar: In case it helps here's a specific example discussed on Jeni's blog (but I didn't post all the code there) As far as I can see the function and template versions are "equally" tail recursive, but as you see the function version fails much earlier. Perhaps not surprisingly the template version also hits the limit if TP tracing is turned on. Code at end. \$ time saxon8 -it function l.xsl length=50 Error on line 106 of file:/c:/tmp/l.xsl: Too many nested function calls. May be due to infinite recursion. Transformation failed: Run-time errors were reported real 0m2.213s user 0m0.061s sys 0m0.046s \$ time saxon8 -it template l.xsl length=50 8 real 0m7.581s user 0m0.092s sys 0m0.015s \$ time saxon8 -TP -it template l.xsl length=50 2>&1 | tail
 Re: [saxon] Problems with Tail Recursion again From: Rashmi Rubdi - 2007-05-04 22:23:06 ```I just noticed this thread, sorry my comments are irrelevant, but I just wanted to point out a few things... On 5/4/07, David Carlisle wrote: > Perhaps not surprisingly the template version also hits the limit if TP > tracing is turned on. The above limit can be extended by increasing the memory (stack frames) used by recursive function in question with the -Xss ####k option. > \$ time saxon8 -it function l.xsl length=50 > Error on line 106 of file:/c:/tmp/l.xsl: > Too many nested function calls. May be due to infinite recursion. I too got the above message while calculating the factorial recursively (normal recursion , not tail recursion) , and by extending the memory with -Xss , more stack frames were made available. Sorry if you all already know this. -Regards Rashmi ```
 Re: [saxon] Problems with Tail Recursion again From: Michael Kay - 2007-05-04 23:21:09 ```> Please, do have a look at the comments on Jeni's > "Levenstein's Distance" article, and this one in particlar: > > http://www.jenitennison.com/blog/node/11#comment-54 > > What should one do in order for tail recursion (TR) in > functions to be recognised by Saxon? Thanks for alerting me to this. It's certainly not obvious why tail-call optimization isn't kicking in here (but it is late in the evening and I'm just back from a long journey...) Michael Kay http://www.saxonica.com/ ```
 Re: [saxon] Problems with Tail Recursion again From: Michael Kay - 2007-05-05 09:06:58 ```The reason the function isn't being treated as tail recursive is because it's doing a cardinality check on the function result. This is to implement the "as=xs:integer". The cardinality check is being applied because the other branch of the choice (the \$thisRow[last()]) has a static cardinality of zero-or-one. There are two things I could do to improve matters here. One is to recognize that when \$thisRow has cardinality one-or-more, then \$thisRow[last()] (and indeed \$thisRow[1]) will have cardinality exactly-one. That's something of a special case and one expects it won't come up that often. This other thing is to move the cardinality check into the branches of the choice where it is actually needed. It's true that templates sometimes benefit from tail recursion in cases where functions don't. The main reason for this is that templates are always evaluated in push mode, where concatenation of the result into a sequence is essentially a null operation. Functions are evaluated in pull or push mode depending on the circumstances, and it's a run-time decision. In this case the template isn't tail-recursive for the same reason as the function, that is, because of the (unnecessary) cardinality check applied to the result. Michael Kay http://www.saxonica.com/ > -----Original Message----- > From: saxon-help-bounces@... > [mailto:saxon-help-bounces@...] On Behalf > Of Dimitre Novatchev > Sent: 04 May 2007 20:47 > To: Mailing list for SAXON XSLT queries > Subject: [saxon] Problems with Tail Recursion again > > Please, do have a look at the comments on Jeni's > "Levenstein's Distance" article, and this one in particlar: > > http://www.jenitennison.com/blog/node/11#comment-54 > > What should one do in order for tail recursion (TR) in > functions to be recognised by Saxon? > > -- > 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 > > -------------------------------------------------------------- > ----------- > This SF.net email is sponsored by DB2 Express Download DB2 > Express C - the FREE version of DB2 express and take control > of your XML. No limits. Just data. Click to get it now. > http://sourceforge.net/powerbar/db2/ > _______________________________________________ > saxon-help mailing list > saxon-help@... > https://lists.sourceforge.net/lists/listinfo/saxon-help ```
 Re: [saxon] Problems with Tail Recursion again From: Michael Kay - 2007-05-05 09:26:37 ```> One is to recognize that when \$thisRow has cardinality > one-or-more, then \$thisRow[last()] (and indeed \$thisRow[1]) > will have cardinality exactly-one. That's something of a > special case and one expects it won't come up that often. I've added this special case to the cardinality computation for filter expressions and it solves the problem. Pushing cardinality (and item type) checks into the branches of a choose is a bit more difficult, but should also have more widespread benefits. Michael Kay http://www.saxonica.com/ ```