- From: <bugzilla@jessica.w3.org>
- Date: Thu, 06 Feb 2014 21:26:47 +0000
- To: public-qt-comments@w3.org
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: ndw@nwalsh.com Reporter: cmsmcq@blackmesatech.com QA Contact: public-qt-comments@w3.org 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.
Received on Thursday, 6 February 2014 21:26:49 UTC