W3C home > Mailing lists > Public > www-rdf-logic@w3.org > June 2001

Re: RDF Statements as floating Cons Cells

From: pat hayes <phayes@ai.uwf.edu>
Date: Thu, 7 Jun 2001 20:33:07 -0500
Message-Id: <v04210163b745cc599866@[205.160.76.219]>
To: Sandro Hawke <sandro@w3.org>
Cc: www-rdf-logic@w3.org
>Pay Hates:
> >Ah, point taken. I guess I was taking the triple itself to be the
> >thing analogous to the LISP dotted pair, so that it already
> >identifies its subject and object. This assumes that triples inside a
> >nest have a unique 'location' (analogous to an address in LISP) so
> >that they can be pointed at. Maybe this assumption is RDF-inimical?
>
>Yes, I think it is RDF-inimical.  An RDF statement is like a
>mathematical pair of numbers.  Some encoding schemes might give you
>ways to point to encodings of statements, but the abstract syntax does
>not.  It says the way to refer to a statement is by its complete
>description.  (In the math anology, how do you identify the pair <21,
>-3>?  Well, as "the pair <21, -3>", although you are free to assign it
>some names if you like.)

Light bulb goes on in head!

Ah. No wonder the triple-nesting was turning out so easy. Ive been 
(mis) using a triple to encode two LISP cons cells, but I really only 
have a licence to use them for one, you are absolutely right. Now I 
see why Tim accused me of using quads.

>So how is an RDF statement like a cons cell?   I normally think of a
>cons cell has having two information parts (the car and the cdr), but
>of course it has a third - its location.
>
>This actually gives us an interesting angle on representing sequences
>in RDF.

Not just sequences; arbitrary graph structures (put a list pointer in 
place of an item to make a sublist)

>Let's consider a list X being (A B).  And let's say the tail of X
>(the list containing B) is Y.
>
>The DAML-style for expressing this in RDF takes four statements:
>
>    X first A                [ syntax here is  "subject predicate object" ]
>    X rest Y
>    Y first B
>    Y rest empty
>
>but in LISP it's only two cons cells:
>
>    X:  [  a  |  Y  ]                           location: [ car | cdr ]
>
>    Y:  [  b  |  empty ]

But this isnt quite fair since in LISP everything is a list, but in 
RDF we need to say this is a list, which would add one more triple.

>Can we use the RDF-statement == cons cell analogy to come up with a
>more compact list representation?
>
>    X Y A
>    Y C B

Is that still SPO ? If so I would suggest writing it as
A X Y
B Y C
as this will preserve the list ordering when written out in lexical 
syntax, and it puts the list constructors in the predicate position.

>Yeah.  This defines a sequence structure using one term (C)

ie NIL, right?

>instead of
>three (first, rest, empty).  And it uses one RDF statement per list
>element, instead of two.   Lets try the list (J K L M) in cons cells
>named X1, X2, X3, X4.
>
>    X1 X2 J
>    X2 X3 K
>    X3 X4 L
>    X4 C M
>
>I wonder how this works...
>
>   case 1:  I want to know if X is a list
>
>   I look up all the RDF statements with X as a subject.  I take each
>   predicate, and look it up the same way (recursively) until I find
>   the predicate C or I give up.   A type declaration might be good.
>   How does LISP do this?

The question doesn't really arise in LISP since everything is 
Sexpressions. The nearest q. would be: is this an atom? and that is 
decided by a marker at the front, so your example should probably 
start with

   X0 LIST X1

and the way you tell X0 is a list is by looking at its predicate.

>   case 2:  I want to know if the list X contains Q.
>
>   Same kind of recursion until I find C, but I also check the objects
>   of the statements, to see if they are Q.

Right, to check membership needs a scan through the list. Its only 
iterative, not fully recursive.

>So what the heck is the class of X2, etc?  Yeah, they are cons cells.
>But what are they?

I guess I am not sure what this question means. Why do you need to 
say anything other than they are cons cells? However, if you were to 
write it the way I suggested above, then you can think of each list 
as being built up by a kind of self- consing, where a list L is 
identified with the function
(lambda (?x) (cons ?x L)) which conses something onto the front of 
it, and LIST would be the function that takes an entire cons-sequence 
and confers listitude upon it.

You could call this Currying, but it would be a currying of a 
variadic function like KIF's 'list' where you can write (list a b c 
d...) with as many arguments as you like, and you would have to write 
it backwards, as Tim pointed out. But to hell with Currying, we don't 
need it if we think in terms of cons.

> Is this just Currying?  X2 is a third-order
>predicate?   Yeah, maybe.   I guess you can have an UnCurry predicate
>to map from X1 to the daml:list of the same elements.  Can I write
>that in a Horn logic?  Um, not knowing that it's a list until we've
>traversed it in a pain.

Yes, it is too much of a pain. Better stick it on the front.

>And if we add type declarations, we're back
>to two RDF statements per list element.   Sigh.

No, it just adds one triple per list : n+1, not 2n. [later: I see we 
in fact agree and had come to the same conclusion.]

>   case 3:  Someone adds
>      X1 XX R
>      XX C S
>   (that is, X1 is the Curry list of the element "R S")
>   Now case1 and case2 will only notice the shorter list.

Why? Are you assuming some kind of breadth-first search?

> They can't
>   know the list is doubly defined without continuing the recursion
>   until they run out of all kinds of properties, which may never
>   happen.

Oh God, I am inclined to give up at this point. Why are we even 
bothering to try to adapt this unbelievably broken system to make it 
do something which it is  incapable of doing? I thought that I could 
see a way to extend RDF to add more complex syntax to it, and now you 
have convinced me that it can't be done.

>However, if we set out to do this with Currying in mind, it might look
>like:
>
>   X1a is-a-curried-list-with-next-term X2a
>   X2a X3a J
>   X3a X4a K
>   X4a X5a L
>   X5a stop-currying M
>
>which I think solves all these problems.

How does it stop someone adding

X3a X4b S
X4b nil T

and making the structure 'doubly defined' ? There is no way to do 
that, as far as I can see. At this point I think I shall just go home 
and go to bed.

Pat Hayes

---------------------------------------------------------------------
IHMC					(850)434 8903   home
40 South Alcaniz St.			(850)202 4416   office
Pensacola,  FL 32501			(850)202 4440   fax
phayes@ai.uwf.edu 
http://www.coginst.uwf.edu/~phayes
Received on Thursday, 7 June 2001 21:33:01 GMT

This archive was generated by hypermail 2.2.0+W3C-0.50 : Monday, 7 December 2009 10:52:40 GMT