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 08:57:16 +0100
Message-ID: <440E8E5C.7000209@ilog.com>
To: public-rif-wg@w3.org

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 07:56:37 GMT

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