[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

Subject: Re: 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: Wed, 11 Sep 2019 22:02:39 -0000
Re:  W3C Specification of fn:filter() -- is this a bug
>  To my mind the solution is to add to the literature, not try to repeal
>  the past. Of course, you are doing that (as will your forthcoming
>  papers on the topic). Which is the part I find interesting and
>  instructive, not the fault-finding.

Wendell -- Absolutely!

I was just trying to use the suggested "equivalent implementation" as a
base for my own tests -- then the question naturally had to arise -- Why on
earth did they provide **this** implementation and not something better
(shorter, non-recursive, easier to read and hopefully in pure XPath 3.1
only)

>  even if we were to concede the truth of everything you are
>  saying, no standards committee can operate forever can it?

Yes, and we have the good example of Satoshi Nakamoto who published just a
single white paper that is revolutionizing technology today.

Most good results we all are aware of were produced outside of any
committee :)

Cheers,
Dimitre

On Wed, Sep 11, 2019 at 2:17 PM Wendell Piez wapiez@xxxxxxxxxxxxxxx <
xsl-list-service@xxxxxxxxxxxxxxxxxxxxxx> wrote:

> Dimitre -- even if we were to concede the truth of everything you are
> saying, no standards committee can operate forever can it?
>
> To my mind the solution is to add to the literature, not try to repeal
> the past. Of course, you are doing that (as will your forthcoming
> papers on the topic). Which is the part I find interesting and
> instructive, not the fault-finding.
>
> Cheers, Wendell
>
> On Mon, Sep 9, 2019 at 6:43 PM Dimitre Novatchev dnovatchev@xxxxxxxxx
> <xsl-list-service@xxxxxxxxxxxxxxxxxxxxxx> wrote:
> >
> > > The alternative formulation wouldn't change anything. It would still
> have the same theoretical weakness that the rewritten
> > > expression might use different resources and therefore fail under
> different circumstances. It might make it less likely that the
> > > two formulations would differ in practice, but this is a
> specification, not a suggested implementation.
> > >
> > > The convention in specifications is to ignore efficiency
> considerations when specifying functionality. Saying that A is equivalent
> > > to B carries implicit caveats, like, "provided you have enough memory
> and no-one turns the power switch off while waiting for it
> > > to finish".
> >
> > Sounds like a convenient excuse for providing code that may be far from
> good :(
> >
> > Dimitre
> >
> > On Mon, Sep 9, 2019 at 7:12 AM Michael Kay mike@xxxxxxxxxxxx <
> xsl-list-service@xxxxxxxxxxxxxxxxxxxxxx> wrote:
> > >
> > > The alternative formulation wouldn't change anything. It would still
> have the same theoretical weakness that the rewritten expression might use
> different resources and therefore fail under different circumstances. It
> might make it less likely that the two formulations would differ in
> practice, but this is a specification, not a suggested implementation.
> > >
> > > The convention in specifications is to ignore efficiency
> considerations when specifying functionality. Saying that A is equivalent
> to B carries implicit caveats, like, "provided you have enough memory and
> no-one turns the power switch off while waiting for it to finish".
> > >
> > > Michael Kay
> > > Saxonica
> > >
> > > On 9 Sep 2019, at 14:20, Dimitre Novatchev dnovatchev@xxxxxxxxx <
> xsl-list-service@xxxxxxxxxxxxxxxxxxxxxx> wrote:
> > >
> > > > 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/
> > >>>
> > >
> > > XSL-List info and archive
> > > EasyUnsubscribe (by email)
> > >
> > >
> > > XSL-List info and archive
> > > EasyUnsubscribe (by email)

Current Thread

PURCHASE STYLUS STUDIO ONLINE TODAY!

Purchasing Stylus Studio from our online shop is Easy, Secure and Value Priced!

Buy Stylus Studio Now

Download The World's Best XML IDE!

Accelerate XML development with our award-winning XML IDE - Download a free trial today!

Don't miss another message! Subscribe to this list today.
Email
First Name
Last Name
Company
Subscribe in XML format
RSS 2.0
Atom 0.3
Site Map | Privacy Policy | Terms of Use | Trademarks
Free Stylus Studio XML Training:
W3C Member
Stylus Studio® and DataDirect XQuery ™are products from DataDirect Technologies, is a registered trademark of Progress Software Corporation, in the U.S. and other countries. © 2004-2013 All Rights Reserved.