Logic Programming with Prolog

Concepts of Programming Languages

Sebastian Macke

Rosenheim Technical University

Prolog

2

Terms

The single data type in prolog is a term. Terms can be either

3

Atoms

Examples:

x
red
romeo
pizza
'Pizza'
'foo bar'

The closest thing to an atom in other languages is a constant string, which contains the name of the variable.

const string pizza = "pizza"
4

Variables

Examples:

5

Facts

Clauses without body are called facts.

The fact "Romeo loves Juliet" can be expressed as:

loves(romeo, juliet).

where loves is a predicate and romeo and juliet are called atoms.
Facts end with a dot (just like a semicolon in Java).

6

Rules

Clauses with a body are called rules and expressed as Horn clauses.

The rule "Juliet loves Romeo as long as Romeo loves Juliet." can be expressed as:

loves(juliet, romeo) :- loves(romeo, juliet).

Rules end with a dot (just like a semicolon in Java).

7

Facts are Rules

The fact from the previous slide

loves(romeo, juliet).

can also be written as a rule:

loves(romeo, juliet) :- true.
8

Interactive Prompt

9

Conjunction and Disjunction

Multiple predicates in the body of an expression can be composed as

Note: usually it is better to write separate rules instead of a disjunction.

Example:

happy(juliet).
with_romeo(juliet).
dances(juliet) :- happy(juliet), with_romeo(juliet).
10

Logical operators

Standard Logic operators

Prolog Read as Logical operation
:- if implication
; or disjunction
, and conjunction
not not negation
11

Playing with variables

Given some facts:

loves(romeo, juliet).
loves(william, juliet).

Variables can be used to get everyone that loves Juliet:

?- loves(X, juliet).
X = romeo ;
X = william.

Or to express general rules:

grandparent(X, Y) :-
    parent(X, Z),
    parent(Z, Y).
12

Live Demo 1

likes(dan, sally).
likes(sally, dan).
likes(josh, brittney).

dating(X,Y) :- likes(X,Y), likes(Y,X).
friendship(X,Y) :- likes(X,Y); likes(Y,X).
%friendship(X,Y) :- likes(X,Y), \+ dating(X,Y).
%friendship(X,Y) :- likes(X,Y), not( dating(X,Y) ).
13

Live Demo 2

14

Exercise 10

15

Naming Conventions

16

Hello World

Prolog supports printing values:

write('Hello World!'), nl.

Can also be used in rules for printing intermediate results.

Or to print the actual results in a nicer way:

get_loves_juliet :-
    loves(X, juliet),
    write(X), write(' loves Juliet'), nl.

?- get_loves_juliet.
romeo loves Juliet ;
william loves Juliet .

There is also format/2.

Usually it is fine to use atoms only. However, they have restrictions on length.

17

Lists

Denoted in brackets

L = [a,b,c].

length/2 gives you the length of a list:

?- length([1,2,3], X).
X = 3.

Split into head and tail:

?- [Head|Tail] = [1,2,a].
Head = 1,
Tail = [2, a].

There is also reverse/2, append/2, member/2 and many more.

18

Demo: Logical puzzles

3 Kids: Bryan, Sean, Tony
3 Ages: 6 years, 8 years, 10 years
3 superheroes: Batman, Spiderman, Superman

Solve this logic puzzle to find out the name, the age and the favorite superhero of each kid.

1. Bryan likes Spiderman.
2. Tony doesn't like Superman.
3. The youngest kid likes Spiderman.
4. The kid who likes Superman is 8.

19

Exercise 10.2

20

Arithmetic

Examples:

?- X is 1, Y is X+1.
X = 1,
Y = 2.

?- 3 =< 5.
true.

get_age(BirthYear) :-
    Age is 2020-BirthYear,
    format('Someone born in ~w is age ~w in ~w.~n', [Age, BirthYear, 2020]).
21

Difference between is, =, == and =:=

Number is Expr evaluates to true when Number is the value to which Expr evaluates

?- 1 is 1+1-1.
true.

Term1 = Term2 is true if Term1 unifies with Term2

?- 1 = 1+1-1.
false.

Term1 == Term2 is true if Term1 is equivalent to Term2

?- 1 == 1+1-1.
false.

Expr1 =:= Expr2 is to true if expression Expr1 evaluates to a number equal to Expr2, i.e. float 1.0 =:= integer 1.

?- 1 =:= 1+1-1.
true.
22

Unification

Unification is mostly done implicitly while matching the head of a predicate. However, it is also provided by the =/2 predicate that tests if its two arguments unify. It is usually written infix.

Two terms unify if they are the same term or if they contain variables that can be uniformly instantiated with terms in such a way that the resulting terms are equal.

?- bob = bob.
true.

?- X = 2.
X = 2.

?- 2 = X.
X = 2.

?- X = 2*3.
X = 2*3.

?- loves(X,X) = loves(romeo,juliet).
false.
23

Not in Prolog

\+ Goal (same as not/1) is true if Goal cannot be proven.

?- \+ (2 = 4).
true.

This is not the same as logical not!!

Logical negation in Prolog is problematic:

Try to avoid negative terms. Think positive!

24

Solution by side effects

Sometimes write can be used for printing the actual solution as a side effect:

% Towers of Hanoi

move(1,X,Y,_) :- write('Move top disk from '), write(X), write(' to '), write(Y), nl.
move(N,X,Y,Z) :-
    N > 1,
    M is N-1,
    move(M,X,Z,Y),
    move(1,X,Y,_),
    move(M,Z,Y,X).

run :- move(3,left,right,center).

Loops are done with recursion just like in functional programming.

25

Debugging Tools

Trace/1 enables tracing of a given predicate, very useful for debugging:

trace(loves).

Trace/0 traces everything:

trace.

Listing gives you a list of all known facts:

listing(loves).

You may also simply print intermediate results:

loves(X, Y) :- write(X), write(Y), nl.
26

Execution

27

Execution

28

Live Coding

Three missionaries and three cannibals want to cross a river with a boat.
However, the small boat only carries at most two people.
On both banks, the missionaries may not be outnumbered by the cannibals, otherwise
it is to be feared that the cannibals overpower the missionaries and eat them alive.
Find a solution for the six people to safely cross the river.

29

Exercise 3

30

There is more to Prolog

31

Applications: Authorization

32

Thank you

Sebastian Macke

Rosenheim Technical University

Use the left and right arrow keys or click the left and right edges of the page to navigate between slides.
(Press 'H' or navigate to hide this message.)