🚀 go-pugleaf

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.
------------------------------------------------------------------------
------------------------------------------------------------------------