24568 2014-02-06 21:26:47 +0000 Is the type system really a lattice? Or just a partially ordered set? 2014-10-20 12:28:53 +0000 1 1 1 Unclassified XPath / XQuery / XSLT Data Model 3.0 Proposed Recommendation PC All RESOLVED FIXED P2 normal --- 24569 1 cmsmcq ndw andrew_coleman public-qt-comments oldest_to_newest 99953 0 cmsmcq 2014-02-06 21:26:47 +0000 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. 113029 1 ndw 2014-10-13 16:36:37 +0000 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.