Path: utzoo!attcan!uunet!munnari.oz.au!goanna!ok
From: ok@goanna.cs.rmit.oz.au (Richard A. O'Keefe)
Newsgroups: comp.lang.prolog
Subject: Re: Why prolog uses depth-first search ?
Message-ID: <4212@goanna.cs.rmit.oz.au>
Date: 6 Nov 90 09:34:47 GMT
References: <1990Nov5.182613.1571@watserv1.waterloo.edu>
Organization: Comp Sci, RMIT, Melbourne, Australia
Lines: 31

In article <1990Nov5.182613.1571@watserv1.waterloo.edu>, yfeng@watnow.waterloo.edu (Feng Yang) writes:
> (1) Why does prolog use depth-first, left-to-right search ?  

When you come right down to it, the answer is "because THAT is what
gave us the procedural interpretation of Prolog in the first place",
that is precisely the thing that made Prolog usable as a programming
language.

> but it also gives a lot of troubles such that two logical equivalent
> program are not always equivalent in prolog. e.g the well know "repeat":

I don't know any programming language in which it is impossible to find
logically equivalent programs which are behaviourally different (at least
in the sense of taking greately different amounts of time and/or space).
(Yes, I do know about lazy functional languages.  They're the ones I had
in mind where it's easy to find gross cost differences between equivalent
programs.)

> Any other justifications except the memory consideration ?

Breadth-first search can require EXPONENTIALLY more memory than
depth-first search, to the point that breadth-first search on non-trivial
problems is almost always completely infeasible.  We are talking about
ENORMOUS differences here.
On the other hand, it is trivially easy to do iterative deepening in
Prolog (see "The Craft of Prolog" plug plug), which gives you the safety
of breadth-first search with the efficiency of depth-first.

-- 
The problem about real life is that moving one's knight to QB3
may always be replied to with a lob across the net.  --Alasdair Macintyre.