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 14:53:33 +0100
Message-ID: <440EE1DD.5020707@ilog.com>
To: "Peter F. Patel-Schneider" <pfps@inf.unibz.it>
CC: public-rif-wg@w3.org

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 13:53:57 GMT

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