🚀 go-pugleaf

Well, I've devoted the last three days to working on the idea of a
depth-first iterative-deepening Prolog, and it's potential for parallel
implementation.  The results are far from optimistic, particularly as far as
parallelism goes.

There are some applications which could be much more cleanly programmed in
DFID-prolog then normal Prolog.  (Read "programmed" as programmed with
realistic efficiency.) In particular, many puzzle-solving programs
fall into this category.  As far as I can tell, not much else does.

However, I also found that the DFID search can be quite cleanly programmed
in Prolog in a way that keeps the distinction between logic and control
fairly clear.

Thus, I would guess that DFID doesn't warrant a modified Prolog interpreter,
but rather merely inclusion in Prolog programmers' "bag of tricks."

I also discovered that (contrary to my original claims) parallel deepening
is *not* a good use for parallelism.  The reason is simple: almost all the
time in DFID search is in the last iteration (that's why DFID is
asymptotically optimal).  This means regardless of the depth of the search or
the number of processors available, DFPD's speedup over DFID can be at most
(1-1/b)^-2 (where b is the branching factor).  Don't be fooled into thinking
that for small b this is a significant speedup: this is merely saying that
for small b DFID performs especially poorly.

This means that even considering parallel processors, DFID is best
considered an option for Prolog programmers and not for Prolog implementors.