fp@PROOF.ERGO.CS.CMU.EDU (Frank Pfenning) (02/28/90)
I am looking for papers/reports/code/information on "legitimate" uses of "assert" and "retract" in logic programming, that is, uses which are considered to be in good taste by the connoisseurs of the field. Actually, come to think of it, scathing remarks concerning the illegitimate use of assert and retract would also be appreciated. Also, the latest paper on the efficient implementation of assert I have is from the Fourth International Conference (Lindholm & O'Keefe: Efficient Implementation of a Defensible Semantics for Dynamic Prolog Code). Pointers to more recent "assert" compilation papers would be appreciated. - Frank Pfenning ---------------------------------------------------------------------- Frank Pfenning Telephone: (412) 268-6343 School of Computer Science InterNet: fp@cs.cmu.edu Carnegie Mellon University Pittsburgh, PA 15213-3890, U.S.A. ----------------------------------------------------------------------
mmh@cs.qmw.ac.uk (Matthew Huntbach) (02/28/90)
In article <8205@pt.cs.cmu.edu> fp@PROOF.ERGO.CS.CMU.EDU (Frank Pfenning) writes: >I am looking for papers/reports/code/information on "legitimate" uses >of "assert" and "retract" in logic programming, that is, uses which are >considered to be in good taste by the connoisseurs of the field. "assert" and "retract" are best used to get round what I believe is a very awkward problem with Prolog, the fact that computations on the OR-branches of search trees cannot otherwise communicate. e.g pred(<args1>) :- body1 pred(<args2>) :- body2 Suppose body1 fails, but some of the partial calculations done within it are useful in body2. Then you have to use "assert" to pass them on. I still don't think this is in good taste. I would prefer something like: pred(<args>) :- body1',body2'. where body1' passes on any information required to body2' and has a flag which if set to "true" causes body2' to immediately halt. This is, of course, an argument against backtracking in Prolog, and an argument for the non-backtracking languages like Parlog. Relevant paper: "Compiling OR-parallelism into AND-parallelism" Codish & Shapiro, 3rd Int. Conf. Log. Prog. 1986. A good example of this is something like branch-and-bound search where body1 might produce bounds which restrict the amount of search done in body2. An unpublished paper of mine discusses this in great detail. Matthew Huntbach
mmh@cs.qmw.ac.uk (Matthew Huntbach) (03/01/90)
The book "Artificial Intelligence through Prolog" by N.C.Rowe, published by Prentice-Hall (which coincidentally just turned up in our library today) demonstrates my point. He uses asserts and retracts all over the place to program AI search algorithms (if Mr.Rowe reads this, I would be interested in hearing his reasons for this, personally I think I would recommend his book as a good demonstration of how NOT to program in Prolog). Matthew Huntbach
cdsm@sappho.doc.ic.ac.uk (Chris Moss) (03/01/90)
In article <8205@pt.cs.cmu.edu> fp@PROOF.ERGO.CS.CMU.EDU (Frank Pfenning) writes: >I am looking for papers/reports/code/information on "legitimate" uses >of "assert" and "retract" in logic programming, that is, uses which are >considered to be in good taste by the connoisseurs of the field. Many of the best uses are for assert WITHOUT retract. They generally come into the area of "lemmas": asserting things you've found to be true so you don't have to prove them all over again. This is mentioned in Sterling and Shapiro (The Art of Prolog) p.181 - section entitled "Memo Functions" with an example of Towers of Hanoi. (retract is used simply to clean up at the end) Another example is the (bottom-up) chart parser in Rob Simmons' "Computations from the English" p.202. Here again the information is additive, because every part of the well-formed substring table remains valid. Chris Moss.
debray@cs.arizona.edu (Saumya K. Debray) (03/01/90)
Frank Pfenning (fp@PROOF.ERGO.CS.CMU.EDU) writes: > I am looking for papers/reports/code/information on "legitimate" uses > of "assert" and "retract" in logic programming, that is, uses which are > considered to be in good taste by the connoisseurs of the field. One of the very few situations where I find the use of "assert" justifiable is in flow analysis of Prolog programs. I have a Prolog compiler written in Prolog, and wanted to analyze Prolog programs. A straightforward implementation would have involved two levels of execution -- the analyzer (symbolically) executing the input program, and it in turn being executed by the underlying system. Because this happens during an iterative fixpoint computation, the overhead can be quite high. We were able to get a significant improvement (about an order of magnitude) in speed by short-circuiting one level of interpretation -- the idea was to construct a "specialized" analysis program on the fly (think of it as partial-evaluation-to-the-max), assert it, then transfer control to it. Whereas in the "old" implementation the performance bottleneck was in the fixpoint computation, in the "new" system the bottleneck was assert. (For details, see the paper by Debray and Warren, JLP v. 5 n. 3, Sept. 1988, and by Warren, Hermenegildo and Debray, 5th ICLP, Seattle, 1988). (Caveat: I won't vouch for this being considered "in good taste" by connoisseurs, the best I can say is that it's useful and I can't think of a reasonable workaround of comparable efficiency that doesn't use assert.) -- Saumya Debray CS Department, University of Arizona, Tucson internet: debray@cs.arizona.edu uucp: uunet!arizona!debray
brahme@vlsic2.ti.com (Dan Brahme) (03/01/90)
mmh@cs.qmw.ac.uk (Matthew Huntbach) writes: >"assert" and "retract" are best used to get round what I >believe is a very awkward problem with Prolog, the fact that >computations on the OR-branches of search trees cannot >otherwise communicate. >e.g >pred(<args1>) :- body1 >pred(<args2>) :- body2 >Suppose body1 fails, but some of the partial calculations done >within it are useful in body2. Then you have to use "assert" >to pass them on. >I still don't think this is in good taste. I would prefer >something like: >pred(<args>) :- body1',body2'. >where body1' passes on any information required to body2' and >has a flag which if set to "true" causes body2' to immediately >halt. >Matthew Huntbach I think you can avoid the use of assert in the situation you mentioned. There are ; and -> clauses introduced in several prologs (quintus has them definitely), which precisely serve this purpose. Dan brahme Texas Instruments
finin@prc.unisys.com (Tim Finin) (03/02/90)
In article <1649@gould.doc.ic.ac.uk>, cdsm@sappho (Chris Moss) writes: >In article <8205@pt.cs.cmu.edu> fp@PROOF.ERGO.CS.CMU.EDU (Frank Pfenning) writes: >>I am looking for papers/reports/code/information on "legitimate" uses >>of "assert" and "retract" in logic programming, that is, uses which are >>considered to be in good taste by the connoisseurs of the field. > >Many of the best uses are for assert WITHOUT retract. They generally come into >the area of "lemmas": asserting things you've found to be true so you don't >have to prove them all over again. This is mentioned in Sterling and Shapiro >(The Art of Prolog) p.181 - section entitled "Memo Functions" with an example >of Towers of Hanoi. ... Slightly more general than this is allowing some rules to be forward chaining rules which always add their conclusions to the database. If you do this and want to support default rules or a dynamic database, then retractions are needed, although they should be done in a principled way using a truth maintenance system. The result is a very useful component for building certain kinds of systems in Prolog. It supports the use of a blackboard type architecture and also provides a very easy and potentially efficient way to do certain computations in which the deductive closure of a set of clauses needs to be computed. Our own work in this area is described in Finin, Tim, Rich Fritzson and Dave Matuzsek, ``Adding Forward Chaining and Truth Maintenance to Prolog'', IEEE Artificial Intelligence Applications Conference, (pp. 123 - 130), Miami, March 1989. -- Tim Finin finin@prc.unisys.com Center for Advanced Information Technology 215-648-2840, 215-648-2288 (fax) Unisys, PO Box 517, Paoli, PA 19301 215-386-1749 (home)
mmh@cs.qmw.ac.uk (Matthew Huntbach) (03/02/90)
In article <112803@ti-csl.csc.ti.com> brahme@vlsic2.ti.com (Dan Brahme) writes: >mmh@cs.qmw.ac.uk (Matthew Huntbach) writes: >I think you can avoid the use of assert in the >situation you mentioned. There are ; and -> clauses >introduced in several prologs (quintus has them definitely), >which precisely serve this purpose. I agree. However, I am not sure ; and -> are very nice either. You can always program them out altogether. Personally, I prefer to program out backtracking as well though ...