# Help with append/3 infinite loop with explicit arguments

**URL:** <https://swi-prolog.discourse.group/t/help-with-append-3-infinite-loop-with-explicit-arguments/7741>\
**Category:** Help!\
**Created:** [August 29, 2024, 6:29am UTC](https://swi-prolog.discourse.group/t/help-with-append-3-infinite-loop-with-explicit-arguments/7741 "2024-08-29T06:29:02Z")\
**Posts on this page:** 17\
**Page:** 1

<div class="post-metadata">

**Author:** ![asanay](https://avatars.discourse-cdn.com/v4/letter/a/3ec8ea/32.png) [@asanay](https://swi-prolog.discourse.group/u/asanay)\
**Post date:** [August 29, 2024, 6:29am UTC](https://swi-prolog.discourse.group/t/help-with-append-3-infinite-loop-with-explicit-arguments/7741/1 "2024-08-29T06:29:02Z")

</div>

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.

```prolog
       % 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]), 

```

---

<div class="post-metadata">

**Author:** ![anon419083](https://avatars.discourse-cdn.com/v4/letter/a/53a042/32.png) [@anon419083](https://swi-prolog.discourse.group/u/anon419083)\
**Post date:** [August 29, 2024, 7:50am UTC](https://swi-prolog.discourse.group/t/help-with-append-3-infinite-loop-with-explicit-arguments/7741/2 "2024-08-29T07:50:26Z")

</div>

> [@asanay](#):
>
> `% similar, but does not infinite loop. Due to binding order?`

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

---

<div class="post-metadata">

**Author:** ![asanay](https://avatars.discourse-cdn.com/v4/letter/a/3ec8ea/32.png) [@asanay](https://swi-prolog.discourse.group/u/asanay)\
**Post date:** [August 29, 2024, 9:28am UTC](https://swi-prolog.discourse.group/t/help-with-append-3-infinite-loop-with-explicit-arguments/7741/3 "2024-08-29T09:28:40Z")

</div>

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](https://courses.cs.washington.edu/courses/cse341/12au/prolog/append.html)

---

<div class="post-metadata">

**Author:** ![anon419083](https://avatars.discourse-cdn.com/v4/letter/a/53a042/32.png) [@anon419083](https://swi-prolog.discourse.group/u/anon419083)\
**Post date:** [August 29, 2024, 10:30am UTC](https://swi-prolog.discourse.group/t/help-with-append-3-infinite-loop-with-explicit-arguments/7741/4 "2024-08-29T10:30:00Z")

</div>

> [@asanay](#):
>
> ```prolog
> % infinite loop. Why?
> append2([], R, R).
> append2(L, R, O) :- L = [H | T], append2(T, R, O1), O = [H | O1].
> 
> ```

> [@asanay](#):
>
> `% infinite loop happens with append2(X, Y, [1, 2, 3, 4, 5])`

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

---

<div class="post-metadata">

**Author:** ![asanay](https://avatars.discourse-cdn.com/v4/letter/a/3ec8ea/32.png) [@asanay](https://swi-prolog.discourse.group/u/asanay)\
**Post date:** [August 29, 2024, 10:35am UTC](https://swi-prolog.discourse.group/t/help-with-append-3-infinite-loop-with-explicit-arguments/7741/5 "2024-08-29T10:35:41Z")

</div>

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.

---

<div class="post-metadata">

**Author:** ![peter.ludemann](https://yyz2.discourse-cdn.com/free1/user_avatar/swi-prolog.discourse.group/peter.ludemann/32/48_2.png) [@peter.ludemann](https://swi-prolog.discourse.group/u/peter.ludemann)\
**Post date:** [August 29, 2024, 10:56am UTC](https://swi-prolog.discourse.group/t/help-with-append-3-infinite-loop-with-explicit-arguments/7741/7 "2024-08-29T10:56:29Z")

</div>

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)`:

```prolog
?- 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 `[]`.

---

<div class="post-metadata">

**Author:** ![brebs](https://avatars.discourse-cdn.com/v4/letter/b/e9c0ed/32.png) [@brebs](https://swi-prolog.discourse.group/u/brebs)\
**Post date:** [August 30, 2024, 7:01am UTC](https://swi-prolog.discourse.group/t/help-with-append-3-infinite-loop-with-explicit-arguments/7741/8 "2024-08-30T07:01:56Z")

</div>

> [@asanay](#):
>
> ```prolog
> % infinite loop. Why?
> append2([], R, R).
> append2(L, R, O) :- L = [H | T], append2(T, R, O1), O = [H | O1].
> 
> ```

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](https://stackoverflow.com/a/27944482/17628336) of the program.

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

---

<div class="post-metadata">

**Author:** ![asanay](https://avatars.discourse-cdn.com/v4/letter/a/3ec8ea/32.png) [@asanay](https://swi-prolog.discourse.group/u/asanay)\
**Post date:** [August 31, 2024, 4:14am UTC](https://swi-prolog.discourse.group/t/help-with-append-3-infinite-loop-with-explicit-arguments/7741/9 "2024-08-31T04:14:21Z")

</div>

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.

---

<div class="post-metadata">

**Author:** ![asanay](https://avatars.discourse-cdn.com/v4/letter/a/3ec8ea/32.png) [@asanay](https://swi-prolog.discourse.group/u/asanay)\
**Post date:** [August 31, 2024, 4:20am UTC](https://swi-prolog.discourse.group/t/help-with-append-3-infinite-loop-with-explicit-arguments/7741/10 "2024-08-31T04:20:34Z")

</div>

> [@asanay](#):
>
> append2(X, Y, [1, 2, 3, 4, 5])

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](https://global.discourse-cdn.com/free1/uploads/swiprolog/original/2X/4/42c8da61d0e8d5feebeceaeafe2c8d8300860fa4.png)

---

<div class="post-metadata">

**Author:** ![brebs](https://avatars.discourse-cdn.com/v4/letter/b/e9c0ed/32.png) [@brebs](https://swi-prolog.discourse.group/u/brebs)\
**Post date:** [August 31, 2024, 9:07am UTC](https://swi-prolog.discourse.group/t/help-with-append-3-infinite-loop-with-explicit-arguments/7741/11 "2024-08-31T09:07:52Z")

</div>

> [@asanay](#):
>
> I will try writeln

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

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

```

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

```

---

<div class="post-metadata">

**Author:** ![asanay](https://avatars.discourse-cdn.com/v4/letter/a/3ec8ea/32.png) [@asanay](https://swi-prolog.discourse.group/u/asanay)\
**Post date:** [August 31, 2024, 12:02pm UTC](https://swi-prolog.discourse.group/t/help-with-append-3-infinite-loop-with-explicit-arguments/7741/12 "2024-08-31T12:02:16Z")

</div>

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.

```prolog
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).

```

---

<div class="post-metadata">

**Author:** ![asanay](https://avatars.discourse-cdn.com/v4/letter/a/3ec8ea/32.png) [@asanay](https://swi-prolog.discourse.group/u/asanay)\
**Post date:** [August 31, 2024, 3:37pm UTC](https://swi-prolog.discourse.group/t/help-with-append-3-infinite-loop-with-explicit-arguments/7741/14 "2024-08-31T15:37:06Z")

</div>

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?

---

<div class="post-metadata">

**Author:** ![brebs](https://avatars.discourse-cdn.com/v4/letter/b/e9c0ed/32.png) [@brebs](https://swi-prolog.discourse.group/u/brebs)\
**Post date:** [August 31, 2024, 7:37pm UTC](https://swi-prolog.discourse.group/t/help-with-append-3-infinite-loop-with-explicit-arguments/7741/15 "2024-08-31T19:37:10Z")

</div>

> [@asanay](#):
>
> Or do I just prettify my initial debug printer piecemeal?

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](https://stackoverflow.com/help/minimal-reproducible-example)

---

<div class="post-metadata">

**Author:** ![asanay](https://avatars.discourse-cdn.com/v4/letter/a/3ec8ea/32.png) [@asanay](https://swi-prolog.discourse.group/u/asanay)\
**Post date:** [September 1, 2024, 3:07am UTC](https://swi-prolog.discourse.group/t/help-with-append-3-infinite-loop-with-explicit-arguments/7741/16 "2024-09-01T03:07:55Z")

</div>

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!).

---

<div class="post-metadata">

**Author:** ![Boris](https://yyz2.discourse-cdn.com/free1/user_avatar/swi-prolog.discourse.group/boris/32/7486_2.png) [@Boris](https://swi-prolog.discourse.group/u/Boris)\
**Post date:** [September 1, 2024, 4:06am UTC](https://swi-prolog.discourse.group/t/help-with-append-3-infinite-loop-with-explicit-arguments/7741/17 "2024-09-01T04:06:39Z")

</div>

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](https://www.swi-prolog.org/pldoc/man?section=guitracer).

---

<div class="post-metadata">

**Author:** ![wlodr](https://avatars.discourse-cdn.com/v4/letter/w/dec6dc/32.png) [@wlodr](https://swi-prolog.discourse.group/u/wlodr)\
**Post date:** [September 2, 2024, 8:43pm UTC](https://swi-prolog.discourse.group/t/help-with-append-3-infinite-loop-with-explicit-arguments/7741/18 "2024-09-02T20:43:42Z")

</div>

> [@asanay](#):
>
> ```prolog
> append2([], R, R).
> append2(L, R, O) :- L = [H | T], append2(T, R, O1), O = [H | O1].
> 
> ```

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.

---

<div class="post-metadata">

**Author:** ![wlodr](https://avatars.discourse-cdn.com/v4/letter/w/dec6dc/32.png) [@wlodr](https://swi-prolog.discourse.group/u/wlodr)\
**Post date:** [September 2, 2024, 8:45pm UTC](https://swi-prolog.discourse.group/t/help-with-append-3-infinite-loop-with-explicit-arguments/7741/19 "2024-09-02T20:45:23Z")

</div>

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.
