[XSL-LIST Mailing List Archive Home] [By Thread] [By Date] [Recent Entries] [Reply To This Message] Re: W3C Specification of fn:filter() -- is this a bug
> 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/
|
PURCHASE STYLUS STUDIO ONLINE TODAY!Purchasing Stylus Studio from our online shop is Easy, Secure and Value Priced! Download The World's Best XML IDE!Accelerate XML development with our award-winning XML IDE - Download a free trial today! Subscribe in XML format
|