🚀 go-pugleaf

  
    

Some points to a possible implementation of DFID search in Prolog:

1. The DFID algorithm always finds the solution; so does a useful Prolog
program, unless it goes into an infinite loop. This means that DFID
can never find a solution in a shorter time than the usual Prolog:
either Prolog's depth-first search is faster or Prolog fails to
find anything and it loops. The same holds then for a parallell
implementation of DFID, it could only be a way to prevent infinite
loops in a better time than a serial DFID rather than speeding
up the search in comparison with Prolog.

2. DFID always finds the optimal solution, the usual Prolog finds
*any* and maybe all solutions if necessary. If the user wants to find
all solutions and the usual Prolog loops, DFID will loop as well;
therefore the use of DFID could be only restricted.

3. As Max says, the predicates would have to be divided into two
groups, ordered and unordered; this would be the case in any
non-sequential processing of the subgoals. If we allow ordered
predicates to call the unordered ones and vice versa then the
distribution of processors in a parallell execution is no more
so easy. There is maybe a simple solution to this problem, otherwise
one direction of calls between the two classes of predicates
must be forbidden - is it a significant restriction?

(I suspect anyway that this is another of George's attempts to bring
flames into net.lang.prolog, right? :-)

Micha