🚀 go-pugleaf

George Van Treeck raised the interesting question of depth-first
iterative-deepening (DFID) search's applicability to Prolog execution in
general and parallel execution in particular.  A quick check with the gurus
around here (ECRC is a major center of Prolog activity) came up with no
knowledge of any existing literature on DFID and Prolog.  But of course
there might be some.  What follows are my own comments, in the absence of
any literature.

DFID could be integrated into a Prolog interpreter.  The language it
interpreted would have to be a bit modified, as the standard Prolog control
structures and side-effect primitives wouldn't work.  The smallest possible
change in language definition (I think) would be:
   - declaration of ordered vs. unordered predicates
   - cuts only allowed in ordered predicates
   - no side-effects (assert, retract, I/O).

The three non-obvious points in the design of such an interpreter are
   - negation as failure
   - bagof
   - ordered predicates.

The implementation of these three features has to take as its guiding rule:
truncating the search at a particular depth may only eliminate solutions,
never add any.  Concretely this means that when executing not(X), you have
to keep a record of whether the cutoff-depth is reached in executing X.  If
so, then not(X) should fail even if X failed.  This is because X might have
succeeded given a greater cutoff-depth.  The same technique is necessary for
bagof: if it is possible that not all members of the bag were found, the
bagof should fail.  Similarly, if a clause of an ordered predicate fails,
but had been prematurely truncated by the cutoff-depth, the whole predicate
should fail, even if clauses remain.

The next question is whether DFID would do any good.  In today's Prolog
programs it wouldn't, because the average branching factor is extremely low
(between 1 and 2).  The graph in the article in Artificial Intelligence
shows quite clearly how big a loss DFID search is with such a low branching
factor.  Moreover Prolog programmers are very clever about always putting
the easiest clauses first, and also use non-logical constructs to direct the
search.  Prolog execution is not a brute-force search in a well-balanced
tree.  So for normal Prolog programs, DFID would make the execution slower
rather than faster.

Whether the class of programs no one writes with today's Prologs but would
write if they had a DFID Prolog is an interesting class of programs is an
open question.  Note, however, that DFID can also be used for only those
portions of a program which would benefit from it.  There have also been
proposals for adding heuristic control information to Prolog's search.  This
would encourage programmers to use Prolog's built-in search rather than
programming their own.  Thus some amount of optimism about DFID's
applicability may be justified.

Finally comes the question of parallel execution (my own specialty).  *If*
DFID were useful (see the paragraph above), or in fact if it even came close
to the performance of normal depth-first search, then a parallel version
could be a practical way of exploiting parallel processing for logic
programming.  For example, if we could find interesting programs that a DFID
Prolog executed at half the speed of normal Prolog, then by using 20
processors we could hope to get an order-of-magnitude speedup over normal
Prolog.

This possibility is so interesting because DFID has an extremely easy, low
overhead parallel version.  The idea is that each depth-first search is
still sequential, but the search for the proper depth is done in parallel.
This "DFPD" (depth-first parallel-deepening) strategy might for example have
processor A search to a depth of 1 in parallel with processor B searching to
a depth of 2.  As soon as A is done, it starts searching to a depth of 3.
In general: each time a processor is free, it starts a depth-first search
with the next untaken cutoff-depth.  This has a much lower communication and
coordination overhead than OR-parallel Prologs.

Returning to my original caution: DFPD is only a speedup over DFID, *not
necessarily* over other forms of search.  With a finite number of
processors, there will be many realistic programs (virtually all of today's
Prolog programs) for which even a normal single-processor depth-first search
will be faster than DFPD.  (In the infinite-processor case DFPD can be no
worse than depth-first search.)  Thus this is only a useful use of
parallelism if we write programs for which DFID performs at least comparably
to depth-first search.

Conclusions:
   1) a DFID Prolog is easily implementable, though not for normal Prolog
   2) today's Prolog programs would not benefit from DFID
      (in fact, they would suffer)
   3) it is possible that conclusion 2 can be changed
      (particularly if Prolog is extended to accept heuristic control
       information)
   4) if conclusion 2 were changed, generalizing DFID to DFPD would be an
      easy way to make use of parallel processing
      (actually it's not necessary that conclusion 2 be changed -- DFID need
       only approach depth-first search in efficiency, not surpass it)