PROLOG-REQUEST@SU-SCORE.ARPA (Chuck Restivo, The Moderator) (08/20/86)
PROLOG Digest Wednesday, 20 Aug 1986 Volume 4 : Issue 40
Today's Topics:
Query - Errors & Typos,
Puzzle - Lemmas
----------------------------------------------------------------------
Date: Tue, 19 Aug 86 15:54:32 -0200
From: Ehud Shapiro <udi%wisdom.bitnet@WISCVM.WISC.EDU>
Subject: The Art of Prolog
Although the "Art of Prolog" came out only last week, MIT Press is
planning a second printing in two months time. We will appreciate
the help of anyone who has got the book in finding typos and errors,
so we can fix them for the second printing. For a bug report to make
the second printing, it should arrive before the end of September.
Please send them to me or to Leon:
ARPA: udi%wisdom.bitnet@wiscvm
leon%case.csnet@csnet-relay
CSNet, uucp: udi@wisdom leon@case
Bitnet: udi@widom
Thank you,
-- Ehud Shapiro
------------------------------
Date: 17 Aug 86 23:10:59 GMT
From: Ran Ever-Hadani <raan@ucbvax.berkeley.edu>
Subject: Lemmas
It has been done - at least partialy. Theory + experiments for
Prolog with assert and retract, esp. for very large databases
of facts. The reference is:
Oded Shmueli, Hana Zfira, Shalom Tzur, Ran Ever-Hadani
"Dynamic Rule Support in Prolog"
Fifth Generation Computer Architectures, J.V. Woods (ed.)
Elsevier Science Publishers B.V. (North-Holland)
IFIC, 1986
-- Ran Ever-Hadani
------------------------------
Date: 17 Aug 86 17:30:38 GMT
From: Mario O. Bourgoin <mob@media-lab.mit.edu>
Subject: Lemmas
In article <1311@lsuc.UUCP>, dave@lsuc.UUCP writes:
> In article <292@mit-amt.MIT.EDU> mob@mit-amt.MIT.EDU writes:
> >
> >If Prolog refused to solve for goals already encountered,
> >this problem would not exist. ...
>
>I'd be interested in hearing the answer to this too. I believe this
>is what Kowalski describes as "lemmas" in Logic for Problem Solving -
>that is, whenever a goal is resolved (to either yes or no), that fact
>can be recorded.
I think that we aren't trying to solve the same problem. In my case,
if I solve for the goal "goal(A)" which I reduce to solving for the
goal "goal(B)" then I am no better off, especially since Prolog will
then reduce the last goal to solving for "goal(C)". I want Prolog to
refuse to solve for "goal(B)" whether or not "goal(A)" has been solved
already.
What you want appears to be what Suzanne Deitrich called "Extension
Tables" which is a form of dynamic programming. The problem of what is
current in the lemma hash table has been solved with what is called a
Truth Maintenance Systems (TMS). In such a system, an asserted fact
would include both it's current truth value (yes, no) _and_ a
dependancy record of how it was deduced. For your example, the
deduction that you are tired today would be removed from the lemma
table when the fact that netnews was read for 180 minutes yesterday
would be removed.
A better solution is to have the asserted lemmas keep track of _both_
a dependancy record of how it was deduced _and_ the assumptions under
which it holds, in this case, yesterday's netnews reading time and the
rule used for goal reduction. Prolog then keeps track of which facts
are current as usual. These current facts form the context under which
deductions are made. When a goal is called, if it can be found in the
lemma table, its entry's context is checked against the current
context and if it is a subset of the current context, the conclusion
reached earlier can be used; otherwise the goal is resolved. For
efficiency reasons, the context of deduction of a fact is composed of
only those facts which the fact depends upon. This method is like what
Johann de Kleer proposed in Artificial Intelligence, Vol. 28, No. 1.
1986.
Caveat: the above statements are a simplification of what would really
need to be done to make the algorythm work because they doesn't take
into account adding in new rules or facts under which the deduction
could be made.
As is usual, we are trading off processing time for space.
-- Mario O. Bourgoin
------------------------------
End of PROLOG Digest
********************