A more systematic introduction to Prolog

Propositions

Prolog programs consist of clauses. A clause is always terminated by a dot (.). Propositions start with a lower case letter or you can use quotes to use (almost) arbitrary strings as propositions. The simplest clauses are facts. Here we define three propositions to be true, for the last two we use quotes:

rains.
'I am not wearing a hat'.
'The sun is shining'.
beach :- fail.

We can now ask the Prolog system whether the sun is shining:

?- beach.

false

?-'The sun is shining'.

true

More complicated clauses make use of the implication operator :-. They are also called rules. Logically they stipulate that the left-hand side of the clause must be true if the right-hand side is true. The right-hand side can contain multiple propositions separated by commas. The comma can be read as a logical conjunction (and).

carry_umbrella :- rains, 'I am not wearing a hat'.
rainbow :- rains, 'The sun is shining'.

?- rainbow.

true

The corresponding logic formula to the rule for rainbow is rainbow ← rains ∧ 'The sun is shining'

Using propositional logic is limited, but we can for example encode the logic circuit example from the lecture as follows. Note that \+ is the Prolog symbol for negation.

:- dynamic a/0,b/0,c/0,d/0,e/0.
a. c. e.
% first-level circuits

and11 :- a,b.
or11 :- b,c.
and12 :- c,d.
not1 :- \+ e.

% second-level circuits
or21 :- and11.
or21 :- not1.

and2 :- or11, not1.

or22 :- and12.
or22 :- not1.

not2 :- \+ not1.

% third-level circuits
and3 :- or21, and2.

or3 :- or22.
or3 :- not2.

% fourth-level circuits
or4 :- and3.
or4 :- or3.

and4 :- or3, not2.

% last level
and5 :- and4, or4.

output :- and5.

?-output.

true

Still, propositional logic is much too limited for most applications. Hence we move to predicate logic.

Predicates

Instead of propositions we can also use predicates with arguments within our clauses. The arguments to predicates denote objects for which the predicate is true. Arguments which start with an upper-case letter are logical variables. Below X is such a variable and it can stand for any object.

Prolog provides a few built-in predicates like > or = or is.

?- 2>3.

false

?- is(X,3+2).

X = 5

Let us now define our own predicates. In this case mother/2 and grandma/2. Note: we often use the notation p/n to denote the fact that the predicate p takes n arguments. n is called the arity of p.

mother(a,b).
mother(b,c).
grandma(a,c) :- mother(a,b),mother(b,c).

You can now ask questions about logical consequences of your logic program. In simple queries you provide all arguments:

?-grandma(a,c).

true

?- grandma(a,c) ; mother(c,d).

true

Logical variables

Variables start with an upper-case letter or an underscore. Variables are called logical variables in Prolog: once assigned, their value is immutable and cannot be changed (except upon backtracking).

?- X=1.

X = 1

Above we have set the logical variable X to 1. The scope of the name X is a Prolog clause (i.e., a fact or rule or a query). Thus, in the query below we talk about another X:

?- X=2.

X = 2

However, in the same scope we cannot change the value of X, once assigned:

?- X=1, X=2.

false

?- X=1, X2 is X+1.

X = 1,
X2 = 2

Within a clause variables are implicitly unversally quantified. Let us now define the grandma predicate in a more general fashion:

grandma(X,Y) :- mother(X,Z), mother(Z,Y).

The above clause is equivalent to this logical formula:

∀ X,Y,Z . grandma(X,Y) ← mother(X,Z)∧ mother(Z,Y)

Let us query the predicate:

?- grandma(a,X).

X = c

When we have variables in a query, Prolog gives us solutions for variables such that the instantiated predicate calls are logical consequences of your program.

We can find all solutions using the print_table command of our Jupyter kernel:

jupyter:print_table(grandma(a,X))

X
c

true

Prolog also has a built-in predicate called findall which can be used to find all solutions in one go:

?-findall(X,grandma(a,X),Results).

Results = [c]

Prolog terms and substitutions

Terms represent data values (aka objects). We have that

• constants like a and b are terms
• variables like X are terms
• terms can also be constructed using function symbols

A predicate call takes terms as arguments. E.g. for grandma(a,X) we have the term a as first argument and the term X as second argument.

Exercise

Let us try exercise 2.1.1 (iii) from the Art of Prolog (https://mitpress.mit.edu/9780262691635/the-art-of-prolog/), describing the layout of Figure 2.3 using left_of/2 and above/2.

left_of(bicycle,camera).
left_of(pencil,hourglass).
left_of(hourglass,butterfly).
left_of(butterfly,fish).

above(bicycle,pencil).
above(camera,butterfly).

We can use the Jupyter notebook to render the graph. The print_transition_graph predicate requires a ternary predicate, so that we can provide the edge labels:

edge(A,above,B) :- above(A,B).
edge(A,left_of,B) :- left_of(A,B).

?- edge(A,B,C).

A = bicycle,
B = above,
C = pencil

By calling jupyter:print_transition_graph(PredSpec, FromIdx, ToIdx, LabelIdx), a transition graph can be created (FromIdx is the number of argument specifying the origin, ToIdx the destination and LabelIdx the label).

jupyter:print_transition_graph(edge/3, 1, 3, 2).

true

We now define the predicates right_of and below in terms of the existing predicates:

right_of(X,Y) :- left_of(Y,X).
below(X,Y) :- above(Y,X).

jupyter:print_table(right_of(X,Y))

X	Y
camera	bicycle
hourglass	pencil
butterfly	hourglass
fish	butterfly

true

% next(A,B) :- above(A,B); below(A,B) ; left_of(A,B) ; right_of(A,B).
next(A,B) :- edge(A,_,B).
next(A,B) :- edge(B,_,A).

jupyter:print_table(next(X,Y))

X	Y
bicycle	pencil
camera	butterfly
bicycle	camera
pencil	hourglass
hourglass	butterfly
butterfly	fish
pencil	bicycle
butterfly	camera
camera	bicycle
hourglass	pencil
butterfly	hourglass
fish	butterfly

true

Recursion

Recursion is also allowed in Prolog rules. We now define the simple graph of Figure 2.4 of the Art of Prolog as Prolog facts.

Note that Prolog allows the same predicate name to be used with multiple arities. Above we have defined edge/3, below we define edge/2. For Prolog these two predicates are different and there is no confusion within the Prolog system. However, for programmers it can be a bit tricky to read code which uses the same predicate name with multiple arities.

edge(a,b). edge(a,c).
edge(b,d). edge(c,d).
edge(d,e).
edge(f,g).

With the underscore we indicate that we are not interested in an argument; it is an anonymous logical variable. Here we use this to find the last element of a list:

jupyter:print_transition_graph(edge/2, 1, 2,0).

true

conn(A,A) :- true.
%conn(X,Y) :- edge(X,Y).
conn(X,Y) :- edge(X,Z), conn(Z,Y).

?- jupyter:print_table(conn(a,X)).

X
a
b
d
e
c
d
e

true

?- findall(X, conn(a,X),Ls), length(Ls,Len).

Ls = [a,b,d,e,c,d,e],
Len = 7

Let us now try and define the transitive and reflexive closure of edge.

connected(N,N).
connected(N1,N2) :- edge(N1,Link), connected(Link,N2).

?- connected(a,X).

X = a

jupyter:print_transition_graph(connected/2, 1, 2,0).

true

How should we adapt the definition to only provide the transitive (non-reflexive) closure?

conn1(X,Y) :- edge(X,Y).
conn1(N1,N2) :- edge(N1,Link), conn1(Link,N2).

?- conn1(a,X).

X = b

jupyter:print_transition_graph(conn1/2, 1, 2,0).

true

Arithmetic

Prolog provides integers and floating point numbers as primitive data structures. With the is predicate we can for example compute with those numbers:

?- X is 2^200.

X = 1606938044258990275541962092341162602522202993782792835301376

?- X is 1.0+1.

X = 2.0

Compound data values

So far we have seen these primitive Prolog data values:

• constants (called atoms in Prolog) like a and b
• integers
• floats

More complex data values can be wrapped in so-called functors (also called function symbols). Like predicates they have an arity and take terms as arguments. Unlike predicates, they denote a value and not a logical truth value.

This can be confusing to beginners: whether something is a predicate or functor depends on the position in the Prolog file:

• top-level symbols in Prolog clauses are predicates
• arguments to predicates and functors only contain functors

Functors have many uses in Prolog. The can be used for simple records up to recursive data structures like lists or trees.

Below we first use the functor employe/2 as a simple record.

construct(Name,Department,employe(Name,Department)).

get_name(employe(Name,_),Name).
get_dept(employe(_,Dept),Dept).

?- construct(peter,cs,E1), construct(mary,cs,E2), get_name(E1,N1), get_dept(E2,D2).

E1 = employe(peter,cs),
E2 = employe(mary,cs),
N1 = peter,
D2 = cs

Let us work out a small database example using such compound terms for data abstraction:

% Facts for courses with time slot and location:
course(logic_programming,time(tuesday,1430,1600),location(25,'5F')).
course(sks,time(monday,1430,1600),location(25,'5G')).
course(drones,time(thursday,1430,1600),location(25,'12.O2.55')).
course(navigating_tomorrow,time(thursday,1430,1600),location(25,'12.O2.21')).
% separate facts about which programme the courses belong to (can be multiple):
programme(logic_programming,bachelor_cs).
programme(logic_programming,master_dsai).
programme(sks,master_cs).
programme(navigating_tomorrow,bachelor_cs).

Let us try and write a predicate for:

• which courses take place on a particular day
• which courses take place in a particular building (e.g., 25)
• which courses are available for multiple programmes
• which courses are in conflict (time-wise)
• on which days there are courses a given programme (e.g., bachelor_cs).

Here is a solution. You will see that the compound term encoding of times and buildings has some advantages and drawbacks over a flatter representation such as course/6 with 6 arguments:

course(logic_programming,tuesday,1430,1600,25,'5F').

day(Lect,Day) :- course(Lect,time(Day,_,_),_).
building(Lect,Bldg) :- course(Lect,_,location(Bldg,_)).
multi(Lect) :- course(Lect,_,_), programme(Lect,P1), programme(Lect,P2), P1\=P2.
conflict(L1,L2) :- course(L1,T,_), course(L2,T,_), L1\=L2.
lecture_day(Day,Progr) :- course(L1,time(Day,_,_),_), programme(L1,Progr).

?- multi(L).

L = logic_programming

?- conflict(X,Y).

X = drones,
Y = navigating_tomorrow

?- findall(D,lecture_day(D,bachelor_cs),L).

L = [tuesday,thursday]

Peano Arithmetic

The arguments to a functor can in term also make use of a functor.

We can also use functors of arity 1. (Functors of arity 0 are simply constants, i.e., atoms in Prolog terminology.) This can be used to represent natural numbers:

• we can represent zero using the atom zero/0
• we can represent the successor of a number using a functor s/1

Thus the number 1 is represented by the term s(zero) and the number 2 by s(s(zero)).

How could one write predicates to check if a term is a valid natural number in that representation? E.g., s(zero) is valid, s(a) is not. How could one write addition and multiplication predicate to add or multiply two numbers?

A possible solution is this one. This is also called Peano arithmetic. Note, that contrary to built-in arithmetic (using is/2), these predicates are reversible

nat(zero).
nat(s(X)) :- nat(X).

plus(zero,X,X).
plus(s(X),Y,s(Z)) :- plus(X,Y,Z).

mult(zero,_,zero).
mult(s(X),Y,Z) :- mult(X,Y,XY), plus(Y,XY,Z).  % (x+1)*y = x*y + y

exp(zero,s(_),zero).
exp(s(_),zero,s(zero)).
exp(Y,s(X),Z) :- exp(Y,X,YX), mult(YX,Y,Z).

?-plus(s(s(zero)),s(zero),R).

R = s(s(s(zero)))

?-mult(s(s(zero)),s(s(s(zero))),R).

R = s(s(s(s(s(s(zero))))))

?-exp(s(s(zero)),s(s(s(zero))),R).

R = s(s(s(s(s(s(s(s(zero))))))))

?-plus(X,s(zero),s(s(zero))).

X = s(zero)

?-mult(X,s(zero),s(s(zero))).

X = s(s(zero))

Recursive Data Structures

Compound terms can be used the represent complex data structures, as will see below. First, think on how one could represent a list of objects, say a list of length 2 containing a and b.

One could for example represent a list in Prolog by using a functor cons/2 to denote a non-empty list and nil/0 to denote an empty list. (Remember, a functor of arity 0 is simply a constant (aka atom in Prolog).) So a list of length two with a and b as elements can be represented as follows:

?- Mylist = cons(a,cons(b,nil)).

Mylist = cons(a,cons(b,nil))

Let us now try and define some useful predicates for our data type:

• is_empty/1 to check if something is the empty list
• is_list/1 to check if something is a list
• head/1 to get the first element of a list
• element_of/2 to check if something is an element of a list
• last/1 to get the last elemetn of a list

is_empty(nil) :- true.

This should succeed:

?- is_empty(nil).

true

?- is_empty(cons(a,nil)).

false

Let us now define is_list0 (is_list is predefined):

is_list0(nil).
is_list0(cons(_,B)) :- is_list0(B).

is_non_empty_list(cons(_,B)) :- is_list0(B).

?-is_list0(cons(employe(a,cs),cons(b,nil))).

true

head(First,cons(First,_)) :- true.

?- head(X,cons(employe(a,b),cons(b,nil))).

X = employe(a,b)

element_of(First,cons(First,_)).
element_of(H,cons(_,T)) :- element_of(H,T).

?- element_of(c,cons(a,cons(b,Y))).

Y = cons(c,_8970)

jupyter:retry.

Y = cons(_8968,cons(c,_8976))

?- element_of(First,cons(a,nil))

First = a

jupyter:print_table(element_of(X,cons(a,cons(b,nil))))

X
a
b

true

last0(X,cons(X,nil)).
last0(X,cons(_,Y)) :- last0(X,Y).

?- last0(X,cons(a,cons(b,nil))).

X = b

Exercise: write predicates prefix/2 and suffix/2 which is true if the first argument is a prefix or suffix of the second one.

Trees

As a quick example let us represent binary trees using compound Prolog terms. For this we use a ternary functor tree/3. It has three arguments:

• the left sub-tree
• the information at the root of the tree
• the right sub-tree We also need the empty tree, which we represent by nil.

For example, how would you represent this tree:

?- Mytree = tree(  tree(nil,a,nil), b, tree(nil,c,tree(nil,d,nil))).

Mytree = tree(tree(nil,a,nil),b,tree(nil,c,tree(nil,d,nil)))

Let us now try to write a predicate which reverses (mirrors) the tree, swapping left and right children:

revtree(nil,nil).
revtree(tree(L,Info,R),tree(RR,Info,RL)) :- revtree(L,RL), revtree(R,RR).

?- Mytree = tree(  tree(nil,a,nil), b, tree(nil,c,tree(nil,d,nil))),
   revtree(Mytree,Result).

Mytree = tree(tree(nil,a,nil),b,tree(nil,c,tree(nil,d,nil))),
Result = tree(tree(tree(nil,d,nil),c,nil),b,tree(nil,a,nil))

Optional Appendix: Visualising data values as trees

Below we try to use the Jupyter graph visualisation to represent data values in a tree-like fashion.

:- use_module(library(lists)).

We define a subtree relation, using the =.. built-in predicate, which deconstructs a term by generating a list consisting of the function symbol and all its arguments:

?- tree(nil,a,nil) =.. List.

List = [tree,nil,a,nil]

We can now define a subtree relation:

subtree(Term,Nr,SubTerm) :- Term =.. [_|List], nth1(Nr,List,SubTerm).

?- Mytree = tree(  tree(nil,a,nil), b, tree(nil,c,tree(nil,d,nil))),
   subtree(Mytree,Nr,SubTerm).

Mytree = tree(tree(nil,a,nil),b,tree(nil,c,tree(nil,d,nil))),
Nr = 1,
SubTerm = tree(nil,a,nil)

For the Jupyter graph visualisation we also need to restrict this relation and define a set of terms of interest. Indeed, otherwise there are infinitely many terms.

For this we define the transitive and reflexive closure of the subtree relation and only consider subtrees of a given starting term (here tree( tree(nil,a,nil), b, tree(nil,c,tree(nil,d,nil)))).

rec_subtree(Term,Sub) :- Term = Sub.
rec_subtree(Term,Sub) :- subtree(Term,_,X), rec_subtree(X,Sub).

of_interest(Term) :- rec_subtree(tree(  tree(nil,a,nil), b, tree(nil,c,tree(nil,d,nil))),Term).

subt(Term,Nr,SubTerm) :-
    of_interest(Term), % only consider subterms of the above term as nodes
    subtree(Term,Nr,SubTerm).

?- Mytree = tree(  tree(nil,a,nil), b, tree(nil,c,tree(nil,d,nil))),
   subtree(Mytree,Nr,SubTerm).

Mytree = tree(tree(nil,a,nil),b,tree(nil,c,tree(nil,d,nil))),
Nr = 1,
SubTerm = tree(nil,a,nil)

jupyter:print_transition_graph(subt/3, 1, 3,2).

true