https://www.w3.org/Bugs/Public/show_bug.cgi?id=24568
Bug ID: 24568 Summary: Is the type system really a lattice? Or just a partially ordered set? Product: XPath / XQuery / XSLT Version: Proposed Recommendation Hardware: PC OS: All Status: NEW Severity: normal Priority: P2 Component: Data Model 3.0 Assignee: [hidden email] Reporter: [hidden email] QA Contact: [hidden email] Section 2.7.4 Type system of the XDM PR draft [1] reads in part: Item types in the data model form a lattice rather than a hierarchy: in the relationship defined by the derived-from(A, B) function, some types are derived from more than one other type. Examples include functions (function(xs:string) as xs:int is substitutable for function(xs:NCName) as xs:int and also for function(xs:string) as xs:decimal), and union types (A is substitutable for union(A, B) and also for union(A, C). [1] http://www.w3.org/TR/xpath-datamodel-30/#types-hierarchy The text is correct to say that the set of types does not form a hierarchy. But do they form a lattice? My understanding (such as it is) is that a partially ordered set forms a lattice if and only if for any two members a and b of the set, there is a unique least upper bound of a and b, and a unique greatest lower bound for a and b. In section 19.2 [2], XSLT 3.0 says that two items do not necessarily have a unique least upper bound (join): In some cases the above entries require computation of the least common type of two types T and U. Since item types form a lattice rather than a hierarchy, there may be a set of types V such that T and U are both subtypes of every type in V, and no type in V is unambiguously the "least" common type in the sense that all the others are subtypes of it. In this situation the choice of which type in V to use as the inferred static type is implementation-defined. [2] http://www.w3.org/TR/xslt-30/#determining-static-type I'm not sure what pairs of items the XSLT spec has in mind, but if they exist, then it may be wrong to say that our types form a lattice. Unions are perhaps a sufficient example. Since XSD's union types are ordered (so the unions (A, B) and (B, A) are both supersets of both A and B), and there will be no other types definable in XSD which are intermediate between them and A or B, so they are both least upper bounds for the pair A and B. Functions (to take the other example named in the paragraph quoted from XDM) are described by XPath as forming a hierarchy -- but if we accept A and B as subtypes of both union(A, B) and union(B, A) then functions don't form a hierarchy, either. If the sequence of membertypes in the definition of unions is NOT considered significant for these purposes, then perhaps it is correct after all to say that the type system forms a lattice. But before deciding that all is well, it would be a good idea to find out why XSLT 3.0 says there may not be a unique least common type (which I am taking to mean least upper bound, or join) for two item types. -- You are receiving this mail because: You are the QA Contact for the bug. |
https://www.w3.org/Bugs/Public/show_bug.cgi?id=24568
--- Comment #1 from Norman Walsh <[hidden email]> --- The minutes of XML Query WG Face-To-Face Meeting #563 Minutes -- 2014-02-17 DAY ONE (https://lists.w3.org/Archives/Member/w3c-xsl-query/2014Feb/0095.html) record: J4.1.1 Bug 24568 - Is the type system really a lattice? Or just a partially ordered set? https://www.w3.org/Bugs/Public/show_bug.cgi?id=24568 Mike: I think that if you look at it certain ways the types may form a lattice, but if you look at just the types you have syntax for they don't. Propose removing the claim that it is a lattice. No objections. DECISION: Make the editorial change to remove the description of the type system as a lattice, adding a note that the type system is not a hierarchy. In addition, I see that the 3.1 data model now says, in part: "Item types in the data model form a directed graph, rather than a hierarchy or lattice: ..." I propose that this bug can be closed as overtaken by events. -- You are receiving this mail because: You are the QA Contact for the bug. |
In reply to this post by Bugzilla from bugzilla@jessica.w3.org
https://www.w3.org/Bugs/Public/show_bug.cgi?id=24568
Andrew Coleman <[hidden email]> changed: What |Removed |Added ---------------------------------------------------------------------------- Status|NEW |RESOLVED CC| |[hidden email] Resolution|--- |FIXED -- You are receiving this mail because: You are the QA Contact for the bug. |
Free forum by Nabble | Edit this page |