Laboratorul 1 - Programare Logică s, i Funct, ională

Seria 36
Februarie & Martie 2024

1 De ce programare logică?
• Programarea logică este utilă ı̂n strategii de căutare, prototipuri, rezolvare de puzzle-uri etc.
• Idei declarative apar ı̂n multe domenii din informatică:
– conceptele din programarea logică sunt utile ı̂n AI s, i ı̂n bazele de date; demonstratoare
automate, model-checking, constrain programming
– sunt importante ı̂n analiza programelor, ı̂n semantica Web.

Prolog este cel mai cunoscut limbaj de programare logică. Este bazat pe logica clasică de ordinul
I s, i funct, ionează pe bază de unificare s, i căutare.
În acest laborator, vom folosi implementarea SWI-Prolog:
• gratuit, folosit pentru predare, cont, ine multe librării;
• [Link]
• există s, i o variantă online: [Link]
În laboratorul de astăzi răspundem următoarelor două ı̂ntrebări:
• cum arată un program ı̂n Prolog?
• cum punem ı̂ntrebări ı̂n Prolog?

2 Sintaxă
Ca elemente de sintaxă ı̂ntâlnim constantele, variabilele s, i termenii.

Constantele din limbajul Prolog sunt atomii s, i numerele.

• atomi: secvent, e de litere, numere s, i care ı̂ncep cu o literă mică, s, iruri ı̂ntre apostrofuri s, i
anumite simboluri speciale: atom, my atom, ’Sir de Caractere’, ’(@ *+’, +;
• numere: 2, 2.5, -33.
În Prolog avem predefinit un predicat atom de aritate 1 (s, i notăm atom/1).
?- atom('(@ *+ ').
true.
Variabilele sunt secvent, e de litere, numere s, i care ı̂ncep cu literă mare sau cu simbolul .
Variabila este o variabilă anonimă. Două aparit, ii ale simbolului sunt variabile diferite s, i, ı̂n
general, folosim atunci când nu vrem detalii despre variabila respectivă. Exemple: X, myVar, .
Termenii sunt constante sau variabile, iar termenii compus, i au forma p(t1, ..., tn) unde p
este un atom, iar t1, ..., tn sunt termeni. De exemplu,
father(oliver, ben).
father(oliver, X).
Un termen compus are, astfel, două atribute, s, i anume:
• un nume (functor ): father ı̂n exemplul de mai sus;

1
 • o aritate (numărul de argumente): 2 argumente ı̂n cazul de mai sus.
Observat, ii:
• predicatele cu acelas, i nume, dar cu arităt, i diferite, sunt predicate diferite;
• există predicate de aritate 0 (nu au argumente): de exemplu true s, i false;
• scriem foo/n pentru a indica predicatul foo de aritate n.
Pentru a defini un program ı̂n Prolog, vom avea o bază de cunos, tint, e (adevăruri ı̂n universul
programului, facts) s, i reguli de inferent, ă (rules). În general, o regulă este de forma
Head :- Body.
s, i citim ”Head dacă Body” sau ”dacă Body este adevărat, atunci Head” (implicat, ia este de la dreapta
- antecendent, la stânga - consecvent). Un adevăr (fact) este o regulă care nu are un Body.
Un exemplu de bază de cunos, tint, e:
male(sam).
male(oliver).
male(ben).
male(peter).
male(roger).

female(elizabeth).
female(sandra).
female(mary).
female(lisa).
female(olivia).

parent_of(sandra, sam).
parent_of(sandra, elizabeth).
parent_of(ben, sam).
parent_of(ben, elizabeth).
parent_of(peter, oliver).
parent_of(peter, sandra).
parent_of(roger, ben).
parent_of(roger, lisa).
parent_of(olivia, roger).
parent_of(olivia, mary).

Pentru a scrie o regulă, avem ı̂n vedere următoarele:

2
 • Head este un predicat (termen compus);
• Body este o secvent, ă de predicate, separate prin virgulă.
În Prolog, virgula se interpretează drept conjunct, ie, astfel că citim
P :- Q1, Q2, ..., Qn.
ca fiind formula Q1 ∧ Q2 ∧ . . . ∧ Qn → P .
De exemplu, putem adăuga ı̂n baza de cunos, int, e un predicat happy/1. Vom pune acest predicat
pentru Roger si Olivia:
happy(roger).
happy(olivia).
Vom defini ca regulă că Ben este happy dacă s, i fiul lui, s, i nepoata lui sunt happy.
happy(ben) :- happy(roger), happy(olivia).
Observat, ie: ı̂n Prolog toate demonstrat, iile sunt făcute ı̂ntr-un univers ı̂nchis! În acest moment,
putem demonstra că Roger, Olivia s, i Ben sunt happy pentru că avem această informat, ie. Acest
lucru nu ı̂nseamnă automat că tot, i ceilalt, i sunt sad, ci ı̂nseamnă doar că nu s, tim nimic despre ei.
În Prolog dacă nu putem demonstra o proprietate P, ı̂nseamnă doar că nu am reus, it să ı̂i găsim
demonstrat, ia.
Vom defini o regulă ca Elizabeth să fie happy dacă cel put, in unul dintre copiii ei este happy
(Sandra sau Ben). Pentru a introduce disjunct, ia ı̂n Prolog, avem două variante: sau cu operatorul
;, sau scriind regula pe mai multe linii, câte una pentru fiecare disjunct. Astfel, putem avea una
dintre următoarele două:
happy(elizabeth) :- happy(sandra) ; happy(ben).
SAU
happy(elizabeth) :- happy(sandra).
happy(elizabeth) :- happy(ben);
Important! Predicatele scrise (atât adevărurile cât s, i regulile de inferent, ă) trebuie să fie grupate
după atomii din Head. În caz contrar, există riscul erorilor de parsare, iar răspunsul dat de Prolog
poate fi gres, it. Contează ordinea de scriere a clauzelor
O ı̂ntrebare ı̂n Prolog este o secvent, ă de forma
?- p1(t1,...,tn),...,pn(t1',...,tn').
Fiind dată o ı̂ntrebare (t, intă), Prolog caută răspunsuri. Va returna true sau false dacă
ı̂ntrebarea nu cont, ine variabile, respectiv daca ı̂ntrebarea cont, ine variabile, atunci sunt căutate
valori care fac toate predicatele din ı̂ntrebare să fie satisfăcute. Daca nu se găsesc astfel de valori,
răspunsul este false. Predicatele care trebuie satisfăcute se numesc goals.
Exemplu de ı̂ntrebare:
?- happy(elizabeth).
true.
Putem pune ı̂ntrebări care cont, in s, i variabile, de exemplu:
?- parent_of(ben, X).
Observăm că Prolog răspunde cu
X = sam
dar nu este unicul răspuns. Pentru a-l obt, ine pe următorul, folosim ;, s, i obt, inem s, i
X = elizabeth
Putem defini reguli complexe folosind variabile. Vom defini predicatul father of/2, astfel:
father_of(X, Y) :-
parent_of(X, Y),
male(Y).
Utilizăm ı̂n definit, ie ce ı̂nseamnă father: să fie părintele direct s, i să fie bărbat.

3
3 Aritmetică ı̂n Prolog
În Prolog avem operat, iile aritmetice uzuale:
1. + pentru adunare;
2. - pentru diferent, ă;
3. * pentru ı̂nmult, ire;
4. / pentru ı̂mpărt, ire pe floats;
5. // pentru câtul ı̂mpărt, irii;
6. div tot pentru câtul ı̂mpărt, irii;
7. mod pentru restul ı̂mpărt, irii;
8. ** pentru ridicarea la o putere.
Toate operat, iile de mai sus sunt simboluri binare, astfel că avem egalitate, de exemplu, ı̂ntre +(3,5)
= 3 + 5.
ATENT , IE! În Prolog există mai multe simboluri pentru egalitate, fiecare cu alt scop!

1. = caută un unificator ı̂ntre termeni (vom vedea);

2. == verifică egalitatea structurală a termenilor;
3. =:= compară egalitatea aritmetică.
Astfel, 8 == 3 + 5, respectiv 8 = 3 + 5 vor fi evaluate la false, dar 8 =:= 3 + 5 va fi evaluat
la true.
Pentru a efectua calcule, nu putem folosi niciunul dintre operatorii de mai sus. Dacă vrem să
evaluăm expresia aritmetica 3 + 5 s, i să stocăm rezultatul ı̂n variabila X, sintaxa care ne permite
este cea de a utiliza operatorul is/2, sub forma X is expression.
Despre operatorul is avem următoarele:
• primes, te două argumente;
• al doilea argument trebuie să fie o expresie aritmetică validă, cu toate variabilele instant, iate;
• primul argument este fie un număr, fie o variabilă;
• dacă primul argument este un număr, atunci operatorul se comportă ca egalitatea aritmetică;
• dacă primul argument este o variabilă, atunci răspunsul este pozitiv dacă variabila poate fi
unificată cu evaluarea expresiei aritmetice din al doilea argument.
Pentru condit, iile booleene avem operatorii de aritate 2: >, >=, <, =< (atent, ie la ultimul din această
listă).
Operatorii aritmetici se ı̂mpart, astfel, ı̂n funct, ii s, i relat, ii: adunarea, ı̂nmult, irea etc. sunt exemple
de funct, ii aritmetice, s, i le putem scrie ı̂n Prolog ı̂n mod uzual,
?- X is 2 + (-3.2 * 7 - max(17, 3)) / 2 ** 5.
X = 0.7687499999999998
dar avem acces s, i la alte funct, ii precum min/1, abs/1, sqrt/1, sin/1 etc. Relat, iile sunt relat, iile de
ordine.
Un exemplu de prediat pentru suma a trei numere este add/4:

add(X, Y, Z, Result) :- Result is X + Y + Z.

?- add(1, 2, 3, Res).
Res = 6

4 Exercit, ii
Rezolvat, i următoarele exercit, ii

4
4.1 Exercit, iul 1
Definit, i, pentru baza de cunos, tint, e de mai sus, predicatele următoare: mother of/2, brother of/2,
sister of/2. uncle of/2, aunt of/2, grandfather of/2, grandmother of/2. Verificat, i aceste
predicate punând ı̂ntrebări s, i urmărind pe arborele genealogic de mai sus.

4.2 Exercit, iul 2

Utilizând aceeas, i bază de cunos, tint, e de mai sus, definit, i un predicat ancestor of/2, care să verifice
dacă al doilea argument este strămos, al primului. Predicatul trebuie să fie true pentru toate
ı̂ntrebările pe linia directă, de exemplu ?- ancestor of(olivia, sam).

4.3 Exercit, iul 3

Definit, i un predicat distance/3 pentru a calcula distant, a dintre două puncte ı̂ntr-un plan 2-
dimensional.

4.4 Exercit, iul 4

Fie write/1 un predicat care scrie argumentul primit (un atom) la STDOUT. Folosit, i acest predicat
pentru a defini un predicat nou, write n/2 care primes, te ca argumente un număr natural nenul s, i
un atom s, i afis, ează la STDOUT un triunghi format din atomul primit s, i din dimensiunea primită.
De exemplu, pentru write n(5, *) se va afis, a:
*****
****
***
**
*
Modificat, i afis, area pentru a obt, ine reprezentarea:
*
**
***
****
*****

4.5 Exercit, iul 5

Scriet, i un predicat min/3 care să calculeze minimul a două elemente. Ce obervat, i ı̂n implementare?

4.6 Exercit, iul 6

Scriet, i un program Prolog care, primind trei puncte ı̂n plan, verifică dacă ele determină un triunghi
dreptunghic. Punctele sunt reprezentate ca perechi (X, Y).