Help with append/3 infinite loop with explicit arguments

Help!
1

I’m using: Swish

I was showing someone interesting features of prolog and started with bidirectional append. Since the standard way with unification in the arguments looks unfamiliar
to people, I made the arguments explicit, and created an infinite loop. Tracing did
not get me anywhere, I can see the lists are getting larger with unbound variables,
but I don’t know Prolog well enough to see why.

Could someone please explain what is happening append2 and append3 below,
and ideally, how I could have discovered it using Swish visualizations?

My initial example and variations are as follows.

       % standard append
       append1([], R, R).
       append1([H | T], R, [H | O]) :- append1(T, R, O).

       % infinite loop. Why?
       append2([], R, R).
       append2(L, R, O) :- L = [H | T],  append2(T, R, O1), O = [H | O1].

       % similar, but does not infinite loop. Due to  binding order??
       append3([], R, R).
       append3(L, R, O) :- L = [H | T], O = [H | O1], append3(T, R, O1).

       % infinite loop happens with append2(X, Y, [1, 2, 3, 4, 5]),
2

I don’t know about the rest, but for sure goal ordering in a clause’s body counts…to make it work the recursive call should be the last

3

The page below claims “trace it to see what happens”, so it looks like a known issue. But I can’t tell from the tracing – tracing has too many unbound variables, and I could not figure it out. Hope someone can explain…

https://courses.cs.washington.edu/courses/cse341/12au/prolog/append.html

4

Nonetheless it delivers some expected results at the start, which surprises me because this thing is written so strangely that I wonder how it can at least get some of them right before looping

5

The reason I stumbled across this form is I was just typing as I was talking: first remove the head, then finish appending the tail, and stick the head back on the result. Operational-ish, but ought to be also logical, it seems to me.

7

I presume that the query that’s causing you an “infinite loop” (actually infinite backtracking) is append(A,B,[]) after the first result A=[],B=[].
This query is equivalent to C=[], append(A,B,C) but there’s a subtle difference from append(A,B,C), C=[].

Let’s try just append(A,B,C):

?- append(A,B,C).
A = [], B = [] ;
A = [_A], C = [_A|B] ;
A = [_A,_B], C = [_A,_B|B] ;
A = [_A,_B,_C], C = [_A,_B,_C|B] ;
   ...

After the first result, C can never unify with [], so backtracking just generates longer and longer results that all fail to unify with [].

1 Like
8

Because it’s calling itself without checking R or O. If L is var/1, it can extend in length into infinity.

Can be seen using trace/1, or gtrace/1, or just adding a writeln/1 to show the state of the variables.

This is the termination property of the program.

The program should be considering R and O, before looping, to be more informed of whether it is sensible to loop.

9

trace is showing so much noise due to all the unbound variables that I can’t really see the flow. I will try writeln and try to see what is going on.

10

The infinite backtracking is caused by query above, not by putting [] as the last argument. My append2 produces all the correct answers and the loops as shown below.

image

11

Here is an example of using writeln/1, and also sleep/1 to slow it down to human speed:

append2d([], R, R).
append2d(L, R, O) :-
    L = [H | T],
    writeln(L),
    sleep(1),
    append2d(T, R, O1),
    O = [H | O1].

?- append2d(A, [b], [a,b]).
[_4300|_4302]
A = [a] ;
[_5552|_5554]
[_5560|_5562]
[_5568|_5570]
[_5576|_5578]
... to infinity.
12

Thanks. I did the following ugly thing to see the behavior (a nicer way to print variable names and values would be most welcome) and stop after 6 steps.

But it let me see that after getting P=[1,2,3] and Q=, the remaining empty O= does not have a base case of the recursion as a stopping condition and keeps unifying longer and longer unbound lists.

dbw(M, X) :- write(M), write('='), writeln(X).

append22([], R, R, N) :- N < 6.
append22(L, R, O, N) :- N < 6, M is N+1, dbw('N', N),
    L = [H | T],  dbw('L',L), dbw('H',H), dbw('T',T), writeln(' L --------------------'),
    append22(T, R, O1, M), dbw('T=',T), dbw('R',R), dbw('O1', O1), writeln('app -----------------'),
    O = [H | O1], dbw('O', O), dbw('O1', O1), writeln('O -------------').

?- append22(P, Q, [1, 2, 3], 1).
13

Did you try Tau-Prolog tree visualizer with limit=1, etc... on this query:

?- app(X,Y,[]).

It should only give X=[] and Y=[] (green), but it keeps running after
the first solution. The reason is an infinite failure tree. Its not
the case that it would not combine []=O and O=[H| O1] into

a failure (red). But O1 gets larger and larger through backtracking and
recursive call (violet). You can avoid that if the failure comes before the call,
i.e. changing your code and moving the unification to the front of the call.

Download
Download1129×789 35.2 KB

Edit 31.08.2024
People might be worried that rearranging goals has such a dramatic
effect, but this is just one of the many effects of the incompleteness
of strict left to right SLD(NF) Resolution as used by Prolog.

14

Didn’t know that! The Tau Prolog visualization is very pretty, I tried it out. Also will help explain other simpler programs.

Within textual Prologs, is there some facility to print say all the variables in some clause e.g. show(L, R, H, T, O1, O) which prints all of them as "L = termvalue, R = termvalue … " etc? Or do I just prettify my initial debug printer piecemeal?

15

That’s only level 1 of Prolog programming and debugging, whilst still learning the fundamentals of the language.

This relates to the art of debugging in any programming language, and a Prolog program in particular.

If my code doesn’t work, I mostly try kinda-simultaneously:

  • Identify most-likely sources of the error (knowing common gotchas, and knowing which code portions I haven’t already scrutinized, etc.)
  • Zero in on the error, using e.g. writeln/1 to show crucial variables at crucial points
  • Produce my own minimal, reproducible example
16

Its the “Prolog in particular” bit because of its unusual control flow and variable binding discipline.

Usual imperative and eager functional have simpler control flows that we all have experience with so its easy to do binary searches to locate problems, create minimal examples, etc.

But like in the example I stumbled on, infinite unification is so unlike any other failures, and so unusual (and interesting!).

17

Are you stuck with Swish or can you run real Prolog somehow? At the very least, you will have access to the tracer and debugger.

18

A quick explanation.
This program with a query append2(variable,variable,anything)
invokes append2 with three variable arguments. The latter has infinitely many answers. So the computation for the initial query does not terminate.

19

On the other hand, in the recursive call of append3 the third argument is a (proper) subterm of that in the initial query. Thus if the third argument of the initial query append3(…,…,…) is ground (e.g. a list) the computation will terminate.