Path: utzoo!utgpu!news-server.csri.toronto.edu!cs.utexas.edu!sun-barr!decwrl!ucbvax!bloom-beacon!eru!hagbard!sunic!mcsun!unido!uklirb!powers From: powers@uklirb.informatik.uni-kl.de (David Powers ) Newsgroups: comp.lang.prolog Subject: Re: Why prolog uses depth-first search ? Message-ID: <7101@uklirb.informatik.uni-kl.de> Date: 9 Nov 90 11:05:25 GMT References: <1990Nov5.182613.1571@watserv1.waterloo.edu> <4212@goanna.cs.rmit.oz.au> Organization: University of Kaiserslautern, W-Germany Lines: 108 ok@goanna.cs.rmit.oz.au (Richard A. O'Keefe) writes: >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. YES and NO! It is not the only possible control structure that allows a procedural interpretation, and it is not even the best. It was one of the simplest to implement and it does admit significant optimization for efficient execution. In fact there are control strategies which for many programs can execute with a number of inference steps logarithmic (or better) in that taken by Prolog (see my (Powers) CONG work, or Tarnlund et al's REFORM work). Kowalski defined Logic Programming as "Logic + Control". But SOMETIMES the control requirements become too much in PROLOG and lead to obscuring of the declarative semantics, simulation of another control structure, etc. This negates the advantages of compilation and optimization IN THESE CASES. >> 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.) Logical equivalence is very broad and it is always possible to add work which will impact efficiency but not results. Executing a cut-free Prolog program in non-SLD ways will natural be influenced by search order. (SLD is the top-down left-to-right PROLOG control.) Research is proceeding steadily on ways of better executing declaratively nice programs with unfortunate SLD behaviour. This includes work by Naish with delays; Warren and Pereira with goal reordering; Verschaetse, De Schreye and Bruynooghe with manual or automatic selection of an alternative strategy (by rewriting before executing with SLD), and my (Powers) work on programming in a theorem prover guided by heuristics. In particular it is possible for such techniques to eliminate the pathological and undesirable executions for at least some classes of examples. >> 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. Iterative deepening is a useful compromise. But it should also be noted that the characterization "breadth-first" admits some variations. The search "tree" has actually two dimensions. These correspond to the "left-to-right" and the "top-down" of SLD - the AND dimension of working on a consistent set of subgoals in some order, and the OR dimension of working on the alternate elaborations of a subgoal in some order. The possibilities for breadth-first search correspond to those of Parallel Logic Programming known as AND-parallelism and OR-parallelism (or the combination thereof). A "usual" definition of breadth-first is that new subgoals are added at the end of a QUEUE rather than the beginning of a STACK. This corresponds to the AND dimension and CAN still be implemented with a form of backtracking obviating a space explosion. The replacement of OR backtracking by elaborating a disjunctive set of bindings or constraints can be implemented independently of the above sort of breadth-first search. A full breadth-first search can require exponential space in the length of the "proof". The time for a cut-free program will not necessarily be worse as the whole search space will be explored. But the addition of an appropriate (e.g. oracular) control heuristic can bring EITHER back to linear. But I reiterate, there are yet other control strategies. I think the aim of Logic Programming should be to increasingly give the programmer the freedom to progam declaratively without having to worry about control, and to allow the intransigence to be handled by high level introduction of heuristics. Logic Programs without a great deal of blind search should be able to have their control supplied efficiently and cheaply through analysis. Artificial Intelligence applications, which can really make use of the fact that we actually have a Theorem Prover at our disposal, should perhaps rely on a new maxim: Artificial Intelligence = Logic + Heuristics ------------------------------------------------------------------------ David Powers +49-631/205-3449 (Uni); +49-631/205-3200 (Fax) FB Informatik powers@informatik.uni-kl.de; +49-631/13786 (Prv) Univ Kaiserslautern * COMPULOG - Language and Logic 6750 KAISERSLAUTERN * MARPIA - Parallel Logic Programming WEST GERMANY * STANLIE - Natural Language Learning Riddle: What is the difference between the university and me. Disclaimer: My opinion.