Re: RDF Statements as floating Cons Cells

These curried lists are looking promising.

----- Original Message -----
From: "Sandro Hawke" <sandro@w3.org>
To: "pat hayes" <phayes@ai.uwf.edu>
Cc: <www-rdf-logic@w3.org>
Sent: Thursday, June 07, 2001 5:44 PM
Subject: 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

I think that this is exactly the same as the "list1" method I mentioned
in the "BTW" in
http://lists.w3.org/Archives/Public/www-rdf-logic/2001Jun/0124.html
or the bit of it exceprted below, but explained better.  C corresponds to
"list1".

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

I gave the rules for that mapping.  I wouldn't say it was
a predicate, just a set of axioms to express a curried list as a daml list.

1) list1(x,y) => type(x,list) & first(x,y) & rest(x,nil)
2) type(x,list) & x(y,z) => type(y,list) & first(y,z) & rest(y,x)

or in N3

this log:forAll :z, :y, :z.
{ :x p:list1 :y } log:implies { :x a p:List; daml:first :y; daml:rest
daml:nil}.
{ :x a p:List; :y :z} log:implies {:y a p:List; daml:first :z; daml:rest
:x}.

The reverse rules to curry the list are

1) first(x,y) & rest(x,nil)  => list1(x,y)
2) first(y,z) & rest(y,x) => x(y,z)
generating a spurious x(y,nil) as well as a the essential list1(y,x)

I suppose we could do without list1 is we make nil very magic -- if
we make any x(y,nil) imply x and y were lists -- but I feel one can
legitimately hang magic meaning on a predicate in RDF but not on
an object.  That is, it is the predicate which defines the meaning of
a triple.  In the "anything can say anything about anything" spirit,
you can't make a thing which, when talked about, takes over what
you said.

I don't know whether that has been written down anywhere but
I think it is implicit.

> 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

That could be a fact your implementation recognizes internally
during processing but doesn't have to be in the interchange information.

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


It can be easier to work with, which is why I was looking at it.
In the store,  with a curied list I can propagate from the tail
the fact that a curried list does not contain any variables. This happens
triple by triple. With daml:first and daml:rest I have to track the
two triples at a time, which involves serching the store each time
or linkiing the triples in some way for speed.

What we have here are two vocabularies for expressing lists.
One is more efficient, the other more natural.  The semantic web
doesn't fall apart when people express things in two ways.
So long as there is a well-defined mapping between them, we can
work.

Thought1.
This could be a way we tackle the reification statndardization problem.
The problem is of represnting a list of statments.  I think everyone is
happy
with representing a statement by giving its pred,subj, and object
properties.
The systems all diverge in the problem of representing the set.  The current
spec's rdf_1 etc has a bug in that it doesn't rule out any more things
being in the set.  The daml:collection with first: and rest: solves that.
The curried lists are equivalent.
All  those have a small bug in that they intrduce an arbitratry order
to what is an unordered set.   We should recognize the properties of
a list an settle eventually perhaps on a cannonical rendering to RDF.
However, not that our exchange syntax  (XML with some form of
list, or () for sets or () for lists  in N3) can be settled independently.

Thought2
I like Sandro's idea of explcitly connecting a set and a list which
represents an arbitrary ordering of it.  I like the idea of preserving
the difference between a set and a list.

>    -- sandro
>
> [1] http://lists.w3.org/Archives/Public/www-rdf-interest/2001Apr/0058.html
>     mid:200104100044.f3A0iJ701421@daniel.hawke.org
>
_______________________________
excert from
http://lists.w3.org/Archives/Public/www-rdf-logic/2001Jun/0124.html
[[[ BTW  I was looking at mapping lists into triples in
an alternative way and came up with the predicate "list1" which seeds lists,
in that     list1(x, y) means x is a list  containing just y.  Any list used
as a predicate
indicates that its subject is a list containing first the object and then
the elements of that list.

The 3 statements

list1(x,c)
x(z,b)
z(w,a)

would mean that w was a list contain 3 elements (a b c).

That list could be written in N3 as  [[[list1 c] b] a] although one would of
course
use a shorthand.  (Compare  [first a; rest[first b;rest[first c; rest nil]]]
in daml lists)

(Axioms into daml:  list1(x,y) => type(x,list) &first(x,y) & rest(x,nil)
                 type(x,list) & x(y,z) => type(y,list) & first(y,z) &
rest(y,x)

This connects with Dan's way of making predicates from a seed. Eg to write
z=y+3

     isAFunctionWhichIncrementsBy(x,3)
     x(y,z)

This form of list is weirder, but more efficient than the daml:first and
daml:last mapping.
While human-hairy it is RDF-ok.  Each predicate has a meaning.
]]]

Received on Friday, 8 June 2001 09:25:02 UTC