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

Re: On production rules and phase I&II

From: Hassan At-Kaci <hak@ilog.com>
Date: Wed, 08 Mar 2006 15:27:44 +0100
Message-ID: <440EE9E0.6060602@ilog.com>
To: "Peter F. Patel-Schneider" <pfps@inf.unibz.it>
CC: public-rif-wg@w3.org

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([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... :-)
>>>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
>>>>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
>>>>	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
>>>>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.
>>>>	isTrue(C) <- A & B.
>>>>	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,
>>>>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 14:27:18 UTC

This archive was generated by hypermail 2.3.1 : Tuesday, 6 January 2015 21:47:37 UTC