Oliver Steele

The Model-View-Controller (MVC) architecture is a standard architecture for interactive applications. In client-server programming, the MVC components are distributed across at least two nodes of a network. This leads to a set of choices about where to deploy each component of the architecture. One solution is the traditional server-based MVC model. Another is the Rich Internet Application (RIA) model. In a real-world application with client-side validation, these are more similar than they might seem.

Desktop MVC

In an interactive application, there is typically a domain model, code to present the model to the user, and code to act upon the model in response to the user manipulation of input devices such as the keyboard and mouse. For example, in a word processor the domain model is the document, which contains entities such as paragraphs, spans, and styles. The system presents the document to the user as (for a sighted user) glyphs rendered as pixel patterns, and interprets keystrokes and mouse actions as edit, formatting, and control commands.

Smalltalk-80 introduced the Model-View-Controller (MVC) architecture for structuring this type of application. MVC separates the maintainance of the domain model (the Model), the presentation of the model (the View), and the interpretation of user input (the Controller).

Model-View-Controller Control Flow²

Together with the User, the components of an MVC architecture form two cycles of data and control flow:

1. The View Cycle: User -> Controller -> View -> User. The user manipulates an input device — for example, by clicking the mouse button, while the mouse cursor is positioned in the down region of a scroll bar. The Controller responds by sending a message to the View (e.g., by invoking view1.scrollDown()). The View updates its state (it adjusts the value of view1.xoffset), and updates the information that it presents to the user (calls bitblt on view1’s screen area, and invokes the draw() methods of views that intersect the accumulated damage region).
2. The Model Cycle: User -> Controller -> Model -> View -> User. The user manipulates an input device in a different way or in a different context — for example, by pressing control-D while an entry from a list of contacts is selected. The Controller updates the state of the Model, the view updates to match the model, and the user is presented with the updated view. For example, when the user selects the Delete item from a menu, code in the Controller might invoke view.deleteRow(), which invokes view.currentSelection.delete(), where view.currentSelection is a Model object and view.currentSelection.delete() is a Model method. The delete() method changes the Model data, which notifies these objects’ Listeners, say by invoking their registerChange() methods. The set of Listeners includes View objects, which respond to the invocation by updating the display.

In a desktop application, the Model, View, and Controller run on the machine that the user interacts with. This kind of application is easy to write (or, as easy as the domain model allows); it easily takes advantage of client platform features such as dialog boxes, offline storage, and drag and drop; and it’s responsive. The disadvantages of desktop MVC architecture are the disadvantages of desktop applications in general: they are difficult to deploy, they tend to be platform-dependent, and they are generally limited to manipulating data on the local file system³.

Web Application Programming

In a web application, the server software runs on a server, and the user interacts with browser software running on a client. The Model’s data is stored on the server. The user interacts with software running on the client.

Client-server programming is difficult because the program is distributed across more than one network node. Some code has to run on the client to interact with the user. Other code has to run on the server to interact with the data store.

In the case of a web application, the code that runs on the client includes the user agent, or browser. The distributed nature of a web application creates two challenges. One is that the application has to render data from the server into a context where it can be displayed on the client. The other is that information about user events has to get back from the client to the server.

The architectural decision about client-server MVC is which components to deploy to which nodes, and how to manage the communication between them. Should the View and the Controller run on the server, or the client? What about the Model?

There’s a variety of ways to make these decisions. One solution is Server-Side MVC (below). Another is the Rich Internet Application architecture (also below). But all the solutions have some elements in comment, because of the following ground rules:
# At least part of the Model has to run on the server. This is because the Model is responsible for maintaining the integrity of the business objects, and has to be immune from client spoofing. It also sychronizes changes requested by simultaneously executing clients if the changes are bottlenecked through code that runs on the server, although in a clustered server environment this doesn’t come for free.
# The user has to be able to see the information presented by the View. This means the View, no matter where it runs, ultimately must control the display of this information on the client.
# The Controller must be able to receive events that represent user activity.

Server-Side MVC

In Server-Side MVC, the Model, View, and Controller run on the server. The View generates a representation of a presentation. This representation is downloaded to the client, which displays it. User interactions with the client are sent back to the server, where they generally result in the generation of a new presentation, which is downloaded in turn, and updates the previous presentation. This is the view update operation.

Server-Side MVC

In a Server-Side MVC web application, the View generates an HTML page, which is sent to the client as an HTTP response. The browser, on the client, encodes user events as the URL, query, and POST parameters in an HTTP request. The Controller, on the server, interprets this information as Model or View changes, and routes the request to the View, which responds with another HTML page. The view update operation in a web application is implemented as wholescale replacement of the previous view by the new view. In a browser, this is the page refresh.

In the Java community, “MVC” means “Server-Side MVC“. In this context, (Server-Side) MVC is also called Model 2. (Model 1 was a server-side application without the architecture.) JSP, Struts, and PHP are all specific technologies that can be used to implement Server-Side MVC.

The advantage of Server-Side MVC for the developer is that if the Model (aka business logic) is running on the server anyway, this architecture allows the developer to use the same language, libraries, and data structures to write the rest of the application, and local procedure calls to communicate between components.

The disadvantage is that the quality of the user experience is limited by three factors:
# View updates in Server-Side MVC are more coarse-grained than they are in a desktop application. A Server-Side MVC application can’t generally update just part of a view (or an interior node in a view hierarchy); it has to create an entirely new view and replace the old view by the new one, even when the new view is almost identical to the old one¹⁰. The user experience correlate of this limitation is the ubiquitous full-page refresh in Server-Side MVC applications.
# User events in Server-Side MVC are more coarse-grained than they are in a desktop application. Multiple client-side user events, such as a series of clicks and keystrokes, are aggregated into a single HTTP request that summarizes their effect. This has implications for the kind of feedback that the Controller is able to give; it’s why direct manipulation such as drag and drop is impossible in this architecture, and why client validation is difficult.
# The previous two problems are the special cases of the problem that the bandwidth of communication between the user and the application is low. The latency of communication is also high, compared to desktop interactivy — any Model cycle, or View cycle that involves a page refresh, is an expensive and offputting activity.

Server-Side MVC is the path of least resistance towards developing an application that provides access to an existing Model implementation. It allows the incremental expenditure of developer resources towards a limited degree of user interactivity. For many applications, only limited interactivity is required. This is especially true for non-consumer web applications: both the users and the organizaton would rather have developer resources go towards back-end improvements and new business features, if these resources are coming out of the same pool that improvements to the user experience would come from.

Server-Side MVC: Under the Hood

Let’s look again at how the user interacts with a Server-Side MVC application. The View in a Server-Side MVC application isn’t actually displaying information on the user’s screen or to the user’s screen reader; it’s creating data which will instruct the user’s browser to display this information. The Client isn’t reading the state of the input devices; the browser is reading this state and summarizing it into HTTP requests.

The diagram above hid this complexity by conflating the User and the User Agent, and placing them both inside the computer. (That’s why the User was inside the computer in the Server-Side MVC diagram.) But the human user doesn’t interact directly with the HTTP and HTML protocols. There’s actually an additional piece of software — the browser — mediating the interaction of the user with the server component of the application. The browser has its own Model, View, and Controller. The browser’s Model is the HTML page. The View renders the page to the screen or screen reader, and the Controller interprets the keyboard and mouse events against the input focus state and the position of rendered elements (such as links and form elements) within the browser window.

Server-Side MVC unpacked (slightly)

This is still (a variant of) an MVC architecture, it’s just that the View and Controller are each split between the client and the server. The high-overhead HTTP request/response transactions occur within components: the back-end View communicates via HTML to the front-end View, and the front-end Controller communicates via HTTP to the back-end Controller.

Cycle Time

There’s an additional complication, which is that now there are two View cycles. User actions that don’t involve a page refresh, such as scrolling the page or choosing a new form element, initiate a Client View Cycle. Actions that require a page refresh, such as paging to the next ten items in a list, or searching for products that contain the term “AAC”, initiate a Server View Cycle. Neither of these actions changes the Model — they’re both View cycles, not Model cycles — but they require different kinds of changes to the View.

Cycles that cross the client-server boundary — the Model Cycle, and the Server View Cycle — are more expensive than cycles that are encompassed within a single node.

The Client Thickens

The final step in fleshing out the diagram above is to account for input validation, such as checking that a credit card number has the right syntax or that input field co-occurrence restrictions hold (if menu item 1 is selected, then input field 2 must be non-empty). Given the expense of a View Cycle that involves the server, it’s desirable to do as much input validation on the client as possible, to avoid the page refresh. Since the input is validated against the model schema, this requires downloading a little bit of business logic to the client.

Server-Side MVC unpacked

We could draw this as a special case of single-Model MVC, just like we did when only the View and the Controller were split between the server and the client. The Model in this interpretation contains multiple components: a server-side component which runs on the server, and at least one client-side library which the View links into the HTML page that it downloads to the client.

This isn’t a thick client, or a Rich Internet Application. The only code running on the client is the browser, and whatever the current page includes. This is still the world of Server-Side MVC, as produced by JSP, Struts, CGI, or other server-side technologies that generate HTML+JavaScript. All that’s changed is that the architecture diagram now reflects (more of) the software’s full complexity.

That complexity includes the real world application of what are still research topics in academia: staged programming for multiple-target code generation (Mac IE, Windows IE, Netscape, Mozilla, Safari, Opera), process migration, and (usually manual) CPS conversion to maintain program state across pages. No wonder web programming is hard!

RIA Architecture

For comparison, here’s an RIA architecture. In this case, the RIA includes a domain model, in order to support client interaction.

Conclusion

When I started working on RIAs, I thought I’d find the comparison between RIAs and conventional server-side applications would look like this:
|Server-Side MVC|RIA|
|||

These diagrams makes RIA architecture look more complex than server-side applications. But it turns out that server-side programming is plenty complex, it’s just that the complexity isn’t represented in the left hand diagram. That diagram conflates the User and the User Agent. It doesn’t take into account interactions between the User and the User Agent, but takes them as a monolithic whole. This makes the surface architecture simpler, because the architecture isn’t at enough level of detail to represent the kinds of interactions that determine the user experience, which include the user’s interactions with the browser.

These diagrams also simplify the architecture of (many) RIAs, which need at least some of the model in order to support RIA functionality.

Once the architectures are fleshed out, the comparison looks more like this:

Server-Side MVC	RIA

This makes the RIA architecture look simpler than Server-Side MVC, because it’s only got one view.

Let’s return from architecture astronaut space to earth. The RIA architecture may look simpler on paper, but it can still be a more complicated deployment story. It’s only simpler overall if there’s a significant amount of client-side programming anyway.

Notes

¹ There’s a middle ground between changing the Model and changing the View, where the user previews a set of changes, in a dialog box or a multipage web form, before committing them with an Okay button or Order button. This is where Undo and the Back button break down. However, the distinction is generally clear enough to organize an architecture around.

² This may not be your father’s MVC. Sometimes the User is omitted from the diagram. (The user is integral to the control flow, but isn’t part of the software architecture, after all.) Sometimes the arrow from Controller to View is missing. (Presumably you can’t page or scroll in these applications, or else the state of the presentation is considered part of the Model.) Sometimes there are extra control flow or dependency arrows; and sometimes there are extra components, representing the Store that backs the Model, or who knows what else. But none of this variation makes a difference to what I want to talk about in this post, which is what happens when there’s at least a Model, and Controller, a View, and a client and a server.

Google for MVC

³ Just because the Model runs on the user’s desktop machine, doesn’t mean that the Model’s Store is the local file system. That’s just the path of least resistance, and the typical use case for a desktop application. Putting the store somewhere else is an uphill battle for a desktop application, but comes for free with a web application. Conversely, supporting interactivity (e.g. responsive feedback, direct manipulation) is an uphill battle for a server-application, and comes easily with a desktop application.

XML schemas change over time, for the same reasons that library APIs evolve in programming language. Over time, the schema designers introduce new content, and change or remove existing content, as they acquire greater familiarity with the domain model and the use cases, as they add additional functionality, and as they fix design bugs.

Often it is necessary to maintain instances of old versions alongside instances of new versions. (I’ll discuss why this is necessary.) An example is XSLT, where XSLT 1.0 and XSLT 2.0 documents may be present on the same file system. Other examples are XHTML, and SVG. The presence of instances of multiple schema versions frequently requires the presence of descriptions of multiple versions, and the problem of maintaining these multiple schema versions arises.

This posting is about the issues of maintaining and applying side-by-side versions of a schema. It describes a stylesheet that implements one solution, version annotation, where a single source schema is annotated with version information that is used to create version-specific output schemas.

I use RELAX NG Compact Syntax in the examples, but most of the techniques are applicable to other schema definition languages too.

Side-by-Side Versions

Once more than one version of a schema exists, the problem of defining multiple versions of a schema emerges. In the simple case, previous versions of the schema definition can be abandoned, if support for them no longer exists, or frozen, where the files remain unchanged.

Sometimes edit and processing tools must support the old and new schema versions at the same time. This is the case when the programs that process documents in the schema are distributed, so that a document author must author some documents for an older version, to take advantage of wider support, and others documents for a more recent version, to take advantage of additional features. It’s also the case for XML processors that have a compatibility code, where a single version of the processor supports more than one version of a schema. Both of these are cases of side-by-side versioning, where documents with different schema versions are present in the same computing environment. To the extent that the tools involved in the creation or processing of these documents use schema definitions, these scenarios require the presence of multiple schema definitions, as well.

When multiple versions of a schema definition are present in the same environment over an extensive length of time, it is useful to represent these versions in a single source file. It is useful to the schema designer, who can make changes within the context of their interactions with previous versions of the schema definition. It is useful to the human reader, who can see which features are available in which versions of a schema. It is useful for schema documentation tools, which can parse both constant and changed elements of the schema from a single definition.

Maintaining a single schema source is analogous to the maintenance, in a modern programming language such as C# or Java, of a single source file that incorporates information about how the API has changed. Java, for example, supports annotations such as @deprecated. In affect, these annotations allow multiple versions of an APIs to be maintained within a single source file. A Java source file that is annotated with @deprecated defines two versions of an API: one that includes the deprecated element, and another that doesn’t. These two versions can be selected for documentation generation and compilation, respectively, through the use of javadoc and compiler options which tell these tools how to process language elements marked with @deprecated.

Modular Schemas for Versioning

A RELAX NG schema definition can be implemented as a set of RELAX NG files. One file references the others through the use of include, import, and external keywords. These files act like classes in an OO language: extensions of the schema can incorporate these documents (akin to subclassing them), and supplement or override the definitions that they contain.

If a single schema definition is factored into multiple files, multiple schema definition can be implemented as a sets of files that overlap. This applied to multiple schema definitions that implement versions of a single definition. The include mechanisms allows the version-independent portions of a schema to be placed in documents that the version-specific schema definitions include.

In a world without tradeoffs, every schema would be modular. A modular schema definition provides the additional benefits that it can be more easily extended, and that portions of the schema can be reused in different document types.

The problem is that modularity comes with a cost in development time, and also in readability, with the accompanying increase in maintenance cost. Separating the version-independent portions of a schema from the version-specific portions can be expensive, and the result can be unreadable. There’s an example of this below.

Modularity is often the right choice for schema extensibility. However, it is an expensive price to pay for schema versioning — especially versioning of simple schemas. Below I will describe a middle ground, that is more expensive than the single-version schema but less expensive than the fully extensible schema, that can be used when versioning is required but the expense of extensibility is not.

Modularity is also unlikely to allow extensibility in areas which the designer didn’t have in mind. In On Versioning XML Vocabularies, Dare Obasanjo describes the difference between schema versioning, where the schema designer maintains a linear sequence of schemas, and schema extensibility, where multiple designers make independent, concurrent changes to a schema. Obasanjo recommends placing extensions in their own namespace. This recommendation doesn’t help with version changes, though.

Version Selection

The changes between schema versions and document versions must be coordinated. A document is only valid relative to a particular version of a schema that has multiple versions.

In On Versioning XML Vocabularies, Obasanjo analyzes some techniques for specifying schema versions . In brief, two of these techniques are to change the namespace of the XML tags, and to attach a version attribute to the XML document root. In RELAX NG, a third technique, implicit versioning, is equally easy to implement, but is generally inferior.

Namespace versioning

In namespace versioning, the namespace is changed with each new version. This has the disadvantage that it changes the name of every element in the namespace. It makes it difficult to share modular documents, modular schema definitions, and modular stylesheets between versions of a schema, and it complicates the implementation of editing tools and of namespace-aware processors such as XSLT stylesheets.

Attribute versioning

In attribute versioning, a version attribute on the document root specifies the schema version. The value of the version attribute matches the value of the version attribute that the schema definition defines. In effect, the pair of the document namespace and the version attribute value specifies a schema, just as the namespace alone does for an unversioned schema (or one that doesn’t use attribute versioning).

The version annotation technique below works with attribute versioning. It doesn’t work as it stands with namespace versioning.

Implicit Versioning

In implicit versioning, a document doesn’t include any schema version information at all. If the document is valid with respect to a schema version, then it belongs to that version.

The advantages of this solution are that the version doesn’t need to be declared (instance documents are therefore more concise), and that a document that is doesn’t depend on any properties of a particular schema version is valid with respect to any of those versions, and can be used in a variety of processing environments. This is similar to the way Java works. Many Java source files can be compiled against both JDK 1.3 and JDK 1.4, for instance. Dependencies on a particular version of the JDK are not explicitly marked in the source, but they are detected during compilation, by the fact that they generate compilation errors when compiled against other JDK versions.

A disadvantage of implicit versioning are that it requires a validation pass to determine the version of a document. This is a problem for editing tools and human readers. It also increasing the processing demands on document processors that process different versions differently or that only accept documents written against one version of a schema, by making the validation step mandatory.

A second disadvantage of implicit versioning is that it can be difficult to determine, for an invalid document, which version of the schema the document is an invalid instance of.

Nonetheless, the version annotation technique below works equally well for implicit versioning as it does for attribute versioning. In fact, it can be used with a combination of attribute versioning and implicit versioning, where an explicit version attribute is allowed, but not required — allowing documents that require a specific version to say so, but letting documents that are valid with respect to any version underspecify this.

An Example

We will define a simple schema that has two versions, “version 1″ and “version 2″. A version 1 document looks like this:

v1.xml

<root version="1.0" x="1">
  <a/>
</root>

A version 1 document has a mandatory x@ attribute, an optional @z attribute (not present in v1.xml), and an optional @a@ child. No other attributes or children are allowed.

In a version 2 document, the x@ attribute has been removed, and there is a new mandatory @y attribute. A root may have more than one a@ element (as opposed to a version 1 document, which may have just one), and a @b element as well (as opposed to a version 1 document, which does not allow this element). The @z@ attribute is still optional.

v2.xml

<root version="2.0" y="1">
  <a/>
  <a/>
  <b/>
</root>

A version 2 document is distinguished from a version 1 document by the value of its version attribute. A version 1 document has a version of “1.0″. A version 2 document has a version of “2.0″.

The RELAX NG Compact Syntax schemas for version 1 and version 2 documents, respectively, look like this:

v1.rnc

start = root
root = element root {
  attribute version {"1.0"} &
  attribute x {string} &
  attribute z {string}? &
  element a {empty}?
}

v2.rnc

start = root
root = element root {
  attribute version {"2.0"} &
  attribute y {string} &
  attribute z {string}? &
  element a {empty}* &
  element b {empty}?
}

Schema Definition Alternatives

The annotated schema definition defines both the version 1 and version 2 schemas. Before introducing the annotated schema, it will be useful to investigate some alternatives. These will help to illustrate how the annotated schema works, and how it can be used to produce version-specific schemas.

Alternative 1: Pointwise Union

The following schema accepts the union of the version 1 and version 2 schemas. Where a version 1 document requires a version of “1.0″, and a version 2 document requires a version of “2.0″, this schema requires a version of either “1.0″ or “2.0″. Where a version 1 document requires an x@ attribute, and a version 2 document requires a @y attribute, the schema allows both attributes and makes them both optional.

start = root
root = element root {
  attribute version {"1.0" | "2.0"} &
  attribute x {string}? &
  attribute y {string}? &
  element a {empty}* &
  element b {empty}
}

The problem with this solution is that, although it accepts any version 1 or version 2 document, it also accepts a number of documents that are neither version 1 nor version 2. It does this because each portion of the schema accepts the content model of either version or version 2, regardless of whether the same or a different content model version was used in a different portion of the schema. For example, the schema accepts the following hybrid document, which declares itself to be version 1 but includes some content version 1-specific content (the x@ attribute) and some version 2-specific content (the @y attribute and the @b@ element):

<root version="1.0" x="1" y="2">
  <b/>
</root>

Alternative 2: Local Disjunction

What is needed is to coordinate the different version-dependent portions of the schema file, so that, for example, the x@ attribute is only present when the @version attribute has the value “1.0″.

This can be done with a disjunction:

root = element root {
  ((attribute version {"1.0"} & attribute x {string}) |
   (attribute version ("2.0") & attribute y (string)))
  ...
}

This solution doesn’t have any of the problems of the pointwise union. It accepts all version 1 and all version 2 documents, and nothing else.

The problem with this solution is that it is unmaintainable as the grammar increases in complexity. Consider a schema such as the following:

start = element root {
  attribute version {"1.0"} &
  a*
}
a = element a {a* & b* & c*}
b = element b {b* & c*}
c = element c {a*}

Imagine that the only change, aside from the value of the version attribute, is the addition of an x@ attribute to @c:

c = element c {
  attribute x {string}? &
  a*
}

If the document root has a version of “1.0″, the x@ attribute is not permitted anywhere in the document. If it has a @version of “2.0″, the x@ attribute is allowed on every @c element, but nowhere else.

This is a very simple change, yet to implement it, an additional copy of each definition is required, in order to pass the information about which version of the schema is being used to the one definition (for @c@) that uses it:

start = element root {
  (attribute version {"1.0"} & a1*) |
  (attribute version {"2.0"} & a2*)
}
a1 = element a {a1* & b1* & c1*}
a2 = element a {a2* & b2* & c2*)
b1 = element b {b1* & c1*}
b2 = element b {b2* & c2*}
c1 = element c {a1*}
c2 = element c {a2* & attribute x {string}?}

The complexity is linear in the number of definitions. It is also linear in the number of versions, so that a document that defines three versions of a schema whose version-specific definition defines 100 entities, will require up to 300 definitions.

Alternative 3: Global Disjunction

RELAX NG also allows the two sets of definitions to be placed in separate files and incorporated into a single file by means of the external keyword. For example, if v1.rnc and v2.rnc are the file names of the version 1 and version 2 schema definitions above, a schema that accepts either a version 1 or a version 2 file, but not both, is:

start = external "v1.rnc" | external "v2.rnc"

(This solution is due to Norm Walsh. I’ll refer to it as the “Walsh disjunction”.)

Maintaining both the v1.rnc and v2.rnc files has the same maintenance problems as the “local disjunction” solution above. Two similar sets of sources must be maintained. However, although it is cumbersome as a source-level solution for writing the multi-version schema, we will use it as an output format, and compile the multi-version schema to it.

The Modular Solution

The problem with the “global disjunction” is the maintenance of two sets of sources, one for each version. How about factoring out the common portions of each version-specific specific schema into a set of files that each includes? A modular version of the problem schema in the previous example is:

start = element root {
  root.version &
  a*
}
root.version = attribute version {"1.0"}
a = element a {a* & b* & c*}
b = element b {b* & c*}
c = element c {c.content}
c.content = a*

(This schema has been modularized just to the extent necessary to support the version change. That’s why the definition of c@ uses @c.content, but the definitions of a@ and @b haven’t been similarly updated.)

The updated schema, that accepts an x@ attribute within the @c element when version is “2.0″, can be written:

include "base.rnc" {
  root.version = attribute version {"2.0"}
  c.content &= attribute x {string}?
}

However, this modularization comes with a price. Attempting to factor the v1 and v2 schemas yields something like this:

common.rnc

root = element root {
  root.version &
  root.content
}
root.content = a?
a = element a {empty}

modularized-v1.rnc

include "common.rnc"
root.version = attribute version {"1.0"}
root.content &= attribute x {string}?

modularized-v2.rnc

include "common.rnc"
root.version = attribute version {"2.0"}
root.content &= a*
root.content &= element b {string}?

The content of the root element has been distributed to the point where it’s difficult to read the content of either a version 1 or a version 2 document. The greater abstraction and extensibility comes at the price of readability.

Version-Annotated Schema

The solution we will use is to write a single file that defines both versions of the schema, but uses annotations to mark the content that is specific to only one version. We will use attributes from the http://osteele.edu/namespace/versioning/1.0 namespace to annotate version-specific content. We will use these annotations, and an XSLT stylesheet, to create version-specific schema files. We can then use the Walsh union from the “global disjunction” alternative above to validate against the union of these version-specific files.

Here is a source file that combines the v1 and v2 schemas above:

combined.rnc

namespace v = "http://osteele.edu/namespace/versioning/1.0"
start = root
root = element root {
  attribute version {
    [v:version="1.0"] "1.0" |
    [v:version="2.0"] "2.0"
  } &
  [v:version="1.0"]
  attribute x {string} &
  [v:version="2.0"]
  attribute y {string} &
  [v:version="1.0"] a? &
  [v:version="2.0"] (
    a* &
    element b {empty}
  )
}
a = element a {empty}

Note that, with the exception of the v:version annotations, this schema is almost exactly the same as the local disjunction alternative from above. It accepts any version 1 or version 2 document, but it also accepts hybrid documents that are neither valid version 1 nor version 2 documents. Nonetheless, it is useful as it stands, as a human-readable description of the schema, and as an overly permissive approximation for documentation tools or schema-aware editors.

The v:version attribute annotates version-specific content. v:version="1.0" marks content that is specific to version 1 of the schema. Any RELAX NG element can be annotated: element, attribute, value, and definition (including partial definitions introduced by |=@ and @&=).

The following stylesheet, when applied to the XML representation of this definition, produces the XML representations of either v1.rnc or v2.rnc, depending on the value of the version parameter. For example, xsltproc --param version 1.0 combined.rng v1.rng creates a version 1 schema, and xsltproc --param version 2.0 combined.rng v1.rng creates a version 2 schema.

<xsl:stylesheet xmlns:xsl="http://www.w3.org/1999/XSL/Transform"
                xmlns:v="http://osteele.edu/namespace/versioning/1.0"
                exclude-result-prefixes="v"
                version="1.0">
 
  <!-- stylesheet invoker should specifiy this -->
  <xsl:param name="version"/>
 
  <!-- copy the document, except for elements that match
       another template -->
  <xsl:template name="copy" match="/|@*|node()">
    <xsl:copy>
      <xsl:apply-templates select="@*|node()"/>
    </xsl:copy>
  </xsl:template>
 
  <!-- if it has a version attribute, only copy it if
       the version matches -->
  <xsl:template match="*[@v:version]">
    <xsl:if test="@v:version=$version">
      <xsl:call-template name="copy"/>
    </xsl:if>
  </xsl:template>
 
  <!-- remove version annotations -->
  <xsl:template match="@v:*"/>
</xsl:stylesheet>

(The code can be trivially extended to allow additional annotations such as v:since, v:until, and v:deprecated. With more work, it can be extended with annotations such as v:count="1" that manipulate the cardinality depending on the version. This latter extension removes the cumbersome duplicate definition of the @a@ element in the example.)

Applying this stylesheet to the combined schema above, with version set to 1.0, creates the v1.rnc schema file. Applying it with version=2.0 creates the v2.rnc schema file (plus some extra parentheses that reflect the way the combined schema was written).

> trang combined.rnc combined.rng
> xsltproc --param version 1.0 combined.rng v1.rng
> trang v1.rng v1.rnc

A Walsh union can be used to create a schema that validates against either of v1.rnc or v2.rnc, depending on the value of the version attribute. In fact, one could use the Xalan, Saxon, or XSLT 2.0 output redirection extensions to write a stylesheet that created all the versions of a schema (by iterating over the values of //@v:version), and whose main output was a Walsh union that included them all.

If the version attribute is marked as optional in the schema definition, this same technique can be used to implement optional versioning. If the attribute is missing altogether, it can be used to implement implicit versioning.

References

Dare Obasanjo, On Versioning XML Vocabularies

David Orchard, Providing Compatible Schema Evolution

Norm Walsh, Validating XSLT 2.0

I spent part of my vacation last month working on my web site. One change I wanted to make was to put a banner on every page, and a directory-specific column on the left. Nothing fancy by web design standards, but an adventure for a hobbiest without a CMS.

The first time I had to make a number of pages with a common template was in 1995, and I wrote a Lisp program to generate them. The next time I made a web site, I used Barry Warsaw’s Python program to create some pages. (I still didn’t have access to a server with server-side includes.)

Last year when I moved my site to a modern server, I used PHP include to add navigation elements to some of the pages. But this time I didn’t relish editing a number of HTML files, and, more to the point, I was ready to try something new.

The Problem

Let’s say that software/index.html looks like this:

<h1>This is my software page</h1>
<p>Welcome to my software page</p>

Furthermore, let’s say that there’s a file categories.html in the same directory:

<ul class="categories">
  <li><a href="lisp">Lisp software</a></li>
  <li><a href="python">Python software</a></li>
</ul>

I would like a request for http://osteele.com/software/index.html to retrieve this content:

<html>
...
<ul class="categories">
  <li><a href="lisp">Lisp software</a></li>
  <li><a href="python">Python software</a></li>
</ul>
<h1>This is my software page</h1>
<p>Welcome to my software page</p>
...
</body>
</html>

where the <html>...<body> and ...</body></html> are generated by header.php and footer.php.

A conventional solution would be to modify index.html so that it included some header and footer material as well as the actual content:

<?php include('header.php'); ?>
<h1>This is my software page</h1>
<p>Welcome to my software page</p>
<?php include('footer.php'); ?>

Of course, then I have to edit all my other files too, and any new files I add. And if I ever change the header and footer includes, I have to edit them all again. (For example, it’s likely that include('header.php') will become include($_ENV['DOCUMENT_ROOT'] . 'header.php') — now how many files will I need to touch?)

The include lines are domain-specific boilerplate. Like all boilerplate, they distract for the content of my source files, they add to the overhead of creating and maintaining the site, and they’re a chance for something to go wrong.

It seems backwards to edit the inside of a number of files just to control what gets shown on the outside (before the beginning and after the end). If each of the files is treated the same, something outside the file itself should do the wrapping.

Wrapping with RewriteRule

I used the Apache mod_rewrite module to solve this problem. I configured my .htaccess file so that a request for a URL with the path /index.html is rewritten into a request for the file /wrap.php. Within the body of wrap.php, the expression $_ENV['REQUEST_URI'] evalutes to the original path, in this case /index.html. The code in wrap.php can do whatever it wants with this pathname — show the original file, show just its name, or process it in some more sophisticated way.

My .htaccess file contains the following:

RewriteEngine On
RewriteBase /
RewriteRule ^.*.html$ /wrap.php [QSA]

and wrap.php looks like this:

wrap.php

<?php
  $file = $_ENV['DOCUMENT_ROOT'] . $_ENV['REQUEST_URI'];
  $sidebar = dirname($file) . '/sidebar.html';
  include('header.php');
  if (file_exists($sidebar)): include($sidebar); endif;
  include($file);
  include('footer.php');
?>

This strategy has several advantages over modifying every content file. The includes can be added or removed from any number of files without editing each file (just modify the regular expression in the RewriteRule); the includes don’t need to be copy/pasted to each existing file and each new file; and the includes can be maintained separately from the content.

AOP

The problem that motivated this — how to inject behavior into a set of source entities without modifying each one — is the same as one of the motivations for Aspect-Oriented Programming (AOP).

A “Hello World” of AOP is the problem of adding timing code to a set of methods. Adding timing code by hand to a single method is, like the header/footer problem above, a simpe matter of wrapping the method’s implementation at the source level. A method such as this:

void f() {
  do_something();
}

is replaced by this:

void f() {
  long startTime = System.currentTimeMillis();
  try {
    do_something();
  } finally {
    Logger.logTime(startTime, System.currentTimeMillis());
  }
}

AOP lets us leave the method body source unchanged, and place the timing code somewhere else (in a method on Aspect or Interceptor, depending on the AOP framework.) The timing code has a hole in it where the original method is spliced in — this is like the parameter to a function or macro. The location of this hole is signalled in the source by the proceed keyword in AspectJ, the JoinPoint.proceed() method in AspectWerkz, or the Invocation.invokeNext() method in JBossAOP.

Using AOP to insert the timing code has three advantages over modifying the method source: the timing code can be applied and removed without modifying the source; the same timing code can be applied to a number of methods without repeating it; and the timing code can be maintained separately from the methods. These are the same advantages of the RewriteRule+PHP solution to wrapper pages.

RewriteRule and AOP

In the language of AOP, the code that is injected into a program is advice. The location where it is injected is a join point. A set of locations is a pointcut; pointcuts are generally defined as a pattern or predicate that selects locations from a program.

In the timing example, the timing code (long time = ..., etc.) is the advice, the f@ method is the join point, and the pointcut is a specification such as @call(void C.f(void)) (in AspectJ, and if f@ is a method on @C).

In the web page wrapper, the advice is wrap.php, the pattern in the RewriteRule is the pointcut, and the join points are the URLs that that pattern matches. The statement include($_ENV['REQUEST_URI']) in wrap.php plays the same role as proceed or invokeNext() in Java AOP: it specifies where in the advice to insert the code at the join point.

Limitations

RewriteRule, not surprisingly, doesn’t do everything an AOP framework does. One way it falls short is that it only implements advice, not aspects. (An aspect is a set of advices, designed to be applied in concert.) It only implements around advice — although given around, it’s trivial to implement before and after by placing the include at the beginning or end.

Perhaps most seriously, it’s not possible to apply multiple advices to the same file. (Or at least, I haven’t figured out how.) In the example above, I listed the rewrite rule as RewriteRule ^.*.html$ /wrap.php [QSA], and used $_ENV['REQUEST_URI'] in wrap.php to retrieve the original URL. Since my actual .htaccess contains other rewrite rules too, I actually use RewriteRule (.*.html)$ /wrap.php?file=$1 [QSA] to rewrite the URL, and $_GET['file'] to retrieve the original URL. Either of these methods only works for one rewrite per URL, though.

This limitation means it’s not actually possible to factor a number of crosscutting concerns out of a page — just one. Certain other concerns can be factored out because RewriteRule and RewriteCond can check request headers and test and set variables, but in general you’re stuck with one general-purpose solution (aspects), and a few special-purpose solutions for whatever mod_rewrite handles. Of course, you can always use traditional OO techniques in the server-side code that you do weave together, to handle everything else in a non-AOP manner.

Summary

There’s something of a dancing bear quality to this: .htaccess is enough like assembly language that you can implement an aproximation of something high-level in it! (I remember being thrilled by Z-80 assembly language as a big step up from Dartmouth Basic, because now I could use subroutines for the first time.)

What I find interesting is that this wasn’t the motivation at all. I didn’t decide “let’s port AOP to .htaccess, just to see if it can be done”. Instead, I implemented wrapper pages the laziest way I could think of (where “lazy” means I didn’t have to do anything repetitive, now or in the future), and the result turned out to be closely analogous to AOP.

The stages of web site generation techniques that I gave at the beginning of this post — write a program to generate pages statically, use somebody else’s static page generation program, generate the pages dynamically, and finally weave the code that does the generation together dynamically — recapitulates the history of programming techniques in general. First there were a few domain-specific special-purpose code-generators, then compilers for general-purpose static languages, then dynamic languages caught on, and finally — as the binding time for everything, including program construction, gets later — AOP.

Web programming really is web programming.

An A Fresh Canvas I argued that there’s a human-factors advantage to allowing an XML document to contain names from multiple namespaces without requiring namespace prefixes on the elements from all but one of them. In What’s in a Namespace I looked at how namespaces and namespace imports work in programming languages, which generally allow both qualified imports (like XML Namespace) and unqualified imports as well.

I also said that I would demonstrate that unqualified imports could be added to XML in a well-defined way, if certain conditions were met. (The conditions are that the set of names in each namespace is known when the document is processed. This is the same condition that programming languages such as C++ and Java, that resolve the namespace of unqualified names at compile time, impose.) Here’s where I make good on that promise.

Running Example

The first example below is an LZX program. The second example is how the same program would look if XHTML and XInclude elements were qualified with their respective namespace prefixes. ¹

Impliicit namespace qualifiers

<canvas xmlns="http://www.laszlosystems.com/2003/05/lzx">
  <include href="button.lzx"/>
  <button>Click <b>me</b></button>
</canvas>

Explicit namespace qualifiers

<canvas xmlns="http://www.laszlosystems.com/2003/05/lzx"
        xmlns:xhtml="http://www.w3.org/1999/xhtml"
        xmlns:xi="http://www.w3.org/2003/XInclude">
  <xi:include href="mytext.lzx"/>
  <mybutton>Click <xhtml:b>me</xhtml:b></mybutton>
</canvas>

In order to show that the first document can be disambiguated into the same infoset as the second example, it’s sufficient to show a way to transform the first document into the second document. I’ll use an XSLT stylesheet to do this.

¹ I’ve played a switcheroo. Yesterday’s no-namespace LZX example didn’t even include the default namespace. I’ve added it today because the mechanism for defaulting the default namespace is completely different from the mechanism for qualifying prefix-free elements from other namespaces.

Defining the Name Map

In order to accomplish the transformation, we’ll need a map from unqualified names to qualified names. Here’s what the entries in the map look like:

(where xi@ and @xhtml are the prefixes that correspond to the XInclude and XHTML namespaces.)

I’ll represent this map in an XML file as a flat list of (_key_, value) pairs, where each key or value is represented by an XML element whose namespace and name are the namespace and name of the key or value. This representation lets us use XML Namespaces to define the namespaces for the key and value.

The keys have odd number positions, and values have even number positions.

<?xml version="1.0" encoding="utf-8"?>
<map xmlns:lzx="http://www.laszlosystems.com/2003/05/lzx"
     xmlns:xhtml="http://www.w3.org/1999/xhtml"
     xmlns:xi="http://www.w3.org/2003/XInclude">
 
  <!-- includes -->
  <lzx:include/>
  <xi:include/>
 
  <!-- XHTML -->
  <lzx:b/>
  <xhtml:b/>
 
  ...
</map>

(Purists take note: This is a schema that has been optimized for readability, not processing. A schema that was optimized for processing would relate the corresponding keys and values hierarchicaly instead of positionally; for example, <entry><source><lzx:include/></source><target><xi:include/></target></entry> or <lzx:include><xi:include/></lzx:include>. I experimented with these formats while I was writing this post and found them so unreadable I decided it was worth the extra XSLT to process the more readable schema above.)

To transform a document that uses unqualified names — all names are in the default (LZX) namespace — into one that uses qualified names — XInclude names are in the XInclude namespace and XHTML names are in the XHTML namespace — it’s sufficient to look each tag name up in this map, and if it’s found, replace it by the value.

The Stylesheet

Here’s the stylesheet that uses the map above to transform the first example into the second example. It copies every item in the source document unchanged unless the name and namespace of the source element match the element at an odd-numbered position in the map. If it does, the name of the element is replaced by the name of the element at the even-numbered position in the map.

The stylesheet only performs the replacement if it’s unique. One might want it to signal an error if an element in the source document matched more than one key. This would match the semantics of Java, where multiple namespaces can be wildcard-imported, but a name that is present in more than one unqualified import must be qualified at its point of use. Alternatively, one could choose the last value, for Python semantics, or define a file that contains an ambiguous map (that is, a relation that isn’t a function) as an error, whether or not the ambiguous key is used, for Common Lisp semantics.

<xsl:stylesheet xmlns:xsl="http://www.w3.org/1999/XSL/Transform"
                version="1.0">
 
  <xsl:param name="map.file">qualify.xml</xsl:param>
 
  <xsl:template name="copy" match="/|@*|node()">
    <xsl:copy>
      <xsl:apply-templates select="@*|node()"/>
    </xsl:copy>
  </xsl:template>
 
  <xsl:template match="*" priority="1">
    <xsl:variable name="name" select="local-name()"/>
    <xsl:variable name="ns" select="namespace-uri()"/>
    <xsl:variable name="value" select="document($map.file)/map/*[
                  (position() mod 2)=1 and
                  namespace-uri()=$ns and
                  local-name()=$name]/
                  following-sibling::*[1]"/>
    <xsl:choose>
      <xsl:when test="count($value)=1">
        <xsl:element name="{local-name($value)}"
                     namespace="{namespace-uri($value)}">
          <xsl:apply-templates select="@*|node()"/>
        </xsl:element>
      </xsl:when>
      <xsl:otherwise>
        <xsl:call-template name="copy"/>
      </xsl:otherwise>
    </xsl:choose>
  </xsl:template>
</xsl:stylesheet>

Taking the Qualifiers Back Out

The same stylesheet can be used to remove the qualifiers, if it’s run on the inverse map. Here’s an auxiliary stylesheet that reverses a map file such as the one above. Here’s where we pay the price for the readable map file format. (We also paid it in the complex select expression that initializes value in the renaming stylesheet above.) This stylesheet contains a couple of extra lines, that aren’t needed for functionality, to copy the text and comments between entries and between keys and values in an entry, so that the result is readable.

<xsl:stylesheet xmlns:xsl="http://www.w3.org/1999/XSL/Transform"
                version="1.0">
 
  <xsl:template name="copy" match="/|@*|node()">
    <xsl:copy>
      <xsl:apply-templates select="@*|node()|text()"/>
    </xsl:copy>
  </xsl:template>
 
  <xsl:template match="/map">
    <xsl:copy>
      <xsl:apply-templates select="@*"/>
      <xsl:for-each select="*">
        <xsl:if test="(position() mod 2) = 1">
          <xsl:variable name="pos" select="position()"/>
          <!-- text, comments, and pi's that precede this pair -->
          <xsl:apply-templates select="../node()[count(preceding-sibling::*)+1=$pos and not(self::*)]"/>
          <!-- the second element becomes the first -->
          <xsl:apply-templates select="../*[position()=1+$pos]"/>
          <!-- text, commens, and pi's that interpolate the pair -->
          <xsl:apply-templates select="../node()[count(preceding-sibling::*)=$pos and not(self::*)]"/>
          <!-- the first element becomes the second -->
          <xsl:apply-templates select="."/>
        </xsl:if>
      </xsl:for-each>
    </xsl:copy>
  </xsl:template>
</xsl:stylesheet>

When using this reverse map to remove namespace prefixes, an element that matches more than key should be ignored (in contrast to the possibilities for addin prefixes that were listed above). This is so that an element that needs an explicit namespace qualifier to disambiguate it, keeps this qualifier.

Extensibility

In the example above, the relation between the LZX, XInclude, and XHTML namespaces was baked into the processor (or whoever generates the name resolution map). An system designed for extensibility might allow per-document declarations, as the XML Include specification does. For example, a document that uses unqualified imports from XInclude and XHTML might begin with declarations to this effect:

<canvas xmlns="http://www.laszlosystems.com/2003/05/lzx">
  <import namespace="http://www.w3.org/2003/XInclude"/>
  <import namespace="http://www.w3.org/1999/xhtml"/>
  <xi:include href="mytext.lzx"/>
  <mybutton>Click <xhtml:b>me</xhtml:b></mybutton>
</canvas>

The namespace qualification stage of the processing pipeline would in this case be responsible for retrieving or constructing maps for the XInclude and XHTML namespaces.

Stepping Back

Unqualified imports solve one of the XML readability problems when XML is being used as a programming language. They let the author combine names from multiple namespaces without writing a prefix for each element, unless this is necessary to disambiguate the element’s name.

As with unqualified imports in conventional programming languages, unqualified imports in XML involve a tradeoff. In exchange for brevity, they introduce ambiguity — even if it’s a local ambiguity that downstream processing disambiguates in a well-specified manner. They complicate the rules for determining a name’s namespace — both for processing stages (which must be placed after the disambiguation step given in XSLT in this posting), and for humans looking to determine which qualified name a given tag name in the document source refers to.

Unqualified imports also give up some degree of forwards compatability. An XML document that uses XML Namespaces won’t break if one of the namespaces is extended with a name that matches a tag name that is used, unqualified, in the document. A document that uses unqualified imports may.

These tradeoffs — a more complicated qualification model, decreased chance of forwards compatability — are the same tradeoffs that the use of unqualified imports raises in programming languages. Unqualified imports aren’t always appropriate, but they would be good as a choice for XML programming just as they are in conventional programming — to be used when the context makes them appropriate.

In the design of LZX, we decided the context was appropriate for unqualified imports. The current implementation of LZX doesn’t actually use this system (you can’t actually use xi:include and xhtml:b, just include and @b@), but LZX is designed to be forwards-compatable with a system that does.

Last week I discussed the fact that “namespace hygiene” — the use of XML namespaces — would cause a simple Laszlo program such as this one:

<canvas>
  <include href="button.lzx"/>
  <button>Click <b>me</b></button>
</canvas>

to balloon to the following mixture of namespace declarations and namespace prefixes:

<canvas xmlns="http://www.laszlosystems.com/2003/05/lzx"
        xmlns:xhtml="http://www.w3.org/1999/xhtml"
        xmlns:xi="http://www.w3.org/2003/XInclude">
  <xi:include href="mytext.lzx"/>
  <mybutton>Click <xhtml:b>me</xhtml:b></mybutton>
</canvas>

This namespace explosion isn’t a problem for the server-side Java engineer or the XML-savvy processing pipeline plumber. XML is moving in this direction, and the preceding document isn’t overly heavy on punctuation compared to the typical XSLT source file, Jelly file, or JSP file that uses tag libraries.

It is a problem for a number of OO, GUI, and DHTML developers that should also be able to use LZX. The concepts associated with LZX aren’t that difficult, and don’t have anything to do with the hard problems in document integration that XML Namespaces are intended to resolve.

I also believe that the extra verbosity slows the speed of even expert developes, because it gets in the way of simple examples, in documentation and pedagogy, and exploratory programming and unit testing during development. I suspect that this is a contentious statement, because it comes down to a difference in development styles that is masquerading as a religious issue. I would like to discuss this later, but not today.

For now I’d like to assume there’s some merit to making programs that are written in XML look more like the first example above than the second one, and explore whether this can be done in a well-defined way.

Namespaces reviewed

A namespace is a map from names (string literals or “symbols”) to something else. The something else might be a variable, value cell, type, class, or just a longer name (which might name one of these). If a name can mean two different things in two different contexts, then namespaces are involved.

An example from the C programming language is the difference between struct names and variable names. A struct can be named date, and this is completely independent of whether a variable is also named date. An example from Java is the package. The java.lang.awt.List class is unrelated to the java.util.List interface, because one is in the java.awt package, and the other is in java.util.

Each interface and class in Java defines a namespace. Two classes A@ and @B, that are unrelated by class inheritance, can define a field named x@. @A.x is unrelated to B.x: the two fields can have different types and visibilities.

In fact, a Java class definition defines more than one namespace. One namespace is the namespace of fields of that class. Another is the namespace of class methods. A Java class A@ can therefore define both a _field_ named @A.year, and a method named A.year. This is in contrast to Python, where a method is a particular kind of attribute (the Python name for “field”) — fields and methods belong to the same namespace. (This also illustrates the difference between the space of names and the space of referents for those names. If B@ extends @A, then the year@s in @A.year and B.year are in different namespaces, but refer to the same method or field.)

Namespaces in programming languages solve two problems. One is the tendency to run out of meaningful identifiers within a package controlled by a single owner. The other is the problem of packages controlled by multiple owners. (”Owner” here simply means someone with authority to modify the names used within the package. If you’re able to modify all the source code you use, the second problem reduces to the first one.) Namespaces address these problems by doing away with the one-to-one correspondence between the spelling of the name and its referent. The correspondence between the name and the named entity is now a function of the context of the name, as well as its spelling.

Namespace selection

Given multiple namespaces, what rules are used to determine which namespace is used for a given occurrence of a name? There are two main methods of namespace selection, or name resolution.

First, the namespace may be a function of its syntactic type. For example, in Java, methods and fields are in different namespaces, as we saw above. In XML, tag names and attribute names are in different namespaces. Lisp dialects are famously divided into Lisp 1 and Lisp 2 dialects, depending on whether variables and functions share a namespace. This method of namespace resolution is used when there’s a small number of implicitly defined namespaces, as in the difference between methods and fields, or the namespaces that a class definition introduces.

The second method of namespace resolution is explicit: Each namespace has a name, and the program language has syntax for specifying the namespaces that are used in different contexts. Java and Python use the import statement for this. XML uses the xmlns and xmlns:* attributes.

(Note that if namespaces are named, as in the second method, there still has to be a way to resolve the referent of a namespace — there has to be a namespace of names, as it were. Often this bottoms out in a load path or other list of linked libraries. For example, the resolution of java.util.List into an interface is defined by the classes on the CLASSPATH.)

Programming languages that use import generally have two styles for specifying what is imported, and two styles for specifying how the imported name is named:

Literal and wildcard imports

Consider the difference between the following two Java statements:

import java.util.List;

import java.util.*;

The first line makes List available as a name for java.util.List. The second line does this too, but makes any other class and interface names in java.util available, without the preceding java.util., as well.

This corresponds to the distinction between the Python statements:

from java.util import List

from java.util import *

and also between the Haskell statements:

import Prelude

import Prelude {List}

The point of the multiple examples being that this is a pretty widely accepted design for namespaces, not just an accident of Java.

(Python differs from Java and Haskell in that (1) in Python, a namespace is a runtime object, and (2) import is defined to modify an existing namespace at runtime. Also in Python, like XML and unlike Java and Haskell, the scope of an import can be smaller than the entirety of a source file. These are three of many other differences among the way name lookup happens in different languages, that I’m ignoring here.)

Unqualified and qualified names

A qualifier is a string that is attached to the name (usually by prefixing it), at the point where the name is used. For instance, List is an unqualified name; java.util.List is a qualified name: it is the simple name List, prefixed by the string java.util. to indicate that it names the List interface in the java.util package.

Java always allows qualified names. java.util.List is valid as an interface name regardless of whether an import statement for java.util or java.util.List exists. The import statement, in Java, is only for the purpose of allowing unqualified names as well: in the presence of import java.util.List or import java.util.*, List and java.util.List are synonymous.

Python and Haskell require an import statement in order to use a name defined in a different code unit. Consider the difference between the Python statements:

import java.util.List
from java.util import List

The first introduces java.util.List (but not List). The second introduces List (but not java.util.List). It is perfectly legal to include both statements in a source file. In this case, List and java.util.List will refer to the same value.

Rounding out the example set, Haskell allows this same distinction:

import qualified Prelude
import qualified Prelude {List}

Note that the distinction between qualified and unqualified imports is orthogonal to the distinction literal and wildcard imports:

import java.util.List      # Qualified literal
from java.util import List # Unqualified literal
import java.util.*         # Qualified wildcard
from java.util import *    # Unqualified wildcard

Conflict resolution

What happens when both java.util.List and java.awt.List are imported? (As unqualified imports, otherwise there isn’t any problem.) There are a number of logical possibilities, but there are three that I’ve seen used:

1. It’s a compile-time error, whether or not List is ever used. The Common Lisp package system used this. It was incredibly painful.

1. It’s a compile-time error if List is used; otherwise it’s legal. C++ and Java use this policy. It seems to work well.

1. One takes precedence. Python uses this policy. It sounds like it would be a potential source of errors, but it seems to work in practice.

Where does XML fit in

XML Namespaces allow both qualified and unqualified names. xmlns="http://www.w3.org/1999/xhtml" defines a namespace that is used by unqualified tag names such as h1@. @xmlns:xhtml="http://www.w3.org/1999/xhtml" defines a namespace that is used by names such as xhtml:h1 that are qualified by the prefix xhtml:.

XML is like Python in that a namespace must be declared to be used. In the absence of an xmlns or xmlns:xhtml attribute, it is impossible to use the h1@ tag from the @http://www.w3.org/1999/xhtml namespace. {http://www.w3.org/1999/xhtml}h1 is often used in XML written material to refer to this tag, but this is an abbreviation for h1@ or @xhtml:h1. In a context that contains an xmlns attribute. It’s not valid XML.

XML differs from the programming languages I discussed in one important way: In any given context, only names from one namespace may be used without qualification. Unlike Java, Python, Haskell, C++, Common Lisp, and every other language I know that has explicit namespaces at all, in XML, you can’t mix and match names from n different namespaces unless you prefix n-1 of them at each point that they’re used.

For example, In Java you can import both List from the java.util package and FastArrayList from the org.apache.commons.collections, and use both List and FastArrayList without qualifiers. (This is handy because FastArrayList implements the List interface.)

import java.util.List;
import org.apache.commons.collections.FastArrayList;
...
  List children = new FastArrayList();

In XML, you can choose one namespace or the other to use without qualification, but not both — even if the two namespaces don’t define any tags with the same names. This is the same as the conflict resolution rule I found unwieldy in Common Lisp, but worse — it’s not only an error if the two namespaces share a name, it’s an error just to import them both unqualified at all!

If Java did this, you would have to choose between writing:

List children = new FastArrayList();
java.util.List children = new org.apache.commons.collections.FastArrayList();
java.util.List children = new org.apache.commons.collections.FastArrayList();

I think there’s a reason that none of C++, Java, Python, and Haskell confines you to this choice.

Is there a way out?

In my next post I’ll propose a way to make XML look more like a programming language in its use of namespaces, discuss where it’s appropriate to do this (there are plenty of places XML Namespaces are used today where my proposal wouldn’t be appropriate), and give a proof of concept, in XSLT, that this can be done with a well-defined semantics.