Comments on (informal) meaning of lists

At 09:11 AM 2/3/03 -0800, pat hayes wrote:

>Concerning the notion of 'well-formed' lists, there is a characterization 
>of the RDF graphs which describe such lists in the relevant section of the 
>semantics document.  Here is a more exact and careful statement of that 
>characterization.
>
>Define a 'link' in a graph G to be a subgraph consisting of two triples of 
>the form
>
>aaa rdf:first bbb .
>aaa rdf:rest ccc .
>
>where ccc may be rdf:nil, but otherwise aaa and ccc are bnodes or urirefs 
>which are not in the RDFS namespace. Call aaa the *addr* of the link, bbb 
>the *head* of the link, and ccc the *tail* of the link. Define a 'line' in 
>G to be a finite subgraph of G consisting of links and satisfying the 
>following conditions: exactly one link in the line has rdf:nil as its 
>tail; otherwise, every link's tail is the addr of exactly one other link 
>in G; one link in the line has an addr which is not a tail of any other 
>link - call this the *addr of the line* - and otherwise, the addr of every 
>link in the line is the tail of exactly one other link in G; and no addr 
>or tail (except rdf:nil) in the line occurs as the subject or object of 
>rdf:first or rdf:rest elsewhere in G.

Ummm...  I assume this is intended to describe a "well-formed list" -- it's 
not obvious to me (other than by prior experience) what part of this is a 
well formed list.

I don't recognize anything here that prevents the following:

   aaa rdf:first bbb .
   aaa rdf:rest ccc .
   aaa rdf:first ddd .

being regarded as two distinct links:

   aaa rdf:first bbb .
   aaa rdf:rest ccc .

   aaa rdf:first ddd .
   aaa rdf:rest ccc .

in that these are both subgraphs of the original.

You talk of the *addr of the line* as being a link that is not the tail of 
any other link.  Why this restriction?  Isn't every link the head of some line?

...

I'm not really comfortable with this description;  it seems easier to me to 
adopt a recursive strategy:

(a) a *link* in G is a subgraph of the form
    aaa rdf:first bbb .
    aaa rdf:rest ccc .
where aaa denotes an object of type rdf:List, and
there are no other statements in G of the form:
    aaa rdf:first yyy .
or
    aaa rdf:rest zzz .
Call aaa the *addr* of the link, bbb the *head* of the link, and ccc the 
*tail* of the link.

(b) a (well-formed) *line* is one of the following:

    (i)  rdf:nil
    (ii) a *link* whose head is any node, and whose *tail* is a 
(well-formed) *line*.

>Given any line, the sequence of denotations of the heads of links obtained 
>by starting with the addr of the line and following the tails in order, is 
>the *list denoted by the line*.  Semantic extensions of RDF may well want 
>to require that addrs of lines denote the list denoted by the line.

(I considered offering a recursive definition for the list thus denoted, 
but that seems unnecessary.)

>This allows the heads of links to be the addrs of other lines, so it 
>allows arbitrary S-expressions, in LISP parlance. To restrict oneself to 
>'linear' lists, add the condition that no head of any link in the line 
>occur as the subject of any rdf collection property in G.

I'm assuming we'll allow full s-expressions.  DO we need to say anything 
explicitly about this -- I think it follows from the (intended) definition.

#g


-------------------
Graham Klyne
<GK@NineByNine.org>

Received on Tuesday, 4 February 2003 12:47:59 UTC