Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP Path: utzoo!watmath!clyde!burl!ulysses!allegra!mit-eddie!genrad!panda!husc6!harvard!seismo!mcvax!unido!ecrcvax!max From: max@ecrcvax.UUCP (Max Hailperin) Newsgroups: net.lang.prolog Subject: Re: Depth First Iterative Deepening in parallel PROLOGs Message-ID: <235@ecrcvax.UUCP> Date: Wed, 28-May-86 10:57:47 EDT Article-I.D.: ecrcvax.235 Posted: Wed May 28 10:57:47 1986 Date-Received: Fri, 30-May-86 09:14:23 EDT References: Reply-To: max@ecrcvax.UUCP (Max Hailperin) Organization: ECRC, D-8000 Muenchen 81, W. Germany Lines: 37 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.