RDF Statements as floating Cons Cells

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.)

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.

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 ]

Can we use the RDF-statement == cons cell analogy to come up with a
more compact list representation?

    X Y A
    Y C B

Yeah.  This defines a sequence structure using one term (C) 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?

   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.

So what the heck is the class of X2, etc?  Yeah, they are cons cells.
But what are they?  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.  And if we add type declarations, we're back
to two RDF statements per list element.   Sigh.

   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.   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. 

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.  It may be a little harder
to work with than first/rest lists, but it's N+1 statements instead of
2*N statements.  In other words, I should add this to my list of ways
to do lists in RDF [1].

   -- sandro

[1] http://lists.w3.org/Archives/Public/www-rdf-interest/2001Apr/0058.html
    mid:200104100044.f3A0iJ701421@daniel.hawke.org

Received on Thursday, 7 June 2001 16:44:18 UTC