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

Re: On production rules and phase I&II

From: Michael Kifer <kifer@cs.sunysb.edu>
Date: Wed, 08 Mar 2006 13:45:21 -0500
To: =?ISO-8859-1?Q?Hassan_A=EFt-Kaci?= <hak@ilog.com>
Cc: "Peter F. Patel-Schneider" <pfps@inf.unibz.it>, public-rif-wg@w3.org
Message-ID: <24796.1141843521@kiferserv.kiferhome.com>


Hasan,

The claim was that negation-free production rules with only asserts behave like
Horn clauses. Not the other way around (i.e., that any pure Prolog program
is immediately a production rule system).

By the way, the append example doesn't validate your claim that production
rules are inherently non-recursive, and I don't buy that being able to look
into the intermediate models is a significant difference. To make use of
that, you need additional syntax, which takes us out of the subset that we
were discussing.

Anyway, what you said in a previous email was that this is an uninteresting
subset of production rules. I won't argue with that, because even pure Horn
is a relatively uninteresting subset of rule systems.

The implication of this is that RIF will have two completely disjoint
things: declarative rules and production rules, and that we should probably
split into two subgroups.

This is not unreasonable, since even according to our proposal this would
have happened in Phase 2. The distance between production rules and
declarative rules is very large -- much larger than between OWA and CWA
(i.e., between the two subsets within the declarative part of RIF).


	--michael  


> 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" ...
> 
> >                                   I'm not claiming that pure production rules
> > can do everything, after all, just that pure production rules aren't any
> > different from recursive rules (as in Prolog).
> 
> Nice wiggling... but won't do! ;-)
> 
> I agree that any two Turing-complete computational systems "aren't any different".
> If this is your best argument to convince me, then I shall happily keep on
> living in my universe... :-)
> 
> > peter
> > 
> > 
> > From: Hassan At-Kaci <hak@ilog.com>
> > Subject: Re: On production rules and phase I&II
> > Date: Wed, 08 Mar 2006 14:53:33 +0100
> > 
> > 
> >>Peter F. Patel-Schneider wrote:
> >>
> >>
> >>>I don't understand which universe I've fallen into here.
> >>>
> >>>In my universe, production rule systems derived from OPS5.  
> >>>
> >>>In my universe, OPS5 allowed rules like
> >>>	(p (parent ^parent <x> ^child <y>)
> >>>	   (ancestor ^ancestor <y> ^descendant <z>)
> >>>	   -->
> >>>	   (make ancestor ^ancestor <x> ^descendant <z>))
> >>>
> >>>In my universe, this was a recursive rule.
> >>
> >>Can you please explain what this rule does and where exactly is
> >>the recursion? Better: can you please write a PR program (in OPS5,
> >>CLIPS, JESS, Fair Isaac's Blaze, ILOG's JRules, or whatever) that
> >>appends two lists using only asserts, and without resorting to
> >>encoding a Horn Logic meta-interpreter as a PR? Thanks.
> >>
> >>
> >>>What is different in this universe?
> >>
> >>I think that the universe I live in is one where square pegs do
> >>not fit into round holes - at least, not naturally nor easily. At
> >>any rate, if you can do the very simple exercise that I am asking
> >>(append in OPS5 with only asserts), then maybe I'll join you in your
> >>shape-insensitive edenic universe... :-)
> > 
> > 
> > 
> >>>peter
> >>
> >>-hak
> >>
> >>
> >>>From: Hassan At-Kaci <hak@ilog.com>
> >>>Subject: Re: On production rules and phase I&II
> >>>Date: Wed, 08 Mar 2006 08:57:16 +0100
> >>>
> >>>
> >>>
> >>>>This is related to Frank's point and the replies he got from Peter and
> >>>>Michael.
> >>>>
> >>>>There is no recursion in PRs simply because PRs are not driven by names
> >>>>(as in Prolog, i.e., Horn Logic, or functional Rewrite Rules). For a
> >>>>computational system to be "recursive" there must be something that
> >>>>"recurses". In Prolog, e.g., the name of the head predicate is what
> >>>>"recurses" (in  Rewrite Rules, the head's functional symbol is what
> >>>>recurses:
> >>>>
> >>>>	Prolog:         append([H|T],L,[H|R]) :- append(T,L,R).
> >>>>	Rewrite Rule:   append([H|T],L) -> [H|append(T,L)].
> >>>>
> >>>>Clearly the symbol "append" is recursive (i.e., it reoccurs in its
> >>>>definition).
> >>>>
> >>>>Now PRs are NOT driven by names. Since a rule is not using a relational
> >>>>or functional name in its head to drive the rule's call, it is simply
> >>>>not possible to have recursive rules.
> >>>>
> >>>>Does it mean PR's cannot compute iteratively? Certainly not: there is
> >>>>an underlying loop that acytivates the rules based on the data present
> >>>>in the working memory (or Extensional DB, or Fact Base, etc...). Viz.,
> >>>>
> >>>>	WHILE   [some rules match some objects in the WM]
> >>>>	DO      [choose a rule and all the objects it matches]
> >>>>                [do the action of the rules on all these objects.]
> >>>>
> >>>>It is this "hidden loop" that ascribes PR's its Turing-equivalence.
> >>>>Furthermore, while Logical and Functional rules carry an environment
> >>>>along the computation, a "local" handle is passed from one rule to
> >>>>another as data is being constructed ot deconstructed (e.g., the
> >>>>"cons" cell [H|T] in the examples). PR rules communicate with each
> >>>>other only through a global store: the WM. This necessitates explicit
> >>>>modification of existing data (as opposed to inductive non-destructive
> >>>>building of structures passed in local environments). One realizes
> >>>>these subtle points when one tries to write a PR program to append
> >>>>two lists as specified by the recursive rules (as above). To say the
> >>>>least, it is not easy to do so with PRs and one would have to resort
> >>>>to contrived actions involving update and modify (not just assert).
> >>>>
> >>>>Therefore, what Frank meant is that what Harold presented as a Road
> >>>>Map defining a "Pure PR model" is not clear. If only asserts are
> >>>>allowed, one cannot write simple recursive schemed. That's all.
> >>>>
> >>>>Regarding the point of:
> >>>>
> >>>>	C <- A & B.
> >>>>vs.
> >>>>	isTrue(C) <- A & B.
> >>>>vs.
> >>>>	mustBeTrue(C) <- A & B.
> >>>>
> >>>>I agree again with Frank. The last two are not logical - they are
> >>>>META-logical. Using them necessitates carrying an explicit structure
> >>>>(such as a list) to explicate the changed facts. (This is what monads
> >>>>do in Haskell to implement "purely" side-effects and procedural control.)
> >>>>Also, as Frank pointed out: What is true in Pure Horn must ALWAYS be
> >>>>true. So the question is, "When is C true?" in the example above?
> >>>>What Michael and Harold seem to propose is to identify a PR's model
> >>>>with the saturated construction derived from all possible asserts.
> >>>>These models are stable (as fix-points) only as the limit. Hence,
> >>>>this seems to be a valid approach only for finite models. Another
> >>>>snag of this approach is that such "Pure PRs" may very well compute
> >>>>inconsistent models (where "don't care" non-determinism is used).
> >>>>FOr example, a car-rental application will assign (via asserts)
> >>>>one car (any one) to any driver requesting one. However, a saturated
> >>>>model will generate rental contracts with the same car attributed
> >>>>to several drivers.
> >>>>
> >>>>In conclusion, while it is possible to simulate one system in the
> >>>>other (e.g., by mere Turing equivalence), it may be contended that
> >>>>the translations to and from each side (PRs and Pure Horn) are, IMHO,
> >>>>non-trivial and non-intuitive.
> >>>>
> >>>>So, Frank is basically right: what Harold et al.'s Road Map defines
> >>>>as "pure PRs" is computationally uninteresting and its rendition in
> >>>>Pure Horn is likely to be at odds with a rendition for Full PR.
> >>>>
> >>>>My 2 cents,
> >>>>
> >>>>-hak
> >>>>-- 
> >>>>Hassan At-Kaci
> >>>>ILOG, Inc. - Product Division R&D
> >>>>tel/fax: +1 (604) 930-5603 - email: hak @ ilog . com
> >>>
> >>>
> >>>
> >>
> >>-- 
> >>Hassan At-Kaci
> >>ILOG, Inc. - Product Division R&D
> >>tel/fax: +1 (604) 930-5603 - email: hak @ ilog . com
> > 
> > 
> 
> 
> -- 
> Hassan At-Kaci
> ILOG, Inc. - Product Division R&D
> tel/fax: +1 (604) 930-5603 - email: hak @ ilog . com
> 
> 
> 
Received on Wednesday, 8 March 2006 18:45:37 GMT

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