Balisage Paper: Luminescent: parsing LMNL by XSLT upconversion

LMNL: the Layered Markup and Annotation Language

LMNL (Layered Markup and Annotation Language) is an approach to markup first proposed by Jeni Tennison and myself in 2002 [Tennison and Piez 2002]. It emulates XML in some respects, but also differs from it in several fundamental ways, suggesting some very different approaches to modeling text-based information using markup, with some very different applications. For this reason, even if an alternative processing stack could never be built on LMNL (which presumably it could, given enough time, effort and resources), and even if LMNL is never regarded as a replacement for XML (which it was never intended to be), it turns out to be fertile laboratory for solutions to modeling problems - including XML-based solutions for XML platforms.

XML is defined [XML Recommendation] as a syntax, but implies a model, which was described by the (non-normative) XML Information Set [XML Infoset], expressed in any number of code libraries and APIs (both official and unofficial), and finally standardized (at least in one variant) in the XPath 2.0/XQuery Data Model (XDM) [XDM] . LMNL inverts this, being defined first as an abstract model, whose syntax is proposed incidentally, as a form of representation (and as such, one among many conceivable). Nevertheless, the idea is the same: a formal model stabilizes a set of capabilities for tools performing useful operations over text-based information sets, and provides a basis for interoperability, while a syntax provides a serialization format and an interface for developers and users. Like XML, LMNL is conceived in order to support markup, a means of assigning labels and attributing properties and relationships to data points or fields in text, by means of text; and like XML, LMNL expects to provide a basis for descriptive and declarative markup applications (although, again like XML, not only those), which support document and data processing within layered systems that can thus benefit from separation of concerns (between authoring, editorial, data management, and production tasks, for example), and that are not locked into single applications. Again like XML, LMNL does this by leaving it to applications to define their own sets of names, labels or keywords, to which they can assign whatever semantics they see fit. In this respect, LMNL syntax (like XML) is a meta-language while LMNL itself (like the XDM) is a meta-model: a model (with a design and hence a particular set of affordances in application) that we use to make models, of documents, families of documents, and assorted information sets of whatever description.

This much is similar; the differences from XML are (primarily) in the design of the model itself, and (secondarily) in the syntax proposed to represent it. The syntax is designed to look as little like XML as possible, for two reasons: first, so that LMNL syntax may be embedded directly into XML syntax, or the reverse; and secondly, to reduce cognitive overload when thinking about LMNL and XML together, or when thinking about LMNL with the burden of expectations formed by XML. (At the level of the model, we have similarly tried to avoid using XML terminology for LMNL concepts except where the connections are strong.) In the interests of brevity, rather than explicate the model fully and offer rationales for it here, I offer a simple summary description of the model, and of LMNL syntax, together.

[s}[l}He manages to keep the upper hand{l]
[l}On his own farm.{s] [s}He's boss.{s] [s}But as to hens:{l]
[l}We fence our flowers in and the hens range.{l]{s]

[excerpt}
[s}[l}He manages to keep the upper hand{l]
[l}On his own farm.{s] [s}He's boss.{s] [s}But as to hens:{l]
[l}We fence our flowers in and the hens range.{l]{s]
{excerpt]

[r=r1}A case [r=r2}of{r=r1] arbitrary overlap{r=r2]

[excerpt [source}The Housekeeper{source] [author}Robert Frost{author]}
[s}[l [n}144{n]}He manages to keep the upper hand{l]
[l [n}145{n]}On his own farm.{s] [s}He's boss.{s] [s}But as to hens:{l]
[l [n}146{n]}We fence our flowers in and the hens range.{l]{s]
{excerpt]

...[l [n}145{]}On his own farm.{s [id}s1{]]...

[excerpt
  [source [date}1915{][title}The Housekeeper{]]
  [author
    [name}Robert Frost{]
    [dates}1874-1963{]] }
[s}[l [n}144{n]}He manages to keep the upper hand{l]
[l [n}145{n]}On his own farm.{s] [s}He's boss.{s] [s}But as to hens:{l]
[l [n}146{n]}We fence our flowers in and the hens range.{l]{s]
{excerpt]

[link [href}lmnl-markup.org{]}{{logo [src}lmnl-markup.org/hat.png{]}}{link]

xLMNL: an XML-based representation of the LMNL data model

One way LMNL builds on the conceptual foundation of XML is by differentiating between operations on the syntax, which imply parsing, and operations on optimized representations of documents held in memory: the model. This differentiation gives us leverage in development, since we have the opportunity to identify either syntax or model as the appropriate place for design and implementation, whether that be of the tag set itself (considered as a set of labels and constraints over their use), user interfaces, transformations or anything else.

Paradoxically, while the LMNL model is designed in deliberate contrast to XML, it is nevertheless useful to specify an XML-based representation of it, for several reasons. First, it exposes instances conveniently by giving us the opportunity to serialize LMNL documents in XML syntax. Second, it makes it possible to use XML-based tools (such as XSLT, schema technologies, XQuery, XML servers, CMS and database technology) to query and manipulate LMNL – an advantage for those of us who are well-practiced in these technologies for data processing, but not in Java or Python. And thirdly, it clarifies some of the resemblances and differences between LMNL and other approaches (especially XML-based approaches) to the problem set.

Since 2002, I have experimented with adapting XML to LMNL in several different ways. Not only can XML elements be construed as LMNL ranges and XML attributes as LMNL annotations (this is the essence of the CLIX and ECLIX approaches, cf Piez 2004); also, XML-based notations for representing overlap, such as milestone-based notations or segmented and aligned XML elements, can be mapped into LMNL. This provides a framework, at least, for thinking systematically about how to implement and maintain processes to manage these awkward and difficult forms of XML.

Yet the real power of the LMNL model as such cannot be exploited without a more direct representation. xLMNL is an XML-based representation of the model itself: that is to say, it leaves behind the concept of a document as an information set represented in embedded markup (literal tags applied directly to literal text), and simply uses XML as a kind of poor man's (hierarchical) database. This gives us many of the advantages of an XML platform described above, while making downstream applications more tractable, inasmuch as they can work directly with LMNL as conceptualized, rather than at a remove. At the price of being somewhat heavyweight and memory intensive, xLMNL is thus a useful interim format for testing ideas and demonstrating concepts.

Again, the most concise way of presenting this design is by way of an example: the xLMNL equivalent of the document given above is presented in Appendix A.

Developers who work on the overlap problem in XML will recognize this as a standoff representation of ranges. As such, it might be generated and maintained in any number of ways – even (if rather onerously) by hand.

Nevertheless, no claim should be inferred that I suppose xLMNL to be at all an optimal approach to working with LMNL on an XML platform. The best argument for doing this is that fairly dramatic demonstrations of the interest of overlapping markup are not all that hard to come by if one only has a means by which to create them, and xLMNL is a step along the way.

A schema for xLMNL, using Relax NG (compact syntax) appears in Appendix B.

Compiling LMNL syntax into xLMNL via XSLT upconversion

In its current form, the complete Luminescent pipeline has thirteen steps, each of which is implemented in an XSLT 2.0 transformation. These can be chained together using any available means; I have used both XProc and Cocoon (which is convenient for hooking Luminescent together with further transformations processing xLMNL into various targets). Several of the steps could be combined for greater efficiency; the reason to have so many presently is to maximize transparency for development and debugging.

The steps proceed as follows:

[excerpt [source}The Housekeeper{source] [author}Robert Frost{author]]}
[s}[l [n}144{n]}He manages to keep the upper hand{l]
[l [n}145{n]}On his own farm.{s] [s}He's boss.{s] [s}But as to hens:{l]
[l [n}146{n]}We fence our flowers in and the hens range.{l]{s]
{excerpt]

Error UNEXPECTED-TAGGING reported for } at 1:71,
  C:\Projects\LMNL\Luminescent\lmnl\frost-quote.lmnl
No start tag matches end tag {excerpt] at 5:1,
  C:\Projects\LMNL\Luminescent\lmnl\frost-quote.lmnl

Working with the model: prototype LMNL applications

Currently I have several processes running with xLMNL as source. Some of these are tuned to particular tag sets, while others are generic. A selection is offered in place of presentation slides for this paper (the zipped package contains a mix of HTML, XML and SVG and can be reviewed starting from index.html using any current web browser).

Links to demonstrations are provided in Appendix C.

Reflections

I can make no pretense as to the efficiency or scalability of this approach. So far, it has only worked well enough for my purposes: to demonstrate its feasibility in principle, and to test the specifications. While it has performed adequately well on documents up to several hundred Kb in size, and experience suggests that processing bottlenecks for Luminescent are actually more likely coming out of xLMNL rather than into it, I have no data to confirm my intuitions here. There does appear to be a rich and interesting set of problems at hand.

Nevertheless, if nothing else, this exercise has suggested some very interesting things about markup technologies beyond XML. One of the keys appears to be the separation of the parsing of the syntax from the construction of the model; so the parse tree is a tree only of the tags, from which the document model is derived by a different process. (The parse itself works like a parse of S-expressions, in which open and close delimiters are recursively parsed into tags.^[3]) In this view of things, machine-automated text processing can support a very different form of document description than that provided by the operational semantics of XML, which in order to build a document model from the markup in a single pass, must limit itself to a syntax in which not just tags but the element structure itself can be described by a context-free grammar.^[4] Thus its document models are limited to trees and to graphs projected over that tree [Bos 2005]. While not, formally, more expressive than XML markup (since graphs projected over a tree can express the same relations as LMNL markup, as indeed they do in xLMNL or other XML-based representations of LMNL), LMNL markup is practically so; it can get closer to the text than XML does, inasmuch as in order to fit within its own rules, XML's representation of a document (or at any rate, of a document in which overlapping structures or features, or structured annotations, are represented) is always getting in its own way.

Related to this is another aspect of this work: this parsing or compiling process does not assume a single depth-first traversal of structures implicit in the syntax, and so does not perform a single pass over the data. Instead, it considers that the entire text is available to the parser at once, and works by applying several distinct heuristic operations in sequence: first tags are inferred from delimiting tokens; then different types of tags (open, close, empty or atom) are recognized; then open/close pairs are matched, etc. Whether this technique is very novel or interesting, or how it relates to (or evades, or complicates) classic problems in text processing, I am not highly qualified to say. Yet it might be interesting for the sole reason that it serves as a proof of concept for generalized plain text processing in XSLT.

What I as a markup user find most remarkable, however, is what happens once a tool chain like this is in place. XML practitioners, I think, or at least those of us who work with structurally complex texts, are familiar with a conflict between the wish to describe our information accurately, capably and gracefully, and the need to force everything into a single hierarchy of elements – for reasons having nothing to do with the purposes of the markup, but only because the processing infrastructure insists on it, behind the scenes, before work has even begun. This conflict is apparent every time we work with (or must develop) a schema that has to make design compromises in order to address a requirement to represent things that overlap, introducing one or more of the well-worn but cumbersome workarounds for doing so. Sometimes we are faced with truly vexing problems in tagging, and even in the best case, having to use workarounds generates a certain amount of mental background noise. When working with LMNL markup, all this clamor is silenced. Even in small demonstrations, I am finding it liberating to be able to mark exactly what I wish to describe, with concern only for its clearest denotation in tags and its fidelity to what I want to represent in the text. If this is possible at all (and it evidently is), XML's early commitment to a single tree representation of something as complex as a text (meaning that word in the sense that literary scholars do, with everything it entails) appears to be a premature optimization – in other words, not always an optimization at all. When tags in plain text can be used to represent whatever structures in and features of text we care to discover, irrespective of whether they fit easily into a single tree-shaped model, then the potentials of markup are magnified immensely. We have only just started to explore the possibilities.