W3C home > Mailing lists > Public > public-rif-wg@w3.org > March 2006

Re: On production rules and phase I&II

From: Peter F. Patel-Schneider <pfps@inf.unibz.it>
Date: Wed, 08 Mar 2006 11:16:39 -0500 (EST)
Message-Id: <20060308.111639.25940371.pfps@research.bell-labs.com>
To: public-rif-wg@w3.org

From: Hassan At-Kaci <hak@ilog.com>
Subject: Re: On production rules and phase I&II
Date: Wed, 08 Mar 2006 16:54:32 +0100

> My comments are interspersed in Peter's mail below. -hak
> 
> Peter F. Patel-Schneider wrote:
> 
> > From: Hassan At-Kaci <hak@ilog.com>
> > Subject: Re: On production rules and phase I&II
> > Date: Wed, 08 Mar 2006 15:27:44 +0100
> > 
> > 
> >>Peter F. Patel-Schneider wrote:
> >>
> >>>In the absence of any demonstration that appending two lists can be performed
> >>>by recursive (Horn) rules, 
> >>
> >>Here's the requested demonstration for pure Horn and no meta-rules:
> >>
> >>	append([],L,L).
> >>	append([H|T],L,[H|R]) :- append(T,L,R).
> >>
> >>>by recursive (Horn) rules, why should it be incumbent on me to show that it can
> >>>be done in pure production rules?  
> >>
> >>I did my part. Now, it is your (or anyone's) turn in "Pure PRs" ...
> > 
> > How about
> > 
> >  	(p (cons ^head <H> ^tail <T> ^result <L>)
> > 	   --->
> > 	   (make append ^left nil ^right <L> ^result <L>) )
> > 
> >  	(p (append ^left <T> ^right <L> ^result <R>) 
> > 	   (cons ^head <H> ^tail <T> ^result <M>) 
> > 	   (cons ^head <H> ^tail <R> ^result <N>)
> > 	   --->
> > 	   (append ^left <M> ^right <L> ^result <N>) )
> > 	   
> > Well, yes, this doesn't work,  
> 
> Sorry won't do. Nothing short of a fully and correctly working example
> will do to convince me, I'm afraid.

Convince you of what?  That pure production rules are recursive in the same sense
that "recursive rules" are?   That pure production rules can capture all of
Prolog?  That pure production rules can capture all of Datalog?

> Incidentally, your (not working) OPS5 "append" example above still uses
> a meta-encoding (the "p" symbol). 

Huh?  Isn't the "p" symbol just the syntax in OPS5 for introducing a rule?  How
is this in *any* way a meta-encoding?

> This does not stand as a recursive
> rule: the symbol "append" is used as a constructor.  

Ooops - I made a syntax error in one spot - a missing "make".

> Even then, there
> is a more problematic situation here: as you assert partial lists
> (which is what I assume "make" does in your OPS5 example), 

According to my understanding of OPS5, "make" is syntax used on the RHS of OPS5
rules to add working memory elements, i.e., the OPS equivalent of assertion.

> these objects
> will also be matched by your rules in further rule applications. How
> do you suggest preventing those matches to restrict matches only to
> the topmost "cons" cell in the WM? (Without retracts or update of course).

I don't.   Why should I?

> >                               but only because pure production rules don't have
> > functions, which are needed in Prolog to do things like append.  This isn't
> > even a problem in theory, because we could simply provide the working memory
> > elements corresponding to the cons's.
> 
> Ok, then: do not bother with Prolog. Let us retrict Pure Horn to Datalog
> (already a substantial concession, but never mind!) and now your (or anyone's)
> exercise is to do recursive transitive closure in pure PRs (i.e., using only
> asserts and no meta-rules) as in:
> 
> 	ancestor(X,Y) :- parent(X,Y).
> 	ancestor(X,Y) :- parent(X,Z), ancestor(Z,Y).


	(p (parent ^parent <x> ^child <y>)
	   -->
	   (ancestor ^ancestor <x> ^descendant <y>) )

 	(p (parent ^parent <x> ^child <y>)
 	   (ancestor ^ancestor <y> ^descendant <z>)
 	   -->
 	   (make ancestor ^ancestor <x> ^descendant <z>))


peter
Received on Wednesday, 8 March 2006 16:16:49 GMT

This archive was generated by hypermail 2.2.0+W3C-0.50 : Tuesday, 2 June 2009 18:33:27 GMT