Balisage Paper: Axioms of Versioning

Introduction

What is compatibility anyway? What does it mean when we say a version of a language is backward and/or forward compatible with another language? What does it mean when we say this of a document, or message, or schema, or an application? Does the notion of compatibility apply to languages at all, or does it only apply to documents or applications? And what is the difference between syntactical an semantical compatibility?

Questions like these have lead me to explore the notion of compatibility in a more formal way. For efforts in achieving back- and forward compatibility in real life applications, a framework for understanding key notions in compatible versioning can be very useful. Key to understanding the working of advanced compatibility mechanisms is the semantical equivalence set. In this paper we shall define what it is, and explain why this notion is central to understanding compatibility.

I will focus on message exchanges, since that is my main area of expertise, but the principles apply much wider. In general, they should apply to most computer-understandable document formats for data storage and/or exchange. More specific, I do not intend to cover natural language, other non-computer languages, programming languages or specifically multi-document data stores such as databases.

Languages, Sets and Extensions

Consider a set U of language specifications in the above field.

It's easy to define for each language specification the set of conforming document instances extensionally, as a set. For instance, the extension of UBL 1.0 is the set of all possible conforming UBL 1.0 instances, or the extension of HL7v3, May 2007 ballot is the set of all possible conforming HL7v3, May 2007 instances. (Often, language specifications for message exchange have many flavors and variations. HL7v3 has many versions ("ballots") and even those are hardly ever implemented as they are, but instead are localized to a particular national environment before implementation.)

Bal2008graa030601

Extension ELx of a Language

If we show this pictorially, we get the above figure. Lx is a language specification which has all blue rectangles as conforming documents. The extension of Lx, ELx, are all blue rectangles. The complement (everything not in ELx) are all non-rectangular blue shapes, and all shapes in other colors.

Bal2008graa030602

ELx as Subset of ELy

The extension of the language Ly consisting of all rectangles in any color is a superset of the extension of Lx; for shorthand, we say Ly is a superlanguage of Lx.

Bal2008graa030603

ELx as Subset of ELz

Likewise, Lz, the language of all blue shapes, is a superlanguage of Lx.

Bal2008graa030604

ELx as Intersection of ELz and ELy

And Lx is (extensionally) also the intersection of Ly and Lz.

Starting with a rather loose notion of "conformance" (let's assume for the moment this notion is unproblematic) it's easy to define relation between languages extensionally. A language Lx can be an extensional sublanguage of Ly: if every document conforming to Lx is also a conforming Ly document. If the reverse is true, all conforming Ly documents are also conforming Lx documents, Lx is an extensional superlanguage of Ly. If both are true, Lx and Ly are extensionally equivalent. Note that we only speak of extensional equivalence: for all we know, Lx may be about pasta recipes and Ly about reggae albums: if by some weird happenstance both languages have encoded their information in similar data formats, we can still compare the pasta and reggae languages extensionally.

Accepting and Rejecting Documents

Bal2008graa030605

Accept and Reject Behavior of Px

Applications can read and write (produce and consume, send and receive) documents. For now we still suppose an application reads and writes the same set of documents. In the above picture, the implementation Px1 of language Lx accepts all blue rectangles (ELx), and rejects all other documents. So through accepting and rejecting, Px1 decides which documents are syntactically conformant with Lx (as implemented in Px1).

From Syntax to Semantics

When we move from pure extensions, we must consider the semantics of a language. This is a difficult notion. At one extreme, a language may not consider semantics at all, and just define a syntactical data format, and leave all semantics up to applications. It's often said that "XML is just syntax". But if this is true, XML itself is not very interesting, and the real-world applications of XML, such as in UBL or HL7v3, certainly must include some semantics. At its highest level, those semantics are descriptions in natural language, defining for instance what an invoice or a medication prescription is. At a lower level, those semantics may be expressed in more formal ways.

One way to (try to) express the semantics of messages in a messaging system with respect to forward and backward compatibility is to use formal semantics. This is – in my opinion – the wrong way. For simple (abstracted, theoretical) systems this might work. One would have to model the system and the encapsulated exchanged information using a language such as OWL. For real life purposes, this is hardly feasible. To make an OWL description of the underlying semantics of UBL or HL7v3 is a (much) larger undertaking than specifying a decent versioning mechanism to provide back- and forward compatibility to a reasonable degree: so using formal semantics to provide a framework and definitions for the notion of compatibility defeats the problem.

Semantics and Behavior

A language specification of the kind under consideration should enable a capable engineer to implement a conforming application: an application which presumably can read an write conforming documents (let's assume for the moment the application can read every document it writes and vice versa). The application as a total then exhibits some behavior: if we use a word processor to read a document, we expect the word processor to display the stored text and formatting. If we use a medical application to send a prescription, we expect the receiving application to display the intended medication and applicable quantity and dosage.

Languages may not define behavior very strictly. HL7v3 even goes at great length to stress is does not restrict application behavior at all, but I do not think this really holds. Obviously there are a great deal of application behaviors which are at odds with HL7v3 specifications, such as displaying pasta recipes instead of medication prescriptions.

The behavior of a message endpoint is not unproblematic. It's usually best to consider some message endpoint to a certain degree as a black box; to consider only what's going in and coming out, not what is inside. How it works is not relevant; what it does is relevant. But when sending messages, there often is no direct behavior (no response) associated. When I send you a message with my new home address, I may expect no response (or just a simple ask). I do expect future mail to be delivered to my new home address, however. the point is, there may never be new mail to me, so there may never be a response message showing the desired behavior.

On a higher level, the behavior of a corresponding message endpoint may not be deterministic at all. When a general physician sends a medication prescription to a pharmacist, the pharmacist may overrule the general physician's decision: this is an independent professional judgment, based on the pharmacists own competence.

So the behavior of a message endpoint is not unproblematic. I believe the solution is basically to take humans out of the box. We must consider the behavior of a receiving computer system when judging the behavior for a message, not the humans interpreting and acting on the information. The behavior of the application is also in need of human interpretation. For instance, a part of a medication prescription may be:

<code code=”27” codeSystem=”2.16.840.1.113883.2.4.4.5” />

and the receiving application may display:

"Dissolve in water"

which is a faithful rendering of the information sent. However, instead of "Dissolve in water" the receiving application may also display some local code. In general, it is not possible to judge whether a receiving application behaves well without the judgment of a professional well acquainted with the messaging framework as well as the receiving application.

So where does this leave us with behavior as a basis for a framework for compatible versioning? If we take a look a practical aspects, behavior is a near perfect fit. The most practical aspect of a framework for compatible versioning is testing the entire messaging chain. And especially for this aspect, behavior as a basis for semantic compatibility is perfect. The fact that there may – in real life – never be a response message showing the desired behavior is not relevant. Relevant is the fact that such behavior is a testable condition of the messaging chain. In a test, we can send an "update address" message and next test the printing of an address label. Likewise, the fact that behavior is not deterministic with a human "in the box" is not a problem: in testing, we generally want a professional judging whether the system does what it is supposed to do. Again, behavior as a basis for semantic compatibility is a perfect fit.

If we have a certain implementation of a language specification, the reading of a document should result in a changed application state: for instance, the text on the screen has changed, or its internal data store has been updated, resulting in specific behavior if the data store is later queried. Let's assume, as most often is the case, that the behavior (the state change) is deterministic: if the application is in the same state before reading a document, then reading the document always results in the same end-state.

Behavior of Language Processors

Bal2008graa030606

Behavior of Px

We can show the behavior of a processor Px1 pictorially as in the above figure: for every document in ELx, Px1 exhibits some particular behavior. Px1 is partitioned, as it were, in behavioral compartments, one for each document.

Of course it is quite common for messaging systems to have different behaviors for exactly the same document: for instance, a common property of reliable messaging is for an order to be executed, and a duplicate to be rejected (unless the original was lost, which is the raison d'être of reliable messaging). This is no serious obstacle to the model: for testing purposes, it is sufficient (and desirable) to assume a fixed start state for any sequence of messages, which makes the responses deterministic. For real life systems, if we wanted to model this aspect, we could assume the behavior to be determined by the message and (some aspect of) the state of the processor. Like before, I believe a framework in which testable scenario's can be described sufficient.

Next we need to make some idealizations to get rid of all the processors. We'll simply assume every language specification is flawless (not hard to imagine, is it?) and there is a perfect processor for every language; we'll take that processor as an exemplar of the language. And we no longer assume a processor makes the same set of documents as it accepts.

Syntactical Compatibility

This allows us to define syntactic compatibility: a (language) processor is syntactically compatible with another (language) processor if they are able to exchange documents without syntactic failure: if they are able to accept each other's documents. A common case is when they implement the same language (version).

Bal2008graa030608

Behavior with Disjunct ELX and ELy

But the processors need not produce the same documents at all. Another common case is where one processor makes and sends orders, but does not receive orders, and the other processor receives orders and makes order confirmations, but no orders. Even though the processors make and accept different documents, it makes perfect sense to say they are syntactically compatible. So we can say a processor Px is compatible with a processor Py if Px makes only documents which Py accepts, and Py makes only documents which Px accepts. (It would be more common to say Px and Py are partial implementations of one and the same language, but that does not change the point.

Bal2008graa030609

Behavior and Forward Compatiblity of Px and Px+1

For versioning, the interesting case is twofold: for backward syntactical compatibility, a processor Px+1 should accept all documents produced by Px. and for forward syntactical compatibility, a processor Px should accept all documents produced by Px+1. The above picture highlights one variant, where Px and Px+1 both accept the same set of documents, but make different sets.

The accept/reject reaction to a document is fundamental to the entire compatibility and versioning problem. However, the accept/reject distinction is not syntactical in nature. It is a behavioral aspect of a processor: accepting or rejecting is a response to a document, it attaches meaning to the document: acceptable! (or not). So the basic aspect which decides syntactical conformance in a sender/receiver (writer/reader, producer/consumer) configuration is itself semantical in nature.

The key to enhance (future) compatibility on a syntactic level is to make processor accept more than they produce. In other words, a processor should not reject everything it could not produce itself, and should not reject everything it does not completely understand. Next, we'll see what to do with that un-understood "extra".

Semantical Equivalence Sets

Bal2008graa030610

Behavior of Px

In the above figure, we have a processor for a language which makes only blue rectangles, but accepts all rectangles. If we now associate some particular behavior which each class of documents, we get semantical equivalence sets. Not every document is normally associated with some unique behavior: we often have syntactical redundancy, as in C's i=1+1 and i+=1 or attribute order in XML: so there is a set of documents which excite the same behavior in a receiver. The pattern of syntactical forward compatibility, where a receiver accepts more than it can act upon, achieves the same: there is a set of documents for which trigger the same behavior: since the receiver does not understand the extra syntactical components, it cannot act upon them, and it therefore must act the same, whatever the extra content.

Semantics and Compatibility

Bal2008graa030611

Behavior of Px+1

If a language Lx has a successor Lx+1, Lx+1 may specify additional behavior for documents accepted, but not produced by Lx: in the above figure, green and red rectangles. This has two consequences: - for every document produced by Px, Px+1 will behave as Px expects: it is therefore safe for Px to send messages to Px+1 - for documents produced by Px+1 which Px cannot produce (again the green and red rectangles) Px will exhibit the same behavior as for other documents in the same semantical equivalence set: the language designer of Lx+1 will know what behavior this is, and if it is deemed acceptable, it is safe for Px+1 to send messages to Px (if the behavior is not deemed acceptable, Px+1 must make sure in some way that Px will reject those documents, maybe through a "mustUnderstand" flag).

Conclusion

The basics of compatible versioning thus are: 1. make sure Px accepts more documents than it produces (or fully understands), and, 2. partition the semantical equivalence sets of Px into smaller, more refined semantical equivalence sets for Px+1 with additional (new) behavior.