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
<mailto:mike(_at_)saxonica(_dot_)com>
<xsl-list-service(_at_)lists(_dot_)mulberrytech(_dot_)com
<mailto: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
<mailto:dnovatchev(_at_)gmail(_dot_)com>
<xsl-list-service(_at_)lists(_dot_)mulberrytech(_dot_)com
<mailto: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 <mailto:liam(_at_)fromoldbooks(_dot_)org>
<xsl-list-service(_at_)lists(_dot_)mulberrytech(_dot_)com
<mailto: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 <mailto:dnovatchev(_at_)gmail(_dot_)com>
wrote:
The W3C F&O 3.1 spec (at
https://www.w3.org/TR/xpath-functions-31/#func-filter
<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/
<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/
<http://www.fromoldbooks.org/>
XSL-List info and archive <http://www.mulberrytech.com/xsl/xsl-list>
EasyUnsubscribe <http://lists.mulberrytech.com/unsub/xsl-list/293509> (by
email <>)
--~----------------------------------------------------------------
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
--~--