Prolog Recursion and Termination

Question

first StackOverflow question.

I'm writing a predicate in prolog that takes three parameters. These are (respectively) a character, a list of strings, and the last parameter is a list of all the strings in the second parameter that start with the first parameter. My write statements are a substitution for my complete lack of knowledge on how to trace in SWI-Prolog. Anyway, on 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).

Which outputs:

foofoofoo

X = [some, simple]

My methodology is correct, but the predicate doesn't terminate (the lack of period after the write of X isn't a mistake). My question is, why isn't it? From the limited examples of recursion I've found on the internet, the third version of my predicate should terminate the predicate and make x a definite answer.

When I press enter I'm able to enter another query, but I have this same little "issue" in another predicate I wrote in the same program. Any help with this predicate should also carry over to the other. Thanks!

Daniel Lyons Daniel Lyons · Accepted Answer · 2012-02-16T22:55:48

To expand on your question in your comments to @ScottHunter,

I guess my question is, why do my other predicates "Know" they have the right answer, while this and one more do not?

The answer has to do with the existence of choice 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 that to this:

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

In the second case, Prolog "knew" that there were no more solutions; in the first case it did not. The difference between these two situations is that in the first case member had left a choice point on the stack: there was still another item in the list it could consider to find another answer. In the second case, the remainder of the list was empty, and SWI-Prolog's member is smart enough to not leave a choice point on the stack in that case, so it never asked you if you wanted another solution.

If you're getting extraneous choice points, it often points to a logic error. For example, consider this definition of min:

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

This is defective, because you can always backtrack in and get the other value; to wit:

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

The second solution there is erroneous. But you can still wind up with an unnecessary choice point 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 but the second one left a choice point on the stack by having a second body. You can eliminate 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 cut commits Prolog to a particular solution. It says, once you've made it here, there's no need to try any other solutions for this predicate, because we've found the only one we want. Understanding how to apply the cut is a complex topic, but eliminating undesirable choice points is an important use.

Prolog Recursion and Termination

2 Answers