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

Previous Topic Next Topic
 
classic Classic list List threaded Threaded
3 messages Options
Reply | Threaded
Open this post in threaded view
|

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

Bugzilla from bugzilla@jessica.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: [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.

Reply | Threaded
Open this post in threaded view
|

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

Bugzilla from bugzilla@jessica.w3.org
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.

Reply | Threaded
Open this post in threaded view
|

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

Bugzilla from bugzilla@jessica.w3.org
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.