3. Built-in predicates, lists, and language limitations

Built-in predicates

Prolog provides the following built-in predicates:

• operators: $+,-,\ast ,/$ and $=,>,<,=<,>=$
• typles: ${}^{\prime }{,}^{\prime }$
• evaluation: $\text{is}$
• “univ” predicate: $=..$
• control: call/1, fail/0, !/0 (cut)
• I/O: write, nl

The notation p/n indicates that the predicate symbol p has artiny $n$.

% factorial
fact(0, 1).
fact(X, N) :- X > 0, Y is X - 1,
	fact(Y, M), N is X * M.
 
% towers of hanoi
hanoi(X) :- move(X, left, right, middle).
move(1, X, Y, _) :- write([X, "->", Y]), nl.
move(N, X, Y, Z) :- M is N - 1,
	move(M, X, Z, Y),
	move(1, X, Y, Z),
	move(M, Z, Y, X).

Lists in Prolog

Linked lists have a special syntax in Prolog:

• The constant [] denotes the empty list.
• The built-in predicate | is the “cons” operator that joins an element X to the front of a list L, [X | L].
• [X | [Y | Z | []]] is abbreviated to [X, Y, Z].

Pattern matching works as follows:

• [] only matches on the empty list
• [H|T] only matches on a non-empty list

?- [H|T]=[1,2,3].
H = 1,
T = [2, 3].

There also exist built-in predicates for common operations such as member/2, length/2, sort/2, etc.

% get the length of a string
?- length([1,2,3], X).
X = 3.
 
% express result of appending list T to end of list S
?- append([1,2], [3], X).
X = [1, 2, 3].
 
% check whether the list is a reverse of another list
?- reverse([1,2], X).
X = [2, 1].
 
?- reverse([1,2], [2,1]).
true.
 
% check whether an element is in a list
?- member(3, [1,2]).
false.

Implement member/2, length/2, and reverse/2.

% member/2 - member of list L as X
% base case, head of list is element we are looking for
member(X, [X | _]).
% recursive case, check the tail of the list
member(X, [_ | T]) :- member(X, T).
 
% length/2 - length of list L as X
% base case, empty list is of length 0
length([], 0).
% recursive case, length is length of tail add one
length([_ | T], N) :- length(T, M), N is M + 1.
 
% reverse/2 using reverseAux/3 - auxiliary function to implement reverse
% pass off to reverseAux
reverse(L, R) :- reverseAux(L, R, []).
% base case, left list is empty
reverseAux([], A, A).
% recursive case, move item between lists
reverseAux([X | L], R, A) :-
	reverseAux(L, R, [X | A]).
 
% reverse/2 - reverse using append/3
% base case
reverse([], []).
% recursive case, move item between lists
reverse([H|T], L) :- reverse(T, L1), append(L1, [H], L).

Language limitations

It is not possible to directly state facts involving negative statements, e.g. $\neg p(b).$, as Prolog programs are composed only of definite clauses which contain exactly one positive literal.

The following resolution rule is used for computation:

$$\frac{A\vee B\neg A\vee C}{B\vee C}(\text{Res})$$

Any two clauses can be ‘resolved’ as long as they contain complementary literals, potentially generating one or more results. For example, consider $A\vee B$ and $\neg A\vee \neg B\vee C$:

• $B\vee \neg B\vee C$ (from resolving $A$ and $\neg A$)
• $A\vee \neg A\vee C$ (from resolving $B$ and $\neg B$)

Issues with general resolution

Since there are no restrictions on construction of clauses:

• Clauses may be resolved in multiple different ways
• We need to arbitrarily choose the next pair of clauses to resolve

Hence, we must have exactly one positive literal (‘definite’) and clauses in the goal may only contain negative literals. As a consequence, the resolution of a program clause with a goal can be made unique and deterministic (‘selective’), and the resolvent of two clauses will either be empty or generate a new goal (‘linear’).

Negation as Failure

To compensate for lack of logical negation, Prolog uses negation as failure. Informally, failure to prove a literal $A$ is taken as proof that $\neg A$ follows. Using this principle, a negative literal is then allowed to appear in the body of a clause and hence also the goal.

In Prolog, negation as failure is represented as \+:

p(a).
q(a).
s(b).
r(X) :- p(X), q(X), \+ s(X).
 
?- r(a).
true.
 
?- r(b).
false.
 
?- \+ r(a).
false.

In this program, $\neg p(b)$, $\neg q(b)$, and $\neg s(a)$ are indirectly assumed to be true, since their positive counterparts fail.

Disjunctions

Each clause is a disjunction of literals in which at most one is positive, hence it is not possible to represent a disjunction $A\vee B$ faithfully:

• we can add the facts $A$. and $B.$ but we would get $A\wedge B$ which is logically stronger than $A\vee B$. ($A\wedge B⊢A\vee B$ but $A\vee B\cancel{⊢}A\wedge B$)
• We can rewrite $A\vee B$ as $\neg A\to B$ or $\neg B\to A$, which would translate as the rules: B :- \+ A. and A :- \+ B. respectively However, due to how negation as failure works, this does not have the exact same effect.