Re: Two levels of syntax

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>