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.