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: Fri, 8 Jun 2001 18:52:11 -0500
Message-Id: <v04210177b746d0b0c327@[]>
To: "Tim Berners-Lee" <timbl@w3.org>
Cc: <www-rdf-logic@w3.org>
>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


> > 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
>or the bit of it exceprted below, but explained better.  C corresponds to

Yes, I agree it is the same. I didnt follow you at the time, sorry; 
Sandro switched on my light bulb.

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

I really don't think y'all need all this Curry. You just say that 
lists (more generally, say 'sequences', which could represent lists, 
bags, sets, whatever) are unary functions which add their argument to 
themselves (considered as sequences). So that  [b c d] = (lambda x. 
[x b c d]) and so on.  The SKIF axiomatization might be:
(= ((seq @x) ?y) (seq ?y @x))
so that (working backwards)
(seq a b c d)= ((seq b c d) a)= (((seq c d) b) a)= ((((seq d) c) b) a)
Contrast currying, BTW, which would be
(seq a b c d) = ((((seq a) b) c) d)
And then list is a function that takes a sequence into a list:
(list ?x) is the list whose elements are displayed in ?x; (bag ?x) is 
the bag whose elements are... etc. Then you can make a list of bags 
of lists, or whatever takes your fancy. (FAQ: What *are* sequences, 
exactly? A: Whatever you want them to be, as long as you can put 
things in them in order, and are willing to agree that they are not 
lists, bags, sets, etc.. Of course, they can be *isomorphic* to one 
of those thingies, but not *identical*. )

>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
>{ :x a p:List; :y :z} log:implies {:y a p:List; daml:first :z; daml:rest
>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.

Interesting intuition; but not one I share, since an object can 
always be seen as a trivial predicate (true of object and nothing 
else) or a a trivial function (throws away its argument and gives 
object as value.) SKIF doesn't bother to distinguish between 
individuals, relations and functions, which makes life SO much easier 

However, I think that making nil be this magical would be bad 
engineering, for the reasons that Sandro gives: too much searching 
around unbounded chains to find out what it is you are holding.

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

Well, how about something that has an intrinsic type, which makes 
some things you might want to say about it false? That seems 
reasonable: If I say that my desk is thinking about Vienna, then the 
desk kind of refutes me all by itself.

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

It had better be implicit in there somehow, though, right? And then 
the question is, how much work is it to get it made explicit.

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

Actually both have their 'more natural' devotees.

>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


>This could be a way we tackle the reification statndardization problem.
>The problem is of represnting a list of statments.  I think everyone is
>with representing a statement by giving its pred,subj, and object

Not me. See earlier response to Dan C. about this.

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

Thats not a bug, if we think of them as descriptions of the 
containers (which we should, I think, in the RDF model). Look, in set 
theory I might say "The set {a, b, c}" and Ive used an ordered 
description to describe an unordered set, no problem. Of course 
{a,b,c}={a,c,b} but that is OK too, even though "{a,b,c}" /= 
"{a,c,b}" . So for example consider (in SandroSpeak)
      X0 X1 rdf:LIST
      X1 X2 J
      X2 X3 K
      X3 NIL L
      Z0 Z1 rdf:LIST
      Z1 Z2 K
      Z2 Z3 J
      Z3 NIL L
    Y0 X1 rdf:BAG
    Y1 X1 rdf:BAG

Then Y0 = Y1 (bags, same elements) but Z0 /= X0 (lists, different 
order) and X0 /= Y0 (different container type).

> We should recognize the properties of
>a list an settle eventually perhaps on a cannonical rendering to RDF.

No need, I suggest, cf. above.

>However, not that our exchange syntax  (XML with some form of
>list, or () for sets or () for lists  in N3) can be settled independently.
>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.

Right. We can keep the difference in the label at the top (the 
'conversion function') and 'represent' (=describe, in the RDF model 
as I now understand it) all containers by sequences.


IHMC					(850)434 8903   home
40 South Alcaniz St.			(850)202 4416   office
Pensacola,  FL 32501			(850)202 4440   fax
Received on Friday, 8 June 2001 19:52:07 GMT

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