Common Lisp support for the
'Extensible Markup Language'
(CL-XML)

19990503 (v 0.44)
james anderson, benno biewer

we have implemented a primitive "processor" in common lisp for data streams serialized according to the "extensible markup language" standard. this document provides a cursory introduction to xml, describes the implemented parsing/processing mechanism for CLOS-based applications, and explains how to use the processor.

the processor is intended both as an extension to the cl-http server and as a stand-alone xml interface. the runtime environment is examined during the loading process to determine if the if http support is already present. if so, then the existing facilities are used and server extenions are generated to support xml.if cl-http is not present, then these extensions are not loaded and only file streams and primtive http streams are supported.

the xml processor reads a marked up data stream to produce a document object which binds definition information and element content. the respective class definitions include support for access to definition and content data and for document serialization.

additional utilities are included to

• instantiate and serialize instances of arbitrary specializations of STANDARD-CLASS from and to an xml representation.
• offer an element interface to record-oriented data (mcl 3.*, 4.*; allegro 4.3), thereby offering an uniform interface to "ascii" and "binary" data.

several demonstration files are included, among them an example of document and element serialization is included which presents documentation for several common-lisp data classes (function, generic-function, symbol, standard-class) as xml or html, depending on the browser capabilities.

[Top]

a bit of background on xml

in its role as an "introduction" to xml, this note provides an admittedly cursory treatment of two topics: what xml is and, how xml relates to lisp applications and development. please note, that - especially with respect to xml itself - our goal is just to get you started. there are already numerous documents available on-line about xml, none of which it makes sense to duplicate here. the reader is referred, in particular, to

• the W3 xml page,
• an article by Jon Bosak, which suggests various xml applications,
• the textuality xml root (Tim Bray, from textuality, is one of proposal editors),
• and the microsoft xml root (Jean Paoli, from microsoft, is another editor; IE4 includes access to xml data objects),

and to the various links included therein.

the simplest description of xml is, that it is a cross between html and sgml. html is the notation used to "markup" text for display in a "browser". sgml is also a markup notation, which in some forms, looks much like html, but, in general, permits syntax definitions, called "document types", with various markup forms. html, in its recent versions, is a particular document style in sgml. xml is a simplified subset of sgml. it permits document type definitions, but limits the syntax to one resembling html.
xml is intended to be a notation for storing, retrieving, and, in general, communicating data in a "self-describing" serialized form. the standard specifies a syntax to "mark up" text data using annotated, or attributed tags so as to denote sequence and containment relations among data. each application is free to define its own tags and relations as a document type.

xml is proposed, in particular, as a notation for data to be exchanged between http clients and servers (or, more accurately among any processes capable of operating with URL-specified data resources). the www-consortium is administering the proposal and standardization process. to quote the proposed standard

"The Extensible Markup Language (XML) is a simple dialect of SGML.... The goal is to enable generic SGML to be served, received, and processed on the Web in the way that is now possible with HTML. XML has been designed for ease of implementation and for interoperability with both SGML and HTML."

if the xml elements are chosen from the html document definition, then the documents would look much like html documents. documents are also permitted, which have no definition, so long as all elements are marked with matching open and close tags or with an empty tag, and so long as containment relations are unambiguous.

one might, for example, express the most trivial of relations from the lisp domain as the following xml document:

<cons><car>first</car><cdr>rest</cdr></cons>

the following, also trivial, html document, would also be a legitimate xml document:

<html>
 <head></head>
 <body>greetings in xml</body>
 </html>

in addition to straight-forward markup, the standard also includes special purpose syntactic constructs to represent document definitions. the syntax of these forms has been chosen to be compatible with sgml. they could, however, just as well have been encoded using the same markup forms as the rest of the document.

the present thinking about XML is embodied in a collection of w3 proposals and technical notes concerning the representation and manipulation of "document objects".

• the XML proposal itself, concerns the standard notation to serialize "document objects".
• a "document object model" (or "DOM") describes a standard class hierarchy and functional interface to retrieve data from "document objects".
• an "extensible style language (or "XSL") proposes a system-independent description language for presentation and data store interfaces
• an "extensible linking language (or "XLL") concerns the representation on effects of links between "document objects".
• an "xml-data" proposal exists, which suggests a more expressive alternative to the DTD, encoded instead strictly as element data, for encoding meta-object data
• a proposed "channel-definition format" suggests a way to describe data communications links between a browser and a server.
• java classes exist (com.ms.xml.dso) which can operate within a brower to retrieve content from xml data sources and incorporate them in html content.

XML would appear to be on its way to becoming the standard representation for serialized electronic data.

in practical terms, these collected documents describe

• a serialization standard sufficiently expressive to represent arbitrary CLOS data: the data stream proper can encode instance attributes and relations. meta-object data can be encoded either in an optional DTD (or "document type definition") or in an xml "schema". both may be included in the stream either literally or by reference.
• a linking notation and mechanism which can represent and navigate arbitrary graphs.
• a notation which can already be used with a range of sgml editing and viewing applications.
• a notation which can already be used to exchange data among programs written in numerous languages (c, c++, java, and perl among them) and operating on any os-base which supports tcp/ip
• a serialization notation which should not, however, be mistaken, despite the somewhat inaccurate name, for a "language". the standard specifies an encoding syntax only. all encoding rules are internal to the notation and limited to those for verifying whether a document conforms to a given definition.

in terms useful for the lisp developer, this means that a single serialization interface - alternative, but equivalent to the standard reader, would suffice to communicate data with any and all of

• another lisp process, which can parse xml;
• a browser, which uses xml-data sources to present the content as html
• a java process, which can parse xml;
• a sgml (or ultimately xml) editor, which could perform structurally constrained editing and return the data as an xml object;
• any xml-equiped database could be a persistent object store;

we're using it as the serialization form to communicate data among a cl-http server and java front-ends. we intend to use it as the media for communication to editors and persistent stores as they become available. it is straight-forward to implement basic support in a common lisp environment. for a small effort, it will be possible to leverage the development efforts which will follow over the next several years to carry the dynamic development and deployment features which lisp offers into wider setting.

[Top]

what about other "representations"

the lisp world is at no loss for alternatives to serialize data or otherwise represent it external to a lisp process. the lisp standard includes at least two means (reader macros and load forms) which can be used to serialize data for archival or to pass it to another process. with suitable meta-object support, the necessary definitions can be specified as an aspect of class definition.

the lisp application community has also been at no loss to develop representations for data and for data manipulation. in most cases (for example, KIF) the standard incorporates the standard lisp reader and thereby depends on equivalent runtime support among a communicating processes. such standards also extend well beyond the scope of xml, to specify protocols for application-level data-exchange and to specify mechanisms for interpreting messages.

xml, on the other hand, is strictly a convention for encoding. it plays a role analogous to the #(structure-type slot-name slot-value), and could be substituted for it in applications which share data with foreign application environments. as an encoding, xml does not concern protocol questions, which, in the case of a presentation protocol, are relegated to the application domain, and in the case of transport protocols are left to an underlying transport layer. for the latter, http is the likely dominant protocol.for the former, remember "it's not a language, it's an encoding": semantic issues are also left entirely to the application, whereby a number of "standardized" applications are being discussed. (see the various w3c submissions and reports.)

[Top]

implementation level

this collection of files implements a "nonconforming, validating, model-based XML processor". in practical terms, this means that

• it does not catch and /or report all possible syntax errors,
• it is able to verify a document against a document definition, and
• it transforms the document stream into a "DOM-like" object model.

this version of the processor can parse and process complete xml documents, including

• internal elements, and entity references,
• document type definitions, also referred to as DTD's, both internal and external to an XML document,
• external parsed entities.

it also includes a provisional pattern matcher for use, for example, as the core of an XSL matcher, and a compiler for element models which can be used to implement validation.

the most significant limitations are

• it does not observe character encodings.
• it is rather careless about storage, generating strings and interning symbols which could just be managed more efficiently
• it makes no effort to perform efficient io and is too dependant on the lisp reader

a the next version will address these issues.

the processor reads XML document to produce an internal node tree which represents the node containment relations denoted in the stream and which establishes links to the specified element definitions for reference to model and attribute declarations and to entity definitions for replacement text. if the XML document specifies a source for a DTD, the DTD document is read to produce an internal representations of the declared elements, models, atttributes, and entities.

as an optional step when creating element definitions, the respective model is compiled to produce a validation predicate. use of the predicates are left to the 'application' either by means of auxiliary (likely :before) constraint methods, for example on XML-ELEMENT.APPEND-ELEMENT or on (SETF XML-NODE.CONTENT)(t XML-ELEMENT).

DTD and XML streams are, for the most part, processed identically. a distinction is limited to two interface functions which read the named respective stream type and enforce content constraints on the results.
READ-DTD-STREAM (generic-function (stream NAME) DTD)
READ-XML-STREAM (generic-function (stream) XML-ELEMENT)
the additional argument to READ-DTD-STREAM is necessary in order to specify the root element and the namespace into which the dtd is imported.

additional interface functions are provided to read individual elements, read PCDATA, CDATA, etc. look at "interface.lisp" for descriptions.

the reading and construction process is controlled by numerous parameter bindings. there are, for example, bindings to specify the class of each node to be instantiated. see "global-bindings.lisp" for explanations. these bindings may be changed and /or the respective access functions specialized in order to either

• transform the processor from a "model-based" into an "event-based" processor, by instantiating nodes which have merely a control function but do not bind element content
• parse directly to CLOS instances rather than to generic XML-ELEMENT nodes.

this prototype includes support for the following xml forms. the distinction between parsing and processin means that the element is either merely read and instantiated, or that the relations or side effects specified by the standard are implemented.
 

element	parsed	processed	comments
<!--	yes	yes	comments are appended to the parent node. they are bound separate from element children and keyed to the immediately preceeding element.
!ELEMENT	yes	yes	element definitions are bound to the parent DTD. the names are required to be of the same package as the DTD. where element references appear in a model, supplementary (non-standard) ELEMENT-REFERENCE nodes are generated to accommodate forward references and to accept instance-specific attributes.
!ENTITY	yes	yes	internal and external character, parameter and parsed character entities are supported. the processor diverges from standard behaviour in that it does not enforce the specified context constraints entity references.
!NOTATION	yes	no
![CDATA[	yes	yes	bound as text to the parent node
![INCLUDE[	yes	yes	read as a string and reparsed. the last element in the stream is returned.
![IGNORE[	yes	yes	read as string and discarded
?XML	yes	yes	processed to bind the standalone declaration, but without support for encoding
?NAMESPACE	yes	yes	this processing instructions is not a part of the xml standard. on the other hand, it would be hard to manage complex documents without some means to define and select namespaces, so we adopted one. namespaces are implemented through packages. the standard lacks a means to specify that a package is to be known within a given dtd. we use namespace processing instructions to this end.
!DOCTYPE	yes	yes	a document type declaration specifies the root element, it can reference the an external DTD and or provide an internal definition
&entity;	yes	yes	named entity references are appended to the content of containing elements. methods to retrieve and parse the referenced entity's content are not yet implemented. if they were PCDATA only, the dtd is available through the containing elements dtd-element-reference and the string content could be reread with READ-PROCESS-PCDATA. this should wait, however, until we understand the meaning and uses of notations, since things like external entities and binary data aren't that simple.
%entity;	yes	yes	wherever they are permitted (type names, models, attributes, ... ?), parameter entities are supported by concatenating streams. the entity value is prepended to the active stream in place of the entity reference. this means that syntactic restrictions specified by the standard for entity values are not enforced.
element	yes	yes	elements are parsed and processed. the processing step appends an element to its parent node. attributes are parsed and bound to the element node. limited attribute normalization is not supported. empty elements are supported.

[Top]

programm structure

the implementation (version 0.44 and successive) takes the form of a recursive-descent parser.

the control-tree comprises successive layers of

read-production

production-reader-macro

reduce-production

each of these functions comprises methods specialized on the types specified int he xml standard. the following syntactic xml forms are recognized implemented in as objects with parsing and reduction behaviour:

[1]	document	::=	prolog element Misc*
[16]	Comment	::=	'<!--' ((Char - '-') | ('-' (Char - '-')))* '-->'
[17]	PI	::=	'<?' PITarget (S (Char* - (Char* '?>' Char*)))? '?>'
[19]	CDSect	::=	CDStart CData CDEnd
[24]	XMLDecl	::=	'<?xml' VersionInfo EncodingDecl? SDDecl? S? '?>'
[29]	doctypedecl	::=	'<!DOCTYPE' S Name (S ExternalID)? S? ('[' (markupdecl | PEReference | S)* ']' S?)? '>'
[39]	element	::=	EmptyElemTag
			| STag content ETag
[40]	STag	::=	'<' Name (S Attribute)* S? '>'
[41]	Attribute	::=	Name Eq AttValue
[42]	ETag	::=	'</' Name S? '>'
[44]	EmptyElemTag	::=	'<' Name (S Attribute)* S? '/>'
[45]	elementdecl	::=	'<!ELEMENT' S Name S contentspec S? '>'
[52]	AttlistDecl	::=	'<!ATTLIST' S Name AttDef* S? '>'
[62]	includeSect	::=	'<![' S? 'INCLUDE' S? '[' extSubset ']]>'
[63]	ignoreSect	::=	'<![' S? 'IGNORE' S? '[' ignoreSectContents* ']]>'
[66]	CharRef	::=	'&#' [0-9]+ ';'
			| '&#x' [0-9a-fA-F]+ ';'
[68]	EntityRef	::=	'&' Name ';'
[69]	PEReference	::=	'%' Name ';'
[71]	GEDecl	::=	'<!ENTITY' S Name S EntityDef S? '>'
[72]	PEDecl	::=	| '<!ENTITY' S '%' S Name S PEDef S? '>'
[78]	TextDecl	::=	'<?xml' VersionInfo? EncodingDecl S? '?>'
[83]	NotationDecl	::=	'<!NOTATION' S Name S (ExternalID |  PublicID) S? '>'

[Top]

implementation questions and further work

the present implementation is a prototype. we use it to communicate data among an http server and java clients. there are a number of questions, about how it should evolve, for which we as yet have no answers and must gain experience using it together with other parsers and document generators.

application interface

the form of interface remains a question. the c- and java-based parser/processor implementations make significant distinctions between an interface concerned with the lexical processing and one concerned with the content. contemporary (as of q1.98, that is pre-dom-implementations) deliberations regarding standard interfaces are directed to so-called "event-based" interfaces. in this form of interface a calling application is informed of the presence of lexical tokens and or the completion of syntax productions through a "call-back" interface, as if they were "events" in the data stream.

such interfaces are significant for applications which intend to filter very large amounts of data in order to operate on a small percentage of the content. in our case such an interface is of little interest. the primary interfaces are for entire document objects. if there should be a need to filter data selectively, one method would be to specialize the element and text classes as well as the functions for processsing or appending elements to implement the "call backs" but not retain the data. either

conformance

this version of the processor remains "non-conforming" in a number of respects. in particular it neither fully constrains document syntax to conform to the standard (accepting pcdata where it is not "permitted", allowing a more liberal tag syntax, ...), nor does it terminate processing should it detect an error when it is instead possible to recover from an error. the respective conditions are all bindable to either warning or error specializations to control the effects. (see "xml-error.lisp")

a stricter processor would require further work to implement the restrictions in terms of the additionalconstriant checks.

examples

the directory "dtd" includes several simple document type definitions. one for lisp "lisp.dtd" and one for XSL patterns "xsl.dtd". the directory "xml" contains small example files. one from microsoft contains a channel description. the the best sources for further examples are net resources:

• the xml-dev mailing list discusses xml development issues.
  among the example resources which have been mentioned there are
• encoded transcriptions of shakespeare and religious works.
• Don Park's collection of links to examples and standards.

there are also several test / example files

• example-dtd.lisp
  demonstrates the content od a document type definition;
• example-model-compiler.lisp
  demonstrates the use of the validity predicates;
• example-parser.lisp
  demonstrates how to read an xml stream to produce a document;
• example-server.lisp
  shows how to bind a url to generate xml-form data
• clos-server.lisp
  is an example of how to serve xml/html forms through the cl-http server. it builds on the functions from clos-dom.lisp, which generate dom descriptions for functions, classes, packages, and symbols, and translate the dom forms to html.

nb. these latter two are yet untested in this version

release

in addition to generic elements, this release parses all forms identified by the XML 1.0 recommended standard) (see the XML package in "exports.lisp").

the code is distributed among several dozen files.

there are also several files provided which are specific to run-time support within MCL.the system definition file is "defsystem.lisp". the file "defsystem-xml-records.lisp" concerns an additional modules which provides a uniform interface to xml elements and mcl records.

this prototype is no paradigm of efficiency, it is merely a draft tool for serializing data for exchange with java "front-end" processes. it is in flux and future compatibility is not assured. it should be seen as a base for discussion and possible further implementation only. please do not REdistribute it. it is available from the cl-http contributed source archive, from which, for the time being, all distribution should occur.
working with a 2.5M portion of the old testament xml-example file, for instance, the performance looks like this (mcl 4.1, ppc7300/200):

? (room)
There are at least 13,426,192 bytes of available RAM.

                  Total Size             Free                 Used
Mac Heap:      1295856 (1265K)       477552 (466K)        818304 (800K)
Lisp Heap:    15453968 (15092K)     12948640 (12645K)      2505328 (2447K)
Stacks:         240368 (235K)        236804 (231K)          3564 (3K)
Static:           5584 (5K)               0 (0K)            5584 (5K)
? (time (let ((*xml-text-class* nil)) ; intern text simply as strings
          (defparameter *ot*
            (read-xml-stream #P"entwicklung-server:Source:LISP:XML:otxml Folder:ot-abridged.xml"))))
(LET ((*XML-TEXT-CLASS* NIL)) (DEFPARAMETER *OT* (READ-XML-STREAM #P"entwicklung-server:Source:LISP:XML:otxml Folder:ot-abridged.xml"))) took 125,784 milliseconds (125.784 seconds) to run.
Of that, 19,010 milliseconds (19.010 seconds) were spent in The Cooperative Multitasking Experience.
 11,065,544 bytes of memory allocated.
*OT*
? (gc)
NIL
? (room)
There are at least 5,853,552 bytes of available RAM.

                  Total Size             Free                 Used
Mac Heap:      1295840 (1265K)       477552 (466K)        818288 (800K)
Lisp Heap:    15453984 (15092K)      5376000 (5250K)     10077984 (9842K)
Stacks:         240368 (235K)        236804 (231K)          3564 (3K)
Static:           5584 (5K)               0 (0K)            5584 (5K)
? 

which is several factors slower than the equivalent c++ parser

references

several of the references are gathered here in order since, in many cases, a reference includes an alternative link to the respective original document in addition to the documents included with the distribution.

• [the dom proposal]: the proposed interface specification is available from the w3 consortium or, as the 09.10.97 version, with the cl-http release.
• see please "a theory of semiotics", eco, indiana university press, 1979. in particular p. 38, the discussion of s-codes. the xml standard distances itself from all issues of interpretation and restricts itself to to specify a notation for encoding, rather than an encoding.
• [the "parser" / "processor" dualism]: the xml literature is marked by a "parser" v/s "processor" dichotomy. it arises from a distinction between a mechanism which recognizes and manipulates the lexical entities denoted by document and a mechanism which operates on data in the domain of "parsed entities". for example, while the sequence
  <e1 a1="1"><e2/> and text</e1>
  concerns a "parser" as a sequence of tokens only:
  element start: "e1"
  attribute-name: "a1"
  attribute-value: "1"
  element start: "e2"
  element end: "e2"
  parsed character data: " and text"
  element end: "e1
  a "processor" operates in a domain where the relation between an element e1 and possible content of e2, " and text" may be constrained by a declaration stipulates content types and/or attribute values.
  see also the note on implementation questions.
• [the xll proposal]: the draft standard is available from the w3 consortium or, as the 31.07.97 version, with the cl-http release.
• [the xml proposal]: the proposed standard is available from the w3 consortium or, as the 08.12.97 version, with the cl-http release.
• [the xsl proposal]: the original technical note is available from the w3 consortium or, in the 27.08.97 version, with the cl-http release.

[Top]

© MeCom 1998