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 09:18:39 -0500 (EST)
Message-Id: <20060308.091839.26197846.pfps@research.bell-labs.com>
To: hak@ilog.com
Cc: public-rif-wg@w3.org

In the absence of any demonstration that appending two lists can be performed
by recursive (Horn) rules, why should it be incumbent on me to show that it can
be done in pure production rules?  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).

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
Received on Wednesday, 8 March 2006 14:43:26 GMT

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