Path: utzoo!attcan!uunet!zaphod.mps.ohio-state.edu!van-bc!ubc-cs!news-server.csri.toronto.edu!utgpu!watserv1!watnow.waterloo.edu!yfeng
From: yfeng@watnow.waterloo.edu (Feng Yang)
Newsgroups: comp.lang.prolog
Subject: Why prolog uses depth-first search ?
Message-ID: <1990Nov5.182613.1571@watserv1.waterloo.edu>
Date: 5 Nov 90 18:26:13 GMT
Sender: daemon@watserv1.waterloo.edu
Organization: University of Waterloo
Lines: 37


Hi there, I am novice in Logic programming.  If the following
questions are too naive to put on the net, please forget me.

(1) Why does prolog use depth-first, left-to-right search ?  

I understand that this approach probably requires least memory, 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":

repeat.
repeat :- repeat.

will alway suceed, while

repeat :- repeat.
repeat.

will not.

This kind of problems can be partially remedied by just use
wedth-first search !

Any other justifications except the memory consideration ?

(2). I would like to know any work on proving two prolog program
eqivalent (or not), or one program is subset of another.

Thank you very much.

Feng


--
|---------------------------------------------------------------------------|
| Feng Yang                                                                 |
|---------------------------------------------------------------------------|