Recursion and completion of Prolog

Question

StackOverflow first question.

I write a predicate in a prolog that takes three parameters. This is (respectively) a character, a list of lines, and the last parameter is a list of all lines in the second parameter, starting with the first parameter. My recording statements are a substitute for my complete lack of knowledge on how to track in SWI-Prolog. Anyway, to the code!

---

startString(C, [H1|T1], [H2|T2]) :- atom_chars(H1, [C| _ ]), H2 = H1, startString(C, T1, T2). startString(C, [ _ |T1], Y) :- startString(C, T1, Y), write(foo). startString(_, [], []) :- write(foo). 

---

What outputs:

---

 foofoofoo X = [some, simple] 

---

My methodology is correct, but the predicate does not end (the absence of a period after writing X is not an error). My question is why? Of the limited recursion examples I found on the Internet, the third version of my predicate should break the predicate and make x a definite answer.

When I press the enter button, I can enter another query, but I have the same small “problem” in another predicate that I wrote in the same program. Any help with this predicate should also be transferred to another. Thanks!

Answer 1

To expand your question in your comments to @ScottHunter,

I think my question is why do my other predicates “Know”, do they have the correct answer, while this and another one do not?

The answer is related to the presence of selection points on the stack. Consider this situation:

 reasonably_big(L, X) :- member(X, L), X > 100. ?- reasonably_big([105, 2], X). X = 105 ; false. ?- 

Compare this to this:

 ?- reasonably_big([2, 105], X). X = 105. ?- 

In the second case, Prologue “knew” that there were no more solutions; in the first case this is not so. The difference between these two situations is that in the first case, member left the selection point on the stack: there was one more element in the list that he could consider to find another answer. In the second case, the rest of the list was empty, and the SWI-Prolog member is smart enough not to leave the selection point on the stack in this case, so he never asked you if you want another solution.

If you get extraneous selection points, this often indicates a logical error. For example, consider this definition of min :

 min(X, Y, X) :- X =< Y. min(X, Y, Y). 

This is inferior, because you can always step back and get a different value; to wit:

 ?- min(3,4, X). X = 3 ; X = 4. 

The second solution is wrong. But you can still encounter an unnecessary choice by making the wrong improvement:

 min(X, Y, X) :- X =< Y. min(X, Y, Y) :- Y =< X. 

See what happens when we try different values:

 ?- min(4,3,X). X = 3. ?- ?- min(3,4,X). X = 3 ; false. ?- 

The first one worked fine, and the second left the selection point on the stack, having the second body. You can fix it with a green cut:

 min(X,Y,X) :- X =< Y, !. min(X,Y,Y) :- Y =< X. ?- min(3,4,X). X = 3. ?- ?- min(4,3,X). X = 3. ?- 

The abbreviation captures Prolog for a specific solution. It says that after you have done this here, there is no need to use any other solutions for this predicate, because we have found the only thing we want. Understanding how to apply a slice is a complex topic, but eliminating unwanted selection points is an important use.

Answer 2

You have to be careful what you mean by “termination” in Prolog. The fact that you got the value associated with X when you asked the prolog to prove that startString ('s', some-list, X) means that it is complete (otherwise it will still look for the value for X). But in another sense, this is not so, because you can ask (usually insert a half-time) Prolog to try to find another solution, and you can continue to ask until it runs out of possibilities. It looks like your console is waiting for you to say if you want to try to find another solution or what you did (what happens when you press enter, and the interpreter allows you to enter a new query).