How to read the predicates in prolog

Question

I moved on to Prolog it after learning propositional and predicate logic.

I was wondering if someone could clarify the syntax for me as I am having trouble reading it.

I can read something like the below easily. So it is saying

X is the descend of Y if X is the child of Y.

Then it goes on to say

X is the descend of Y if X is the child of Z and Z is the descend of Y.

descend(X,Y) :-
   child(X,Y).
descend(X,Y) :-
   child(X,Z),
   descend(Z,Y).

But once I got into looking into list programming I am struggling to read the syntax of the predicates. For example the below

remove([], _, []).
remove([X | Xs], X, Ys) :- remove(Xs, X, Ys).
remove([Y | Xs], X, [Y | Ys]) :- X \== Y, remove(Xs, X, Ys).

From testing it, it removes the second item, so for instance if I type in

remove([a,b,c], b, Ys).

I would get Ys = [a,c].

But I do not know how to read the syntax, if someone could break it down for me, that would be great.

Answer 1

As you have some background in logic you might find it helpful to read the rules as logic formulas. Let's replace (\==)/2 by dif/2 then remove/3 reads as follows:

remove([], _, []) ← true

remove([X | Xs], X, Ys) ← remove(Xs, X, Ys)

remove([Y | Xs], X, [Y | Ys]) ← dif(X,Y) ∧ remove(Xs, X, Ys)

Note how the implication arrow points to the head of the rule. That means the body of the rule is the antecedent and the head of the rule is the consequent. So you read a rule as: if the body of the rule is true then the head of the rule is true. The goals in the rules are connected by conjunction. Note how the fact has true as antecedent, meaning that remove([], _, []) is always true. On the other hand, if the body of a rule is false that rule fails but the predicate may still succeed if the body of another rule is true. If the bodies of all other rules are false as well then the predicate fails. So having several rules for a predicate constitutes logical or: the predicate remove/3 succeeds if rule1 OR rule2 OR rule3 succeeds.

As you asked for syntax specifically, it is also opportune to be familiar with the head and tail notation for lists. That is, you can write the first element(s) of a list explicitly then a list constructor | and the rest of the list:

[1|Xs] ... list starts with 1 and then there is a rest

[1,2|Xs] ... list starts with 1 and 2 followed by a rest

[X|Xs] ... list has at least one element followed by a rest

Note how list elements are separated by , while the rest of the list is separated by |. The term after the | is actually a list and can also be an empty list. Here are some examples for equal lists:

[1] is the same as [1|[]]

[1,2] = [1|[2]] = [1|[2|[]]] = [1,2|[]]

For the following list there are already 8 ways to write it:

[1,2,3] = [1,2|[3]] = [1|[2,3]] = [1|[2|[3|[]]]] = ...

With the above observations in mind you would then examine the rules one at a time. As @lurker already did that in his answer I will not go into detail. However, I would add that if a rule has several goals, like the 3rd rule in your example, I find it helpful to walk through the goals one at a time:

remove([Y | Xs], X, [Y | Ys]) :-

Element Y of the original list is also in the list without X IF...

remove([Y | Xs], X, [Y | Ys]) :-
   dif(X,Y),

... X is different from Y AND...

remove([Y | Xs], X, [Y | Ys]) :-
   dif(X,Y),
   remove(Xs, X, Ys).

... the relation holds for Xs, X and Ys as well.

So why the replacement? The built-in predicate (\==)/2 just succeeds or fails without unification or side-effect. It is good for testing term inequality at a given time but does not have any effect later on. Consider the following queries:

   ?- X=Y, X\==Y.
no

First the variables X and Y are unified and subsequently the test for inequality fails. But:

   ?- X\==Y, X=Y.
X = Y

First the test for inequality succeeds, otherwise Prolog would not even consider the second goal. Then X and Y are unified successfully. This is what I mean by no effect later on. So everything I wrote above on reading predicates is not really meaningful with (\==)/2.

As a shorter version I throw the following in the hat, using if_/3 and =/3:

list_without_element([],[],_E).
list_without_element([X|Xs],L,E) :-
   if_(X=E,L=Ys,L=[X|Ys]),
   list_without_element(Xs,Ys,E). 

Answer 2

The fact that you need to test it just to see what it does says that remove/3 probably isn't that well named. remove is pretty generic and leaves open the question "remove what?". Also, it is imperative, and Prolog wants to be relational. Perhaps a better name would be list_without/3 which says that the list in the 3rd argument is the list in the first argument, but without the second argument.

Be that as it may, let's read what you have.

Reading the your remove/3 predicate could be done as follows:

remove([], _, []).

The empty list is still the empty list if I remove any element.

remove([X | Xs], X, Ys) :- remove(Xs, X, Ys).

The list Ys is the list [X|Xs] with the X elements removed if Ys is the list I get after removing all X elements from Xs.

remove([Y | Xs], X, [Y | Ys]) :- X \== Y, remove(Xs, X, Ys).

[Y|Ys] is the list [Y|Xs] with the X elements removed if X is not the same as Y and Ys is the list I get after removing all X elements from Xs.

As an exercise, you should try read these again, but using a more relational name, such as the example renaming I provided.