Category Archives: XML

Introduction to XForms, 14-15 February 2011

Posted on by

[5 January 2011]

It’s official; on Monday and Tuesday, 14 and 15 February, I’ll be teaching a two-day hands-on course on XForms in Rockville, Maryland. Thanks to Mulberry Technologies for allowing me the use of their facilities.

If you use XML seriously, particularly in a multi-person project or organization (but even if you are on your own), and you don’t use XForms, then I think you owe it to yourself to look into the possibilities XForms offers for developing special-purpose editing interfaces for your XML documents. Sometimes, you want a specialized tool to perform one particular task on your documents. Consistency in some matters is a lot easier to achieve if you go over an entire body of material checking just the one thing in all documents. Special-purpose interfaces can help here.

For example: after long drawn-out battles, your project finally agrees on how to capitalize words in section headings: sentence case or title case? It would be nice to have a specialized editor that just showed you the section headings and let you edit them. Or suppose you decide it’s time to make a pass over your entire Web site to improve accessibility. As one task, you want to ensure that all of your images have alt text. That will be easier if you have an interface in which you can pull up each Web page and have a text widget next to each image allowing you to type in the description.

If you’re interested in the course, see the course Web page. If you’re interested in email announcements of courses (and other events at Black Mesa), subscribe to our (new!) announcements list.

Aquamacs, XEmacs, and psgml

Posted on by

[26 April 2010]

The other day I thought perhaps it was time to try Aquamacs again, a nice, actively maintained port of FSF Emacs to Mac OS X. I’ve been using a copy of XEmacs I compiled myself years ago, with Andrew Choi’s Carbon XEmacs patches, but recently it has accumulated some problems I don’t have the patience to diagnose.

Got Lennart Staflin’s psgml package (a major mode for SGML and XML documents) installed and compiled; this is a pre-requisite for any Emacs being habitable for me. (Why is package management such a dirty word in FSF Emacs, by the way?) And discovered that on one of my larger documents, psgml takes 50% longer in some tests (9 seconds vs 14 seconds) to parse a large document in Aquamacs than in XEmacs. In other tests, it was 9 seconds vs. 90 seconds (or so — I kept getting bored and losing count between sixty and eighty seconds).

I may not be leaving XEmacs after all (undiagnosed problems or no undiagnosed problems).

[Postscript, 7 December 2012. I did eventually move to Aquamacs, and have been very happy with it. The performance issues reported here have not recurred on the Intel CPU I’m currently using.]

Posted in XML

One way to define the XPath data model

Posted on by

[6 April 2010; addenda and copy editing 7-8 April 2010]

After discovering earlier this year that the definition of the XPath 1.0 data model falls short of the goal of guaranteeing the desired properties to all instances of the data model, I’ve been spending some time experimenting with alternative definitions, trying to see what must be specified a priori and what properties can be left to follow from others.

It’s no particular surprise that the data model can be defined in a variety of different ways. I’ve worked out three with a certain degree of precision. Here is one, which is not the usual way of defining things. For simplicity, it ignores attributes and namespace nodes; it’s easy enough to add them in once the foundations are a bit firmer.

Assume a non-empty finite set S and two binary relations R and Q on S, with the following properties [Some constraints are shown here as deleted: they were included in the first version of this list but later proved to be redundant; see below] :

  1. R is functional, acyclic, and injective (i.e. for any x and y, R(x) = R(y) implies x = y).
  2. There is exactly one member of S which is not in the domain of R (i.e. R(e) has no value), and exactly one which is not in the range of R (i.e. there is one element e such that for no element f do we have e = R(f)).
  3. Q is transitive and acyclic.
  4. The transitive reduction of Q is functional and injective.
  5. It will be observed that R essentially places the elements of S in a sequence without duplicates. For all elements e, f, g, h of S, if Q includes the pairs (e, f) and (g, h) and if g falls between e and f in the sequence defined by R (or, more formally, if the transitive closure of R contains the pairs (e, f), (e, g), and (g, f)), then h also falls between e and f in that sequence.
  6. The transitive closure of the inverse of R (i.e. R-1*) contains Q as a subset.
  7. The single element of S which is not in the domain of R is also neither in the domain nor the range of Q.

It turns out that if we have any relations R and Q defined on some set S, then we have an instance of the XPath 1.0 data model. The nodes in the model instance, the axes defining their interrelations, and so on can all be defined in terms of S, R, and Q.

For the moment, I’ll leave the details as an exercise for the reader. (I also realize, as I’m about to click “Publish”, that I have not actually checked to see whether the set of constraints given above is minimal. I started with a short list and added constraints until S, R, and Q sufficed to determine a unique data model instance, but I have not checked to see whether any of the later additions rendered any of the earlier additions unnecessary. So points for any reader who identifies redundant constraints in the list given above.)

[When I did check for minimality, it turned out that several of the constraints included in the list above are redundant. The fact that relation R is functional and injective, for example, follows from the others shown. Actually it follows from a subset of them. The deletions above show one way of reducing the number of a priori constraints: they all follow from the others and can be dropped. None of the remaining items follows from the others; if any of them are deleted, the constraints no longer suffice to ensure the properties required by XPath.]

How formal can you get?

Posted on by

[26 January 2010; updated a URI 28 Jan 2010]

In a recent comment on an earlier post here, David Carlisle wrote of proofs concerning properties of the XPath 1.0 data model

It’s not clear how formal any such proof could be, given that the XPath model and even more so, XML itself are defined so informally.

It’s true that the XPath spec defines the data model in prose and not in formulas. But on the whole it’s relatively formal and explicit prose, and I would expect it to be relatively easy to translate the prose into a formal notation.

As a test of that proposition, I recently improved a shining hour or four by translating section 5 of the XPath 1.0 spec into Alloy, the modeling tool developed by Daniel Jackson and others in the MIT Software Design Group. (I would describe Alloy briefly here, but I’ve written about Alloy often enough in this blog that I won’t describe it again now; regular readers of this blog will already know about it, and those who don’t can search the Web for information, or search this blog for what I’ve said about it before.)

The full Alloy model of XPath 1.0 is available from the Black Mesa Technologies web site. It will be of most interest, of course, for those familiar with Alloy, or wanting to learn more about it. But Alloy’s formalism is simple enough that anyone with a taste for formal methods will find it easy going, and the document paraphrases all the important things in English prose.

The net result, I think, is that there are (unsurprisingly) some places where the definition of the XPath 1.0 data model could or should be more explicit, and a few places where it seems a rule or two given explicitly is strictly speaking redundant, but by and large the definition is pretty clean and seems to mean what its creators meant it to mean. By and large, the definition of the data model is formulated without reliance on the XML spec (there are a few places where this separation could be cleaner), so that the informality of the XML spec (or what I prefer to think of as its programmatic promiscuity regarding models) does not in fact make it hard to formalize the XPath 1.0 data model.

In the current version, there are a couple of rough bits that I hope to sand down before I use this model in any other contexts. The ones I’m currently aware of are these:

  • The definition of the parent relation does not require that whenever parent(c,p) is true, either child(p,c) or attribute(p,c) is true. The XPath 1.0 spec doesn’t say this explicitly, but I think its authors probably felt that it would be pedantic to say something like that for a relation with a name like parent.
  • Similarly, the relations parent and ch are not guaranteed acyclic, though I think the original spec assumes that the names parent and child make clear that the relations should be acyclic. (But see the song “I’m my own Grandpa” and the Alloy models illustrating it, developed in Daniel Jackson’s Software Abstractions and shipped with Alloy in the samples directory.)
  • The predicate precedes intended to model document order is defined recursively; this is not legal in Alloy. So a conventional relation on nodes will need to be defined instead, with appropriate constraints. It is still not clear whether the rules given in the spec suffice to make the order total (at least in the absence of multiply occurring children); if they don’t, I’d like to propose an additional predicate which has that effect.

Two, four, three, who’s counting?

Posted on by

[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:

  1. a sequence of character types (i.e. a string-type)
  2. a sequence of character tokens (i.e. a string-token)
  3. 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.]