[25 January 2010; correct botched formulation, 26 January]
The XPath 1.0 puzzle introduced and discussed in earlier posts continues to occupy some of my thoughts. Consider the document which can be written
<a><b/><b/><b/></a>
The central question is this: given an instance of the XPath 1.0 data model corresponding to this document (or to any equivalent document), how many element nodes are present in the instance?
It turns out that not only are the answers four and two both consistent (as far as I can tell) with the definition of the XPath 1.0 data model, but that other answers are possible as well. Well, another answer.
Consider the document
<!DOCTYPE a [ <!ELEMENT a ANY> <!ELEMENT b ANY> <!ENTITY b '<b/>' > ]> <a>&b;&b;<b/></a>
This is not the same serial-form XML document as the one at the top of the page, and the data-model equivalent is not necessarily the same, either, I think. But they both have a document element of type ’a’, whose ordered list of children has length three, with each child being of type ‘b’.
If we take token as denoting some physical object, marks on paper or some other way of writing a character type (here, pixels on screens, magnetic fields on suitable media, or optical effects on other media), which I am told is its proper meaning as it was introduced by Peirce, then here there appear to me to be three string tokens matching the element production (one ‘a’ and two ‘b’s), not four and not two, and thus three element nodes in the data model, not four and not two.
I’m not really at all sure that the right way to define XML documents (and by extension XML elements) is as strings. But if we do wish to say that an element is a string (of some kind), there seem to be at least three different approaches we can take:
- a sequence of character types (i.e. a string-type)
- a sequence of character tokens (i.e. a string-token)
- an occurrence, within some context, of a sequence of character types
Some of the issues relating to these concepts are very well laid out in the article “Types and Tokens” written by Linda Wetzel for the Stanford Encyclopedia of Philosophy. It is interesting to know that SGML and XML accomplish simply, through entity references, what some philosophers have regarded as impossible: we have more occurrences of a thing than we have tokens for it. In the second document given above, it seems clear (at least to me, but I am no philosopher) that there are two string-tokens of type “<b/>” — one in the entity declaration and one in the document content — and three occurrences of that string-type in the document body. When entity expansion is performed by a machine, we are quite likely to be able to identify different tokens with the different occurrences of the string-type (as long as we are willing to entertain time-slices as part of our definition of string-token), but when I just look at the document and count the occurrences of the string-type, I don’t create new tokens in the physical world (unless you want to include mental acts as tokens, but I am pretty sure that that would be a bad idea).
The good news is that there is plenty of philosophical light to throw on these issues, and the issues are well understood by philosophers. Also good news is that the XPath 1.0 data model appears to be consistent with all three possible views.
The bad news, I think, is that while the philosophers understand the issues quite well, they don’t agree on what to do about them. Also bad news is that the XPath 1.0 spec is consistent with all three views, even though it clearly wants to have a single answer to questions like “How many elements are in this document?”. Also, it seems clear that the XPath 1.0 spec really wants to view elements as occurrences (or, at least, the occurrence story produces the results the XPath 1.0 spec relies on its data model producing), but the notion of occurrence appears to be regarded by philosophers as easily the most problematic of the three concepts competing for our patronage.
Fortunately, to make the XPath 1.0 data model do what its creators wanted it to do, all that is necessary is to say explicitly that no node occurs more than once (there’s that word again!) in its parent’s ordered list of children. Or, equivalently, that the cardinality of the set of child nodes is the same as the length of the ordered list of children.
[In full XPath terms, we may also think of it as forbidding any node to appear among the result of evaluating the expression “preceding-sibling::* | following-sibling::*” with that node as the context item. But the data model does not provide a primitive definition of sibling-hood, so it can’t conveniently be formulated that way in the data model.]
xpath 1 (unlike xpath 2) does not have lists in its data model, only sets of nodes.
In Xpath you only have a _set_ of child nodes of each parent that may then be ordered by document order. Given its set based semantics the possibility of having the same thing occur twice can not arise (unlike xpath 2 which is sequence based so xpath steps have to be defined to order and remove duplicates)
I think asking if your interpretations are compatible with xpath is possibly the wrong question. xpath just assumes it is given a tree (or tree view) as input, so if the tree view of any of the given examples was “a single element node with name wibble” then that would i think be compatible with xpath, the only question is then: is parser that reported that tree view compatible with XML?
That’s very hard to answer as XML is so loose in defining exactly what an xml processor (parser) must report. The expectation is that it reports the elements it sees in the order it sees them but that is only implied, not stated explicitly.
You may be right, of course. I am relying on the first sentence of the paragraph immediately preceding section 5.1, which reads
From this I infer that the list of children is primary, in some sense, and the set of children follows logically from it. It would also be possible to define it as you describe, specifying a set of children, and then describing the imposition of document order upon them. But the paragraph on document order in the opening of section 5 doesn’t say anything about the relative position of siblings; I rather think document order for siblings is supposed to follow from the ordering imposed by the ordered list of children (although this is not stated explicitly).
We may also have different understandings of the role of the data model in XPath 1.0. Is it intended that the data model be well defined only for the output of an XML parser, or is it intended that the rules for the data model define a set of abstract structures which may be created by any desired means (including parsing an XML character stream) and operated upon by an XPath 1.0 implementation? I understand the latter to be the goal; if the goal is only the former, of course, much of my worry has been wasted (but in that case, there are a number of statements in the definition of the data model which seem pointless since they follow automatically from the premise that the data model is to deal only with output from an XML parser).
I think the data model is not tied to an XML parser, just as you say. And for example Mike Kay’s XSLT book had an xslt 1 example using a GEDCOM parser that returned sax events, html parsers are also common (tagsoup in particular) so this is a practical point not just a theoretical one.
But I think your basic question is still unanswerable if you only want to go by the letter of the xml spec. You ask how many element nodes are in
<a><b/><b/><b/></a>but if the xml parser checks that this is well formed according to the constraints specified in the XML rec, but then returns a single node with name “david” to the xslt engine as the input from which it has to build a tree that conforms to the xpath 1 (or 2) data model, I don’t think that it is absolutely clear that the xml parser (or anything else) is clearly non conforming.
David, I think we are in agreement. I think the expectation of the creators of XPath 1.0 is clear, but to the extent that they relied on an appeal to XML to determine the matter, that is a flaw in the definition of the data model, first for stylistic reasons (it would be better to make the definition free-standing and as far as possible free of appeals to other specs) and second because the XML spec does not provide (I would say, is not interested in providing) a unique answer to questions like “how many elements are in this document?” (I am tempted to say “just as makers of sewing pins do not label boxes of pins with estimates of how many angels can dance on the heads of this particular size of pin”, but that would suggest that I think element identity is never of practical importance — it has plenty, but the XML spec was created by people who for better and worse did not believe themselves to be in the business of nailing stuff like that down.)
In particular, the XML Rec does not require a conforming XML processor to report elements without attributes at all.
Would some idea of weak and strong equivalence help?
E.g. An infoset for the XML document with the entities (preserving the references) is weakly equivalent to the XPath data model document. A similar infoset for the XML document without is (more?) strongly equivalent to the XPath data model document.
I don’t see how you can ever get 3 (or 2), by the way. The Xpath data model only allows counting and uniqueness by document order, which is a post-parse (pose entity insertion) concept. So an implementation may indeed preparse an entity like “<b>” and re-emit it on multiple references as an implementation technique, I don’t see that it is a difference that is ever surfaced in XDM.
Rick, thanks for the comment. A clear definition of various kinds of equivalence is certainly an interesting topic for XM, as it would be for any markup language.
As regards “how [one] can ever get 3 (or 2)”, I think that if by “the Xpath data model” you mean the abstract objects assumed by the XPath 1.0 spec then you are quite right; there has never been any doubt on that score, as far as I know. But if by “the XPath 1.0 data model” you mean the abstract objects defined by the section of the XPath 1.0 spec entitled “The data model”, then a claim that the definition of the data model clearly determines a particular answer needs to be supported by arguments based on the text of the spec. Can you point to some rule given in section 5 of the XPath 1.0 spec not satisfied by a data model instance in which the document contains two element nodes? Can you identify some gap in the argument given in the preceding post that such an instance conforms to all the data model rules enunciated in the spec, and possesses all the properties it guarantees to its instances?
It won’t do to appeal to document order as having certain properties, given that the question involves identifying just what properties are in fact guaranteed to document order by the definition offered in the spec. And in any case I think my earlier post shows clearly that the instance with two element nodes clearly satisfies all the relevant constraints on document order: the root node is first, and the parent node precedes the child.
Doesn’t this:
answer your request for prose in section 5 which mandates the answer
‘4’ in your example?
Henry, thank you for your comment.
No, I don’t think the requirement for a total ordering suffices to provide an answer here. Following the same line taken in an earlier post on this subject, an instance of the model can comply with the XPath 1.0 spec by saying that we have two
belements (one occurring twice and one occurring onces) and oneaelement, and the total ordering is:a, thebthat occurs twice, and finally thebthat occurs only once.