MINISTERUL EDUCAŢIEI AL REPUBLICII MOLDOVA

UNIVERSITATEA DE STAT DIN MOLDOVA

PROGRAMAREA LOGICĂ ÎN LIMBAJUL PROLOG

LUCRARE DE LABORATOR Nr. 1

Verificat:

Prepeliţă Aurelia,

conferenţiar universitar, doctor în ştiinţe fizico-matematice

Executat:

Musteaţă Daniel,

doctorand, specialitatea: 12.00.10 – Drept Internaţional Public

CHIŞINĂU, 2014

Partea I. Partea teoretică a lucrării practice

1. Sectiunile de baza a unui program Turbo Prolog si destinatia lor: domains,

predicates, clauses, goals. ‘

Limbajul Prolog (a carui nume provine de la Programmable Logic) este un limbaj logic,

descriptiv, care permite specificarea problemei de rezolvat în termenii unor fapte cunoscute

despre obiectele universului problemei şi a relaţiilor existente între aceste obiecte.

Prolog este un limbaj conceput pentru programarea logică (deci un limbaj declarativ) şi a

fost elaborat în cursul anilor 1970 în Europa (mai ales în Franţa şi Scoţia). Prologul este un limbaj

compilat, care utilizează, în locul relaţiilor matematice, relaţii logice între mulţimi de date. Exista

limbaje algoritmice, orientate obiect si logice Limbajele programării logice (Prolog) sunt limbaje

declarative, scutind în acest fel programatorul de a mai menţiona procedura exactă pe care trebuie

să o execute calculatorul pentru a realiza o funcţie. Programatorii folosesc limbajul pentru a

descrie o mulţime de fapte şi de relaţii astfel încât utilizatorul să poată interoga apoi sistemul

pentru a obţine un anumit rezultat.

Programul Prolog conţine 4 secţiuni de bază:

Clauses – conţine faptele şi regulile cu care va opera Prolog pentru satisfacerea

interogărilor. (un fapt precizează “o proprietate a unui obiect sau exprimă o relaţie dintre mai

multe obiecte”. Forma sintactică generală prin care pot fi descrise faptele este: relaţie ( obiect1,

obiect2, …, obiect n ). Sfârşitul unui fapt se identifică prin simbolului ‘ . ’ O regula exprimă “o

relaţie de dependenţă între fapte” şi permite descrierea unor informaţii noi în baza celor deja

cunoscute.)

Predicates – secţiunea în care se declară predicatele şi domeniile argumentelor. În capul

regulii avem un singur predicat. În corpul regulii pot apare unul sau mai multe predicate, legate

între ele prin conectorul „and”. Un fapt poate fi privit şi ca o regulă cu corpul vid. În Prolog

numele de variabile trebuie să înceapă cu majusculă sau „_” (liniuţa de subliniere), urmate de

litere, cifre sau simbolul ‘_’ care înseamnă “orice”. Se foloseşte atunci când în scrierea unei reguli

o variabilă apare o singură dată .)

Domains – cuprinde declararea domeniilor (tipurilor) utilizate în program şi care nu sunt

domenii standard.

Goal – este secţiunea în care se fac interogările. Scopurile sunt folosite pentru a chestiona

sistemul despre informaţiile pe care le are referitor la relaţiile şi obiectele declarate. Scopurile pot

fi interne sau externe. Un scop intern se va scrie în secţiunea „goal”. Unul extern se va scrie în

fereastra de dialog, după rularea programului (dacă acesta nu conţine secţiunea „goal”).

2. Tipuri de date Prolog

Există două clase de tipuri, tipul elementar şi tipul complex. Tipul elementar poate fi

standard sau definit de utilizator. Tipurile definite de utilizator sunt de fapt tot tipuri standard,

dar definite prin nume date de utilizator, nume ce sugerează semnificaţia obiectelor de tipul

respectiv. Tipul complex la rândul lui se subîmparte în: tipul compus şi tipul listă. Un nume de

tip compus are următoarea structură sintactică: nume simbolic urmat de unul sau mai multe tipuri

separate prin virgulă şi închise între paranteze rotunde. Un obiect de tip listă este un şir de obiecte

de acelaşi tip, separate prin virgulă şi închise între paranteze drepte. Elementele unei liste pot fi de

tip elementar sau de tip compus. Tipurile file, ref, db_selector, bt_selector şi place se referă la

fişiere sau baze de date externe.

Tipurile de date cele mai uzuale sunt:

integer – număr cuprins între 32768 si 32767; ex. 10, 0, -15;

char – character încadrat între apostrofuri. Ex. “D” “3” “@”;

real – număr real al cărui modul este cuprins între 5.e-324 şi 1.7e+308. Ex. 6.7, 0.056,

16.3;

symbol – şir de caractere în cere primul character este literă mica. Ex.caracter,character_3;

string – şir de caractere cuprinse între ghilimele. Ex. “literă” “8abc” “38”;

3. Termeni in Prolog

Termenii sunt formaţi dintr-o mulţime de caractere, iar cele recunoscute de limbajul

Prolog sunt:

- mulţimea de litere majuscule,

- mulţimea de litere minuscule,

- mulţimea de caractere numerice,

- mulţimea de caractere speciale.

Termenul este singura structură de date utilizată în programarea logică. Mulţimea de

termeni ce poate fi creată şi utilizată în Prolog sunt: termenii simpli şi structuraţi, cei simpli sunt

constante şi variabile, iar constantele pot fi atomi şi numere. Diferenţa dintre diverşi termeni se

bazează doar pe sintaxa lor.

Termeni simpli:

Constantele definesc obiecte specifice, particulare, sau relaţii particulare. Există două

tipuri de constante: atomi şi numere.

Atomii sunt constante simbolice care încep cu o litera mica si pot contine litere, cifre si

caracterul “_”. Exista si alte caractere ce pot forma atomi speciali, care au o semnificatie aparte in

limbaj. Atomii pot desemna:

- obiecte constante care sunt argumentele predicatelor, de exemplu atomii mihai şi

maria în faptul iubeste (mihai,maria);

- predicate Prolog, fie cele definite de utilizator, fie cele predefinite în sistem; de

exemplu atomul iubeste în faptul iubeste (mihai,maria);

- atomi speciali, de exemplu atomii “:-” si “?-”

Numerele pot fi întregi sau reale.

Variabile - predicate Prolog care admit ca argumente şi obiecte generice. Numele unei

variabile începe cu litera mare şi poate conţine litere, cifre şi caracterul ”_”. Numele unei

variabile poate fi şi simbolul “_”, ceea ce indică o variabilă anonimă. Utilizarea unei variabile

anonime semnifică faptul că nu conteaza valoarea la care se va instanţia acea variabilă. O

variabilă poate fi instanţiată (legată) daca există un obiect asociat acestei variabile, sau

neinstanţiată (liberaă), dacă nu se ştie înca ce obiect va desemna variabila.

Termeni structuraţi – desemnează un obiect în care sunt regrupate alte obiecte numite

component. Regruparea permite o manipulare mai ușoară a obiectelor complexe. Un termen

structurat se definește de functorul său, componentele sale și aritatea sa. Acesta poate fi

reprezentat sub forma unui arbore a cărui rădăcină e simbolul functional, numărul de descendenţi

ai rădăcinii fiind paritatea, adică numărul de component ale termenului structurat ordonarea

descendenţilor corespunde ordonării componentelor. Sintaxa termenelor structurați e

asemănătoare cu cea a faptelor.Deci, un predicat poate fi considerat ca un termen structurat a

cărui functor este numele predicatului, iar argumentele reprezintă componentele termenilor

tructuraţi.

4. Tipuri de reguli in Prolog: cu conjunctii şi disjuncţii

4.1. Structura unei reguli.

O regula Prolog exprimă un fapt care depinde de alte fapte şi este de forma: S :- S1, S2, …

Sn. cu semnificatia urmatoare: S dacă S1 şi S2 şi ... şi Sn. Fiecare Si, i = 1,n si S au forma faptelor

Prolog, deci sunt predicate, cu argumente constante, variabile sau structuri. Faptul S care

defineşte regula, se numeste antetul regulii, iar S1, S2, …Sn formeaza corpul regulii şi

reprezintă conjuncţia de scopuri care trebuie satisfăcute pentru ca antetul regulii să fie satisfacut.

În condiţiile existenţei regulilor în baza de cunoştinţe Prolog, unificarea scopului se încearcă atât

cu fapte din baza de cunoştinţe, cât şi cu antetul regulilor din baza de cunoştinţe. La unificarea

unui scop cu antetul unei reguli, pentru a putea satisface acest scop trebuie satisfacută regula.

Aceasta revine la a satisface toate faptele din corpul regulii, deci conjuncţia de scopuri (de la

stânga la dreapta). Scopurile din corpul regulii devin subscopuri a caror satisfacere se va încerca

printr-un mecanism similar cu cel al satisfacerii scopului iniţial. La satisfacerea unei conjuncţii de

scopuri în Prolog, se încearcă satisfacerea fiecărui scop pe rând, de la stânga la dreapta. Prima

satisfacere a unui scop determină plasarea unui marcaj în baza de cunoştinţe în dreptul faptului

sau regulii care a determinat satisfacerea scopului. Dacă un scop nu poate fi satisfăcut (eşuează),

sistemul Prolog se întoarce şi încearcă resatisfacerea scopului din stânga, pornind căutarea în baza

de cunoştinţe de la marcaj în jos. Înainte de resatisfacerea unui scop se elimină toate instanţierile

de variabile determinate de ultima satisfacere a acestuia. Dacă cel mai din stânga scop din

conjuncţia de scopuri nu poate fi satisfăcut, întreaga conjuncţie de scopuri eşuează.

5. Baze de fapte şi baze de cunostinte în Prolog.

Bază de fapte - faptele reprezintã propoziții adevãrate si se pot grupa într-o bazã de fapte

sau într-o bază de cunoştinţe. Baza de cunostinţe conţine fapte şi reguli, ambele fiind considerate

clauze Horn. Numele faptelor trebuie să înceapã cu literă micã. În programe simple Prolog/Visual

Prolog, fără componente vizuale şi obiectuale (fără clase, etc.), nu există secţiunea facts, iar

faptele fac parte dintr-o bază de cunostinţe/fapte. Secţiunea facts poate fi inclusă numai în

declaraţii/implementări de clase.

Bază de cunoştinţe - contine fapte si reguli, ambele fiind considerate clauze Horn. Baza

de cunostințe dintr-un program Prolog este formatã din mulțimea regulilor si faptelor conținute

de acesta. Baza de cunostințe a unui program Visual Prolog este formatã din clauze Horn (fapte şi

reguli). Compilatorul Visual Prolog urmăreste un scop (o întrebare, o interogare), încercând sã

rãspundã la întrebare, sã proceseze interogarea bazei de cunostințe. Vor fi douã posibilităţi: fail şi

backtracking.

1. Unificarea in Prolog. Exemple.

Unificarea reprezintă modul în care Prologul realizează potrivirile între termeni. La prima

vedere, procesul de unificare pare explicat de fraza obiectul ţintă poate fi potivit obiectului sursă.

Presupunerea implicită este că numai obiectul ţintă este modificat. Dar nu se întâmplă astfel: se

încearcă atât modificarea obiectului ţintă, cât şi a obiectului sursă. De exemplu, dacă se încearcă

potrivirea termenului autor(mihai, X) cu termenul autor(Y, eminescu) am fi tentaţi să credem că

unica substituţie care se face este X/eminescu. Unificarea realizează însă ambele substituţii:

X/eminescu şi Y/mihai. În urma acestui proces, ambii termeni arată astfel: autor(mihai,

eminescu). Procesul de unificare se realizează în ambele sensuri.

Regulile generale pentru determinarea în ce mod doi termini, termen 1 si termen 2 pot fi

unificați.- Menționăm că dacă termenul 1 e o variabilă instanțiată, atunci teremnul 1 se comport ca

termenul cu care a fost instanțiată, adică ca o constantă sau o structură, sau o altă

variabilă.

- dacă termenul 1 și termenul 2 ambii sunt atomi sau numere, ei pot săse unifice cînd

fiecare are același functor principal, acelați număr de argumente și argumentele ce

corespund acelorași poziții la rîndul său pot să se unifice.

- Dacă termenul 1 și termenul 2 sunt ambii variabile neinstațiate, ei pot fi unificați.În acest

caz, variabilele rămîn neinstanțiate, dar legate una de alta, pînă cel puțin una din ele nu va

fi instanțiată și atunci, și cealaltă devineautomat instanțiată cu același termen.

Exemplu. Atomii și numerele se unifică numai cu ei însăși.Prologul procedează astfel.El compară

termenii de la stînga la dreapta symbol cu symbol.Dacă toate simbolurile acestor doi termini

coincide, atunci ei se unifică, în caz contrar ei nu se unifică.

Termen1 Ala, termen 2 ala – se unifică.

Termen1 13, termen2 13.0 – nu se unifică.

Termen1 -, termen2 minus – nu se unifică.

Termen1 8, termen2 8 – se unifică.

Un termen structurat se unifică cu altul dacă și numai dacă: au același functor, au același număr

de argumente, orice argument al uni termen se unifică cu argumentul corespunzător al celuilalt

termen.

2. Expresii aritmetice si logice in Prolog.

Expresiile aritmetice constau din operanzi (numere şi variabile), operatori (+, -, *, /, div şi

mod) şi paranteze.Valoarea unei expresii poate fi calculată dacă toate variabilele sunt legate la

momentul evaluării. Calculele se fac într-o anumită ordine determinată de prioritatea operatorilor

aritmetici: operatorii cu cea mai mare prioritate sunt evaluati primii. Expresiile relaționale - se

pot compara expresii aritmetice, caractere, șiruri și respective simboluri. Operatorii releționali

sunt: <, >, <=, >=, <>, sau ><, =.

Prologul dispune de operatorii pentru cele patru operaţii aritmetice de bază şi operatorii unari

minus şiplus, la care se adaugă operatorii mod şi div . Se folosesc simbolurile următoare:

- Operatori binari: + adunare

- scădere

* înmulţire

/ împărţire

mod restul împărţirii întregi

div împărţirea prin trunchiere

- Operatori unari: - (semnul) minus

+ (semnul) plus

Expresiile obţinute cu ajutorul acestor operatori se evaluează pe baza unui set de reguli,

care precizează precedenţa şi asociativitatea operatorilor precum şi conversiile aplicate

operanzilor:

• Precedenţa (prioritatea) determină ordinea de efectuare a operaţiilor într-o expresie cu

diverşi operatori.

• Asociativitatea indică ordinea de efectuare a operaţiilor într-o secvenţă de operaţii care

au aceeaşi precedenţă.

• Regulile de conversie de tip asigură stabilirea unui tip comun pentru ambii operanzi, la

fiecare operaţie care solicită acest lucru şi în care tipurile diferă.

Asupra reprezentărilor binare a datelor numerice se pot executa o serie de operaţii

specifice de obicei prelucrărilor în limbaj de asamblare:

• Complementarea reprezentării binare : predicatul bitnot(operand1, X) are ca effect legarea la

variabila X a valorii întregi a cărei reprezentare binară se obţine prin complementarea bit cu bit a

reprezentării binare a operand1 (complementare înseamnă înlocuirea valorii 0 cu valoarea 1 şi

invers).

• Deplasarea la stânga a reprezentării binare : predicatul bitleft(operand1, nr_poziţii, X) are ca

efect legarea la variabila X a valorii întregi a cărei reprezentare binară se obţine prin deplasarea

la stânga cu nr_poziţii a codului binar al operand1 (deplasarea la stânga se obţine prin eliminarea

a unui număr egal cu nr_poziţii de biţi din stânga şi inserarea în dreapta a unui număr de

nr_poziţii de biţi egali cu zero).

• Deplasarea la dreapta a reprezentării binare: predicatul bitright(operand1, nr_poziţii, X) are

ca efect legarea la variabila X a valorii întregi a cărei reprezentare binară se obţine prin

deplasarea la dreapta cu nr_poziţii a codului binar al operand1 (deplasarea la dreapta se obţine

prin eliminarea a unui număr egal cu nr_poziţii de biţi din dreapta şi inserarea în stânga a unui

număr de nr_poziţii de biţi egali cu bitul cel mai semnificativ).

Şi : predicatul bitand(operand1, operand2, X) are ca efect legarea la variabila X a valorii întregi

a cărei reprezentare binară se obţine prin operaţia “şi” asupra reprezentărilor binare ale

operanzilor.

• Sau : predicatul bitor(operand1, operand2, X) are ca efect legarea la variabila X a valorii

întregi a cărei reprezentare binară se obţine prin operaţia “sau” asupra reprezentărilor binare ale

operanzilor.

• Sau exclusiv : predicatul bitxor(operand1, operand2, X) are ca efect legarea la variabila X a

valorii întregi a cărei reprezentare binară se obţine prin operaţia “sau exclusiv” asupra

reprezentărilor binare ale operanzilor.

3. Recursivitate si backtracking (profilul real)

Intuitiv recursivitatea se naşte în clipa în care o schiţă este construită prin reproducerea ei

însăşi, la o altă scară sau la un alt nivel. În cadrul programării recursivitatea este o tehnică care

constă în posibilitatea de a include într-o procedură apeluri la ea însăşi. În PROLOG, acesta se

traduce prin posibilitatea ca un nume de predicat să apară atât în corpul unei reguli cât şi în capul

ei. Programarea în Prolog depinde foarte mult de această tehnică numită recursivitate. În

principiu, recursivitatea implică definirea unui predicat în funcţie de el însuşi. Cheia care ne

asigură că această tehnică are sens constă în aceea că întotdeauna trebuie să definim predicatul la

o scală mai mică. Recursia de la nivelul algoritmilor este echivalentă cu demonstrarea prin

inducţie din matematică. O definiţie recursivă (în orice limbaj, nu numai în Prolog) trebuie să

aibă întotdeauna cel puţin două părţi: o condiţie elementară şi o parte recursivă. Condiția

elementară definește un caz simplu, care știm că este întotdeauna adevărat. Partea recursivă

simplifică problema eliminînd inițial un anumit grad de complexitate și apoi apelîndu-se ea

însăși. La fiecare nivel, condiția elementară este verificată, dacă s-a ajuns la ea, recursivitatea se

încheie, altfel, recursivitatea continuă.

Pentru satisfacerea scopului în PROLOG se utilizează tehnica backtracking. Procesul de

resatisfacere prin backtracking poate fi oprit de programator cu ajutorul predicatului cut,

simbolizat prin caracterul !. Cut este un predicat fără argumente. În poziţia în care apare interzice

revenirea, blocând astfel căutarea de noi soluţii. Semnul “!” aşezat între clauzele pi şi pi+1 ale

scopului blochează resatisfacerea clauzei pi. Un efect asemănător se obţine utilizând tăietura

(semnul “!”) în corpul unei reguli, deoarece pentru satisfacerea corpului unei reguli PROLOG

utilizează backtracking.

Partea II. Program Prolog:

1. Conditia problemei: Crearea unui program prolog pentru a determina care sunt relaţiile

dintre obiecte şi de a obţine informaţiile referitoare la obiecte şi relaţiile dintre ele.

2. Prezentarea schemei ierarhice a problemei (pe cel putin 3 nivele) si a legaturilor

(relatiilor) intre obiecte.

Arborele genealogic.

Aliona Dumitru

Ala Alina

Angelina

3. Program Prolog.

domains

s=symbol

predicates

parinte(s,s)

femeie(s)

barbat(s)

acelasi_parinte(s,s)

sora(s,s)

matusa(s,s)

clauses

parinte(dumitru,ala).

parinte(dumitru,alina).

parinte(alina,angelina).

parinte(aliona,alina).

parinte(aliona,ala).

femeie(aliona).

femeie(ala).

femeie(alina).

femeie(angelina).

barbat(dumitru).

acelasi_parinte(X,Y):-parinte(P,X),parinte(P,Y),X<>Y.

sora(X,Y):-acelasi_parinte(X,Y),femeie(X).

matusa(X,Y):- femeie(X),acelasi_parinte(X,P),parinte(P,Y).

bunel(X,Y):-barbat(X), parinte (X,P), parinte (P,Y).

bunica (X,Y):- femeie(X),parinte(X,P),parinte(P,Y).

4. Alcatuirea interogarilor in Prolog si prezentarea echivalentului interogarilor in

limbajul natural.

1. parinte(Parinte,_) – Cine sunt parinti?

Parinte=dumitru

Parinte=dumitru

Parinte=aliona

Parinte=aliona

Parinte=alina

5 Solutions

2. parinte(_,Copil) – Cine sunt copiii?

Copil=ala

Copil=alina

Copil=ala

Copil=alina

Copil=angelina

5 Solutions

3. parinte(Parinte,ala) – Cine sunt parintii Alei?

Parinte=dumitru

Parinte=aliona

2 Solutions

4. parinte(alina,_) – Este oare Alina parinte?

Yes

4. bunil(dumitru,angelina)-Este oare Dumitru bunelul Angelinei?

Yes

6. parinte(_,_) – Este oare predicatul “parinte” in baza de date?

Yes

7. parinte(Parinte,Copil) – Cine sunt parintii si copii lor?

Parinte=dumitru, Copil=ala

Parinte=dumitru, Copil=alina

Parinte=aliona, Copil=ala

Parinte=aliona, Copil=alina

Parinte=alina, Copil=angelina

5 Solutions

8. parinte(aliona,alina) – Este oare Aliona parintele Alinei?

Yes

9. parinte(aliona,Copil) – Cine sunt copiii Alionei?

Copil=ala

Copil=alina

2 Solutions

10. matusa(ala,angelina)- Este oare Ala matusa Angelinei?

Yes

11. bunica(aliona,angelina) – Este oare Aliona bunica Angelinei?

Yes

12.sora(ala,alina) –Este oare Ala sora Alinei?

Yes

5. Analiza solutiilor.

În cadrul programului, Arborele genealogic, cu ajutorul programului Prolog am încercat să

stabilim care sunt relațiile dintre parinți și copiii. De asemenea, am observat că programul

respectiv poate dezvolta numeroase posibilități de determinare a legaturilor dintre fapte și

reguli.

Obiectivul principal a fost de a observa modul în care se realizează satisfacerea scopului unui

program în PROLOG. Astfel, dacă baza de fapte poate satisface întregul scop, PROLOG

răspunde cu “yes”, iar în caz contrar răspunde cu “no”. Atunci cînd scopul conţine variabile,

atunci obiectivul este acela de a găsi, toate legăturile posibile pentru variabile, care să satisfacă

scopul. În exemplul nostru anterior am putea observa cum au fost realizate ambele scopuri, atît

ce ține de afirmarea sau infirmarea existenței unei legături dintre fapte și relații, cît și

identificarea tuturor legăturilor posibile dintre membrii familiei analizate.