8724 2010-01-12 12:06:47 +0000 [XQuery30] Function items need to know if they are non-deterministic 2011-11-01 19:20:49 +0000 1 1 1 Unclassified XPath / XQuery / XSLT XQuery 3.0 Working drafts PC Linux RESOLVED FIXED P2 minor --- 1 john.snelson john.snelson jim.melton jmdyck jonathan.robie jonathan.robie mike public-qt-comments oldest_to_newest 30968 0 john.snelson 2010-01-12 12:06:47 +0000 The signatures of function items need to record if the function is deterministic or not. Dynamic function invocation needs to use that information to restrict the optimizations performed on the function invocation. Looking forward to XQuery Update and XQuery 1.1 support, the signatures should also contain information on whether a function is updating, sequential etc. 31404 1 jmdyck 2010-02-02 20:47:04 +0000 Indicating determinism in the signature of the function item would make it part of the item's type, which I'm not convinced is wanted. Instead, determinism could be another property of the function item (i.e., a "sibling" of the signature rather than part of it). Either way, shouldn't this be raised against Data Model 1.1 (Section 2.7) rather than XQuery 1.1? 31416 2 john.snelson 2010-02-03 11:34:48 +0000 (In reply to comment #1) > Indicating determinism in the signature of the function item would make it part > of the item's type, which I'm not convinced is wanted. Well I guess I was thinking that determinism is part of the information statically known about a function item. But maybe your right that this is different to the function signature. > Either way, shouldn't this be raised against Data Model 1.1 (Section 2.7) > rather than XQuery 1.1? It's against both Data Model 1.1 and XQuery 1.1. The XQuery 1.1 part is to add rules to restrict optimization of dynamic function invocations if the function item is non-deterministic. 31477 3 john.snelson 2010-02-05 11:47:47 +0000 Proposal: Data Model 1.1, 2.7 Function Items Insert 4th bullet * Whether the function is deterministic (either declared or determined by static analysis) XQuery 1.1, 3.1.8 Dynamic Function Invocation Insert 4th and 5th paragraph A function item can be deterministic or non-deterministic. When rewriting expressions into equivalent expressions, as described in 2.3.4 Errors and Optimization, a conforming XQuery implementation must ensure that each run-time dynamic invocation of a non-deterministic function item in the original expression results in exactly one run-time invocation of the function item in the rewritten expression. NOTE: The deterministic behaviour of a function item is a dynamic run-time property, but may be available through static analysis in some cases. Unless otherwise determined, it is most correct to assume a function item for any given dynamic function invocation will be non-deterministic. 31486 4 jmdyck 2010-02-05 20:04:26 +0000 (In reply to comment #3) > > * Whether the function is deterministic (either declared or determined by > static analysis) The parenthetical is incorrect, as it implies that the property can be determined statically, which you point out is not (always) the case. 31512 5 john.snelson 2010-02-05 20:46:02 +0000 (In reply to comment #4) > (In reply to comment #3) > > > > * Whether the function is deterministic (either declared or determined by > > static analysis) > > The parenthetical is incorrect, as it implies that the property can be > determined statically, which you point out is not (always) the case. No; it can always be determined statically at the point of function item creation. It's at invocation that it can't always be accurately determined statically - but you can always guess that it's non-deterministic and get spec compliant behaviour. 31569 6 jmdyck 2010-02-06 01:51:27 +0000 (In reply to comment #5) > (In reply to comment #4) > > (In reply to comment #3) > > > > > > * Whether the function is deterministic (either declared or determined by > > > static analysis) > > > > The parenthetical is incorrect, as it implies that the property can be > > determined statically, which you point out is not (always) the case. > > No; it can always be determined statically at the point of function item > creation. It's at invocation that it can't always be accurately determined > statically Consider a function item (A) whose function's body is basically a dynamic function invocation (DFI). Since the determinism of the function item (B) invoked by the DFI can't necessarily be determined statically, neither can the determinism of the original function item (A). 31579 7 john.snelson 2010-02-06 02:41:30 +0000 (In reply to comment #6) > (In reply to comment #5) > > No; it can always be determined statically at the point of function item > > creation. It's at invocation that it can't always be accurately determined > > statically > > Consider a function item (A) whose function's body is basically a dynamic > function invocation (DFI). Since the determinism of the function item (B) > invoked by the DFI can't necessarily be determined statically, neither can the > determinism of the original function item (A). But the determinism of a dynamic function invocation can always be statically determined - just not always accurately. 31580 8 jmdyck 2010-02-06 03:26:23 +0000 (In reply to comment #7) > (In reply to comment #6) > > > > Consider a function item (A) whose function's body is basically a dynamic > > function invocation (DFI). Since the determinism of the function item (B) > > invoked by the DFI can't necessarily be determined statically, neither can the > > determinism of the original function item (A). > > But the determinism of a dynamic function invocation can always be statically > determined - just not always accurately. Right. And that inaccuracy propagates up to function item A. I.e., the determinism that one statically infers for A is not necessarily as precise as the actual determinism of A. I.e., you cannot always statically ascertain the determinism of a function item, which was my original point. 31675 9 mike 2010-02-09 18:11:18 +0000 In discussion, I put forward an alternative suggestion: it should not be permitted to bind a function item to a non-deterministic function. This would mean that the compiler will always know statically when calling a dynamic function invocation that the result is deterministic. This seems important for optimization. 31848 10 john.snelson 2010-02-12 00:51:02 +0000 (In reply to comment #9) > In discussion, I put forward an alternative suggestion: it should not be > permitted to bind a function item to a non-deterministic function. This would > mean that the compiler will always know statically when calling a dynamic > function invocation that the result is deterministic. This seems important for > optimization. Given time to reconsider, I've got sympathy with this suggestion. I don't think that the optimization options are totally lost with the possibility of non-deterministic function items (ie: partial specialization, data flow analysis), but they are complicated and I don't see an important use case for them. This approach would seem to require a firming up of the static analysis of determinism, so that the error conditions are well defined. 32741 11 john.snelson 2010-03-01 13:08:11 +0000 An alternative (and wider reaching) solution for this bug is proposed here: http://lists.w3.org/Archives/Member/w3c-xsl-query/2010Feb/0204.html http://jpcs.posterous.com/proposal-to-add-function-annotations-to-xquer 59434 12 jonathan.robie 2011-11-01 19:20:49 +0000 Overtaken by events. We added the proposal in Comment #11.