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

14. august 1998 (v 0.41)
jamesanderson, benno biewer


[background on xml] [alternative "representations" in lisp]
[xml-support level] [implmentation approach] [further work]
[examples]

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 an 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


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

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".

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

in practical terms, these collected documents describe

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

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

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

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

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

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

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. each DTD is associated with a package which has the same name as the DTD. where a DTD has been included by virtue of a namespace reference, the respective package is renamed according to the "AS" attribute.
!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.

the processor performs limited case-folding. element and attribute names and values are left unmodified with the exceptions: ID, IDREF, IDREFS, NMTOKEN, NMTOKENS.

 [Top]

programm structure

the implementation (version 0.40 and successive) takes the form of an parse-event driven continuation-based processor. the processor is comprises a set of state elements. the processed forms are selected from those specified in the xml standard and implemented as processor-state operators.

in contrast to the paradigm implicit in the lisp-standard read-eval-print loop, the "evaluation" step is separated into two phases - instantiation and augmentation. since one can expect xml to be used for significantly large data objects than those customarily read as lisp forms, it would not be appropriate to delay the semantic processing (the "evaluation") until the syntactic processing is complete. for example, the parent-child linking and the interpretation of certain attribute values - such as XML:SPACE, are interleaved with parsing.

the following syntactic xml forms are recognized implemented in cl-xml as objects with parsing and processing 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? '>'

the parse process is identified through a finite set of state instances:

current-form

previous-form

current entity

current-element

previous-element

current document

current attribute

parse stream (namestring, position, encoding)


a form class is defined for each such syntactic form. a parse is perform by delegating the syntactic analysis to the an instance of the respective form class based on a lexical analysis. the respective parsing method collects the immediately available components based on a the stipulations given above and then passes control to the appropriate parsing continuation.

this implementation is an extension of the standard lisp reader. it augments the reader with reader macros which transform the serial xml representation into the equivalent node tree. it is a 'hand-coded' implementation of the XML standard and makes no attempt to implement the bnf-specification through the means of automatic translation.

it is implemented in terms of three constructs: (take a look at "markup-reader.lisp")

  1. reader macros:
    the xml standard specifies distinct lexical rules for different aspects of a document. for our purposes, by virtue of the presence of internal document type definitions, the circumstances hold true for xml documents and document type definitions. the lexical behaviour of the parser is defined for each aspect of a document in terms of a specific readtable. each table comprises aspect-specific character syntax and/or reader macros. the lexical analysis is then left (with the exception of occasional application of peek-char) to the reader.
  2. structural analysis through generic dispatch
    the xml standard specifies a small number of structural forms: each has a specific syntax and specific lexical constraints. in order to accommodate these differences, while providing for the foreseeable need to extend the processor, the the parser is distributed among several generic functions and their respective methods.
    the parsing process is initiated in reader macros specific to each lexical aspect. these macros collect a datum, which then serves as the discriminator for an aspect-specific parsing function. this read/discriminate process continues until the element syntax is determined, at which point the parse is performed by a specific method.

    the parsing process passes control among several functional levels. from outermost to innermost they are:
    ( read-dtd-stream | read-xml-stream ) these, the outermost functions for the respective streams, read and process pcdata until the end of the stream is reached.
    markup-dispatching-reader-macro this is function is bound,as a convenience, to the default readtable to facilitate "in-line" element values. it either reads a succeeding element, of if the successor datum is a string, parses the entire string as an xml datum
    -  read-element-stream invoked by markup-dispatching-reader-macro to read a single element
    -  read-element
    - -  read-process-pcdata this, the primary function for parsing a markup stream, employs on reader macros to recognize and dispatch on the respective distinguished characters. nb.one reason the processor is "non-conformant", is that, in the present version this function is called upon to parse a stream under circumstances in which the standard does not allow pcdata. in order to rectify this, we would have to either introduce a number of additional readtables which follow the XML-BNF more closely.
    - - -  element-reader-macro this function is bound the the tag open character, "<", in the readtables.
    - - -  read-typed-markup-element
    - - - -  read-typed-processing-instruction
    - - - -  read-typed-markup-declaration
    - - - -  read-typed-section-element
    - - - -  read-markup-tag-attributes
    - - - -  read-markup-tag-type
    - - - -  read-markup-tag-parameters
    - - - - -  read-process-pcdata
    - - - - -  read-process-cdata
    - - - - -  read

  3. construction by side-effect
    the standard cl reader constructs data structures from returned values to embody relationships identical to the lexical structure of the read expressions. an xml processor, in contrast, instantiates relations which are not necessarily denoted through lexical containment. while the lexical-structural identity may hold for element data, it does not hold for declarations and the relation implied by processing instructions is completely unspecified. for this reason we propose an xml processor which acts as a side-effecting reader rather than as a functional reader. this means that each object establishes a dynamic context as it is read and permits lexically contained objects to assert their relation to it or to any other, or appropriate object.

[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 is "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.

we elected this implementation, because it is important to our application to recover all aossible data in the event of a syntax error. we are prepared to enforce many would-be "well-formedness" constraints on a semantic level.

a stricter processor would require further work to implement the restrictions in terms of the additional reader macros , or through an alternative reader.

namespaces
the current draft for namespace support suggests an encoding method which is insuficient to guarantee unambiguous names. for this reason, the support for namespaces in this package is still in flux.

the problem is that the latest draft proposal suggests an encoding standard which does not guarantee an unambiguous correspondence between names in a DTD and those in the document entity. which renders the dtd meaningless and precludes both validation and attribute defaulting. in order to avoid this fate, the present task is to identify an encoding which captures enough information to ensure uniqueness, but is not incompatible with the encoding which the xml standard bearers prefer. it appears that it should be possible to achieve this, by retaining the namespace-pi which has been dropped in the current draft, and, now that it is no longer restricted to appear in the prolog only (as was the case in the earlier draft), to use it to encode namespace bindings at those articulation points where the prefix-to-uri correspondence must be specified.

the present implmentation requires that any identifiers be exported from the respective package in order to encode/decode properly.

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:

there are also several test / example files

release

in addition to generic elements, this release parses all forms identified by the XML 1.0 Working Draft. (i have not yet read the proposed standard) (see the XML package in "exports.lisp"). in some cases they are parsed but are not 'processed'.

the code is distributed among some two dozen files. they can be divided into four categories:

interface management and documentation
defsystem, exports, interface, xml-node, XapiJ, DOM, xml-error
primitive lexical analysis
markup-reader
document declaration elements
dtd, dtd-element, dtd-element-declaration, dtd-element-reference, dtd-attdef, dtd-entity, dtd-parser
xml elements
xml-document, xml-text, xml-attribute, xml-coment, xml-pi, xml-element, xml-parser
prospective applications
xml-pattern, pattern-function, xml-records

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.

[Top]

© MeCom 1998