Keywords: XML, programming, functional language, pipelines
Biography
Henry S. Thompson divides his time between the School of Informatics at the University of Edinburgh, where he is Reader in Artificial Intelligence and Cognitive Science, based in the Language Technology Group of the Human Communication Research Centre, and the World Wide Web Consortium (W3C), where he works in the XML Activity.
He received his Ph.D. in Linguistics from the University of California at Berkeley in 1980. His university education was divided between Linguistics and Computer Science, in which he holds an M.Sc. While still at Berkeley he was affiliated with the Natural Language Research Group at the Xerox Palo Alto Research Center, where he participated in the GUS and KRL projects. His research interests have ranged widely, including natural language parsing, speech recognition, machine translation evaluation, modelling human lexical access mechanisms, the fine structure of human-human dialogue, language resource creation and architectures for linguistic annotation. His current research is focussed on articulating and extending the architectures of XML.
He was a member of the SGML Working Group of the World Wide Web Consortium which designed XML, is the author of the XED, the first free XML instance editor and co-author of the LT XML toolkit and is currently a member of the XML Core and XML Schema Working Groups of the W3C, and has recently been elected to the W3C TAG (Technical Architecture Group). He is lead editor of the Structures part of the XML Schema W3C Recommendation, for which he co-wrote the first publicly available implementation, XSV. He has presented many papers and tutorials on SGML, DSSSL, XML, XSL and XML Schemas in both industrial and public settings over the last eight years.
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.
1. XML processing
2. An alternative, functional, perspective on XML processing
3. The f(X) approach
4. Generalizing f(X)
5. Summary of f(X) so far
6. Completing basic f(X)
7. Beyond basic f(X): Choosing and binding
8. Drawing the obvious parallel
9. Implementation strategy
10. Conclusion
Acknowledgements
Bibliography
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 [XML] 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 [Infoset]. 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) [XSD], SVG (graphical objects) [SVG] and RDF (triples) [RDF].
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 [XSD], XSLT [XSLT], XQuery [XQuery], XInclude [XIncl], XML Encryption [XEnc] and XML Signature [DSIG] 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:
<?xml version="1.0" encoding="utf-8"?> <p0:pipeline xmlns:p0="http://www.w3.org/2002/02/xml-pipeline"> <p0:processdef name="transform" definition="MT_XSLT_1.0"/> <p0:processdef name="include" definition="MT_XInclude"/> <p0:processdef name="validate" definition="MT_W3C_XML_Schema_1.0"/> <p0:process type="include"> <p0:input label="$IN"/> <p0:output label="#i2.1"/> </p0:process> <p0:process type="validate"> <p0:input label="#i2.1"/> <p0:input name="schema" label="po.xsd"/> <p0:output label="#i4.2"/> </p0:process> <p0:process type="transform"> <p0:input label="#i4.2"/> <p0:input name="stylesheet" label="po.xsl"/> <p0:output label="$OUT"/> </p0:process> </p0:pipeline> |
An alternative approach to XML processing is already in place in a somewhat fragmented and inconsistent way. Consider the following markup items which may be present in an XML document:
xsi:schemaLocation attribute on a document
elementxml-stylesheet processing instruction/the
xsl:version attribute on a (non-XSLT) document elementhttp://www.w3.org/2001/04/xmlenc# namespaceEach of these has a W3C Recommendation-based processing semantics -- a document with one of these markup items can be understood as saying, respectively:
More recently, GRDDL [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
"To understand me, use this stylesheet."
All of these markup items, in other words, provide information about ways that documents containing them might be processed. From a processing perspective, they can be understood as saying "Validate/transform/decrypt/understand me this way."
These mechanisms are neither systematic nor universal. The goal of Functional XML (hereafter f(X)) is to allow XML documents to provide processing information in a systematic and fully general way.
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 standards-based processing required. A mapping is understood to designate the output of the specified process. 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:
<?xml version='1.0'?>
<fx:decrypt xmlns:fx="http://www.w3.org/2005/05/fx">
<EncryptedData xmlns='http://www.w3.org/2001/04/xmlenc#'
MimeType='text/xml'>
<CipherData>
<CipherValue>A23B45C56 . . .</CipherValue>
</CipherData>
</EncryptedData>
</fx:decrypt>
|
Designates the infoset resulting from decrypting the ciphertext and parsing the resulting stream as XML.
Example 1: Simple f(X) example: decryption
<?xml version='1.0'?> <fx:validate xmlns:fx="http://www.w3.org/2005/05/fx"> <purchaseOrder xmlns="http://www.example.com/PurchaseOrder" xmlns:ad="http://www.example.com/Address" orderDate="1999-10-20" xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance" xsi:schemaLocation="http://www.example.com/PurchaseOrder po.xsd"> <shipTo> <ad:name>Alice Smith</ad:name> <ad:street>123 Maple Street</ad:street> <ad:city>Mill Valley</ad:city> <ad:state>CA</ad:state> <ad:zip>90952</ad:zip> </shipTo> <billTo> <ad:name>Bill Gates</ad:name> <ad:street>123 Rich Guy Street</ad:street> <ad:city>Redmond</ad:city> <ad:state>WA</ad:state> <ad:zip>99999</ad:zip> </billTo> <comment>Hurry, my lawn is going wild!</comment> <items> <item partNum="872-AA"> <productName>Lawnmower</productName> <quantity>1</quantity> <price>148.95</price> <comment>Confirm this is electric</comment> </item> <item partNum="926-AA"> <productName>Baby Monitor</productName> <quantity>1</quantity> <price>39.98</price> <shipDate>1999-05-21</shipDate> </item> </items> </purchaseOrder> </fx:validate> |
Designates the post-schema-validation infoset resulting from schema validity assessment of the basic infoset corresponding to the
purchaseOrderelement.
Example 2: Simple f(X) example: validation
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:
<?xml version='1.0'?>
<fx:validate xmlns:fx="http://www.w3.org/2005/05/fx">
<fx:decrypt>
<EncryptedData xmlns='http://www.w3.org/2001/04/xmlenc#'
MimeType='text/xml'>
<CipherData>
<CipherValue>A23B45C56 . . .</CipherValue>
</CipherData>
</EncryptedData>
</fx:decrypt>
</fx:validate>
|
PSVI of decrypted document
Example 3: Simple composition with f(X)
But with respect to validation and decryption, the other order makes sense too:
<?xml version='1.0'?>
<fx:decrypt xmlns:fx="http://www.w3.org/2005/05/fx">
<fx:validate>
<EncryptedData xmlns='http://www.w3.org/2001/04/xmlenc#'
MimeType='text/xml'>
<CipherData>
<CipherValue>A23B45C56 . . .</CipherValue>
</CipherData>
</EncryptedData>
</fx:validate>
</fx:decrypt> |
Decryption of schema-validated document
Example 4: Another simple composition with f(X)
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.
<?xml version='1.0'?>
<fx:validate xmlns:fx="http://www.w3.org/2005/05/fx">
<fx:decrypt>
<fx:validate>
<EncryptedData xmlns='http://www.w3.org/2001/04/xmlenc#'
MimeType='text/xml'>
<CipherData>
<CipherValue>A23B45C56 . . .</CipherValue>
</CipherData>
</EncryptedData>
</fx:validate>
</fx:decrypt>
</fx:validate>
|
PSVI of decryption of schema-validated document
Example 5: Richer composition
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:
<?xml version='1.0'?>
<fx:decrypt xmlns:fx="http://www.w3.org/2005/05/fx">
<fx:include>
<xi:include xmlns:xi="http://www.w3.org/2001/XInclude"
href="encrypted.xml"/>
</fx:include>
</fx:decrypt> |
Functional equivalent of Example 1
Example 6: f(X) with XInclude
The designation of the fx:include 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:
<?xml version='1.0'?> <fx:decrypt xmlns:fx="http://www.w3.org/2005/05/fx"> <fx:include href="encrypted.xml"/> </fx:decrypt> |
Simplified version of Example 6
Example 7: f(X) with XInclude, simplified
The use of fx:includeallows us to separate
the statement of intended or desired designation from the core document, but
does not require it.
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:include elementshref,
xpointer and other XInclude attributes per the XInclude spec.,
then applying these f(X) rules to the resulting infoset;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:
<?xml version='1.0'?> <fx:sic xmlns:fx="http://www.w3.org/2005/05/fx"> <fx:include href="encrypted.xml"/> </fx:sic> |
Designates a single-element
fx:includedocument.
Example 8: 'Quoting' with fx:sic
Also, we provide a sic attribute on
fx:include, 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 fx:transform (XSLT) we allow a second child to directly provide the stylesheet:
<?xml version='1.0'?> <fx:transform xmlns:fx="http://www.w3.org/2005/05/fx"> <fx:include href="po.xml"/> <fx:include href="po.xsl"/> </fx:transform> |
Example 9: Primary and secondary input infosets
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:
<fx:transform xmlns:fx="http://www.w3.org/2005/05/fx">
stylesheet="po.xsl">
<fx:validate schemaDocuments="po.xsd address.xsd">
<fx:include href="po.xml"/>
</fx:validate>
</fx:transform> |
Style the result of validation, using static resources for schema documents and stylesheet
Example 10: Static infosets as attributes
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:
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:case> <fx:when test="boolean-valued XPath expression"> infoset to testresult infoset if test succeeds </fx:when> . . . <fx:otherwise> result infoset if no test succeeds </fx:otherwise> </fx:case> |
<fx:case> <fx:when test="/root/@version > 3"> <fx:include href="doc.xml"/> <fx:validate schemaDocuments="current.xsd"> <fx:include href="doc.xml"/> </fx:validate> </fx:when> <fx:otherwise> <fx:validate schemaDocuments="stale.xsd"> <fx:include href="doc.xml"/> </fx:validate> </fx:otherwise> </fx:case> |
Choosing a schema document based on an XPath expression test
Example 11: Using fx:case for conditional processing
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 or an fx:infoset element.
Once again we'll take
XSLT as our model, using xs:variable to bind names to constructed
or denoted-by-URI infosets:
<fx:with>
<fx:variable name="var name">
f(X) designating an infoset
</fx:variable>
<fx:variable name="another name
href="URI for infoset"/>
. . .
</fx:with> |
<fx:with>
<fx:variable name="doc" href="doc.xml"/>
<fx:case>
<fx:when test="$doc/root/@version > 3">
<fx:validate schemaDocuments="current.xsd">
<fx:infoset expr="$doc"/>
</fx:validate>
</fx:when>
<fx:otherwise>
<fx:validate schemaDocuments="stale.xsd">
<fx:infoset expr="$doc"/>
</fx:validate>
</fx:otherwise>
</fx:case>
</fx:with> |
Explicit binding to avoid extra work
Example 12: Binding infosets to variables
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. . .
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:
(let ((doc {doc.xml}))
(if (gt |$doc/root/@version| 3)
(fx:validate doc {current.xsd})
(fx:validate doc {stale.xsd}))) |
f(X) is really just XMLised Scheme. . .
Example 13: Compact notation
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).
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.
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. It amounts to a functional programming language whose primary data objects are complete XML documents, and as such is qualititatively distinct from such related efforts as XQuery [XQuery], XMLambda [XMLambda], Echo [Echo] or Links [Links].
XHTML preview stylesheet created by Philip Mansfield.