[Bug 24568] New: Is the type system really a lattice? Or just a partially ordered set?

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