2
$\begingroup$

Explain what will happen if we try to evaluate the query “path(a,e).”. When the query was actually run, it kept looping.I used the following method. Is it correct?

When evaluating $path(Z,e)$, if $path(Z,e):-edge(Z,e)$ was chosen, it would have returned true since there is $edge(b,e)$. But why did the program choose the recursive rule? Or am I missing something here?

enter image description here

Another similar question was evaluated the same way,

enter image description here

Improve this question
$\endgroup$
5
  • 1
    $\begingroup$ I disagree with closing this as a programming question. At the level being asked about here, Prolog is a resolution system, and the behaviour of resolution systems is definitely computer science. $\endgroup$
    – David Richerby
    Jul 13, 2016 at 7:49
  • $\begingroup$ What have you tried? Where did you get stuck? We do not want to just do your (home-)work for you; we want you to gain understanding. However, as it is we do not know what your underlying problem is, so we can not begin to help. See here for a relevant discussion. If you are uncertain how to improve your question, why not ask around in Computer Science Chat? You may also want to check out our reference questions. $\endgroup$
    – Raphael ♦
    Jul 13, 2016 at 8:12
  • $\begingroup$ @Raphael Why don't you tell me where to post this question and explain why there is a tag named 'Prolog' here? And bdw I'm not asking for anybody to do my homework, I'm trying to understand the concept and want to know whether what I have understood is correct or not. Maybe you can try to read my question before copying and pasting the same comment in everything you see. I have already worked it out. $\endgroup$
    – Amy Cohen
    Jul 13, 2016 at 10:10
  • $\begingroup$ This question reads like "please explain the teacher's solution" to me which is not a mode we particularly like. Plus, you don't give attribution for the problem or the images. $\endgroup$
    – Raphael ♦
    Jul 13, 2016 at 10:56
  • $\begingroup$ @AmyCohen The misunderstanding, I think, comes from many other posters using pictures from books/etc. and just asking "explain those". Since this is (unfortunately) becoming too common here on CS, people here just assumed the pictures above to be not your solution (possibly misreading the first part of your question). In other words, you put too much effort in preparing your question :-P $\endgroup$
    – chi
    Jul 14, 2016 at 20:22

1 Answer 1

Reset to default
3
$\begingroup$

The order of clauses matters in Prolog: they are tried in order. So, the first clause is always tried first, and the second one would only be considered after the first clause fails. As you discovered, this never happens because the first gets stuck in a loop.

If Prolog used a breadth-first resolution algorithm, the clause order would not matter (but it would be far more consuming in terms of memory). Since instead SLD resolution is depth-first, the order does matter because of infinite paths which can lead to non-termination.

Improve this answer
$\endgroup$
2
  • $\begingroup$ Okay so in the first example, if the last rule was written before the first rule, it would give a result right? $\endgroup$
    – Amy Cohen
    Jul 13, 2016 at 10:13
  • $\begingroup$ Yes, because $edge(b,e)$ will be found first. $\endgroup$
    – chi
    Jul 13, 2016 at 10:15

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.