Prolog - infinite loop

Question

I want to check if element is in the middle of list. I search middle element and next I check if is a member of list, but I get infinite loop.

My predicates:

remove_first([_,H1|T], [H1|T]).

remove_last([_],[]).
remove_last([H|T], [H|T2]) :- remove_last(T, T2).

remove_first_and_last([X],[X]).
remove_first_and_last(In, Out) :- 
    remove_first(In, Out1),
    remove_last(Out1, Out).

middle([X], [X]).
middle(In, X) :-
    remove_first_and_last(In, Out),
    middle(Out, X).

member(X, [X|_]).
member(X, [_|T]) :- member(X, T).

is_middle(X, In) :-
    middle(In, Out),
    member(X, Out), !.

And when I call is_middle(1,[2,1,3]) then I get true. But when I call is_middle(1,[2,2,3]) then I don't get a result. Interpreter don't interrupt the processing.

Answer 1

In a situation as yours, you have two options. Either wade through walls of text of traces as you can see in another answer, or try to reduce first what you have to understand. I prefer the latter for I don't like to read much.

But your major problem is this. You said:

And when I call is_middle(1,[2,1,3]) then I get true.

Yes, Prolog found a solution, but it did not find it once but infinitely many times. Just hit SPACE or ; to see this:

?- is_middle(1,[2,1,3]).
   true
;  true
;  true
;  true
;  true
;  ... .

So, already your first query was problematic. The best way to observe this, is to add false to this query:

?- is_middle(1,[2,1,3]), false.
   loops.

Now, let's try to reduce the size of the query. We can narrow it down to:

?- is_middle(1,[1]), false.
   loops.

With this we can now look at your program. Before anything else I'll remove the cut. It is misplaced anyway.

To understand what is actually happening, I will narrow down your program by inserting false into it. With these extra goals it is possible to eliminate a lot of unnecessary detail. And still, the remaining program called a failure-slice is of relevance to us, if it is still looping.

remove_first_and_last([X],[X]).
remove_first_and_last(In, Out) :- false,
    remove_first(In, Out1),
    remove_last(Out1, Out).

middle([X], [X]) :- false.
middle(In, X) :-
    remove_first_and_last(In, Out),
    middle(Out, X), false.

is_middle(X, In) :-
    middle(In, Out), false,
    member(X, Out).

Compare this to your original program! Much less reading. To fix the problem you have to fix something in the remaining fragment. I suggest to remove the fact remove_first_and_last([X],[X]). This fact suggests that something is removed, but for this very case, nothing is removed.

---

For a solution using a dcg directly:

is_middle(E, Es) :-
   phrase(middle(E), Es).

middle(E) --> [E].
middle(E) --> [_], middle(E), [_].

That is as short as it can get, but it has a tiny problem: It does not compute the answer determinately. You can see this by looking at the answer:

?- is_middle(1, [2,1,3]).
   true
;  false.

This ; false is an indication that Prolog was not able to finish the computation determinately. In other words, some space is left. You might be tempted to use a cut. Resist!

---

If you are really into speed, take the fastest version:

is_middle(X, Xs) :-
   Xs = [_|Cs],
   middle_el(Cs, Xs, X).

middle_el([], [X|_], X).
middle_el([_,_|Cs], [_|Xs], X) :-
   middle_el(Cs, Xs, X).

---

In case you want @DanielLyons' interpretation which admits even-length lists to have two middle elements, see how easy it is to adopt above grammar definition. Simply add the following two rules:

middle(E) --> [E,_].
middle(E) --> [_,E].

Alternatively, combine all four rules into one:

middle(E) --> [E] | [E,_] | [_,E] | [_], middle(E), [_].

For the fastest solution, things are a bit more complex ...

is_middle_dl(X, Xs) :-
   Xs = [_|Cs],
   middle_el_dl(Cs, Xs, X).

middle_el_dl([], [X|_], X).
middle_el_dl([_|Cs], Xs, X) :-
   middle_el_dl2(Cs, Xs, X).

middle_el_dl2([], [A,B|_], X) :-
   ( X = A ; X = B ).
middle_el_dl2([_|Cs], [_|Xs], X) :-
   middle_el_dl(Cs, Xs, X).

To check it, I use:

?- length(Xs, N), N mod 2 =:= 0, is_middle_dl(X, Xs).
   Xs = [X,_A], N = 2
;  Xs = [_A,X], N = 2
;  Xs = [_A,X,_B,_C], N = 4
;  Xs = [_A,_B,X,_C], N = 4
;  Xs = [_A,_B,X,_C,_D,_E], N = 6
;  Xs = [_A,_B,_C,X,_D,_E], N = 6
;  Xs = [_A,_B,_C,X,_D,_E,_F,_G], N = 8
;  Xs = [_A,_B,_C,_D,X,_E,_F,_G], N = 8
;  Xs = [_A,_B,_C,_D,X,_E,_F,_G,_H,_I], N = 10
;  Xs = [_A,_B,_C,_D,_E,X,_F,_G,_H,_I], N = 10
;  ... .

Answer 2

Debugging Prolog takes some different skills, so let's take the long road there.

First, let's notice something interesting about your two sample queries. The first one succeeds, and it should; the second one should fail, but instead it loops. This tidbit is a clue: it suggests that we're trying to handle a false case. This is a common mistake among people using Prolog after other languages. In Prolog, it's often enough to be explicit about successful cases and just let failures happen through failed unifications.

The standard tool for debugging Prolog is trace/0. The idea is, you activate trace mode and then run your query, like this:

?- trace,  is_middle(1,[2,2,3]).

The trouble with trace/0 is that it can take some effort to understand what's happening with it. Each line starts with one of these four verbs: call, exit, redo, or fail. Then there's a number which indicates the nesting level of the call. The call and redo verbs tell you that you're entering a computation; exit and fail tell you a computation is ceasing and the nesting level is about to decrease. Call/exit are the normal case, fail/redo are what makes Prolog special, the non-determinism. In general, an infinite loop will look like some prefix of meaningful work (or possibly not) followed by an endlessly repeating chunk of output from trace. And we see that here. Prefix:

Call: (8) is_middle(1, [2, 2, 3]) ? creep
Call: (9) middle([2, 2, 3], _G1194) ? creep
Call: (10) remove_first_and_last([2, 2, 3], _G1194) ? creep
Call: (11) remove_first([2, 2, 3], _G1194) ? creep
Exit: (11) remove_first([2, 2, 3], [2, 3]) ? creep
Call: (11) remove_last([2, 3], _G1197) ? creep
Call: (12) remove_last([3], _G1190) ? creep
Exit: (12) remove_last([3], []) ? creep
Exit: (11) remove_last([2, 3], [2]) ? creep
Exit: (10) remove_first_and_last([2, 2, 3], [2]) ? creep

Repeating chunk:

Call: (10) middle([2], _G1200) ? creep
Exit: (10) middle([2], [2]) ? creep
Exit: (9) middle([2, 2, 3], [2]) ? creep
Call: (9) member(1, [2]) ? creep
Call: (10) member(1, []) ? creep
Fail: (10) member(1, []) ? creep
Fail: (9) member(1, [2]) ? creep
Redo: (10) middle([2], _G1200) ? creep
Call: (11) remove_first_and_last([2], _G1200) ? creep
Exit: (11) remove_first_and_last([2], [2]) ? creep

Now you can see it would be much easier to trigger the bad behavior just with this query:

[trace]  ?- is_middle(2,[3]).
   Call: (7) is_middle(2, [3]) ? creep
   Call: (8) middle([3], _G398) ? creep
   Exit: (8) middle([3], [3]) ? creep
   Call: (8) member(2, [3]) ? creep
   Call: (9) member(2, []) ? creep
   Fail: (9) member(2, []) ? creep
   Fail: (8) member(2, [3]) ? creep
   Redo: (8) middle([3], _G398) ? creep
   Call: (9) remove_first_and_last([3], _G398) ? creep
   Exit: (9) remove_first_and_last([3], [3]) ? creep
   Call: (9) middle([3], _G401) ? creep
   Exit: (9) middle([3], [3]) ? creep
   Exit: (8) middle([3], [3]) ? creep
   Call: (8) member(2, [3]) ? creep
   Call: (9) member(2, []) ? creep
   Fail: (9) member(2, []) ? creep
   Fail: (8) member(2, [3]) ? creep
   Redo: (9) middle([3], _G401) ? creep

Now it should be clear that the problem has to do with the interplay of middle/2, remove_first_and_last/2 and member/2. Your definition of member/2 is exactly the standard definition so it probably isn't to blame. Now, interestingly, you have middle/2 calling both itself and remove_first_and_last/2. And both middle/2 and remove_first_and_last/2 have an identical clause: m([X], [X]).

This kind of thing is a great generator of infinite recursion, because the first thing middle/2 does in its second clause is exactly what it just tried to do and failed with its own first clause. So it can find itself entering a recursive call in the second clause with exactly the same state it had in an earlier failed call to itself.

The solution is to look at remove_first_and_last/2 and realize that your first clause there does not actually remove the first and last element. Removing the remove_first_and_last([X], [X]) clause fixes the code:

[trace]  ?- is_middle(2,[3]).
   Call: (7) is_middle(2, [3]) ? creep
   Call: (8) middle([3], _G398) ? creep
   Exit: (8) middle([3], [3]) ? creep
   Call: (8) member(2, [3]) ? creep
   Call: (9) member(2, []) ? creep
   Fail: (9) member(2, []) ? creep
   Fail: (8) member(2, [3]) ? creep
   Redo: (8) middle([3], _G398) ? creep
   Call: (9) remove_first_and_last([3], _G398) ? creep
   Call: (10) remove_first([3], _G398) ? creep
   Fail: (10) remove_first([3], _G398) ? creep
   Fail: (9) remove_first_and_last([3], _G398) ? creep
   Fail: (8) middle([3], _G398) ? creep
   Fail: (7) is_middle(2, [3]) ? creep
false.

Both your tests also now work:

?- is_middle(1,[2,1,3]).
true.

?- is_middle(1,[2,2,3]).
false.

I think you added the base case here out of a sense of duty to have one. But the reality is that if you have a list of one element, it should fail to unify with remove_first_and_last/2 under any circumstance. This is very similar to handling an error case explicitly with Prolog, which tends to interfere with the working of the machinery.

Now, one thing that's missing is, how do you want to handle even-length lists? What you have right now won't, with or without my change. Even-length lists don't have a middle element; is that what you intend? I suspect it isn't, because of the appearance of member/2 in is_middle/2.

Comments on is_middle/2

What you have here could be restructured like so:

is_middle(X, In) :- middle(In, [X]).

Usage of member/2 isn't buying you anything because middle/2 can't ever produce a non-singleton list in its second argument. But, if it did, because you had even-length lists, it would be profitable. You could even make this code work that way by adding a third clause to middle/2:

middle([X,Y], [X,Y]).

Now see middle/2 works on even-length lists like so:

?- middle([2,1,3,4], X).
X = [1, 3] ;
false.

Now the cut gets you into trouble though. For instance, 1 and 3 are both is_middle/2:

?- is_middle(1, [2,1,3,4]).
true.

?- is_middle(3, [2,1,3,4]).
true.

Unfortunately though, if you ask for middle elements, you just have 1:

?- is_middle(X, [2,1,3,4]).
X = 1.

What happened to 3? You prevented it from being generated with your cut. I am not sure why the cut is here. I think you must have put it in to try and control the infinite recursion, but it doesn't help you, so get rid of it.

Debugging by random addition of cuts is generally not a great idea. A much better approach is using Ulrich Neumerkel's failure slice approach (see this paper or search the tag for more information).

DCG bonus

You can rephrase remove_first_and_last/2 as a DCG rule:

remove_first_and_last --> remove_first, remove_last.

Pretty cool, huh? :) That's because the kind of input/output threading you're doing in that rule exactly what DCG rules get transformed into.

Summary of changes

remove_first_and_last(In, Out) :- 
    remove_first(In, Out1),
    remove_last(Out1, Out).

middle([X], [X]).
middle([X,Y], [X,Y]).
middle(In, X) :-
    remove_first_and_last(In, Out),
    middle(Out, X).

Answer 3

is_middle(Item,List) :-
    append(Left,[Item|Right],List),
    length(Left,X),
    length(Right,X).

Complex solutions are bad solutions, my friend.

?- is_middle(X,[1,2,3,4,5]).
X = 3 ;
false.

Fully reversible predicate:

?- is_middle(3,L).
L = [3] ;
L = [_G13, 3, _G19] ;
L = [_G13, _G19, 3, _G25, _G28] ;