fuchs@ifi.unizh.ch (Norbert E. Fuchs) (02/11/90)
Some time ago I wrote: >I am looking for references to metainterpreter solutions of iterative >deepening and delayed evaluation. Response to my request was immediate, and I would like to thank everybody who contributed. I also would like to thank Francois Bry, Charles Elkan, Matthew Huntbach, and Andreas Zell for sending me their papers. The following is a summary of the messages I received. --- nef ------------------------------------------------------------------------ From: <lee@munmurra.cs.mu.OZ.au> Organization: Comp Sci, University of Melbourne There have been several articles on meta interpreters for delayed evaluation. The most recent one I can think of off hand is %A Antonio Porto %T Two-level Prolog %J Proceedings of the 1984 International Conference on Fifth Generation Computer Systems %C Tokyo, Japan %D November 1984 %K fgcs fgcs84 logic %P 356-360 I don't know of papers on meta interpreters for iterative deepening per se. Its mentioned in passing sometimes (I have done so myself). Its pretty simple. I can send you a bit of code if you want (if you want code its probably better to write your own specialised version). lee ------------------------------------------------------------------------ From: <lee@munmurra.cs.mu.OZ.au> Organization: Comp Sci, University of Melbourne The fancier schemes for delayed evaluation are more difficult than iterative deepening. If you want something simple, you could get them to implement a breadth first computation rule first (its not too difficult to entend that to more complex computation rules, by changing a queue to some other DS). References to the literature could be a problem though. If you are looking for a reference to a use of iterative deepening (rather than implementation details) you could use the section on testing in the following: %A L. Naish %A P. W. Dart %A J. Zobel %T The NU-Prolog debugging environment %J Proceedings of the Sixth International Conference on Logic Programming %C Lisboa, Portugal %D June 1989 The simple way to implement iterative deepening is as follows solve(Goal) :- generate_depth(D), solve_depth(Goal, D). generate_depth generates increasing depths, and solve_depth tries to solve Goal with a limited depth search (it fails if the depth limit is reached). This method returns solutions more than once (you can avoid this by using an upper and lower bound) and will loop even with a finite tree (the only way to avoid this that I know of is to use side effects). lee ------------------------------------------------------------------------ From: Marco Valtorta <mgv%usceast@mcsun.uucp> Organization: University of South Carolina, Columbia Andreas Zell and Thomas Braunl wrote a paper on a meta-interpreter to do Depth-First Iterative Deepening in Prolog. The paper is entitled "An Alternative Prolog Search Strategy." I do not know if it has been published. The copy I have includes Prolog code for the meta-interpreter. Zell and Braunl's address is: Institut for Informatik Universitaet Stuttgart Azenbergstr. 12 D-7000 Stuttgart 1 Federal Republic of Germany uucp: ...!unido!ifistg!zell ------------------------------------------------------------------------ From: <lang@PRC.Unisys.com> Francois-Michel Lang Paoli Research Center, Unisys lang@prc.unisys.com (215) 648-7256 Dept of Comp & Info Science, U of PA lang@linc.cis.upenn.edu (215) 898-9511 You might want to have a look at the following for iterative deepening. Mark Stickel's PTTP system implements iterative deepening, and his code is available. @INPROCEEDINGS{PTTP1, AUTHOR="Mark E. Stickel", TITLE="A Prolog Technology Theorem Prover", BOOKTITLE=slp84, PAGES="211-217", ADDRESS="Atlantic City", YEAR=1984 } @INPROCEEDINGS{PTTP2, AUTHOR="Mark E. Stickel", TITLE="A Prolog Technology Theorem Prover: Implementation by an Extended Prolog Compiler", BOOKTITLE=AD8, EDITOR={J\"org H. Siekmann}, PAGES="573-587", PUBLISHER="Springer-Verlag", ADDRESS="New York", YEAR=1986 } @TECHREPORT{PTTP-Report, AUTHOR="Mark E. Stickel", TITLE="A Prolog Technology Theorem Prover: Implementation by an Extended Prolog Compiler", TYPE="Technical Note", NUMBER="382R", INSTITUTION="SRI International", ADDRESS="Menlo Park, CA", MONTH=nov, YEAR=1987 } @INPROCEEDINGS{CBDFS, AUTHOR="Mark E. Stickel and W. Mabry Tyson", TITLE="An Analysis of Consecutively Bounded Depth-First Search with Applications in Automated Deduction", BOOKTITLE=ijcai9, PUBLISHER="Morgan Kaufmann Publishers, Inc.", ADDRESS="Los Altos, CA", PAGES="1073-1075", YEAR=1985 } ------------------------------------------------------------------------ From: Charles Elkan <cpe@cs.toronto.edu> Charles Elkan Research Associate Department of Computer Science University of Toronto 10 King's College Road Toronto, Ontario M5S 1A4 Canada It makes a big difference in iterative deepening what measure of depth you use. This is one of the topics of my IJCAI-89 paper. @inproceedings{e89b, author = "Charles Elkan", title = "Conspiracy Numbers and Caching for Searching And/Or Trees and Theorem-Proving", booktitle = ijcai89, pages = {341--346}, month = aug, year = 1989 } More recently, I have used freezing and constructive negation in a metainterpreter for planning. @techreport{e89d, author = "Charles Elkan", title = "{Incremental, Approximate Planning (Preliminary Report)}", institution = torontocs, number = "KRR-89-12", month = nov, year = 1989 } I am sending you copies of both these papers by airmail. ------------------------------------------------------------------------ From: "Francois Bry" <francois%ecrcvax@unido.uucp> Francois Bry ECRC, Munich Iterative deepening: R.E. Korf Depth-first iterative deepening: An optimal admissible tree search, Artificial Intelligence 27 (1985), pp. 97-109 (The author points out that he did not invent the method. But this is the usual disclaimer concerning iterative deepening.) Delay in Prolog etc. The best source for the references is the book: P. Van Hentenryck C0nstraint Satisfaction in Logic Programming MIT Press, 1989 ------------------------------------------------------------------------ From: Matthew Huntbach <mmh@cs.qmw.ac.uk> Matthew Huntbach Dept. of Computer Science Queen Mary and Westfield College London E1 4NS, UK. I have an unpublished paper on programming lazy evaluation in Parlog (submitted to this year's ICLP). If that sounds of use to you, I'll post you a copy. ------------------------------------------------------------------------ ------------------------------------------------------------------------