🚀 go-pugleaf

Well, if George was trying to trigger flaming, he's succeeded.  Strange that
two researchers at the same center should flame at each other via a
world-wide network, but I sincerely believe this is of general interest.

Micha's comments aren't all wrong, but they certainly aren't 100% correct
either.  The big point he misses is this:
   If there is a branch of the tree to the left of the solution that is
   much deeper than the solution, but still finite, DFID is more efficient
   than depth-first search.

This -- not questions of completeness -- is the argument for DFID which
interests me.  Naturally this case only arises in some class of programs, but
that's the point -- I'm curious whether that class of programs is
interesting.

The point about ordered and unordered predicates calling each other is a bit
confused.  In reality there is no problem.  If an unordered predicate calls
an ordered predicate, and that ordered predicate fails because its execution
was truncated, some solutions to the unordered predicate are lost -- but
this doesn't matter.  If an ordered predicate calls an unordered predicate,
and the execution is truncated, the outer ordered' predicate fails, because of
the general rule I proposed in my last note.  Thus the right thing always
happens.

Much of the time all the programmer wants is one solution, any solution.  In
this case it doesn't matter whether it is the leftmost or shallowest (=
"optimal").  If we can get the shallowest faster than the leftmost (or if
they are the same, and we can get it faster by looking for the shallowest),
than that's good.

Naturally if you really want all solutions, DFID has nothing to offer.  This
can be viewed as a consequence of my execution rule for bagof.

By the way, the proposed modified Prolog does not offer one control
structure DFID can support that has been proposed in the context of other
parallel Prologs: an unordered, one-solution predicate.