What is wrong with the Prolog append?

Question

According to my university course in logic, we could expect a different result than what Prolog defined for the following request:

append([], a, X) 

(which combines for X=a ).

However, I do not understand what they are aimed at? What should be expected as a valid answer, given that append should unify X for (in this example) concatenation of [] and a ?

I assume that they can expect to return false or [a] ; however, I believe that this should be the result of combining a and [] , not [] and a (since [] is the tail of [a] ).

Answer 1

However, I do not understand what they are aimed at?

Knowing what they are aimed at is, of course, impossible without asking them.

However, I think they seek to show that the Prolog is (more or less) untyped . append/3 documented as:

append(?List1, ?List2, ?List1AndList2)

List1AndList2 is a concatenation of List1 and List2 .

Thus, it is obvious that the three arguments are lists and a not a list. a not concatenation [] and a , since it can be assumed that two are not “concatenated”.

Now this is still running, because append/3 usually runs as:

 append([],T,T). append([H|T],T2,[H|R]) :- append(T,T2,R). 

So, if you give it append([],a,X). , it simply combines with the first sentence and unifies X = a .

The same “strange” behavior occurs with append([14],a,X) . Here X = [14|a] , which is also not a list. This is because the Prolog interpreter does not “know” what works with lists. For Prolog, [A|B] the same as any other functor.

A safer type type . It could be:

 append([], [],[] ). append([H|T],T2,[H|R]) :- append(T,T2,R). append( [],[H|T],[H|R] ) :- append([],T,R). 

Or more elegantly:

 list([]). list([_|T]) :- list(T). append([], T,T ) :- list(T). append([H|T],T2,[H|R]) :- append(T,T2,R). 

since here we check if the second argument is a list. However, the drawback is that now we will be append/3 in O (m + n), where m is the length of the first list and n is the length of the second list, while in the source code it only takes O (m) time. Also, note that Prolog will not raise a warning / error during parsing. He will not be able to add [] with a at the moment when you request them.

Do not check types leads to the fact that you have less guarantees if the program compiles / does not cause errors when passing it to the interpreter. This may be fine, but the problem may be that you are invoking some predicates in a way that they do not expect, which may cause errors later. This is why statically typed languages ​​are sometimes used: they “guarantee” (at least to some extent) that if you cause a problem, there will be no such errors. Of course, this does not mean that the program cannot be mistaken in other things (or simply does not make sense). haskell , for example, is statically typed and has add:

 (++) [] t2 = t2 (++) (h:t) t2 = h:((++) t t2) 

The definition of "more or less" is the same, but Haskell will infer that the type (++) is (++) :: [a] -> [a] -> [a] . Since he knows the type of input and output of each function, he can do the calculus on it, so during compilation it will cause errors if you give (++) something other than a list.

Whether this is good, of course, is another question: dynamically typed programming languages ​​are designed in such a way consciously, since this allows increasing flexibility.

Answer 2

The fact is that we expect append/3 remain for lists only.

In the query you are showing, a not a list, but append/3 still hold.

Thus, the relation is really more general than we originally expected: it is true for other cases too!

The reason why this is so may be soon from the first sentence of the traditional append/3 definition:

  append ([], Bs, Bs).

Only this offer makes the request successful! No additional pure option can prevent this. Thus, this particular sentence should be limited if we want the relation to be preserved only for lists. This means that we must put a restriction on the second argument, which we make by specifying it in the body of the sentence.

  append ([], Bs, Bs): - ... (left as an exercise)

It obviously comes at a price: performance.

So, the tradeoff between performance and accuracy. In Prolog, we often accept this trade-off, because we implicitly use such predicates only with implied terms. On the other hand, for many predicates we want to capitalize on domain errors or types if they do not cause the expected types

Answer 3

Your course focuses on a very important point in programming Prolog.

Guides are often pretty messy in defining append/3 and similar predicates. In fact, the full definition is so complex that it is often preferred to define only part of the actual relationship. Consider the first definition in Prolog Prolog :

append(Xs, Ys, Zs) true if Zs is a concatenation of the lists Xs and Ys .

Pay attention to if. Thus, the definition gives cases when this relation is satisfied, but does not explicitly exclude further cases. To rule out further cases, ifff would be said instead. The cases mentioned (what we are talking about lists) are the intended use of the predicate. So, what cases can now be further included? Those cases where the precondition (that the arguments are lists) is not satisfied.

Consider the definition of append/3 with 'iff' instead of 'if':

 append([], Xs, Xs) :- list(Xs). append([X|Xs], Ys, [X|Zs]) :- append(Xs, Ys, Zs). list([]). list([X|Xs]) :- list(Xs). 

The cost of adding two lists now | Xs | + | Ys |. This is quite an overhead compared to | Xs | by oneself.

But the situation is even worse. Consider the query:

 ?- append([1,2], Ys, Zs). ; Ys = [], Zs = [1,2] ; Ys = [_A], Zs = [1,2,_A] ; Ys = [_A,_B], Zs = [1,2,_A,_B] ... 

Thus, we get an infinite number of responses to this request. Compare this to the usual definition:

 ?- append([1,2], Ys, Zs). Zs = [1,2|Ys]. 

Only one answer! It contains all the answers for all the lists plus some odd cases that you observed. Thus, the usual definition for append has better completion properties. In fact, it ends if the first or third argument is a list of known length ¹ .

Note that the answer contains Ys . Thus, an infinite number of answers can be folded into one. This is actually the power of a boolean variable! We can imagine endless means of infinitely many solutions. The cost of payment is some additional solutions ² that can lead to programming errors. Therefore, some precaution is required.

---

1 It also ends in some more obscure cases, such as append([a|_],_,[b|_]) .

2 append([a], Zs, Zs). also gives (in many systems) an answer.