Transforming a sentence creates an infinite loop - but how?

Question

I can't figure out where this is going wrong. Please note that I am very new to Prolog and I'm sure I'm missing something - just no idea what that might be. Could anyone help me out please?

Thanks, here is my code:

printSentence([]).   
printSentence([W|[]]) :-
    write(W),
    write('.'),
    nl.  
printSentence([W|R]) :-
    write(W),
    write(' '),
    printSentence(R).

transform([], Result).  
transform([Word|Rest], Result) :-
    replace(Word, Replacement),
    append(Result, Replacement, NewResult),
    transform(Rest, NewResult).

replace(my, your).
replace(i, you).
replace(you, me).
replace(am, are).
replace(Word, Word).

test :-
    X = [you, are, my, only, hope],
    transform(X, Result),
    printSentence(Result).

Answer 1

This should work. Notice you had a singleton in transform([],Result). Also, append doesn't work in the way you tried to use it, but you were on the right track generally.

transform([], []).

transform([Word|Rest], [Replacement|RestOfResult]) :-
    replace(Word, Replacement),
    transform(Rest, RestOfResult).

Answer 2

@Junuxx' answer is one step to the solution ; there is also another problem in your program. But first step back: @Junuxx spotted the problem and fixed it. Nice. But how can you spot such a problem? Actually, you asked »infinite loop – but how?«

What is cool in Prolog is that you can often localize the looping program up to a very tiny fragment of the program. Such a fragment is called a failure-slice. That is: No more eye-sores reading lengthy programs!

Let's get back to your program. If you load it, you will get a message like:

Warning: /usager/SO/paranoid.pl:13:
    Singleton variables: [Result]

Which gives you already a hint on something most probably wrong. Alas, this is not your biggest concern for the moment. Your biggest problem is that the goal test loops!

Localizing non-termination

So how can you with low effort realize what is actually looping?

One way would be to fire up a tracer, which will show you step-by-step how Prolog executes this program. However, the tracer will show you a lot of irrelevant detail. Detail, that you do not need to understand when programming in Prolog. Detail, that fills up your mind such that chances are that you will miss the actual problem completely. So unless you want to spend time on screens full with flickering lines, stay away from tracers.

The other way is to add goals false into your program. Remember, your program loops already, so such extra goals will not hurt you much. Why vandalize your program with these false goals that you never wanted to write in the first place? It's because these false goals will help you detect the culprit of non-termination in your program by hiding "irrelevant" parts. This is so, thanks to the following observation:

If a failure-slice (= your vandalized program) does not terminate then the original program does not terminate either.

In a sense, the failure-slice is a reason why your program does not terminate. Or to put it more strongly: As long as you do not change the visible part in a failure-slice ; that is, as long as you are only trying your luck by modifying parts that are not visible in the failure slice, the problem will persist! Guaranteed! That is not the nicest kind of guarantee but it is better than being blind.

Here is what I get as a failure slice. I removed printSentence/1 because it is no longer used in the fragment. And I added the definition of append/3. Some Prologs offer append/3 as a built-in predicate that you cannot modify. In that case use another name, like local_append/3 – just don't forget to replace all occurrences!

append([], Zs, Zs) :- false.
append([X|Xs], Ys, [X|Zs]) :-
   append(Xs, Ys, Zs), false.

transform([], Result) :- false.
transform([Word|Rest], Result) :-
    replace(Word, Replacement),
    append(Result, Replacement, NewResult), false,
    transform(Rest, NewResult).

replace(my, your) :- false.
replace(i, you) :- false.
replace(you, me).
replace(am, are) :- false.
replace(Word, Word) :- false.

test :-
    X = [you, are, my, only, hope],
    transform(X, Result), false,
    printSentence(Result).

When I load this failure-slice, I get:

?- test.
ERROR: Out of local stack

Which is a good indication that the program does not terminate. On my finite hardware it exhausts all resources instead. ((To be pedantic, this program might still terminate, it might only need too much resources. But remember: We have this if failure-slice loops, then the entire program loops. In any case, proving non-termination of the failure-slice will often be easier, since the fragment is shorter)).

Some observations: Originally, transform/2 used to be recursive. Now, it no longer is. The only recursion left is within append/3. So I first look at the goal append(Result, Replacement, NewResult) and I try to figure out what the variables might be. The easiest is the 3rd argument: NewResult is the only occurrence in our fragment, we can thus replace it by _. The second argument's variable Replacement will always be me. And the first argument (here I have now to look at test/0) will be an uninstantiated variable. So we have to consider the goal append(_, me, _).

Simply run append(_, me, _), false to see that this goal does not terminate! You can see this also by inspecting the failure-slice. Here is it, again:

append([], Zs, Zs) :- false.
append([X|Xs], Ys, [X|Zs]) :-
   append(Xs, Ys, Zs), false.

Look at Ys: Nobody cares about it, it is just "handed over". Only the first and the third argument might guarantee termination!

For more see the tag failure-slice.

---

Fine print

_{Certain restrictions apply! Void where prohibited! You can do above reasoning only with a pure, monotonic Prolog program. Actually, some benign side-effects as the ones you have in your program are OK too. As long as they do not affect the control-flow.}

---

The other problem

There is another problem with your program. Run printSentence([you]), false to see it! Backtracking and side-effects do not flock together easily. For a beginner, the best is to avoid side-effects all together. See this question and that answer for an example, how to remove useless side-effects in programming problems. Why not call transform([you, are, my, only hope], Xs) or maplist(replace,[you, are, my only, hope], Xs) directly? It lets you again concentrate on the relevant parts!