RELAX NG and xml:id

One part of the vision underlying RELAX NG is that validation should not be monolithic: it is not necessary or desirable to have one schema language that can handle every possible kind of validation you might want to do; it is better instead to have multiple specialized languages, each of which does one kind validation, really well. Consistent with this vision, RELAX NG provides only grammar-based validation. There's no implicit claim that other kinds of validation aren't useful and important.

One kind of validation that is clearly useful and important and that can't be done by grammars is checking of cross-references. One possibility is to use Schematron for this. The designers of RELAX NG anticipated that there would be a little schema language specialized to this, which would be created as part of the ISO DSDL effort (as part 6); this wouldn't be a million miles from the kind of thing that XSD provides with xs:key/xs:unique/xs:keyref. Unfortunately this hasn't happened yet.

Since DTDs provide ID/IDREF checking and we wanted people to be able to move easily from DTDs to RELAX NG, we felt we had to provide some transitional support for ID/IDREF checking while awaiting the ultimate "right" solution. We therefore provided a separate, optional spec called RELAX NG DTD Compatibility. Amongst other things, this defines a way in which RELAX NG processors can optionally provide DTD-compatible ID/IDREF checking based on the datatypes of attributes declared in the schema. Note that this can't handled by the XSD datatypes library for RELAX NG, because assignment of types in the schema to values in the instance is not part of the RELAX NG model of validation.

When defining RELAX NG DTD compatibility, we took a fairly hard line about being DTD-compatible. In particular, we made it a requirement that you should be able to generate a DTD subset from the RELAX NG schema that would perform the same type assignment that the process defined by the spec would perform. This creates some problems when you use DTD Compatibility in conjunction with wildcards (which of course aren't a DTD feature). For example:

start = element doc { p* }
p = element p { id?, any* }
id = attribute id { xsd:ID }
any = element * { attribute * { text }*, (any|text)* }

will get a error about conflicting ID-types for p/@id.  This is because the schema allows <p> to contain a <p> element with an id attribute that doesn't have type ID. Instead you would have to write:

start = element doc { p* }
p = element p { id?, any* }
id = attribute id { xsd:ID }
any = element * - p { attribute * { text }*, (any|text)* }

Several years after the DTD compatibility spec was finished, the W3C came out with the xml:id Recommendation. The spec mentions RELAX NG in a non-normative appendix and encourages authors "to declare attributes named xml:id with the type xs:ID". Now on the face of it, this seems pretty reasonable advice.  Unfortunately, from the point of the RELAX NG DTD Compatibility spec it's precisely the wrong thing to do.  For example, this

start = element doc { p* }
p = element p { id?, any* }
id = attribute xml:id { xsd:NCName }
any = element * { attribute * { text}*, (any|text)* }

will work perfectly with RELAX NG with or without DTD compatibility. The XML processor does the xml:id checking, and RELAX NG can ignore ID/IDREFs. But if instead you follow the xml:id Recommendation's suggestion and do:

start = element doc { p* }
p = element p { id?, any* }
id = attribute xml:id { xsd:ID }
any = element * { attribute * { text}*, (any|text)* }

a RELAX NG validator that implements RELAX NG DTD compatibility will give you an error about conflicting ID-types p/@xml:id. You might think you could do

start = element doc { p* }
p = element p { id?, any* }
id = attribute xml:id { xsd:ID }
any = element * { attribute * - xml:id { text}*, id?, (any|text)* }

but that won't work either, because although you can now write a DTD subset that does equivalent type assignment for p, you can't do it for the other elements.

(The xml:id Recommendation also says in the RELAX NG section that "A document that uses xml:id attributes that have a declared type other than xs:ID will always generate xml:id errors.". I don't see why: the xml:id processor is quite likely to be part of the XML parser, which doesn't know anything about RELAX NG, nor does RELAX NG know anything about xml:id.)

Back when RELAX NG DTD compatibility spec came out, I implemented support for the ID/IDREF checking part of DTD Compatibility in Jing.  I also decided to make Jing enforce this by default. There's a -i switch to turn it off. Before xml:id came along, this seemed to work OK: if a schema author specifies ID/IDREF in a RELAX NG schema then they usually want ID/IDREFs to be checked and RELAX NG DTD Compatibility was the only thing that could do this checking. With xml:id this no longer works well: if you

• use xml:id
• declare xml:id attributes as type xsd:ID in the RELAX NG schema
• use wildcards in your RELAX NG schema
• don't use any special options to Jing

you are very likely to get an error from Jing.

At first, my plan was simply to change Jing not to enforce DTD Compatibility by default. However, Alex Brown pointed out that this isn't completely satisfactory: people who are coming from DTDs and aren't using xml:id lose the sensible ID/IDREF checking that they might reasonably expect to happen by default. So now I'm thinking that a better solution might be to add two boolean options to Jing, both of which would be enabled by default.

The first option would be to make it a warning rather than an error if the schema does not use ID/IDREF in a DTD-compatible way. (If the schema is DTD-compatible, then duplicate IDs or IDREFs to non-existent IDs would still be errors.)

The second option would tell Jing to be "xml:id aware". This would have several effects.

• It would require attributes named xml:id to be declared with type xsd:ID (or with the ID type from the datatype library defined by the DTD compatibility spec). This isn't strictly necessarily, but it would seem to minimize confusion and be in keeping with the spirit of the xml:id Recommendation. It's slightly tricky to decide what this means with various unusual RELAX NG wildcards. It is obvious that attribute xml:id { text} is an error.  But the following are not all obvious to me:
  • attribute xml:id|id { text }
  • attribute * { text }
  • attribute xml:* { text }
  • attribute *|xml:id { text }
• When checking whether you can generate an equivalent DTD subset, xml:id attributes would be ignored. In the terms defined by the RELAX NG DTD Compatibility spec, you would ignore xml:id attributes when determining whether the schema is compatible with the ID/IDREF feature.
• When checking uniquess of IDs, and when checking IDREFs, an attribute named xml:id would always be treated as an ID attribute.

It might also be a good idea to revise the RELAX NG DTD compatibility spec to be xml:id aware in this way.

My new laptop

I just bought a new laptop. Previously I was using a Sony VAIO TZ, specifically a TZ38GN:

• 1.15kg
• 11.1" screen, 1366x768 resolution, LED backlit
• U7700 (1.33GHz) CPU
• 2Gb RAM
• 48Gb solid state disk
• DVD writer

I bought this during a period where I was doing mostly email and web browsing and no coding, and it worked beautifully for that.  The screen was fantastic, and it was the perfect size.

However, when I started doing some coding, I began to find it a little bit wimpy: CPU a bit slow, not quite enough RAM, disk too small. Also when I'm at home, I like to use my laptop with an external keyboard and a large 24" (1920x1200) display, and the TZ would only go up to 1680x1050.

I also have an old Dell Precision M65, which I bought nearly two years ago:

• about 3kg
• 15.4" screen, 1920x1200 screen, not LED backlit
• T7600 (2.33GHz) CPU
• 4Gb RAM (but the chipset only allowed 3.25Gb to be used)
• 160Gb 7200rpm disk
• DVD writer

This has enough horsepower for coding, but after getting used to the TZ, I found lugging the Dell around to be a real pain, and the screen is much less nice than the VAIO's.

I ended up using the Dell at my desk, and the TZ elsewhere.  But having things divided between two machines started to be a real pain, so I wanted to find something with the power of the Dell (at least when connected to a monitor) but the size and weight of the TZ.

I ended up choosing a Sony VAIO Z, specifically a VGN-Z26SN:

• 1.46kg
• 13.1" screen, 1600x900 resolution, LED backlit
• P8600 (2.4GHz) CPU
• 3Gb RAM
• 320Gb 7200rpm disk
• DVD writer

They had another model (the Z27), which was 25% more expensive, and offered a 2.53Ghz CPU, 4Gb RAM and a Blu-ray drive. I suspected I wouldn't be able to use much of the extra 1Gb RAM, and I didn't have much use for the Blu-ray drive, but the deciding factor was that, bizarrely, the Z27 didn't come with a proper Thai keyboard.

The VAIO  Z cost me about 80,000 baht (about US$2250 at today's exchange rate), which is not as unreasonable as VAIOs usually are.  By comparison, I think the TZ cost me about 100,000 baht (mainly because of the SSD), and the Dell was about 180,000 baht (it was a very high-end machine at the time).

Overall I'm reasonably happy with it.  The screen is great and the battery life is OK, although not as good as the TZ's. The keyboard is OK, but I wish it was backlit. Also it doesn't have separate Home/End/PgUp/PgDn keys: you have to press the Fn key in conjunction with the arrow keys. It only has two USB ports, which means you will probably need a USB hub. I discovered one incredibly annoying feature: although the CPU has virtualization support, the BIOS prevents you from enabling it.  I can understand Sony's not supporting virtualization in the sense of not providing support if you have problems when you use it, but it's hard to accept a policy that actively prevents a customer making use of an important feature of the hardware they have bought.

I am afraid I don't have any useful information about how well Linux runs on it, because I have been using Vista.  This might seem like a strange thing for me to do.  I'll explain in a separate post.

Saxon performance

Michael Kay has posted  a link to a new paper  of his on Saxon performance. Interesting not just for XQuery/XSLT performance but also for XML performance in general.

MGrammar

MGrammar (Mg) is another key part of Oslo.  My first reaction to Mg was: Yet another lex/yacc clone. Yawn. But now that I've looked at it a bit more closely, there are some features I find quite interesting.

I have always found parser generators to be a bit of a pain. I think one of the reasons is that the input to the parser generator typically mixes together a declarative specification of the grammar with procedural code that does something with the parse.  There's not a clean separation between my code and the generated code.

Mg works in a rather different way.  The specification in Mg is purely declarative.  So how does it actually do anything useful?  It constructs a labeled tree (actually a DAG) that represents the result of the parse.  Mg has language constructs that allow you to control what tree gets constructed, but there's a reasonable default.

Another big difference is that it works much more dynamically than a typical parser generator.  The generated parse tree is not strongly typed: it's just nodes with textual labels.  You don't have to compile that parser ahead of time (although you can if you want).  You can just give the library your grammar and it will compile it into an efficient form; you can them apply that compiled form to an input stream and get a parse tree.

The overall programming experience seems to be much more like using a regex library: at runtime, the regex gets compiled into an executable form; executing the regex tests whether the input matches the regex; and if it does match, you get structured data out (typically an array of strings, one for each captured group).  I think this sort of programming model is much more convenient; it's particularly nice for a dynamic language which can potentially deal very conveniently with the untyped parse tree that you get from Mg.

Another interesting feature of Mg is that it has modules.  The module system together with the fact that the grammar doesn't include any procedural code opens up the possibility of reusing grammars for languages and fragments of languages. It's hard to say how useful this will actually be in practice.

There's one more feature that's worth mentioning.  You can attach annotations (called attributes) to production rules.  These annotations can have structure (the same kind of structure as the parse tree).  For example, the annotations might tell a text editor how to provide syntax aware editing features: in the Microsoft implementation, there's an annotation that the editor uses to highlight keywords.

The obvious missing feature is that there's no way to automatically go from the parse tree back into the textual form.  I assume Microsoft will fix that.

I noticed only one thing that was really broken: Mg supports Unicode, but in cases where you need to specify a single character, it requires a 16-bit code unit representing part of the UTF-16 encoding of a character, rather than a code point (in the range 0 to 0x10FFFF).  This is just wrong.  It's slightly more work to do it properly, but you really can't avoid it.  For example, you need it to properly support Unicode blocks/categories, since these blocks/categories are blocks/categories of code points not code units.

I hope we'll see some open source implementations of Mg: perhaps one in C/C++ hooked up to SpiderMonkey/V8/Python/Ruby/GNU Emacs and one in Java hooked up to Rhino/JRuby/Groovy/NetBeans/Eclipse.

There's a bigger issue lurking here.  I think Microsoft see Mg as more than just a nifty library.  It's part of their vision for a next generation application development platform, where developers become more productive by using custom DSLs rather than XML. I have mixed feelings about this. The syntax for M itself is defined using Mg, and Microsoft seems to be designing things so that much of the tooling that they build for M can easily be applied to anything with a Mg-defined grammar. The tooling seems to have quite an introspective feel to it, like a sophisticated Lisp or Smalltalk environment.  The hacker side of me finds this quite cool.

On the other hand, gratuitous syntactic diversity is not a feature.  I remember in the early days of XML, Tim Bray used to start his pitch for XML by showing a whole bunch of widely different Linux config file formats.  It was quite compelling: the lack of consistency was obviously confusing and pointless. Now I don't think anybody would suggest that XML is the right format for everything.  I wouldn't want to write programs in XML (except sometimes for XSLT :-), and after writing schemas in RELAX NG compact syntax for a while, I wouldn't want to have to go back to writing them in XML.  How do you make your platform encourage developers to use a DSL where it makes sense, and discourage them when it doesn't? Up to now, part of the answer was that libraries made it a bit easier to use XML (or some other standard format) rather than some completely custom syntax; so unless there was a substantial benefit from a custom syntax, developers wouldn't bother.  But if your platform provides tools that make it really easy to design new syntaxes, how do you avoid ending up in situation where every application has it's own private DSL?  It doesn't help users if they have to learn a new syntax for every application. Certainly when I think about interchanging data on the Web, the fewer formats the better; I definitely don't want every application to be using its own completely custom syntax.

Some thoughts on the Oslo Modeling Language

Microsoft recently introduced Oslo.  Microsoft seems to have designed Oslo to replace some of things it now uses XML for.  Since Microsoft have been one of the biggest supporters of XML, I think it's worth looking at what they've come up with.

Overview of M

The key part of Oslo is the "M" language, which Microsoft calls a "modeling language".  This integrates quite a broad range of functionality:

• an abstract data model (analogous to the XML Infoset); M uses the term "value" to describe an instance of this abstract data model
• a syntax for writing values (analogous to XML 1.0)
• a type system which provides language constructs for describing constraints on values (analogous to XML Schema)
• language constructs for querying values (analogous to XQuery)

I guess this is a similar range of functionality to SQL (although there are no constructs for doing updates yet).

I'm going to give a brief overview of M as I understand it.  This is based purely on the spec. Please comment if I've misunderstood anything.

Let's start with the abstract data model. There are three kinds of value

• simple values
• collections
• entities

Simple values are what you would expect (Unicode strings, numbers, booleans, dates etc). An important simple value is null, which is distinct from any other simple value.

A collection is a bag of values: it is unordered, it can have duplicates and it can contain arbitrary values.

An entity is a map from Unicode strings to values; each string/value pair is called a field.

A key feature of the abstract data model is that it's a graph rather than a tree.  When the value of a field is an entity, the field conceptually holds a reference to that entity.  I believe the same goes for collections, but I haven't completely grokked how identity works in M.

Simple values have the sort of syntax you would expect:

• "foo" is a Unicode string (M calls string values Text)
• 123 is an integer
• true is the boolean true value
• 2008-11-22 is a date
• null is the null value

A collection is written in curly brackets with items separated by commas: { 1, 2, 3 } is a collection of three integers.

An entity uses a {field-name = field-value} syntax: { x = 2, y = 3 } is an entity with two fields. If the field name isn't an identifier, you have to surround it in square brackets: { [x coordinate] = 2, [y coordinate] = 3}.

You can label an entity or a collection and then use that label to specify a reference to that entity or collection. You label a collection just by putting an identifier before the opening curly brace.  So

  { jack { name = "Jack", spouse = jill }, jill { name = "Jill", spouse = jack } }

would be a collection of two entities, where the spouse field of each entity is a reference to the other entity, and

   loop { loop }

would denote a collection with a single member, which is a reference to itself.

A type in M can be thought of as being the collection of the values that conform to the type, so one way to specify a type is just to explicitly specify that collection. So, we could define a Boolean type like this:

  type Logical { true, false }

In fact, M has predefined types corresponding to each kind of simple value.  For entities, you specify a type by specifying the fields. So if we define Point like this:

  type Point { x; y; }

then any entity that has both an x field and a y field is a Point.  Note that entity types are open: an entity that has a z field as well as an x and a y field would conform to the Point type. You can also specify types for the fields:

type Point {
    x : Number;
    y : Number;
}

Types can be recursive:

type Node {
  left : Node;
  right : Node;
}

Collections can be specified using the * and + operators: Integer* is a collection of zero or more integers. There's also a ? operator, but it doesn't have anything to do with collections: T? is equivalent to the union of T and { null }.

So far, nothing very exciting. What makes M interesting is that it has a rich functional expression language that can be used for describing instances, types and queries. The analogy in the XML world would be the way XPath is used in instances via XPointer, in schema languages like Schematron and XSD 1.1 and in XQuery.

As well as the obvious kinds of expressions on simple values, you can have expressions on collections:

• C | D is the union of C and D
• C & D is the intersection of C and D
• v in C tests whether v is a member of C
• C <= D tests where C is a subset of D

Most importantly,

  C where E

returns a collection containing those members of C for which E evaluates to true; the keyword value is bound to the member of C for which E is being evaluated.  So

{ 1, 2, 3, 4 } where value % 2 == 0

returns { 2, 4 }.

What's really powerful is that expressions can be used on types in a similar way to how they are used on collections.  If we want a type corresponding to even numbers, we can just do:

  type Even : Integer where value % 2 == 0;

You can apply a where expression to an entity type definition to constrain the fields:

type ZeroSum {
   x: Number;
   y: Number;
} where x + y == 0;

You can also do something like:

type Name {
  firstName: Text;
  lastName: Text;
}
type Person {
  dateOfBirth: Date;
} where value in Name;

Fields can have default values, for example:

type Person {
  dateOrBirth : Date? = null;
}

In fact, when the type of a field is nullable (has null as one of its possible values), it automatically gets a default value of null. Similarly, when the type of a field is a collection that may be empty, it automatically gets a default value of an empty collection. This is quite clever: it makes fields declared as ? or * work nicely for both the provider and the consumer; the provider can leave the fields out, as would be natural for the provider, but the consumer always gets a sensible value for the field.

So we've seen how entity types can specify a default value.  But how does an entity get connected with an entity type so that the default value can be created?   Typing in M is structural.  An entity in M doesn't inherently belong to any type other than Entity.  Like a pattern in RELAX NG, a type in M describes a possible shape for a value, which any given value may or may not have, but a value isn't created with any particular type (other than one of the fundamental built in types).

M solves this by having a notion of type "ascription".  An expression "v : T" ascribes the type T to the value v. M is functional so this doesn't mutate v, rather it returns a new value that has an augmented view of v as specified by T.  So whereas

  { firstName: "James", lastName: "Clark" }.dateOfBirth

will throw an error,

  ({ firstName: "James", lastName: "Clark" } : Person).dateOfBirth

will return null (assuming Person declares dateOfBirth as nullable). (I would guess type ascription also does coercions on simple values.) Note that this implies that types in M aren't simply collections of values. M also allows entity types to have computed fields, which are virtual fields whose values are computed from the value of other fields.

The last area of M I want to look at is identity.  You can specify what determines the identity for a entity:

type Person {
  firstName: Text;
  lastName: Text;
  dateOfBirth: Date? 
} where identity(firstName, lastName);

This means you can't have two Persons with the same firstName and lastName.  The obvious question is: within what scope?

To answer, we have to look at the top-level layer that M provides.  Values don't exist in isolation.  Everything in M has to exist within a module.  A module is a sort of top-level static entity.  The fields of a module are called "extents".  The scope of an identity constraint is an extent.  So, if you do:

module Employee {
  type Person {
    firstName: Text;
    lastName: Text;
    dateOfBirth: Date? 
  } where identity(firstName, lastName);
  Persons: Person+
}

then it would be an error if within the Persons extent, there were two Person entities with the same firstName and lastName. There's also a way to automatically give a field a unique id:

type Name {
  id : Integer32 = AutoNumber(); 
  firstName: Text;
  lastName: Text;
} where identity id;

I don't really have anything to say about the query part: it's quite close to LINQ.

My thoughts about M

There's quite a lot about M that I like.  Mostly it seems pretty clean.  The type system is powerful. Structural typing is clearly the right approach for something like M.  I like the way that constraints that can be checked statically are seamlessly blended with constraints that will need to be checked dynamically.  Static type checking is good, but there's no need to rub your users faces in the limitations of your static type checker. (It's interesting to see C# 4.0 moving in a similar direction.)

It's obviously very early days for M, and there's still lots of scope for improvement.  Microsoft's initial implementation of M targets SQL and works a bit like a database.  But clearly there's potential for using something like M in quite different contexts, e.g. for exchanging data on the Web (like what I talked about some time ago with TEDI).  But several aspects of the current design seem to reflect the initial database focus. For example, the current top level wrapper of modules/entities makes sense for a database application of M, but wouldn't work so well if you were using M for exchanging data on the Web.

The spec needs some fleshing out.  Microsoft's current implementation is a long way from implementing the full language.  I am skeptical whether the language as currently specified can be fully implemented.  For example, can you implement the test for whether one type is a subtype of another type so that it works in non-exponential time for two arbitrary types?

I see several major things missing in M, whose absence might be acceptable for a database application of M, but which would be a significant barrier for other applications of M.  Most fundamental is order. M has two types of compound value, collections and entities, and they are both unordered.  In XML, unordered is the poor relation of ordered.  Attributes are unordered, but attributes cannot have structured values. Elements have structure but there's no way in the instance to say that the order of child elements is not significant.  The lack of support for unordered data is clearly a weakness of XML for many applications.  On the other hand, order is equally crucial for other applications.  Obviously, you can fake order in M by having index fields in entities and such like.  But it's still faking it.  A good modeling language needs to support both ordered and unordered data in a first class way.  This issue is perhaps the most fundamental because it affects the data model.

Another area where M seems weak is identity. In the abstract data model, entities have identity independently of the values of their fields.  But the type system forces me to talk about identity in an SQL-like way by creating artificial fields that duplicate the inherent identity of the entity. Worse, scopes for identity are extents, which are flat tables.  Related to this is support for hierarchy. A graph is a more general data model than a tree, so I am happy to have graphs rather than trees. But when I am dealing with trees, I want to be able to say that the graph is a tree (which amounts to specifying constraints on the identity of nodes in the graph), and I want to be able to operate on it as a tree, in particular I want hierarchical paths.

One of the strengths of XML is that it handles both documents and data. This is important because the world doesn't neatly divide into documents and data.  You have data that contains documents and document that contain data.  The key thing you need to model documents cleanly is mixed text. How are you going to support documents in M?  The lack of support for order is a major problem here, because ordered is the norm for documents.

A related issue is how M and XML fit together. I believe there's a canonical way to represent an M value as an XML document. But if you have data that's in XML how do you express it in M? In many cases, you will want to translate your XML structure into an M structure that cleanly models your data.  But you might not always want to take the time to do that, and if your XML has document-like content, it is going to get ugly.  You might be better off representing chunks of XML as simple values in M (just as in the JSON world, you often get strings containing chunks of HTML).  M should make this easy.  You could solve this elegantly with RELAX NG (I know this isn't going to happen given Microsoft's commitment to XSD, but it's an interesting thought experiment): provide a function that allows you to constrain a simple value to match a RELAX NG pattern expressed in the compact syntax (with the compact syntax perhaps tweaked to harmonize with the rest of M's syntax) and use M's repertoire of simple types as a RELAX NG datatype library.

Finally, there's the issue of standardization.  The achievement of XML in my mind isn't primarily a technical one.  It's a social one: getting a huge range of communities to agree to use a common format.  Standardization was the critical factor in getting that agreement.  XML would not have gone anywhere as a single vendor format. It was striking that the talks about Oslo at the PDC made several mentions of open source, and how Microsoft was putting the spec under its Open Specification Promise so as to enable open source implementations, but no mentions of standardization.  I can understand this: if I was Microsoft, I certainly wouldn't be keen to repeat the XSD or OOXML experience. But open source is not a substitute for standardization.