XML.orgXML.org
FOCUS AREAS |XML-DEV |XML.org DAILY NEWSLINK |REGISTRY |RESOURCES |ABOUT
OASIS Mailing List ArchivesView the OASIS mailing list archive below
or browse/search using MarkMail.

 


Help: OASIS Mailing Lists Help | MarkMail Help

[Date Prev] | [Thread Prev] | [Thread Next] | [Date Next] -- [Date Index] | [Thread Index]
Re: [xml-dev] Two levels of syntax

You're overinterpreting Seibel.  Those aren't the *only* cases that are Lisp forms.

In particular, ((lambda (x y z) (+ x y z) 1 2 3) is also a Lisp form, although its first element is not a symbol.

In Scheme, an expression can have any expression as its first element, but () is not an expression.


On Mon, Aug 1, 2016 at 6:21 AM, Costello, Roger L. <costello@mitre.org> wrote:

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>

 




--
GMail doesn't have rotating .sigs, but you can see mine at http://www.ccil.org/~cowan/signatures


[Date Prev] | [Thread Prev] | [Thread Next] | [Date Next] -- [Date Index] | [Thread Index]


News | XML in Industry | Calendar | XML Registry
Marketplace | Resources | MyXML.org | Sponsors | Privacy Statement

Copyright 1993-2007 XML.org. This site is hosted by OASIS