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>
