[xsl] Fwd: [saxon] About limiting recursion depth (was: Stopping the evaluation of an XQuery in .NET)

Subject: [xsl] Fwd: [saxon] About limiting recursion depth (was: Stopping the evaluation of an XQuery in .NET)
From: "Dimitre Novatchev" <dnovatchev@xxxxxxxxx>
Date: Wed, 16 Jul 2008 06:47:23 -0700
Forwarding this to the xsl-list because of the universal scope of the topic:


---------- Forwarded message ----------
From: Dimitre Novatchev <dnovatchev@xxxxxxxxx>
Date: Wed, Jul 16, 2008 at 6:43 AM
Subject: Re: [saxon] About limiting recursion depth (was: Stopping the
evaluation of an XQuery in .NET)
To: Mailing list for the SAXON XSLT and XQuery processor
<saxon-help@xxxxxxxxxxxxxxxxxxxxx>


> > The other relevant point, of course, is that if your "infinite recursion"
> > involves a tail-call, then you won't get a stack overflow exception anyway;
> > instead you will get an infinite loop.
> >
>
> I was under the impression that tail-call optimization was only
> available on the paid SA edition of Saxon? And, though I may be wrong
> here, the majority of your users are the open source / free version users?

Perhaps at this moment we should be reminded that different XSLT
processors handle tail recursion differently, and some (most) do not
handle it at all. To avoid the consequences of very deep recursion one
can always use the DVC (Divide and Conquer) technique, which is
independent of XSLT processor vendor.

A refresher: using DVC the maximum recursion depth is brought down
from N to log2(N). That means, for example, from one million to just
nineteen.

Of course, DVC is not always straightforward (I remember once I
intended to convert the LR-parser available in FXSL from left-to-right
to a DVC one :)  ).

However, if the problem can be solved with some kind of folding (using
a function such as f:foldl() or f:foldr(), or f:fold-tree()), and most
problem can!, then one can simply use the DVC implementation of
f:foldl(), available in FXSL. No additional effort involved!


--
Cheers,
Dimitre Novatchev
---------------------------------------
Truly great madness cannot be achieved without significant intelligence.
---------------------------------------
To invent, you need a good imagination and a pile of junk
-------------------------------------
Never fight an inanimate object
-------------------------------------
You've achieved success in your field when you don't know whether what
you're doing is work or play



On Wed, Jul 16, 2008 at 1:37 AM, Abel Braaksma <abel.online@xxxxxxxxx> wrote:
>
> Michael Kay wrote:
> > Thanks for this info.
> >
> > The other relevant point, of course, is that if your "infinite recursion"
> > involves a tail-call, then you won't get a stack overflow exception anyway;
> > instead you will get an infinite loop.
> >
>
> I was under the impression that tail-call optimization was only
> available on the paid SA edition of Saxon? And, though I may be wrong
> here, the majority of your users are the open source / free version users?
>
> > Perhaps I need to add an option to limit the recursive depth at the Saxon
> > level. I can't say I'm enthusiastic about this: (a) it involves a run-time
> > cost, and (b) 99.99% of users won't know how to set it correctly.
> >
>
> If it helps: a "competitor" product, Altova XML, has an option to limit
> the recursion depth. However, setting it only yields effect on low
> values (it seems to have a build in limit that it cannot surpass, which
> makes the "competitor" a bad candidate for deep recursion projects).
>
> Maybe you can include it in a debug version of the project? That way one
> would only use it while testing, using the debug version, enabling
> maximum recursion depth. And in the release version all these checks are
> removed.
>
> Cheers,
> -- Abel
>
>
> -------------------------------------------------------------------------
> This SF.Net email is sponsored by the Moblin Your Move Developer's challenge
> Build the coolest Linux based applications with Moblin SDK & win great prizes
> Grand prize is a trip for two to an Open Source event anywhere in the world
> http://moblin-contest.org/redirect.php?banner_id=100&url=/
> _______________________________________________
> saxon-help mailing list archived at http://saxon.markmail.org/
> saxon-help@xxxxxxxxxxxxxxxxxxxxx
> https://lists.sourceforge.net/lists/listinfo/saxon-help



-- 
Cheers,
Dimitre Novatchev
---------------------------------------
Truly great madness cannot be achieved without significant intelligence.
---------------------------------------
To invent, you need a good imagination and a pile of junk
-------------------------------------
Never fight an inanimate object
-------------------------------------
You've achieved success in your field when you don't know whether what
you're doing is work or play

Current Thread