append(X, Y, Y) creates cyclic term

Discussion
1

This creates a cyclic term:

?- append(X, Y, Y).
X = [] ;
X = [_A],
Y = [_A|Y] ;
X = [_A, _B],
Y = [_A, _B|Y] ;

Can be fixed with:

append(L, R, A) :-
    (   R == A
    ->  L = [],
        % Loop through lengths of R
        append_(R, L, A)
    ;   L == A
    ->  R = [],
        append_(L, R, A)
    ;   append_(L, R, A)
    ).

append_([], L, L).
append_([H|T], L, [H|R]) :-
    append_(T, L, R).

… to instead produce:

?- append(X, Y, Y).
X = Y, Y = [] ;
X = [],
Y = [_] ;
X = [],
Y = [_, _] ;

Is this simply a bug with an easy fix, or does the cyclic term have a deliberate use?

2

Why is creating a cyclic term not the right thing to do here though?
The way I read append(X, Y, Y) declaratively is “Y is the list whose beginning is X and tail is Y”. An immediate consequence is that Y is cyclic unless X is empty (which is what we get with your suggested implementation).

3

I suppose my point is more that:

X can only be [], in that situation.

Looping with X increasingly long, is a pointless waste of time, doomed to failure.

4

I think this situation is too “normal” for (logic) programming to “fix”.

Not necessarily as it depends on the programmer’s intent. Some data structures may need a reference to themselves (but in most cases, they probably don’t).

So the question is: which way should have been the default? I guess the early Prolog programmers decided that cyclic terms should be possible by default.

1 Like
5

I believe that also in SWI-Prolog cyclic terms are allowed as default, though I have never seen a description in the document about such default.

6

There is the “occurs_check” flag, is that a kind of documentation? If you set it to true the append example leads to non-termination, but if set to error it just throws:

?- append(X, Y, Y).
X = [] ;
X = [_A],
Y = [_A|Y] ;
X = [_A, _B],
Y = [_A, _B|Y] . % and so on

?- set_prolog_flag(occurs_check, true).
true.

?- append(X, Y, Y).
X = [] ; % then non-termination

?- set_prolog_flag(occurs_check, error).
true.

?- append(X, Y, Y).
X = [] ;
ERROR: Cannot unify _1416 with [_1422|_1416]: would create an infinite tree
ERROR: In:
ERROR:   [11] lists:append([],[_1482|_1484],_1478)
ERROR:    [9] toplevel_call('<garbage_collected>') at /Applications/SWI-Prolog.app/Contents/swipl/boot/toplevel.pl:1173
ERROR: 
ERROR: Note: some frames are missing due to last-call optimization.
ERROR: Re-run your program in debug mode (:- debug.) to get more detail.
   Exception: (11) lists:append(_60, [_58|_66], _66) ? abort
% Execution Aborted
7

Yes, I know it as changable flag. However, the flag seems set as false as Default.

% swipl
Welcome to SWI-Prolog (threaded, 64 bits, version 9.1.11-5-gddaf93732)
SWI-Prolog comes with ABSOLUTELY NO WARRANTY. This is free software.

?- X=[a,X].
X = [a, X].
?- current_prolog_flag(occurs_check, F).
F = false.
8

Yes, exactly. I was however wondering, since you said,

would you consider the linked docs good enough description? Or maybe together with the docs for unify_with_occurs_check/2?

Either way, I was interested how exactly this flag (and its three possible values) interacts with the query posted by OP:

?- append(X, Y, Y).
9

I have checked, thanks. It seems enough to to say that cyclic terms are default for SWI-Prolog, though “error” value there is new to me, which looks for me too much kind for the prologer. I would rather insert “cyclic_term/1” for checking in stead.

10

I expect that, around 99% of the time, append/3 is being used with cyclic terms unintended and unwanted.

Sounds more sensible to rename append to e.g. append_cyclic, and then have append guard against unwanted cyclic terms.

11

I would suggest you use the occurs_check flag if you don’t want cyclic terms. It would be a huge change to work through all the textbook predicates, it will break things for the outliers, and finally, you can just flip a switch and achieve the same effect globally.

Is there a particular reason why the flag solution doesn’t work for you?

1 Like
12

I kind of like the fact that it comes with the, probably unexpected, cyclic solution :slight_smile: As cyclic terms are part of the normal Prolog term space, it is simply correct and (thus) I see no reason to make append/3 ugly.

About the flag, it has this intend:

  • false (default) traditional Prolog mode. Note that SWI-Prolog supports cyclic terms nearly everywhere where it makes sense and built-ins that do nor support them should raise an exception. Pure Prolog predicates tend to loop if they are not prepared to handle cyclic terms. They can be interrupted though.
  • true classical Herbrand universe, causing goals that try to create a cyclic term to fail. Can be really slow though. In practice, it works well for most programs, resulting in only a few percent slowdown. If I recall correctly, the worst case is exponential though. Note that cyclic terms are useful data structures and this mode rules them out. Some programs stop working.
  • error is meant to help debugging programs that accidentally create a cyclic term. It is by default enabled for the SWISH student profile. This profile also reduces the stack limit, such that buggy programs bail out quickly.
1 Like
13

Fair enough :slightly_smiling_face:

What would be a good name for my unsurprising append variant - maybe append_non_cyclic ?

14

Note you can get the output you desire using append/2.

?- append([X,Y],Y).
X = Y, Y = [] ;
X = [],
Y = [_] ;
X = [],
Y = [_, _] ;
X = [],
Y = [_, _, _] ;
X = [],

So maybe append_non_cyclic(X,Y,Z):-append([X,Y],Z).
works for you.

15

That’s a great point - append/2 and append/3 are inconsistent regarding X, Y, Y and whether a circular term is the result.

If circular terms are expected, isn’t append/2 buggy?