Iterative Deepening/Delayed Evaluation 
Author Message
 Iterative Deepening/Delayed Evaluation


Quote:
>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

------------------------------------------------------------------------

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

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

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

Francois-Michel Lang
Paoli Research Center, Unisys        

Dept of Comp & Info Science, U of PA  

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.

        AUTHOR="Mark E. Stickel",
        TITLE="A Prolog Technology Theorem Prover",
        BOOKTITLE=slp84,
        PAGES="211-217",
        ADDRESS="Atlantic City",
        YEAR=1984
        }

        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
        }

        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
        }

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

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.

        author = "Charles Elkan",
        title = "{*filter*} 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.

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

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

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



Thu, 30 Jul 1992 23:58:56 GMT  
 
 [ 1 post ] 

 Relevant Pages 

1. Iterative Deepening/Delayed Evaluation

2. iterative deepening

3. breadth-first -vs- iterative deepening

4. delayed evaluation

5. Call-by-need and/or Delayed Evaluation

6. Delayed evaluation?

7. Delayed Expansion/Evaluation?

8. Delayed evaluation in the context of an object

9. Wanted : Reversi / using alfa-beta (+ progressive deepening)

10. deepening into fortran 90,95, 2003

11. Delays, verilog ignores my delays?

12. Unit Delay vs. Zero Delay

 

 
Powered by phpBB® Forum Software