Functional XML

Henry S. Thompson, School of Informatics, University of Edinburgh
<ht@inf.ed.ac.uk>

Abstract

Existing XML processing models are pipelines, controlled by pipeline descriptions which resemble shell scripts. Functional XML allows XML documents to specify their own processing explicitly, without losing the generality of the pipeline script approach.

Table of Contents

1 Acknowledgements
2 XML processing
3 An alternative, functional, perspective on XML processing
4 The f(X) approach
5 Generalizing f(X)
6 Summary of f(X) so far
7 Completing basic f(X)
8 Beyond basic f(X): Choosing and binding
9 Drawing the obvious parallel
10 Implementation strategy
11 Conclusion


1 Acknowledgements

The work reported here was initiated by a discussion with Tim Berners-Lee, who also first used the phrase "functional XML" in my hearing. The basic direction was first suggested by Richard Tobin.

2 XML processing

XML processing is a heavily overloaded term, appealing as it does to a wide range of possible understanding of the 'meaning' of an XML document. At the base level, the XML Recommendation assigns a meaning to character streams associated with one of the XML family of media types in terms of a tree-structured document abstraction, whose detailed specification is given by the Infoset Recommendation. Applications of XML, i.e. particular XML vocabularies with an associated semantics, may in turn specify a further layer of meaning in terms of a mapping to/from some abstract data model. Examples of this include W3C XML Schema (schema components), SVG (graphical objects) and RDF (triples).

Many W3C XML-related specifications can be understood as having a functional semantics, that is, as specifying a mapping from XML (infoset) to XML (infoset). XML Schema, XSLT, XQuery, XInclude, XML Encryption and XML Signature are all in this category. Individual WSDL operations can also be understood in this way. There has recently been a significant growth in the range of tools available for controlling sequences of infoset-to-infoset mappings. These tools are usually described as specifying XML pipelines, and include at least the following:

These existing pipeline languages have a common core, in which XML processing is defined by a pipeline, which is itself an XML document. A pipeline specifies a sequence of high-level operations, drawn from an inventory such as the list above, to be chained together, one after another, each operating on the output of the one before. Some pipeline systems also provide operations at a lower level, allowing manipulation of parts of documents. Another common feature is provision for conditional processing. Here's an example of a simple pipeline specifying a sequence of inclusion, validation and styling:

3 An alternative, functional, perspective on XML processing

An alternative approach to XML processing is already in place in a somewhat fragmented and inconsistent way. Consider the following signals which may be present in an XML document:

Each of these has a W3C Recommendation-based processing semantics -- a document with one of these signals can be understood as saying, respectively:

More recently, GRDDL provides a way for a document to indicate, using a data-view:interpreter attribute, a transformation which will produce RDF statements. The presence of this attribute thus can be understood as saying "Understand me."

These signals are neither systematic nor universal. The goal of Functional XML (hereafter f(X)) is to allow XML documents to indicate their own preferred processing in a systematic and fully general way.

4 The f(X) approach

As noted above, the first-level semantics of an XML document serialisation is its own XML infoset. f(X) allows for the creation of XML documents which signal a second-level semantics for themselves in terms of one or more infoset-to-infoset mappings. It does this by specifying a compositional infoset-mapping interpretation for elements in the f(X) namespace, covering all the specifications mentioned above.

The names for the mappings covered by f(X) are chosen to describe the output of that mapping, since that is what such elements are understood to designate. In the simplest cases, their input is the infoset designated in turn by their single child element. Taking schema validation and decryption as our starting point, we get the following examples:

The simplicity and power of this approach, and the way in which it most clearly moves beyond the existing ad hoc signalling mechanisms mentioned above, become apparent once we actually compose multiple f(X) elements in a single document:

But with respect to validation and decryption, the other order makes sense too:

Indeed, validation before and after decryption is probably often what is wanted. That is, first we check that the encrypted data is valid per the XML Encryption namespace schema, then we decrypt, then we validate the result to check that it's OK.

5 Generalizing f(X)

The outline of a simple functional language is emerging, but one of limited generality as far as the examples given above. Actually wrapping existing XML documents with f(X) elements to indicate preferred processing won't always work. The starting point may not be local, or may be read-only, or several alternative designations may be appropriate for alternative purposes. But the means to cover these cases is already there in principle, because we've already said we need an f(X) element for XInclude. Consider the following:

The designation of the fx:included element is the result of doing XInclude processing on the designation of its child element. Since the simple pattern above is likely to be very common, it can be abbreviated as follows:

The use of fx:included allows us to separate the statement of intended or desired designation from the core document, but does not require it.

6 Summary of f(X) so far

f(X) provides a means for specifying the desired designation of XML documents in a systematic and compositional way. It does so by specifying the designation of three basic classes of XML elements

fx:included elements

Designate the result of first interpreting the href, xpointer and other XInclude attributes per the XInclude spec., then applying these f(X) rules to the resulting infoset;

other elements in the f(X) namespace

Designate the result of the mapping specified by their name applied to the designations of their children;

all other elements

Designate themselves, that is, their ordinary infosets, except in-so-far as they contain elements in the f(X) namespace, which are interpreted per the above two clauses.

7 Completing basic f(X)

A few things need to be added to cover the intended basic functionality.

It should be possible to prevent the special treatment f(X) specifies for the first two classes of elements above -- f(X) provides the fx:sic element for this purpose:

Also, we provide a sic attribute on fx:included, which defaults to false, but which if true blocks recursive f(X) processing of the inclusion target.

Finally, we need a way of specifying more than one input infoset and, for those specifications which require (or allow) it, parameters. f(X) allows for parameters via attributes on the relevant f(X) elements, and allows additional children where appropriate to designate additional input infosets. For example, for the fx:result (XSLT) we allow a second child to directly provide the stylesheet:

Since infosets such as stylesheets and schema documents are so often static, it also makes sense to allow them to appear as attributes on the relevant f(X) element:

Finally we need to list at least a preliminary set of built-in f(X) designators for each public specification which can be understood as defining XML-to-XML functions:

fx:valid

Validated W3C XML

fx:PSVI

W3C XML Schema

fx:result

W3C XSLT (v.1 or v.2, depending on stylesheet)

fx:queryResult

W3C XML Query

fx:encrypted

W3C XML Encryption

fx:decrypted

W3C XML Encryption

fx:signed

W3C XML Signature

fx:verified

W3C XML Signature

fx:transcluded

W3C XML Include

fx:gMeta

GRDDL

Editorial note: HST 
The complete paper will fill in detail in each case as to calling sequence, results, etc.

8 Beyond basic f(X): Choosing and binding

As mentioned above, some existing pipeline languages allow for conditional processing. If it is judged appropriate to include something like this in f(X), it can be done easily, following the model of XSLT's choose:

fx:when has a test attribute for an XPath expression and two infoset arguments. The first is the infoset to test with the XPath expression, the second the result if the test is satisfied.

Clearly if interpreted literally we have a lot of potential for wasted effort here with respect to the doc.xml resource. There are two possibile ways f(X) could address this. It could do nothing beyond noting that implementors may detect and optimize such cases, or it could provide for explicit binding of infosets to variables, which can then be referenced by XPath expressions and an fx:infoset element:

The provision of an explicit binding mechanism would clearly be of use, particularly since in cases where testing needs to be done on the result of some more or less complex composition of f(X) elements it would enable the concise specification of dependencies which would otherwise require egregious duplication of structure. However there's a real question as to whether this opens up too many uncertainties. In particular the introduction of variable binding into pure functional programming languages is known to have a significant impact on overall computational complexity. . .

9 Drawing the obvious parallel

At this point f(X) is beginning to look a lot like a transcription of a traditional functional programming language such as Scheme into XML. The previous example Example 12, for instance, is just a transcription of something like this expression, which is meant to be Scheme plus a bit of syntactic sugar for XPath expressions and URIs:

Given the history of negative reactions from the Web community to Scheme, it's not clear that promoting this compact syntax would be a good idea, but it is clearly both a fruitful source of insight and a good starting point for any formal characterisation of the semantics of f(X).

Editorial note: HST 
The complete paper will fill in discussion of the benefits, both practical and theoretical, of exploring this parallel.

10 Implementation strategy

Implementations are already available for a number of pipeline languages. It is straightforward to translate basic f(X) into many of these, particularly as long as all the f(X) elements in the document have at most a single child. Multiple children, as will as fx:case and fx:with, will require a bit more work, and may not be straightforwardly possible in all existing languages.

11 Conclusion

f(X) provides a novel approach to XML processing, an alternative way of conceptualizing in terms of function composition what is currently largely understood in terms of pipelines.