Search code examples
prologappend

What's wrong with Prolog's append?

According to my university's course in logic we could expect a different outcome than defined by Prolog for the following query:

append([], a, X)

(which unifies for X=a).

However I don't get what they're aiming at? What should be expected as a valid response, given that append should unify X for (in this example) the concatenation of [] and a?

I assume they may be expecting a return of false or [a]; however I suppose that should be the result of concatenating a and [], not [] and a (since [] is the tail of [a]).

Solution

  • However I don't get what they're aiming at?

    Knowing exactly what they are aiming at is of course impossible without asking them.

    Nevertheless I think they aim to show that Prolog is (more or less) untyped. append/3 is documented as:

    append(?List1, ?List2, ?List1AndList2)

       List1AndList2 is the concatenation of List1 and List2.

    So clearly one expects that the three arguments are lists and a is not a list. a is not the concatenation of [] and a since one would consider the two not "concatenatable".

    Now this still succeeds, because append/3 is usually implemented as:

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

    So if you give it append([],a,X)., it will simply unify with the first clause and unify X = a.

    The same "weird" behavior happens with append([14],a,X). Here X = [14|a] which is not a list as well. This is because the Prolog interpreter does not "know" it is working with lists. For Prolog [A|B] is the same like any other functor.

    A more "type safe" way to handle this 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 whether the second argument is a list. The downside however is that now we will append/3 in O(m+n) with m the length of the first list and n the length of the second list whereas in the original code it would take only O(m) time. Furthermore note that Prolog will not raise a warning/error at parse time. It will only fail to append [] with a at the moment you query these.

    Not checking types results in the fact that you have less guarantees if the program compiles/does not raises errors when you feed it to an interpreter. This can be a good thing, but a problem might be that you call some predicates in a way they don't expect which may raise errors eventually later. That is why statically typed languages are sometimes used: they "guarantee" (at least to some extent) that if you call the problem, no such errors will occur. Of course that does not mean that the program cannot error on other things (or simply make no sense). for instance is statically typed and has an append like:

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

    The definition is "more or less" the same, but Haskell will derive that the type of (++) is (++) :: [a] -> [a] -> [a]. Because it know the type of the input and output of every function, it can perform calculus on it, and therefore at compile time, it will raise errors if you would give (++) something different than a list.

    Whether that is a good thing is of course a different question: dynamically typed programming languages are designed that way deliberately since it allows more flexibility.