Mike Mertsock

• December 2003
• Programming Language Theory

Introduction

Everyone is talking about how XML — the Extensible Markup Language — will enhance their applications. XML has proven to be successful as a data communication tool to integrate and enhance information systems. There are hundreds of high-quality applications already on the market for this five-year old language, making it easy to write XML and to create applications that manipulate it. How many people, though, think of actually creating their applications using XML?

XML has the potential to become a significant force in the development of programming languages. First, it already has a foothold in many related technology areas. Second, its look and feel are significantly different than almost any programming language in existence. Third, if XML programming languages that do follow the spirit of XML become widespread, a whole new way of thinking about language creation and use may emerge.

It is easy to demonstrate that XML-based general programming languages of any type are possible. The more interesting questions are (1) do XML programming languages share any common attributes that set them apart from other languages, and (2) what are the advantages, disadvantages, and possibilities of developing XML programming languages of various classes. These questions will be answered by an in-depth analysis of the syntax, semantics, translation, and implementation possibilities of XML-based languages. Examples in each of the four general programming paradigms — imperative, applicative, declarative, and object-oriented — will help demonstrate the feasibility and applications specific to various types of XML programming languages.

Origins of XML

Though a relatively new technology, there is a long history leading up to XML. As we entered the information age, electronic document formats emerged. Early languages, such as troff and TEX, did nothing but describe the printed representation of a document [RAY 9]. These languages were successful, but documents in these languages could not easily be electronically searched or transformed — the semantics of the data were lost in presentation-specific code. Next came SGML (Standard Generalized Markup Language), an expansive standard that defined common markup syntax and methods for handling any data markup needs. HTML, a subset of SGML, facilitated the explosive growth of the World Wide Web with its simple syntax, though it was much less flexible and again incorporated more presentation-specific code. High demand emerged for a language offering the simplicity of HTML and the flexibility of SGML. To satisfy this need, the World Wide Web Consortium (W3C) published XML 1.0 in 1998 [XML].

What is XML?

Definition

XML solves the need for a generic, flexible standard to describe and communicate structured data. The W3C designed it to retain and improve upon the core aspects of its parent standard, SGML, including flexibility, readability, and markup validation. XML was designed to be a smaller standard and easier to use and program than SGML.

“Despite its name, XML is not itself a markup language: it’s a set of rules for building markup languages,” notes Erik Ray [RAY 2–4]. Markup is information added to a document, enhancing the document’s meaning. It defines positions, boundaries, and relationships among segments of information. It defines sets of information by a organizing the data into a hierarchy of adjacent and nested segments.

Documents in XML are logical, not physical structures. They are not necessarily equivalent to files — one could imagine documents stored in databases, existing as transient memory entities (such as UNIX pipes), etc. Documents are composed of elements, the primary XML markup object, and always contain a single root element. A tree of child elements descends from and is contained by this root element, both in meaning and by markup position. Elements are defined by names and attribute-value pairs, and contain text, comments, and/or child elements. Documents can have free-form elements and structure, or the structure can be strictly defined and validated by an accompanying document model. XML applications can use these models to automatically validate any user-defined document type imaginable.

Example

Figure 1 is an example of an XML document. It describes the equation x² + 4x + 4 = 0. The elements are written with markup called tags, which are the enclosing angle brackets, < and >. Notice that both the content and (via the XML markup) the meaning of the document are present, while the presentation is left to be interpreted (by translation, style sheets, interpretation, or other means). Comments are delimited by <!-- --> brackets.

<?xml version="1.0" encoding="utf-8"?><!-- required document header -->
<!-- the document type, and location of the DTD -->
<!DOCTYPE math PUBLIC "-//W3C//DTD MathML 2.0//EN"
         "http://www.w3.org/Math/DTD/mathml2/mathml2.dtd">
<!-- the root element, with an attribute called xmlns -->
<math xmlns="http://www.w3.org/TR/REC-MathML/">
<mrow><!-- these are all elements -->
<msup>
	
<!-- elements are represented by <start> and </end> tags -->
<mi>x</mi>
<mn>2</mn><!-- elements and text can nest -->
	
</msup>
<mo>+</mo>
<mrow>
<mn>4</mn>
<mo>&InvisibleTimes;</mo>
	
<mi>x</mi>
</mrow>
<mo>+</mo>
<mn>4</mn>
	
</mrow>
<mo>=</mo>
<mn>0</mn>
</math>

Applications of XML

The popularity of XML is growing rapidly, with a wide variety of applications finding it useful. A short list of successful applications includes:

• Electronic Data Interchange (EDI) — a communications medium for middleware solutions
• Custom languages for everything from chemistry symbols to virtual reality models
• XML databases, supported by the XML Query language
• A publishing medium for data retrieved from traditional databases
• Serialization and de-serialization of application data for Java and other object-oriented languages
• XHTML (XML-compatible HTML) web pages
• Web services and streaming data
• Metalanguages for application programming frameworks
• XSLT, a standard language for transforming XML documents to other document types

Charles Goldfarb, the creator of SGML, notes that the applications of XML fall between two extremes: “presentation-oriented publishing” and “message-oriented middleware” [GOLDFARB 60–62]. This range covers most of the examples listed above. But to what extent can XML be useful for general programming languages?

XML and Programming

Feasibility of XML Programming Languages

It is easy to prove that XML can be used as a basis for any general programming language: XML is a universal way to represent the structure and content of data. When you include programming statements within that scope, it is easy to see that any algorithm or data structure can be represented in XML. The interesting question is: when and how should XML be a part of programming?

Attributes Common to XML Programming Languages

XML can represent any class of language — applicative, imperative, declarative, object-oriented, etc. All XML-based programming languages have a set of common characteristics.

To begin, all such languages would share a common context of XML and related technologies. Programs could be edited using any existing XML editing tool, and such tools could be used as the basis for larger-scale integrated development environments, allowing programmers that already use XML to feel immediately at home. As will be shown, existing XML parsing, translation, and communication technologies can form a solid basis for cross-functional, platform-independent system interfaces and middleware for use by applications created with XML programming languages.

Syntax

An important component of XML is the Document Type Definition (DTD), the leading document model for XML. The syntax of XML itself is simple and deterministic; an Extended BNF grammar can easily define XML. DTDs then can fully describe the exact syntax rules of any well-formed XML document of the matching type, including rules for nesting and allowed attribute names and values. Document types are described with DTDs as specific and predictable patterns. Thus, the syntax of an XML programming language can simply be described by a DTD.

XML Schema is a developing technology that will soon emerge as an alternative to DTD. XML Schema documents, unlike DTDs, are themselves valid XML, which simplifies automated handling of document definitions. XML Schema is also a more powerful alternative to DTD, especially when defining data types. Ray mentions that DTD will survive along with Schema because of its firm establishment: it’s been around since SGML, and it is more compact and in some ways simpler than XML Schema [RAY 193].

Validation of XML markup is a well-defined process, and automated validation of syntax is a relatively trivial matter. It is also easy to validate the structure of a document against its DTD. There are already a large number of free, high-quality parsing and validation programs in the public domain, and such parsers would comprise the core of most XML programming language compilers and interpreters. This is a strong advantage of XML programming languages: syntax definition, parsing, and validation are all well-defined, standardized, automated tasks as a result of the W3C-standard XML and DTD specifications.

An additional syntax feature of XML is the processing instruction (PI). PIs are text wrapped in <? ?> delimiters. They are meant to signal application-specific instructions. XML parsers are required to react accordingly to PIs that they recognize, and to ignore all others. Thus, these can serve as a means of communicating pragmas or C-style pre-processor macros to the translator or interpreter.

Semantics, Translation, and Self-Defining Languages

Translation of any XML document, from web pages to databases to program code, begins with parsing and validation. As described above, many standard XML parsers exist, written in every major programming language. All of them, at minimum, accomplish two tasks: validation of well-formed XML syntax and validation of the document’s structure against its document model (if it exists). If an XML programming language comes with a thorough DTD (as it should), then any standard parser can automatically find and describe most syntax errors. This means that not only the actual compilers for a language, but any XML browser (even applications as generic as web browsers), can determine for the most part the syntax validity of your source code.

XSLT (which itself is valid XML) is a popular technology for translating XML documents. It is a full-featured (but specialized) programming language. It works by a call to a template element. This element specifies a pattern of elements/attributes to match, and the output to generate upon a match. It can apply other template elements recursively, set, calculate, and display variable values, use conditionals, and produce iteration (through repeated matches against an template pattern). XSLT can be used to translate any XML document type into any other. Thus, XSLT can serve as a means of translating XML programming language source code into another target language.

Another approach is to use an XML parser program as the basis for a translator or interpreter. XML parsers are classified into two types: event-driven parsers and those that use an in-memory tree representation. The former is the simpler version, generating events whenever a new token or delimiter is encountered within a document. To build a translator, callbacks are defined for events such as “found end tag” and “found attribute” to react to the data and markup. In Java, this is implemented with the Simple API for XML (SAX). The problem with the event-driven approach is that it executes in a single, linear pass. It is fast, simple, and efficient for reading data into memory, searching, and handling processing instructions, but it is not possible to do complex tasks such as reordering elements. [RAY 290]

The second class of parser can actually be built on top of the event-driven model. In response to events, a tree model of the document is constructed in memory. The standard tree representation is called the Document Object Model (DOM). Each element, attribute, and text segment is a an object located at a node in the tree. Though more complex, this class of parser allows all the capabilities necessary for a programming language translator. Java APIs, among others, exist for DOM parsers as well.

Just as BNF itself cannot fully describe the semantics of a language, existing document models such as DTD are not designed to model XML programming language semantics [PRATT 126–128]. However, an XML document type could possibly be created to represent an attribute grammar or some other semantics model.

An exciting prospect of XML-based programming languages is that a language can be created and implemented very quickly because of the standards and software supporting all levels of definition, parsing, and translation. Future versions of XML promise to introduce more opportunities for modularity. One could imagine modular “components” or “interfaces” for languages, for which more specific definitions and implementations are swapped in and out to suit the needs of a business.

Data Elements and Data Structures

The syntax of XML allows for easy representation of a wide range of primitive data types and structured data. For example, records can be easily defined as a root record element encapsulating the structure, and child elements defining fields. The child field elements would simply be elements for variables of other data types. DTDs would describe the rules for data structure creation and nesting, and easily allow recursive nesting. A variety of data types have built-in definitions and syntax in XML, such as character data, numbers, unique IDs, and lists.

XML defines a special data type for attributes, the ID. All ID attributes in all entities within a document must have unique values. Other attributes may then be defined as IDREFs, which are references to IDs. One is tempted to use ID and IDREF values for the actual names of identifiers. This may work well for object-oriented languages, where a single class definition tends to comprise an entire module (i.e. XML document). However, the requirement that IDs must be unique across an entire document may interfere with many language designs. Block-structured imperative languages, with complex static scope rules, are among those most incompatible with ID/IDREF attributes. For these languages, a more appropriate use of IDs may be for line labels and other such metadata. Ultimately, there is no requirement for ID/IDREF attributes to be a central component of any language design.

Control Structures

XML excels at describing hierarchical structures. This is an advantage for applicative languages, where recursion is prominent. Object-oriented languages will find nested elements useful for class definitions, and block-structured imperative languages could use an entity to mark nested subprogram and statement blocks. Other control structure details are largely dependent upon the language type, so there can be great variety in implementation among different XML languages.

An uncommon advantage of XML programming is the built-in provision of easy mechanisms for named correspondence of actual to formal parameters. Two such mechanisms are attribute-value pairs (Figure 2A) and the use of elements to represent parameter transmission (Figure 2B). In 2B, a similar notation could be used in subprogram definitions, allowing convenient specification of formal parameter attributes such as parameter roles. 2B is the method used by XSLT.

2A: <subprogram-name formal1="actual1" formal2="actual2"/>
2B: <call sub="foo">
<parameter name="formal1" value="actual1"/>
	
<parameter name="formal3" value="actual3"/>
<parameter name="formal2" value="actual2"/>
</call>

Feasibility and Examples of Four XML Programming Language Paradigms

Of course, different classes of programming languages can have very different needs and implementations. We will now use examples to discuss the feasibility and features of various types of XML programming languages. Four basic language paradigms — imperative, applicative, declarative, and object-oriented — will be considered.

To begin, it will soon become clear that almost any useful XML programming language will be based on a relatively abstract virtual machine. A practical reason is that XML was designed to be platform-independent, optimized for Internet communications, and even independent of character encoding. Another reason is that XML has a relatively wordy syntax (when compared to languages such as C and Perl) that would prove inefficient for low-level tasks such as systems programming, where there is a large amount of fine-grained steps that are more fluently represented by a terse syntax. Thus, a useful XML programming language will tend to emphasize software engineering and ease of human use, instead of highly efficient machine implementation.

Imperative Languages

Imperative (or sequential) languages are the traditional process-oriented programming languages. They are typified by a sequence of separate statements and heavy use of the traditional constructs of iteration and conditionals to implement an algorithm. An important theoretical achievement of imperative languages is the structured programming model. We will use this as the basis for discussion of imperative XML languages.

Structured programming requires a hierarchical program construction, in both the layout of the code and in the program semantics: the layout should match the logic. Also, a given segment of code should have one entry point and one exit point. The natural structure of XML can serve both of these purposes. Nested elements, a core aspect of XML, correspond directly to block program structure. A particular program segment (XML element) is contained by one larger segment (the parent element) and can contain many other segments (child elements). A particular element, along with all its child text and elements, encapsulates a bit of functionality and it is natural to treat that element as having one entry point, the start tag, and one exit point, the end tag.

The deepest elements of a structured program are the simple atomic statements that came to be known as prime programs. Prime programs are described as consisting only of simple combinations of function, decision, and join nodes [PRATT 323]. Such nodes comprise the primitive statements of imperative languages, such as if/then/else and while statements, as well as simple sequences of assignment and other statements. These also determine the basic sequence control elements of an imperative XML language. Another important point is that function nodes may be composed of a subprogram of any complexity. In XML, nesting of elements can represent this to any complexity and depth. Function calls are represented by a reference to the root of some tree of elements, as opposed to copying those elements to the call point.

ColdFusion Markup Language (CFML) serves as a good example of what such an XML-based language may look like. Though it is tag-based and certainly looks like XML, it technically does not qualify as such. However, it could easily be modified to be an XML language with little effect upon its implementation. CFML is an imperative language created by Ben Forta primarily for use in generating dynamic HTML web pages, and excels at working with databases for such purposes. Macromedia’s ColdFusion MX Server is the leading implementation of the language, providing a fully featured enterprise-level application server that interprets CFML pages and provides a robust runtime environment for programming with CFML.

Most CFML statements and data structures are represented as elements and are meant to blend seamlessly with HTML tags (which by default are sent directly to output). The unique feature of this language is the way its tags work. The cfloop element represents some features of the language:

<!-- loop from 1 to the value of maxIterations, inclusive -->
<cfloop from="1" to="#maxIterations#" index="count">
<!-- the # symbols dereference variable count –>
<cfoutput>Line #count#<br/></cfoutput>
</cfloop>
	
//Equivalent C code:
for ( int count = 1; count <= maxIterations; count++ ) {
printf( "Line %d<br/>", count );
}

Thus, block structures are represented nicely by enclosure between the start and end tags of a single element. Another CFML element is cfquery. This element executes a database query by passing to the database server the query code found between the start and end tags. The element returns a special data structure called a record set containing the records returned from the database. The implementation of such an element is interesting. Nothing happens except for attribute validation upon parsing the start tag. When processing the query code text enclosed by the cfquery start tag and end tag, that text it is simply passed into a buffer. The actual execution of the query does not happen until the end tag is encountered. This model, followed by many other CFML elements, allows child elements to affect the behavior of the parent element. For example, child cfqueryparam elements specify dynamic criteria for the parent cfquery by affecting the code stored in its buffer.

Applicative Languages

Languages that fully embrace the applicative (or functional) paradigm are more suitably represented in XML. Such languages apply layers of functions (often involving recursion) that transform the data to achieve the necessary result. Thus, nesting and recursion are more natural phenomena than in imperative languages.

A traditional applicative language is Lisp. A unique attribute of this language is its Cambridge Polish notation; all operations are written as (operator operand1 operand2 ... operandN). Such lists can be nested to any complexity. The other unique attribute of Lisp (and of many other applicative languages) is that does not differentiate between data and functions. To Lisp, a function is simply a list of statements. This works well for the very dynamic, interpreted runtime implementation of this language.

One XML programming language that has applicative features is XSLT — the Extensible Stylesheet Language Transformations. It can also be thought of as a declarative language, as we will see later. The goal of this language is to facilitate transformations of XML documents into other XML documents [XSLT]. Usually, the source and object documents are of different document types. Thus, XSLT is a means of translation among heterogeneous document types.

In XSLT, function definitions appear as a series of element trees. These trees, with root elements named xsl:template, apply a set of transformations to a fragment of the source document, returning a piece of the new XML document. Templates can be called recursively to achieve complex transformation, and the transformed document can be completely different from the source. Arbitrary literal elements can be added to the result tree at any location, as in CFML. XSLT is also a full-fledged programming language. The usual conditional statements and arithmetic expressions exist, and variables can be set and retrieved. You can also search for elements and display the value of their attributes.

The most important aspect of XSLT is its ability to nest template calls. The xsl:apply-templates and xsl:call-template elements accomplish this. They allow an element from the source document to be transformed in one way, and then for another template to be called to perform different actions upon child elements. Processing of a document normally begins at its root node, and traversal after that point is determined by the behavior of the templates. XSLT has a referencing environment, the most important part of which is a pointer to the context node within the source document tree [RAY 207]. This points to the element that the template is currently transforming, and automatically changes when encountering a limited set of elements, such as xsl:apply-templates and xsl:for-each. This referencing environment provides a context for the scope of operations on the data contained in the source document’s elements and attributes.

A problem with XSLT is that there is no way to verify whether some arbitrary XSLT document will transform a valid document of type X into a valid document of type Y. Of course, it is easy enough to validate the new document after it has been translated, but there is no way to determine whether the set of all input documents of type X can correctly transform into documents of type Y when using a given XSLT stylesheet.

Declarative Languages

XSLT is also described as a declarative language, and it will serve equally well for discussion of this paradigm. Declarative programs typically declare a set of rules that match particular logical or physical patterns in the input data and define an action to take when such conditions are met. Prolog, based on predicate logic principles, is the best-known declarative language.

xsl:template elements are the primary declarative feature of XSLT. These elements normally specify a match attribute, which defines a specific filter by which the template is applied. These filters trace a particular path segment through the document tree. For example, / matches the document root. book matches all elements named book, relative from the context node. For a more complex example, child::category[@type=’humor’] matches all child elements of the context node named category that have a type attribute with the value “humor”. These patterns, part of the XPath W3C standard, specify when to apply a particular template.

Translation of a document takes place by a preorder tree traversal. After building the source document tree, the XSLT runtime sets the root element as the context node and searches for a template whose match pattern best matches that context node. If no match is found, it applies the built-in default template [RAY 215–216]. The default template simply returns the selected start tag, runs xsl:apply-templates for each child node, and then returns the matching end tag. The power of using xsl:apply-templates is the ability to explicitly specify when (if ever) to continue traversing down the tree from the context node. It allows reordering of content by placing the call early or late within a template. This element can also specify a pattern to match, allowing subsets of the context node’s children to be transformed in different locations and in different ways.

The generality of XSLT allows for plenty of possible uses. For example, this paper is written in XML and viewed in your web browser as a series of formatted paragraphs, via an XSLT translation into an XHTML document. For programming, an intriguing usage is as a high-level compiler. Once an appropriate XSLT document is complete, one would simply run the translation and validate the resulting XML document against the appropriate DTD. XSLT has the restriction, however, that the only allowable translations are those into other XML languages. One possibility where this would be very useful is when a specialized, extended version of a more general XML programming language is created. XSLT would provide an easy means of translating code in the specific language upwards into the parent language by expanding specialized elements into their generalized equivalent. Another use is translating code among versions of a language and cross-functionally among similar sister languages.

However, XSLT is actually aimed toward translation for publishing and presentation purposes, by using other features of its parent language, XSL (Extensible Stylesheet Language). However, XSLT still functions capably as a general-purpose translation tool. There will undoubtedly emerge other translation languages more directly suited for program translation. More appropriately presentation-oriented uses of XSLT with programming languages include reverse engineering into pseudocode and automatic HTML documentation generation.

There are already a considerable variety of other declarative XML languages. For example, some programming frameworks (such as Fusebox 4 and Mach-II for ColdFusion, and Struts for Java) use an XML metalanguage to describe top-level application logic. These metalanguages are often full-fledged programming languages with at least the minimum set of prime program elements.

Another feature of Fusebox is its effective usage of the Fusedoc XML documentation language, used to document code modules in the style of design contracts [HELMS 152–154]. Many developers have created automated tools to verify the correctness of entire Fusebox applications by comparing Fusedocs among modules. XML programming languages could easily take this a step further by integrating similar design contracts (along with other metadata) into the language itself, as the new D programming language [BRIGHT] does.

Object-Oriented Languages

One common implementation of object-oriented programming languages is the event-driven model. This is a reactive execution model, in which some hidden mechanism captures input actions, determines a list of objects and/or methods that are registered to handle the input, and then invokes all members of that list.

XML is a useful way to implement this kind of model. XML syntax and structure are friendly to, and similar to, the usual syntax for class definitions. It is convenient for an XML document to represent a class definition, similar to Java. The high level of abstraction found in event-driven programming hides a lot of the detailed housekeeping tasks, allowing the logical essence of the program to dominate the code. XML is well suited for describing the higher-level logical flow and structure of a program in that way.

An example of event-driven programming is the Bean Markup Language (BML). The goal of this XML language is to provide a generic means to define the user interface and specify the event bindings that handle actions performed on the interface objects [GOLDFARB 693–694]. A BML document consists of a hierarchy of bean element sets, each of which instantiates a user interface element, an object class implementing that element, optional child beans, and properties and event bindings for the appearance and behavior particulars of each bean interface object. Programmers with HTML experience may find the tag-based syntax of BML to be a more natural way to specify a user interface, compared to the deluge of declarations that often result from defining interfaces using a language such as Java or Visual Basic .NET.

One place that XML has already proven effective is as a means of communication among object-oriented programs. XML serves as a natural format in which to serialize entire object instantiations, to pass the data through a communications medium, and then to de-serialize the object into another (potentially differently-implemented) system. This method of communication is generally platform- and language-independent.

Advantages and Disadvantages of XML Programming Languages

XML programming languages are clearly in their own class, when compared to the history and approach of traditional programming languages. They share a number of advantages and disadvantages when compared to other languages.

Advantages

• Easy creation of modular, domain-specific languages [MARTIN]
• Easy translation, parsing, and validation of new languages
• Standard, easy to read and easy to parse syntax
• Modularity and reuse of language definitions: opportunities for this will increase with future versions of XML
• Nested-element syntax is natural for complex data structures and applicative programming
• Large and complex constructs, such as select statements, can be more readably and efficiently represented by XML syntax, compared to traditional languages
• Well-established industry support of XML and related technologies
• Existing, widely-followed standards for XML itself, as well as for many essential satellite technologies, including parsers and translators
• High-quality existing XML development environments that are easily customizable for XML programming

Disadvantages

• Larger source file size
• Many may consider XML too wordy when compared to (terse) imperative languages
• Strict syntax (which, of course, can also be an advantage)
• Lack of support for familiar syntax, such as infix arithmetic operators and the < (less than) symbol
• Correctness of XSLT translators cannot be verified

Conclusion

As a well-designed technology built for the needs of an Internet-based information age, XML is successfully taking on new applications every day. Its use in the fringes of programming, such as for communication among programs, is already well established. As customization becomes the new “killer app” and the modularity and translation capabilities of XML mature, we may begin to see domain-specific languages developing in any imaginable field. There may never be a successful XML programming language with the do-all capacity and scope of languages such as C++, but XML languages are poised to make significant inroads into any possible programming niche over the next five years. The good news is that when the designers of these new languages follow the standards, the result will be a slew of effective new languages that, while optimized for specific uses, will be self-describing, easy to write and translate, and easy to maintain.