2008-11-23

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.

11 comments:

callingshotgun said...

Interesting post- Hadn't looked into Oslo yet. A question, though- This seems similar to Google's open-sourced "Protocol Buffers." How do they compare in terms of pros/cons?

Joey said...

Looks like JSON to me!!

M. David Peterson said...

>> 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. <<

True, but isn't making an attempt to standardize a language that exists in an alpha state a bit premature? After reading your analysis I'm /REALLY/ liking what I'm seeing: It's like the best of Scheme, XSLT, and XML wrapped into a C-style syntax that's feels familiar to a broader swath of folks.

Let's start talking about standardization once a field-tested 1.0 release hits the streets. In the mean time, fuck standardization: Let creativity and real-world problem solving take its due course. Then standardize once the language feels complete enough to start imposing "You MUST do this to be considered a standards compliant implementation."

Or am I missing something more obvious that suggests letting the standardization process reign supreme over the creativity process is a better approach than just letting creative, brilliant people such as yourself get involved with the creation process before then taking things to the next obvious level of standardization.

I hope not, because /your/ brain and talent involved with the creation of a wrist friendly executable version of XSLT causes feelings of "Oh, Dear God... What could the collective forces of James Clark, Don Box, Chris Sells, and other prominent members of the "If I had my way, S-Expressions inside of LISP/Scheme/DSSSL/related dialects would reign supreme" community create if they weren't forced to work through the confines of a standardization body until they were God damn ready to work with a standardization body to bring an official definition to the end result of their open sourced creative process of creating a language that couldn't be criticized by anyone with the credentials for their criticisms to actually matter.

Hell, I'd bet even Knuth would find joy in the end result of just such a creation from just such a group of folks.

James: Get involved. PLEASE!

M. David Peterson said...

@callingshotgun:

>> This seems similar to Google's open-sourced "Protocol Buffers." How do they compare in terms of pros/cons? <<

Huh? Protocol Buffers are a binary data serialization format. Suggesting ProtoBuf's and the M language represent the same thing would be like suggesting,

'(foo '(bar baz))

... and ...

(foo '(bar baz))

... represent the same thing.

For the record, they don't. ProtoBuf's are binary data structures. Like the first sample from above, PB's just represent data. Nothing more, nothing less.

On the other hand, like LISP/Scheme, M combines both code and data such as that represented by the second sample.

Another example: XSLT == XML, but XML certainly != XSLT.

James Clark said...

Absolutely. Entering the standards process now would be very premature. Design by committee tends not to produce very elegant results. But I would like standardization to be on the agenda eventually, when the time is ripe (which I would have thought would be several years away at least).

Anthony B. Coates said...

Thanks for taking the time to post this review of M, James! It was just the kind of summary I was looking for.
Cheers, Tony.

Kingsley Idehen said...

James,

How is "M" conceptually distinct from RDF and the Semantic Web vision in general? In both cases we are looking at Entity / Conceptual Level Data Modelling.

I continue to scratch my head about the degrees of cognitive dissonace exhibited by these efforts :-)

Kingsley Idehen

logomachist said...

What Kingsley Idehen said.

Is there any indication that MS is targeting XML with this language or is it possible they're out to snip the very gradual growth of RDF before it becomes serious competition? Or, put another way, maybe M could revitalize the Semantic Web push? RDF has had years of slow growth but so far it's kind of floundered about. A serious commitment by MS to an alternate syntax might but just what the SW needs.

M. David Peterson said...

@Kingsley:

Conceptually speaking what's the difference between what C is trying to accomplish and what LISP is trying to accomplish? Scratching your head at why on earth C was ever needed in the first place doesn't change the fact that C hit a developers sweet spot that to this day LISP has yet to hit.

Is LISP a better overall language than C? I think so, but I also look at XSLT and see poetry while others see utter chaos and confusion.

RDF and M might theoretically solve the same domain of problem(s) just as LISP and C might do the same for their respective domain(s).

But C won. Why?

Arguing that one way of solving a problem simply mirrors an existing way of solving the /same/ problem does not mean the argument has been won. Instead, it means that if you find yourself arguing why the predecessor is better than the follower, it's probably because the follower now owns 90% of the same market the predecessor is lucky to still be consider a contender in.

Worser is better, Kingsley. Just ask Bill Gates and Steve Jobs. ;-)

M. David Peterson said...

@Kingsley:

Conceptually speaking what's the difference between what C is trying to accomplish and what LISP is trying to accomplish? Scratching your head at why on earth C was ever needed in the first place doesn't change the fact that C hit a developers sweet spot that to this day LISP has yet to hit.

Is LISP a better overall language than C? I think so, but I also look at XSLT and see poetry while others see utter chaos and confusion.

RDF and M might theoretically solve the same domain of problem(s) just as LISP and C might do the same for their respective domain(s).

But C won. Why?

Arguing that one way of solving a problem simply mirrors an existing way of solving the /same/ problem does not mean the argument has been won. Instead, it means that if you find yourself arguing why the predecessor is better than the follower, it's probably because the follower now owns 90% of the same market the predecessor is lucky to still be consider a contender in.

Worser is better, Kingsley. Just ask Bill Gates and Steve Jobs. ;-)

M. David Peterson said...

@James:

I think I may have submitted my last comment more than once, and possibly more than twice. "How?" you might ask?

Yeah, you got me on that one, cuz' I'm not really sure. But there was definitely at least one "did that get submitted correctly?" statement followed by a "I don't think it did" followed by a "Oh /PLEASE/ tell me I didn't just resubmit it *TWICE*!".

You'd think after programming these damn things for the last 25 years I would have got the hang of how to use them.

Apparently not. ;-)

Anyway, please feel free to delete however many duplicates made their way through, and in the mean time:

You: "Absolutely. Entering the standards process now would be very premature. Design by committee tends not to produce very elegant results. But I would like standardization to be on the agenda eventually, when the time is ripe (which I would have thought would be several years away at least)."

Can't help but agree. For the Record, and FWIW, it seems to me that "M" is something that the "Big Dogs" at MSFT have been planning for quite some time. See: http://www.xsltblog.com/archives/2005/11/is_the_agile_de.html for a better understanding of what I am referring to (closer to the bottom where I mention Chris Sells "LISP" comment is where things sorta come together...)

In other news, what reminded me about this post was Doug Purdy's post [http://douglaspurdy.com/2008/12/05/james-clark-on-oslo-m/] from a few days ago which, at present time, is linked to on the front page of the MSDN "Oslo" front page under the "Oslo Team Blogs" header in the bottom left hand corner of the page: http://msdn.microsoft.com/en-us/oslo/default.aspx

"Big Brother" is paying attention, apparently. Good for Big Brother! It's about time he started realizing that little brother knows twice as much, is twice as fast, and is half his size.

The word "agile" comes to mind. ;-)

Go show Big Brother what little brother is all about, James! w00t! :-D