xsl-list
[Top] [All Lists]

Re: [xsl] W3C Specification of fn:filter() -- is this a bug in the document or in Saxon?

2019-09-11 16:17:09
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(_at_)gmail(_dot_)com
<xsl-list-service(_at_)lists(_dot_)mulberrytech(_dot_)com> 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(_at_)saxonica(_dot_)com 
<xsl-list-service(_at_)lists(_dot_)mulberrytech(_dot_)com> 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(_at_)gmail(_dot_)com 
<xsl-list-service(_at_)lists(_dot_)mulberrytech(_dot_)com> 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(_at_)saxonica(_dot_)com 
<xsl-list-service(_at_)lists(_dot_)mulberrytech(_dot_)com> 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(_at_)gmail(_dot_)com 
<xsl-list-service(_at_)lists(_dot_)mulberrytech(_dot_)com> 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(_at_)fromoldbooks(_dot_)org 
<xsl-list-service(_at_)lists(_dot_)mulberrytech(_dot_)com> wrote:

On Mon, 2019-09-09 at 00:18 +0000, Dimitre Novatchev
dnovatchev(_at_)gmail(_dot_)com 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)



--
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
-------------------------------------
To avoid situations in which you might make mistakes may be the
biggest mistake of all
------------------------------------
Quality means doing it right when no one is looking.
-------------------------------------
You've achieved success in your field when you don't know whether what you're 
doing is work or play
-------------------------------------
To achieve the impossible dream, try going to sleep.
-------------------------------------
Facts do not cease to exist because they are ignored.
-------------------------------------
Typing monkeys will write all Shakespeare's works in 200yrs.Will they write 
all patents, too? :)
-------------------------------------
Sanity is madness put to good use.
-------------------------------------
I finally figured out the only reason to be alive is to enjoy it.

XSL-List info and archive
EasyUnsubscribe (by email)



-- 
...Wendell Piez... ...wendell -at- nist -dot- gov...
...wendellpiez.com... ...pellucidliterature.org... ...pausepress.org...
...github.com/wendellpiez... ...gitlab.coko.foundation/wendell...
--~----------------------------------------------------------------
XSL-List info and archive: http://www.mulberrytech.com/xsl/xsl-list
EasyUnsubscribe: http://lists.mulberrytech.com/unsub/xsl-list/1167547
or by email: xsl-list-unsub(_at_)lists(_dot_)mulberrytech(_dot_)com
--~--

<Prev in Thread] Current Thread [Next in Thread>