Why is append/3 considered an anti-pattern?

[jjtolton]

I have heard before that using append/3 is often considered an anti-pattern (in preference to list differences). I would have assumed using DCGs for list manipulation was faster, but I was surprised when I performed some benchmarking.

:- use_module(library(dcgs)).
:- use_module(library(clpz)).
:- use_module(library(time)).
:- use_module(library(lambda)).
:- use_module(library(clpz)).
:- use_module(library(lists)).


?- _+\(length(Xs, 100000), length(Ys, 100000), time(append(Xs,Ys,Zs))).
   % CPU time: 0.024s, 100_034 inferences
   true.

?- _+\(length(Xs,100000),length(Ys,100000), time(phrase((Xs,Ys), Zs))).
   % CPU time: 0.036s, 200_102 inferences
   true.

?- _+\(length(Xs,1),length(Ys,100000), time(phrase((Xs,Ys), Zs))).
   % CPU time: 0.025s, 100_103 inferences
   true.

?- _+\(length(Xs, 1), length(Ys, 100000), time(append(Xs,Ys,Zs))).
   % CPU time: 0.000s, 35 inferences
   true.

?- _+\(length(Xs,100000),length(Ys,1), time(phrase((Xs,Ys), Zs))).
   % CPU time: 0.028s, 100_103 inferences
   true.

?- _+\(length(Xs, 100000), length(Ys, 1), time(append(Xs,Ys,Zs))).
   % CPU time: 0.025s, 100_034 inferences
   true.

?- Last+\(bagof(X, (X in 0..10000, indomain(X)), Xs), time(append(_, [Last], Xs))).
   % CPU time: 0.003s, 20_034 inferences
   Last = 10000
;  % CPU time: 0.000s, 4 inferences
   false.

?- Last+\(bagof(X, (X in 0..10000, indomain(X)), Xs), time(phrase((...,[Last]), Xs))).
   % CPU time: 0.006s, 60_048 inferences
   Last = 10000
;  % CPU time: 0.000s, 8 inferences
   false.

/* - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
   
|         | append/3 | phrase/2 |
| xs/ys   |          |          |
|---------+----------+----------|
| 1/1e5   |        1 |      1e5 |
| 1e5/1   |      1e5 |      1e5 |
| 1e5/1e5 |      1e5 |      2e5 |
|---------+----------+----------|
| last-of |          |          |
| 1e5     |      2e4 |      6e4 |
   
- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - */

Is append/3 just unusually fast in Scryer or am I missing something? Why is append/3 considered an anti-pattern?

Edit: I wish I could select more than one answers, the response from @UWN is fantastic!

[triska]

Frequent use of append/3 in the same program or predicate may indicate that a portion of the code could benefit from DCGs.

For example, consider the task: "Does the list "hello there" contain the subsequence "eee"? Easy to express with DCGs:

?- phrase((...,"e",...,"e",...,"e",...), "hello there").
   true
;  false.

With append/3, it is also possible, though significantly more tedious and prone to errors. (Try it!)

Multiple uses of append/3 in a row can also lead to significantly increased asymptotic complexity compared to using DCGs. As an example, consider describing a longer text as a list of characters or tokens from multiple parts with DCGs, and contrast it to various different ways of using append/3.

Even a single use of append/3 is sometimes an opportunity to improve the code. For example:

?- Ts = "ello", Rs = [h|Ts].
   Ts = "ello", Rs = "hello".

No append/3 is needed here, yet sometimes I see the equivalent of this code in which append/3 is used.

Other than that, append/3 is an imperative name and suggests only a single direction of use even though the predicate is a very general relation with good termination properties in different modes.

[jjtolton]

Brilliant. I too sometimes and concerned that I am doing Prolog all wrong, but it is so interesting to learn why I am doing it all wrong!

I had not considered that it is not about the use of append/3 in isolation, but rather the use of it for building complex sequences that makes it an anti-pattern.

I have a feeling that these benchmarks are quite misleading. For instance, there are applications for which DCGs are very well suited -- I have a feeling that if you were to decompose such a problem, say, a parser, from DCGs into append/3, that the differences in runtime
complexity would be subsumed by the cyclomatic complexity (if it were
even possible to reformulate some of them as append/3).

[UWN]

It starts with incomplete and thus misleading documentation. Take any Prolog book or system and look up how append/3 is documented. It reads somehow like "appends two lists" or declaratively "append(Xs, Ys, Zs) is true if Zs is the concatenation of the lists Xs and Ys." With a magnifying glass you may spot the problem: It just says if and not iff. In fact, neither Ys nor Zs have to be lists to make append/3 true.

?- append(Xs, Ys, non_list).
   Xs = [], Ys = non_list.

A fully declarative description is quite contorted and makes append/3 look more like a single ripped out PNP transistor with its three legs staring into the air. Try to solder them together to form append3/4. All the chatbots get this wrong. No wonder with the used training material.

Contrast this to the non-terminal seq//1, which just describes a sequence. And, as long as you use phrase/2, there is no interference with non-list constructs. In its (internal) expansion seq//1 is exactly the same as append/3 up to the argument order. It's just the way it is used. So you could encode all of this with append/3, but you would have to maintain a bunch of auxiliary variables that are easily confused.

append3(Xs,Ys,Zs, XsYsZs) :-
   phrase((seq(Xs),seq(Ys),seq(Zs)), XsYsZs).

Concerning your examples you cannot compare phrase((Xs,Ys), Zs) and append(Xs,Ys,Zs). After all, Xs = {true}, Ys = [] as well as Xs = [], Ys = 27 produce different results. (And I suspect, this phrase((Xs,Ys), Zs) came from a maltrained Co-Pilot...)

The next problem is the operationalizing name which suggests that someone is appending here something. While this is true sometimes, in many uses it not true at all. And it's not just the inverse, like splitting a list in two parts. How do you call this here:

?- append(Xs, _, [a,b,c|Xs]).
   ... .

The power of names is often underestimated. They exert their full power when we are weak. Like in the moment when we "just fixing" this little issue not really worth our attention.

The most iconic anti-pattern use of append/3 is to encode grammars. In fact, prior to Prolog it was not clear how the parsing with a grammar can be seen as an efficient deduction process. Both a (context free) grammar as well as a set of clauses were describing a set of sentences (the language)/solutions. So it was straight forward to encode a non-terminal as a predicate with one argument. And naturally, concatenation would be encoded with append/3 (it was rather called conc):

s --> "a".
s --> t, u, v.

s("a").
s(S) :-
   append(T, UV, S),
   t(T),
   append(U,V, UV),
   u(U),
   v(V).

But no matter what refinement of resolution they tried, no matter how they reordered the goals, it was clear that parsing was extremely costly. And to generate sentences, another resolution method was needed. Still today one can see such feeble attempts to encode grammars. Only when the encoding using a pair of lists (or markers) was understood what we now call a difference, was Prolog born in the summer of 1972.

[jjtolton]

Legendary.

[jjtolton]

A fully declarative description is quite contorted and makes append/3 look more like a single ripped out PNP transistor with its three legs staring into the air.

🤣

(And I suspect, this phrase((Xs,Ys), Zs) came from a maltrained Co-Pilot...)

You are not entirely incorrect, although in this case the maltrained Co-Pilot was a human 😆 I was trying to remove as many intermediate pieces of machinery for comparison purposes as possible.

The power of names is often underestimated. They exert their full power when we are weak.

🫨 😮 🫨 😮 🫨 😮

[jjtolton]

I have never before encountered a language where the design runs so deep. It is almost like every predicate has its own history associated with it. Usually I can infer/predict the reasoning behind design choices as most "production" languages are quite similar. But here it is always a surprise and a delight, even with questions that seem so simple!

[UWN]

@haijinSk, you are permanently posting and quickly removing your questions. This is quite irritating. Why prepare an answer, if you remove your post anyway?

[haijinSk]

Thank you very, very much!!! As I'm only a naive user, I have to study your response/code, I have to think about it a lot, to understand it...

A tried/experimented with the firstocc/1 and it seems to be cool to me, but, at least for now, I don't understand whether/how it is better than the first .... I would say, I see it from the wrong angle for now. I need more time for thinking about it.

Thank you.

[haijinSk]

Or, I didn't consider length/2...

[jjtolton]

firstocc(Seq) --> % a sequence not equal to Seq followed by Seq
{length(Seq,N)},
seqfirstocc(N, Seq).

seqfirstocc(N, Seq) -->
{length(Pre,N)},
mlook(Pre), % variable look ahead
{ =(Pre,Seq, T) },
( {T == true} -> seq(Seq)
; [_], seqfirstocc(N, Seq)
).

mlook(Es) --> seq(Es), unseq(Es).

unseq([]) --> [].
unseq([E|Es]), [E] --> unseq(Es).

fmlook(Es, S0,S) :- seq(Es, S0,_), S0 = S. % optimization

Whoaaaa 🫨

[UWN]

Or, I didn't consider length/2...

This does not fully work at the end. There, a further situation is when the length of the remaining sequence is less than the marker-sequence.

[haijinSk]

This does not fully work at the end. There, a further situation is when the length of the remaining sequence is less than the marker-sequence.

Thank you for the clue/thank you for your patience.