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 08:38:48 -0500 (EST)
Message-Id: <20060308.083848.56443721.pfps@research.bell-labs.com>
To: public-rif-wg@w3.org

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.

What is different in this universe?

peter



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
Received on Wednesday, 8 March 2006 13:38:58 GMT

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