Prolog

236319 Spring 2023, Prof. Lorenz

Prolog

introduction

basic constructs

the basic constructs of prolog are terms and statements

terms - atoms

the simplest term is an atom, the following are atoms:

john
$<@
'an atom'

an atom is

a string of letters, digits, and an underscore starting with a lower-case letter: anna x_25 nil
a string of special characters (+ - * / < > = : . & _ ~): $<@ <----> .:.
a string of characters enclosed in single quotes: 'Tom' '2A$'

terms - numbers

integers: 123 -42
real numbers: 3.14 -0.573 2.4e3

terms - variables

a variable is a string of letters, digits and an underscore starting with an upper-case letter or an underscore

X_25
_result

compound terms

a compound term comprises a functor and arguments

course(236319, pl)

a functor f of arity n is denoted f/n

terminology

a term is ground (קונקרטי) if it contains no variables
a goal is an atom or a compound term
a predicate (פרדיקט) is a functor for which a list of clauses is defined
a clause (פסוקית) is a fact or a rule

facts

a fact (עובדה) is a kind of statement

eats(bunny, carrot).

this fact states that the predicate eats holds for the atoms bear and honey

facts can have any arity

summer.
sad(john).
plus(2, 3, 5).

a finite set of facts constitutes a program

mammal(rat).
mammal(bear).
fish(salmon).
eats(bear, honey).
eats(bear, salmon).
eats(rat, salmon).
eats(salmon, warm).

facts can contain variables

likes(X, course236319).

variables are universally quantified

\[\forall X,likes(X, course236319)\]

queries

a query (שאילתה) is a conjunction of goals

?- eats(X, salmon), eats(X, honey).

variables are existentially quantified

\[\exists X,eats(X, salmon) \land eats(X, honey)\]

rules

a rule (חוק, כלל) is a statement which enables us to define new relationships in terms of existing ones

predicate(term1, ..., termN) :- goal1, ..., goalN.

Y is a survival dependency of X if:

X eats Y
or X eats Z and Y is a survival dependency of Z

survival_dependency(X, Y) :- eats(X, Y).
survival_dependency(X, Y) :-
    eats(X, Z), survival_dependency(Z, Y).

?- survival_dependency(bear, X).

writing Prolog programs

create a file named prog.pl
write clauses in prog.pl
enter the prolog interpreter
type consult(prog.pl)
query the interpreter

dynamic clauses

you can add clauses dynamically

:- assertz(eats(bear, tuna)).
:- assertz((
  mother(Child, Mother) :-
    parent(Child, Mother),
    female(Mother)
)).

?- eats(bear, tuna).

asserta asserts the clause as first clause of the predicate while assertz asserts it as last clause

dynamically remove a clause using retract/1

:- assertz(q(a)).
:- assertz((p(X) :- q(X))).
:- assertz(p(b)).

:- retract(p(X) :- q(a)).

?- p(a).

dynamically remove clauses using retractall/1

:- assertz(q_2(a)).
:- assertz((p_2(X) :- q_2(X))).
:- assertz(p_2(b)).

:- retractall(p_2(_)).

?- p_2(a).
?- p_2(b).

dynamically remove a predicate using abolish/1

:- assertz(p(a)).
:- assertz(p(b)).

:- abolish(p/1).

?- p(X).

meaning of a prolog program

declarative meaning
- the inference algorithm is an implementation detail
- not always easy to achieve
procedural meaning
- but thinking procedurally makes it harder to come up with an elegant solution
- beats the purpose of the paradigm

matching

two terms match if:

they are identical
the variables in both terms can be instantiated to make the terms identical

the operator = performs matching

?- course(N, S, 95) = course(X, fall, G).

?- course(N, S, 95) = course(Y, M, 96).

?- course(X) = semester(Y).

matching rules

terms S and T match if:

S and T are the same atom
S and T are the same number
if one is a variable it’s instantiated to the other
if S and T are compound terms, they match iff:
- they have the same functor and arity
- all their corresponding arguments match
- the variable instantiations are compatible

geometric example

use compound terms to represent geometric shapes

point(1, 1)
seg( point(1, 1), point(2, 3) )
triangle( point(4, 2), point(6, 4), point(7, 1) )

?- triangle(point(1, 1), A, point(2, 3))
=
triangle(X, point(4, Y), point(2, Z)).

matching as means of computation

facts:

vertical(seg(
    point(X, Y1),
    point(X, Y2)
)).

queries:

?- vertical(seg(point(1, 1), point(1, 2))).

?- vertical(seg(point(1, 1), point(2, Y))).

?- vertical(seg(point(2,3), P)).

arithmetic

the operators + - * / div mod are (infix) binary relations
but they are arithmetic operators after the operator is

?- X = 1 + 2.

?- X is 1 + 2.

comparison operators

X > Y
X < Y
X >= Y
X =< Y
X =:= Y  % equal
X =\= Y  % not equal

the comparison operators also force evaluation

?- 11 * 6 = 66.

?- 11 * 6 =:= 66.

`=` VS. `=:=`

= is used for matching and may instantiate variables
=:= causes an arithmetic evaluation of its operands and cannot instantiate variables

?- 1 + X = Y + 2.

?- 1 + X =:= Y + 2.

GCD

gcd(X, X, X).
gcd(X, Y, D) :-
    X < Y,
    Y1 is Y - X,
    gcd(X, Y1, D).
gcd(X, Y, D) :-
    Y < X,
    gcd(Y, X, D).

?- gcd(12, 30, D).

builtin control predicates

conjunction `,/2`

the goal (G1, G2) succeeds if G1 and G2 succeed

disjunction `;/2`

the goal (G1 ; G2) succeeds if G1 or G2 succeed

defined as follows:

(G1 ; G2) :- G1.
(G1 ; G2) :- G2.

true

the predicate true/0 always succeeds

false

the predicates false/0 and fail/0 always fail

negation as failure

the negation predicate is \+/1
for known predicates, prolog works under a closed world assumption - if something can’t be proved then it is false
it is not logical negation!

person(jimmy).
person(cindy).

?- person(rick).
?- \+ person(rick).

it might not work like you’d expect

?- person(X).

?- \+ person(X).

why doesn’t prolog answer with X = rick or simply with true?

person(X) succeeds so its negation fails

if G fails \+ G succeeds
if G succeeds \+ G fails

\+/1 allows for non-monotonic reasoning - a fact can become false by adding clauses to the database

illegal(murder).
legal(X) :- \+ illegal(X).

illegal(theft).

?- legal(theft).

exercise - family tree

you have a database with the following predicate

parent(X, Y).  % X is Y's parent

% examples:
parent(adam, cain).
parent(eve, cain).
parent(cain, enoch).

define a predicate grandparent(X) that holds when X is a grandparent

...

?- grandparent(X).

grandparent(X) :- parent(X, Y), parent(Y, _).

define a predicate nuclear(X, Y) that holds when X and Y are in the same nuclear family

a nuclear family consists of 2 parents and their common children

...

?- nuclear(adam, X).

nuclear(X, Y) :-  % siblings
    parent(P1, X), parent(P2, X),
    parent(P1, Y), parent(P2, Y),
    \+(P1 = P2).  % alternatively: `P1 \= P2`

nuclear(X, Y) :-
    parent(X, C), parent(Y, C).

nuclear(X, Y) :-
    (parent(X, Y); parent(Y, X)).

exercise - binary trees

we represent binary trees as terms:

nil is the empty tree
node(N, Tl, Tr) is a tree node where N is some number and Tl and Tr are binary trees

define a predicate tree_size(T, S) such that T is a binary tree and S is its size

...

?- tree_size(node(1,
	node(2, 
		nil, 
		nil
	),
	node(3,
		node(4, nil, nil),
		nil
	)),
	S).

tree_size(nil, 0).
tree_size(node(_, Tl, Tr), S) :-
    tree_size(Tl, Sl),
    tree_size(Tr, Sr),
    S is Sl + Sr + 1.

define a predicate tree_max(T, M) such that T is a binary tree and M is the max of the values of T’s nodes

you may use the arithmetic function max/2

...

?- tree_max(node(10,
    node(-3, 
        nil, 
        nil
    ),
    node(14,
        node(4, nil, nil),
        nil
    )),
    M).

tree_max(node(N, nil, nil), N).
tree_max(node(N, nil, Tr), M) :-
    tree_max(Tr, Mr), M is max(N, Mr).
tree_max(node(N, Tl, nil), M) :-
    tree_max(Tl, Ml), M is max(N, Ml).
tree_max(node(N, Tl, Tr), M) :-
    tree_max(Tl, Ml),
    tree_max(Tr, Mr),
    M is max(N, max(Ml, Mr)).

define a predicate perfect_tree(T, H) such that T is a perfect binary tree and H is its height

a node’s value should be its height

a perfect binary tree is a binary tree in which all interior nodes have two children and all leaves have the same depth

...

?- perfect_tree(T, 2).

perfect_tree(nil, 0).
perfect_tree(node(H, Tl, Tl), H) :-
    H > 0,
    H1 is H - 1,
    perfect_tree(Tl, H1).

Prolog

introduction

basic constructs

terms - atoms

terms - numbers

terms - variables

compound terms

terminology

facts

queries

rules

writing Prolog programs

dynamic clauses

meaning of a prolog program

matching

matching rules

geometric example

matching as means of computation

arithmetic

comparison operators

= VS. =:=

GCD

builtin control predicates

conjunction ,/2

disjunction ;/2

true

false

negation as failure

exercise - family tree

exercise - binary trees

`=` VS. `=:=`

conjunction `,/2`

disjunction `;/2`