Hi Folks,
Recall that with XML Schema you can create a complexType that restricts another complexType. That “derive-by-restriction” capability is useful when you have two levels of syntax, one level restricting the other.
Lisp provides a neat example of multiple levels of syntactic rules. The Lisp language specification has a syntactic rule which says that lists can contain anything. The specification then layers on top a second syntactic rule which requires that lists specifically start with a symbol.
Here is a list that is valid according to the first level of syntax:
(“Hello, world” 10)
but it is invalid per the second level of syntax (i.e., the list does not start with a symbol – a string is not a symbol).
Terminology: A list that conforms to the first level of syntax is called a symbolic-expression (s-expression). A list that conforms to the second level of syntax is called a Lisp form.
A Lisp form is a restricted s-expression:
I converted these concepts over to XML and XML Schema. The result is a beautiful example of restriction. Here is the complexType for the first level of syntax (s-expression):
<xs:complexType name="s-expression">
<xs:choice>
<xs:element name="atom" type="atom" />
<xs:element name="empty-list" type="empty-list" />
<xs:element name="non-empty-list" type="non-empty-list" />
</xs:choice>
</xs:complexType>
The following is the complexType for the second level of syntax (Lisp form). Notice that it restricts the s-expression.
<xs:complexType name="Lisp-form">
<xs:complexContent>
<xs:restriction base="s-expression">
<xs:choice>
<xs:element name="atom" type="atom" />
<xs:element name="empty-list" type="empty-list" />
<xs:element name="non-empty-list"
type="non-empty-list-that-starts-with-a-symbol" />
</xs:choice>
</xs:restriction>
</xs:complexContent>
</xs:complexType>
By the way, I believe that the XML language specification defines only one level of syntax. Do you agree?
For those that are interested in more details, I have included below the precise definitions of s-expression and Lisp form, and the XML Schemas plus sample XML instances.
/Roger
In the first level of syntax, symbolic-expressions (s-expressions) are defined:
Note: the definitions come from the excellent book: Practical Common Lisp by Peter Seibel.
This list is an s-expression: (“Hello, world” 10 foo)
In the second level of syntax, Lisp forms are defined:
A Lisp form is a restricted s-expression. Specifically, lists must begin with a symbol. The above example is a valid s-expression but an invalid Lisp form. Here is a valid Lisp form: (foo 10)
Here is an XML Schema for s-expressions:
<xs:schema xmlns:xs="http://www.w3.org/2001/XMLSchema">
<xs:element name="s-expression" type="s-expression" />
<xs:complexType name="s-expression">
<xs:choice>
<xs:element name="atom" type="atom" />
<xs:element name="empty-list" type="empty-list" />
<xs:element name="non-empty-list" type="non-empty-list" />
</xs:choice>
</xs:complexType>
<xs:complexType name="empty-list">
<xs:choice>
<xs:sequence>
<xs:element name="left-parenthesis" type="empty" />
<xs:element name="right-parenthesis" type="empty" />
</xs:sequence>
</xs:choice>
</xs:complexType>
<xs:complexType name="non-empty-list">
<xs:sequence>
<xs:element name="left-parenthesis" type="empty" />
<xs:element name="first" type="element"/>
<xs:element name="rest" type="rest" minOccurs="0" />
<xs:element name="right-parenthesis" type="empty" />
</xs:sequence>
</xs:complexType>
<xs:complexType name="rest">
<xs:sequence>
<xs:element name="first" type="element"/>
<xs:element name="rest" minOccurs="0" type="rest"/>
</xs:sequence>
</xs:complexType>
<xs:complexType name="element">
<xs:sequence>
<xs:element name="element" type="s-expression" />
</xs:sequence>
</xs:complexType>
<xs:complexType name="atom">
<xs:choice>
<xs:element name="number" type="xs:double" />
<xs:element name="string">
<xs:simpleType>
<xs:restriction base="xs:string">
<!-- Incomplete -->
<xs:pattern value='"[a-zA-Z][a-zA-Z0-9\-, ]*"' />
</xs:restriction>
</xs:simpleType>
</xs:element>
<xs:element name="symbol" type="symbol" />
</xs:choice>
</xs:complexType>
<xs:simpleType name="symbol">
<xs:restriction base="xs:string">
<!-- Incomplete -->
<xs:pattern value='[a-zA-Z][a-zA-Z0-9\-]*' />
</xs:restriction>
</xs:simpleType>
<xs:complexType name="empty" />
</xs:schema>
Here is a sample s-expression, expressed in XML:
<s-expression>
<non-empty-list>
<left-parenthesis/>
<first>
<element>
<atom>
<string>"Hello, world"</string>
</atom>
</element>
</first>
<right-parenthesis/>
</non-empty-list>
</s-expression>
Here is an XML Schema for Lisp forms:
<xs:schema xmlns:xs="http://www.w3.org/2001/XMLSchema">
<xs:include schemaLocation="s-expression.xsd" />
<xs:element name="Lisp-form" type="Lisp-form" />
<xs:complexType name="Lisp-form">
<xs:complexContent>
<xs:restriction base="s-expression">
<xs:choice>
<xs:element name="atom" type="atom" />
<xs:element name="empty-list" type="empty-list" />
<xs:element name="non-empty-list"
type="non-empty-list-that-starts-with-a-symbol" />
</xs:choice>
</xs:restriction>
</xs:complexContent>
</xs:complexType>
<xs:complexType name="non-empty-list-that-starts-with-a-symbol">
<xs:complexContent>
<xs:restriction base="non-empty-list">
<xs:sequence>
<xs:element name="left-parenthesis" type="empty" />
<xs:element name="first" type="symbol-element"/>
<xs:element name="rest" type="rest" minOccurs="0" />
<xs:element name="right-parenthesis" type="empty" />
</xs:sequence>
</xs:restriction>
</xs:complexContent>
</xs:complexType>
<xs:complexType name="symbol-element">
<xs:complexContent>
<xs:restriction base="element">
<xs:sequence>
<xs:element name="element" type="symbol-s-expression" />
</xs:sequence>
</xs:restriction>
</xs:complexContent>
</xs:complexType>
<xs:complexType name="symbol-s-expression">
<xs:complexContent>
<xs:restriction base="atom-s-expression">
<xs:choice>
<xs:element name="atom" type="symbol-atom" />
</xs:choice>
</xs:restriction>
</xs:complexContent>
</xs:complexType>
<xs:complexType name="atom-s-expression">
<xs:complexContent>
<xs:restriction base="s-expression">
<xs:choice>
<xs:element name="atom" type="atom" />
</xs:choice>
</xs:restriction>
</xs:complexContent>
</xs:complexType>
<xs:complexType name="symbol-atom">
<xs:complexContent>
<xs:restriction base="atom">
<xs:choice>
<xs:element name="symbol" type="symbol" />
</xs:choice>
</xs:restriction>
</xs:complexContent>
</xs:complexType>
</xs:schema>
Here is a sample Lisp form, expressed in XML:
<Lisp-form>
<non-empty-list>
<left-parenthesis/>
<first>
<element>
<atom>
<symbol>foo</symbol>
</atom>
</element>
</first>
<rest>
<first>
<element>
<atom>
<number>10</number>
</atom>
</element>
</first>
</rest>
<right-parenthesis/>
</non-empty-list>
</Lisp-form>
