Path: utzoo!attcan!uunet!ncrlnk!ncr-sd!hp-sdd!hplabs!decwrl!curie.dec.com!vantreeck
From: vantreeck@curie.dec.com
Newsgroups: comp.lang.prolog
Subject: Search strategies in PROLOG
Message-ID: <8811171657.AA18741@decwrl.dec.com>
Date: 17 Nov 88 16:57:48 GMT
Organization: Digital Equipment Corporation
Lines: 76

>Path: decwrl!sun!pitstop!sundc!seismo!uunet!munnari!vuwcomp!lindsay
>Subject: Re: Determining order of argument unification
 
>I have often wondered about this.  It would seem to be a fairly simple 
>optimisation in a Prolog compiler to look at the arguments in a call and
>process them in an order that does the easiest things first.  For example:
					.
					.
					.
>	Lindsay Groves


Most PROLOG interpreters/compilers are optimized for deterministic execution of
very small procedures, in particular, naive reverse which has only two clauses
and calls another procedure, append, which also has only two clauses. For this
case, the search time is extremely small. And special optimizations for order of
search are unnecessary. These implementations have added indexing on the first
argument in the head of a clause as an after thought to address real-world
programs, where searching is generally the dominant time consumer. 

I implemented a research version of PROLOG that supports multiple levels of
indexing on all arguments and subarguments. But this is space expensive, so I
chose to eliminate the linked list that preserved order of clause assertion. And
I chose to use a search paradigm analogous to other languages: Search for the
specific case first, and then try the catch-all case. Therefore, this PROLOG
first unifies a goal variable to any constants, then structures, then non-void
variables, and finally void variables -- almost exactly like the paradigm you
suggested. I added a hack for those less frequent (but important) cases where
order of clauses is important. 

Not that anyone would want yet another "non-standard" PROLOG, this PROLOG is not
available to the public. 

George Van Treeck
Digital Equipment Corporation



>Can somebody point to a reference for "iterative deepening"?
>I have looked in the indexes of a half-dozen or so standard AI textbooks
>and found nothing.  I know this is a term and a search strategy
>that Richard discusses.  Richard, did you come up with the name?
>If not, do you know who did, or where the strategy is referred to
>as such (other than your messages and tutorial notes)?

The reference for Depth-First Iterative-Deepening (DFID) is in the Journal of
Artificial Intelligence 27 (1985) pp. 97-109. DFID asymptotes to the optimal
space and optimal time algorithm for large search spaces.

When I suggested using DFID in PROLOG several years ago, the consensus on the
USENET was that the number of cases where it would be useful are too small to
put a lot implementation study into it. Examples of useful applications are
finding: a chemical synthesis paths, mathematical proofs, optimal electronic
circuit synthesis, little reasoning problems like the monkey and bananas. There
may not be a lot of cases where it's important. But when it is needed it's very
handy. 

I've spent some time looking at ways to build DFID search efficiently into
PROLOG. The primary problem is that PROLOG programs have side-effects which
aren't reversible on backtracking (e.g., keyboard input). DFID does a lot more
backtracking where "normal" PROLOG would be deterministic. 

Ideally, one would like to have a DFID predicate for calling PROLOG procedures
which no side-effects in their proof. And ideally, the overhead of checking
depth shouldn't impact PROLOG execution in general. So, I've been looking at
ways to break DFID execution out into a separate case from normal DF search
(much as most commercial versions of PROLOG that are based on the WAM separate
out the read and write modes). 

It may also be that with DFID one would need to use coroutining predicates less
often in order to determine constraints. That would help remove some of the
requirement to think about implementation and concentrate on the declarative
statement of the problem. 

George Van Treeck
Digital Equipment Corporation