Subject: Re: [xsl] W3C Specification of fn:filter() -- is this a bug in the document or in Saxon? From: "Dimitre Novatchev dnovatchev@xxxxxxxxx" <xsl-list-service@xxxxxxxxxxxxxxxxxxxxxx> Date: Mon, 9 Sep 2019 13:20:37 -0000 |
> I'm aware that some languages have attempted to formulate rules in the language semantics making tail call optimization mandatory. The XSL and > XQuery WGs considered several times whether to try and make the whole "errors and optimization" rules more formal and rigorous, and we decided we > didn't have the skills and resources to do it, for the same reason that work on the XQuery formal semantics was abandoned. > > Michael Kay > Saxonica The original problem can be eliminated (and the same solution may be applicable in similar cases), if the "equivalent implementations" were replaced with non-recursive code, As in this case -- just use: function($f as function(item()) as xs:boolean, $list as item()*) as item()* { $list ! .[$f(.)] } Thanks, Dimitre On Sun, Sep 8, 2019 at 10:22 PM Michael Kay mike@xxxxxxxxxxxx < xsl-list-service@xxxxxxxxxxxxxxxxxxxxxx> wrote: > The "errors and optimization" rule in XPath says that processors can quite > legitimately rewrite one expression with another that has different > resource requirements and that therefore has different failure > characteristics. This is by design. It means that either of these > formulations could fail with a stack overflow, and in that sense they are > indeed equivalent. > > I'm aware that some languages have attempted to formulate rules in the > language semantics making tail call optimization mandatory. The XSL and > XQuery WGs considered several times whether to try and make the whole > "errors and optimization" rules more formal and rigorous, and we decided we > didn't have the skills and resources to do it, for the same reason that > work on the XQuery formal semantics was abandoned. > > Michael Kay > Saxonica > > On 9 Sep 2019, at 02:44, Dimitre Novatchev dnovatchev@xxxxxxxxx < > xsl-list-service@xxxxxxxxxxxxxxxxxxxxxx> wrote: > > > You can never guarantee that two expressions are equivalent in your > > sense, because of "errors and optimization". Any construct might raise > > an error - in the case of this example, stack overflow if the recursion > > gets too deep. > > What about tail-recursion? > > For years we have known recursive expressions whose tail-recursiveness is > correctly recognized in BaseX and it provides correct evaluation regardless > of the input size (recursion depth) but other processors fail miserably... > > How much value for the developers would have been provided by the > specification if it mandated proper handling of tail-recursion!!! > > The value provided in a document is rather debatable when specifying > "equivalent implementations" that blow up for reasonably long inputs > (several thousand items isn't too high!) when other implementations could > have been provided that demonstrate equivalence with much longer inputs > (millions of items) > > Also, why in an XPath specification give "equivalent implementations" in > two different languages neither of which is XPath? > > Cheers, > Dimitre > > On Sun, Sep 8, 2019 at 5:54 PM Liam R. E. Quin liam@xxxxxxxxxxxxxxxx < > xsl-list-service@xxxxxxxxxxxxxxxxxxxxxx> wrote: > >> On Mon, 2019-09-09 at 00:18 +0000, Dimitre Novatchev >> dnovatchev@xxxxxxxxx wrote: >> > The W3C F&O 3.1 spec (at >> > https://www.w3.org/TR/xpath-functions-31/#func-filter ) says: >> > >> > Rules >> > >> > The effect of the function is equivalent to the following >> [...] >> > >> > Because "equivalent" means the two functions must produce the same >> > result >> > for for all possible values in the same set of arguments, >> >> That is one possible definition of "equivalent" but it is not the one >> used in the Functions and Operators document... >> >> You can never guarantee that two expressions are equivalent in your >> sense, because of "errors and optimization". Any construct might raise >> an error - in the case of this example, stack overflow if the recursion >> gets too deep. >> >> Liam >> >> -- >> Liam Quin, https://www.delightfulcomputing.com/ >> Available for XML/Document/Information Architecture/XSLT/ >> XSL/XQuery/Web/Text Processing/A11Y training, work & consulting. >> Carefoot Web-slave for historical images http://www.fromoldbooks.org/
Current Thread |
---|
|
<- Previous | Index | Next -> |
---|---|---|
Re: [xsl] W3C Specification of fn:f, Michael Kay mike@xxx | Thread | Re: [xsl] W3C Specification of fn:f, Michael Kay mike@xxx |
[xsl] [Annon] - XSpec 1.4.0 is out, Christophe Marchand | Date | Re: [xsl] W3C Specification of fn:f, Michael Kay mike@xxx |
Month |