Programare Logica si Functionala

Programare logic i funcional

1. Introducere

1.1 Clasificarea limbajelor de programare

Limbajele de programare sunt mprite pe diferite niveluri n funcie de gradul de interaciune cu suportul hardware:

Limbaje main corespund unui set de instruciuni restrnse pentru o arhitectur hardware particular i sunt dependente de main. Instruciunile au lungimi de 16, 24, 32, 64 bits. Primii bii specific codul operaiei, iar ceilali specific operanzii sau modurile de adresare. De obicei se exprim n binar i realizeaz operaii de baz (transfer de date ntre memoria central i procesor, instruciuni de calcul aritmetic i logic). Este dificil s se programeze la acest nivel, deoarece trebuie s se considere lucrul cu regitrii, modurile de adresare, maparea memoriei. Datorit acestei modaliti de programare la detalii sunt des ntlnite erorile.

Limbajele de asamblare folosesc mnemonici pentru operaii i operanzi, ceea ce face instruciunile main mai uor de scris i de neles. nainte de a rula un program n limbaj main codul trebuie transformat ntr-o form de limbaj main.Programul translator carerealizeaz acestlucruse numete

assembler. Limbajele de asamblare sunt mai uor de programat dect limbajele main, dar au dezavantajul c sunt dependente de main. Assemblere-le vin de obicei odat cu partea hardware i sunt specifice unei configuraii hardware.

Limbaje de nivel nalt subliniaz natura unei probleme i folosete proceduri pentru rezolvarea problemei. Aceste limbaje sunt independente fa de main, iar programele pot rula pe orice tip de configuraie hardware. Limbajele de nivel nalt se clasific n procedurale i declarative (neprocedurale). Mai mult, se pot clasifica i n interpretate sau compilate. Sunt posibile oricare combinaii dintre dou din tipurile enumerate mai sus.

Limbajele de nivel foarte nalt includ limbajele de generaia a patra, limbajele de interogri baze de date i limbajele vizuale (de exemplu, Visual Basic). n aceast categorie pot fi incluse i limbajele de nivel comand (exemple, Shell Unix, DOS Batch Command Language).

Un limbaj procedural (de exemplu, C, Java) folosete o secven logic de pai pentru a obine rezultate. Cu alte cuvinte, acest tip de limbaje trebuie s conin informaii despre cum (how) se poate obine rezultatul ateptat.

Limbajele declarative (numite i limbaje de generaia a-4-a sau limbaje de procesare simboluri)demonstreazce (what) va firealizati elibereaz programatorului de specificarea detaliilor pailor (exemple, LISP i variantele sale, Prolog). ntr-un program declarativ se specific definiiile taskurilor care trebuiesc ndeplinite, dar fr a se urmri detaliile despre cum se ndeplinesc task-urile.

Un interpretor este un program translator, care interpreteaz individual comenzile i corespunztor cu configuraia calculatorului. Translatarea are loc de fiecare dat cnd este rulat un program. Interpretorul lucreaz repetnd urmtoarele trei operaii la ntlnirea fiecrei linii din program: citete linia din codul surs; analizeaz, verific i codific binar linia; execut instruciunea asociat cu linia interpretat. n acest caz, limbajul se spune c este interpretat (exemple tipice, Basic, LISP, Prolog, TclTk). Este

1

posibil s existe ambele variante ale unui limbaj, interpretat i compilat. Interpretoarele implementeaz direct comenzile unui limbaj de nivel nalt ntr-un calculator, prin interpretarea a ceea ce cere comanda. Dac este o bucl, va fi interpretat de fiecare dat i calculatorul va da instruciuni echivalente. Aceast modalitate de lucru poate fi uneori ineficient i consumatoare de timp.

Un compilator este un program translator care convertete programul ntr-un limbaj main echivalent. Odat tradus, programul poate rula de oricte ori se dorete. n acest caz se spune c limbajul este compilat (exemple C++, Java, Pascal). Compilatoarele produc cod main echivalent care poate fi optimizat s ruleze eficient. Dac se mai adaug i faciliti de testare i debugging, limbajele compilate sunt folosite mai des pentru aplicaii.

Avantajele la limbajele interpretate: disponibilitatea programului surs pentru modificri, realizarea rapid de programe mici i execuia lor. Dezavantajele limbajelor interpretate provin din faptul c nu exist programe executabile, interpretorul trebuie furnizat cu programul surs dac se dorete executat, sunt mai lente ca programele compilate. Dezvoltarea unui program compilat dureaz mult mai mult dect unul interpretat.

Sistemele de operare asigur suport prin interpretoare, compilatoare, assemblere, linkeditoare, editoare. Aceste programe sistem pot accesa rutine folosite pentru funciile uzuale (de exemplu citirea sau afiarea unor date), care sunt cuprinse n biblioteci.

Etapele de lucru pentru:

Limbajul interpretat

Cod sursa

(fisier)

Date de intrare

Computer Interpretor pentru limbaj

Date de iesire

Program sursa

Citeste intrare

(comanda)

Evalueaza

(interpreteaza)

Ruleza

(executa)

Afiseaza iesire

(rezultate)

ciclare

Un ciclu de interpretare const n citire-decodare-aciuni-scriere. Primii doi i ultimii doi pai pot fi combinai. Termenul generic de decodare indic interpretarea unei propoziii surs i analiza lexical a formurilor sau evaluarea expresiilor. Aciunea implic transferul datelor i calculul acestora. n unele cazuri

(de exemplu la Lisp pentru ciclul citete-interpreteaz-scrie), pot fi dou tipuri de ieiri, una disponibil s fie citit din nou, iar alta care satisface cererile cerute de utilizator.

2

Limbajul compilat

Cod sursa

(fisier)

Directive de compilare

Computer Compilator pentru limbaj

Date de intrare

Cod echivalent, n limbaj maina

Date de iesire

Program sursa

Analiza lexicala

Analiza sintactica

Generare de cod

OptimizareModul obiect

Procesul de compilare implic, n mod normal, o secven de pai sau faze. Aceti pai, care realizeaz verificarea i analizarea ntregului fiier surs, sunt etape ale compilrii.

1.2 Principiile programrii

Se face referire la principiile programrii structurate. Scopul acestor principii este de a ghida programatorul n planificarea i realizarea programelor complexe. Aceste principii, au ca intenie prescrierea regulilor aplicabile oricrui tip de programare i a structurilor de control utilizate n programare (n englez, constructs).

Principiile programrii structurate sunt:

Structura ierarhic top-down;

Modularitatea;

Definirea clar a intrrilor i ieirilor;

Intrare simpl, ieire simpl;

Folosirea exclusiv a structurilor secven, selecie, case, iteraie.

Funciile i procedurile sunt folosite mai ales n limbajele procedurale. Dar i limbajele neprocedurale conin construcii similare,cu definiii diferitei cu implementri distincte.

O funcie poate accepta argumente multiple i poate returna un singur rezultat. Din acest motiv, o funcie poate accepta ca argument o invocare a altei funcii (prin care se pot transmite rezultat multiple). O procedur poate fi definit cu argumente multiple i poate ntoarce rezultate multiple. Procedurile nu pot folosi alte proceduri ca argumente. Deosebirea dintre proceduri i funcii este c primele pot avea rezultate multiple.

Pentru operaiile de intrare-ieire sunt disponibile diferite tipuri de date i structuri.

1.2.1 Structuri de programare

Structurile de programare sunt diferite din punctul de vedere al aspectului i al comportamentului la diverse limbaje de programare, dar implementeaz aceleai principii fundamentale.

Structurile de programare sunt:

Secvena este o comand simpl sau un grup de comenzi care alctuiesc un bloc de program. Blocurile de program sunt delimitate prin simboluri sau prin cuvinte cheie

3

(de exemplu, {, }, begi, end, [, ]). Exemplu de comand simpl atribuirea

(lvaloare:=rvaloare). Limbajele de asamblare folosesc comanda MOVE item-surs to destinaie.

Selecia simpl permite execuia condiional a unei secvene de instruciuni. Implementarea acestei structuri se face cu ajutorul instruciunii if-else sau if-then- else sau formatul simplificat, ?:.

Selecia multipl (case) este o form general de selecie, n care, punctele de control au alegeri multiple. Cuvintele cheie folosite sunt switch, case, of, got o, depending on.

Repetitive iteraia i recursia, care realizeaz execuia repetat a unui secvene de comenzi. Structura de iteraie asigur controlul explicit al unei bucle, corespunztor cu condiiile impuse n instruciune. Cuvintele cheie utilizate pentru implementarea iteraiei sunt do-while, repeat-until, for-next, while. Execuia repetitiv se poate executa i cu ajutorul subrutinelor care se apeleaz n ele nsele, procedeul numindu- se recursivitate. Limbajele procedurale folosesc repetiia cu control explicit, iar cele declarative (logice, procedurale) folosesc recursivitate.

Structurile de programare pot avea interpretri apropiate sau nu n implementrile din diferitele limbaje de programare. Majoritatea structurilor din limbaje de programare sunt implementate ca subprograme, care sunt fiiere compilate separat (cu excepia limbajelor interpretate). Subprogramele sunt seciuni identificabile care servesc scopuri distincte n cadrul unui fiier program. Un subprogram corespunde unui aa numit modul software, un fiier pe disc, care poate sau nu s fie executat separat. Modulele conin subrutine, iar n unele cazuri, subrutinele mpreun cu structurile de date se numesc packages. Termenul de subrutin este folosit pentru proceduri interne i funcii care completeaz un modul.

Un subprogram, vzut ca obiect independent, trebuie s fie inclus n faza de linkeditare i n subrutinele n care poate fi folosit de alte programe (shared). Trebuie s se fac distincie ntre programul principal main, care poate fi doar apelat i care ruleaz de sine stttor cu ajutorul serviciilor sistemului de operare, i, subprograme, care sunt apelate de programul principal sau de alte subprograme. Astfel, programul principal apeleaz alte subprograme i le face s ruleze.

Implementrile structurilor de programare i declaraiile de rutine i subrutine se realizeaz conform regulilor sintactice ale limbajului de programare.

1.2.2 Tipuri i structuri de date

Tipurile de date (data type) sunt tipuri fundamentale, care sunt disponibile ntr- un limbaj de programare. Mai sunt numite i tipuri predefinite (built-in). Tipurile adiionale, construite plecnd de la tipurile fundamentale, se numesc tipuri definite de utilizator (user-defined).

Reprezentarea intern a unui tip de date determin precizia limbajului.

Tipurile de date avansate sunt mixturi omogene din acelai tip de date sau mixturi eterogene din tipuri diferite. Primele sunt reprezentate prin iruri de date (array), care pot fi vectori (vector) sau matrici (matrix) sau chiar cu 3 dimensiuni. Din a doua categorie fac parte nregistrrile (record) i structurile (struct). Aceste tipuri sunt, de obicei, independente de reprezentarea intern n memorie.

Tipurile de date i structurile de date se mai numesc i tipuri de date abstracte

(abstract data types).

Un alt aspect al datelor este reprezentarea nainte sau n timpul rulrii programului, de unde i denumirea de date statice sau dinamice.

4

Fiecare limbaj de programare poate avea propria sa terminologie i concepte la care se face referire ca sintaxa limbajului.

Exemplu: de structuri definite n diferite limbaje de programare:

Limbaj C o structur poate fi definit de utilizator cu nume i cmpuri:

struct persoana{

char nume[20];

int varsta;

} pers;

Lisp se numete proterty list i se definete ca o list de perechi atom-valoare, care are structur de arbore:

(SETQ PERSOANA(NUME (Popescu Ion)

VARSTA 45)))

Prolog se numete functor i se definete ca atom urmat de argumente: Persoana (nume (Popescu Ion), varsta (45)).

1.2.3 Taxonomia

Se refer la clasificarea limbajelor de programare. Se aplic limbajelor de nivel nalt, deoarece ofer mecanisme pentru dezvoltare, cu evitarea detaliilor hardware. Limbajele pot fi clasificate dup urmtoarele criterii:

1. scopul propus i aria de utilizare;

2. scopul principal de aplicare;

3. filozofia, stilul sau paradigma de programare.

1. ar fi ideal dac s-ar putea utiliza un singur limbaj pentru toate domeniile de aplicabilitate ale calculatoarelor. Fiecare limbaj de programare este indicat a fi folosit pentru un domeniu restrns. De exemplu, C este un limbaj de nivel sistem, uor de implementat, tiinific, folosit i pentru aplicaii de tip business, dar i la nivel academic; Ada - este utilizat n programarea sistemelor dependente de timp; Lisp util la procesare de liste i expresii simbolice, cu implementri n inteligena artificial; Prolog este un limbaj de programare logic pentru demonstrare de probleme i este implementat n aplicaii de inteligen artificial care modeleaz logica predicatelor.

2. clasificarea domeniilor de aplicabilitate:

-aplicaii tiinifice programare liniar, analiza regresiilor, soluii ale ecuaiilor difereniale, etc.;

-procesri de date pentru business state de salarii, calcule, facturare, inventarieri, vnzare, informaii management, etc.;

-procesoare de text editare, formatare, setri de editare, listare, verificri gramaticale, etc.;

-home entertaiment jocuri, filme, muzic, etc.;

-inteligen artificial prelucrarea limbajului natural, sisteme expert pentru diagnoz, micri roboi, metode inteligente de rezolvare de probleme, etc.;

-programare sistem componente sisteme de operare, compilatoare, interpretoare, assemblere, drivere, sisteme n timp real cu tratri de excepii, etc.;

3. la acest punct clasificarea se bazeaz pe modelul teoretic al computaiei:

-imperative Ada, Basic, C, Cobol, Fortran, Pascal, Java. Controlul este direcionat pe aciuni, iar aciunile sunt realizate prin proceduri specificate pas cu pas;

-funcionale (simbolice) Lisp, Scheme, Ml, Acml. Se bazeaz pe computaia funcional, care implic expresii incluse n alte expresii, iar fiecare expresie

5

utilizeaz funcii care pot folosi alte funcii ca parametri. Teoria matematic

implicat este calculul lambda .

-Logice - Prolog. Implic evaluri ale expresiilor logice care conduc la rezultatele dorite. Teoria matematic care st la baz este calculul predicatelor.

-concurente Ada (nivel de task), Fortran (la nivel comand). Permit diferitelor pri din program s ruleze concurent. Are dou avantaje: permite programarea condus de evenimente n care pri din program sunt rulate ca rspuns la evenimente, i folosete calculabilitatea paralel pentru creterea vitezei de execuie.

-orientate obiect Smalltalk, C++, Java. Permit controlul bazat pe obiecte. Fiecare obiect are o descriere care corespunde structurilor de date i un set de aciuni care lucreaz asupra structurilor de date.

-vizuale VisualBasic, VisualC++. Implementeaz instruciuni pentru controlul aciunilor la interfaa grafic.

1.2.4 Elemente de limbaj

Alfabet/Vocabular reprezint setul de caractere de baz utilizat n scrierea de programe.

Elemente lexicale blocuri primitive construite cu ajutorul alfabetului. Elementele lexicale pot fi: cuvinte rezervate (numerice, alfanumerice, constante), cuvinte cheie, identificatori (nume date de utilizator unor structuri), literali, simboluri (operatori, delimitatori, separatori, comentarii).

Construcii sintactice tipuri de date i structuri, expresii, variabile scop i clase de memorare, proceduri, funcii.

1.3 Concepte de reprezentare

Pentru reprezentarea i implementarea limbajelor de programare este nevoie de limbaje formale, care trebuie s fie precise (s nu permit mai multe interpretri, s nu fie ambigui), expresive, concise (o exprimare s se realizeze printr-un numr finit de expresii), s asigure procedurile prin care se pot folosi expresiile limbajului pentru realizarea de raionamente. Conceptele fundamentale sunt aceleai pentru orice limbaj folosit pentru a reprezenta cunotine.

Conceptele de reprezentare au n vedere urmtoarele aspecte:

Sintaxa stabilete regulile care trebuie respectate pentru scrierea corect din punct de vedere sintactic a unui program ntr-un limbaj de programare. Aceste reguli se refer la elementele sau entitile primitive (elemente lexicale).

Semantica asigur explicaia, interpretarea sau nelesul entitilor sintactice. Prin semantic se urmrete ce efecte va avea sintaxa la execuia unui program.

Pragmatica include toate aspectele colaterale n implementarea programrii unui limbaj i stilul de programare (strategiile i filozofia stilului de programare). Pragmatica se mai numete i paradigm sau stil de programare. Aceste paradigme pot fi imperative, funcionale, logice, concurente, orientate obiect, vizuale.

6

1.3.1 Sintaxa

Este stabilit printr-un set de reguli i convenii pentru realizarea corect de programe. Gramatica asigur o notaie formal pentru specificarea sintaxei unui limbaj de programare.

O gramatic independent (liber) de context, care se numete simplu gramatic (n tiina calculatoarelor), este implicat n teoria formal a limbajelor. O astfel de gramatic este utilizat la descrierea sintaxei limbajelor de programare, care sunt considerate limbaje de nivel simplu. Este folosit, de asemenea, i la definirea algoritmilor de analiz din punct de vedere gramatical (engl. parsing), care determin, pentru un ir dat, dac i cum poate fi generat de gramatic.

O gramatic dependent de context, implic definirea complex a limbajelor, inclusiv a limbajelor naturale.

O gramatic independent de context are patru pri:

Simboluri terminale sunt simboluri de sine stttoare (de exemplu constante).

Simboluri non-terminale grupri de alte simboluri dect cele terminale.

Producii prin care se specific aciuni, nlocuiri sau rescrieri (de exemplu,

, =>).

Simboluri de nceput (iniiale) care specific axiomele gramaticii.

O gramatic liber de context este o gramatic formal n care fiecare regul de producie este de forma V w, unde V este un simbol non-terminal, iar w este un ir format din simboluri terminale sau non-terminale. Termenul de independent de context provine de la faptul c simbolul non-terminal V poate fi ntotdeauna nlocuit cu simbolul w, fr s se ia n considerare contextul n care apare.

Un limbaj formal este independent de context dac exist o gramatic liber de context care l genereaz.

Pentru a specifica o gramatic exist diferite notaii i convenii:

Backus-Naur Form (BNF) simbolurile terminale sunt scrise cu litere ngroate sau italice, cele neterminale sunt include ntre , atribuirea se specific prin simbolul ::=.

Extended BNF simbolurile neterminale ncep cu liter mare fr a fi nevoie de .

Diagrame de sintax.

Formate de codificare.

1.3.2 Semantica

Pentru a nelege semantica unui limbaj de programare este nevoie de documentaie. Documentaiile pot fi prezentate sub mai multe forme:

Tutoriale constau ntr-o prezentare ghidat i cuprind principalele aspecte i modul cum trebuiesc utilizate. Sintaxa, semantica i pragmatica sunt introduse gradual, dac este nevoie.

Ghidul utilizatorului (Users Guide) implic aspecte informale asupra implementrilor i aspectelor caracteristice ale limbajului.

Manualul programatorului (Programmers Reference Manual) este organizat n jurul sintaxeii a semanticii limbajului, ntr-o manier rigidi

7

comprehensiv. De obicei conine definiii sintactice formale ntr-o notaie formal. Are un grad de detaliere ridicat.

Definiii formale cuprind descrieri precise de sintax i semantic.

1.3.3 Pragmatici de programare

Reprezint stilul de programare care ncurajeaz anumite metode de rezolvare a problemelor sau paradigme. Aceste paradigme sunt aspecte reale de distingere n proiectarea unui limbaj de programare. Trebuie fcut observaia c toate limbajele implementeaz structuri sau constructori de baz pentru secveniere, selecie, repetare. Exist mai multe modaliti de programare astfel:

Iteraia i Recursia

Iteraia se refer la controlul explicit asupra componentelor unui program. n limbajele de programare este caracterizat n special prin bucle, numite i structuri iterative. Recursia se refer la controlul implicit asupra componentelor unui program prin aplicarea metodei de rezolvare asupra lor nsele repetat, pn la obinerea soluiei. n limbajele de programare acesta implic proceduri i funcii care fac referire la ele nsele. Un aspect care caracterizeaz i face distincie ntre iteraie i recursie este numrul de pai necesari pentru obinerea soluiei. Dac metoda este iterativ, numrul de pai este cunoscut. Dac metoda implementat este recursiv, atunci nu se cunoate numrul de pai. Limbajele funcionale (de exemplu, Lisp, Scheme, ML), utilizeaz recursivitatea i descurajeaz utilizarea iteraiei. Limbajele logice (de exemplu, Prolog), prin natura lor nu permit iteraia. Limbajele de programare clasice permit att iteraia, ct i recursia. Exemplu: calculul factorialului scris n limbaj C:

double fact-iterativ(int n){

int i; double f;

for (i=2; i0,

N1 is N-1,

fact-reursiv(N1,F1),

F is N * F1.

Tablouri i Liste

Un alt aspect este implementarea la diverse niveluri a tipurilor de date abstracte suportate de limbajele de programare. Folosirea termenului abstract indic independena fa de implementarea hardware.

Cel mai des ntlnite tipuri de date abstracte sunt nregistrrile (record). O nregistrare este o grupare eterogen de tipuri de date diferite. nregistrrile sunt principalul mecanism folosit pentru ierarhizarea datelor prin gruparea pe cmpuri i subcmpuri.

Tablourile sunt structuri de date de acelai tip, multidimensionale. Listele sunt structuri simbolice folosite n limbajele de procesare de liste (de exemplu Lisp). Listele pot reprezenta simbolic informaii ntr-o manier flexibil i uor utilizabil, dar sunt greu de manipulat. Tablourile sunt folosite n programe iterative, iar listele ncurajeaz metodele recursive. De obicei, tablourile sunt utilizate pentru manipulri de numere, n special ordonate, n timp ce listele pentru manipulri de simboluri neordonate.

Limbajele procedurale lucreaz cu tablouri, iar cele declarative (logice i funcionale) lucreaz cu liste.

Au fost realizate i implementri hardware pentru prelucrri simbolice, dar nu au rezistat n timp, spre deosebire de calculatoarele actuale care implementeaz software prelucrrile simbolice.

1.4 Paradigme de programare

1.4.1 Programare imperativ

Caracteristica acestui tip de programare este c folosete proceduri i funcii pentru abstractizarea componentelor funcionale ale unei probleme. Se alctuiesc ierarhii de proceduri i funcii care acioneaz ca structuri de date pasive i care alctuiesc mecanisme de control orientat aciune. Se numete orientat aciune deoarece procedurile conin informaii necesare pentru rezolvarea problemei i informaii despre procedurile de nivel de baz care particip la rezolvare. Aceast paradigm ncurajeaz folosirea limbajelor procedurale.

Limbajele de programare imperative sunt utilizate pentru descrierea algoritmilor i a structurilor de date concrete.

9

Pentru a scrie un program se folosesc structuri de programare, de baz (secvene, selecii, repetitive). Procedurile i funciile pot fi structurate pe module. Modulele sunt componente funcionale. Partiionarea unei probleme se face printr-o ierarhie top-down. Motivul principal pentru aceast abordare este simplificarea problemelor prin spargerea lor n sub-probleme.

Principalul aspect de discutat n legtur cu limbajele de programare procedurale este natura sau tipul procedurilor, modul de activare, cum se face transferul parametrilor i cum sunt obinute i transmise rezultatele. Deci la aceast categorie de limbaje subiectele de atins sunt: definirea funciilor i a procedurilor, invocarea rutinelor, transferul parametrilor, prelucrarea excepiilor.

Majoritatea limbajelor folosite n industrie i n scopuri pedagogice fac parte din aceast categorie. Sunt limbaje structurate pe module (cu definirea clar a scopurilor pentru date, cu respectarea referinelor i a modificrilor) i lucreaz cu tipuri de date

(definite n limbaj, mpreun cu operatorii i restriciile asociate).

1.4.2 Programare funcional

Se mai numete i programare aplicativ, deoarece aplic o funcie unei expresii. Aceast paradigm de programare are ca scop formularea problemelor mai aproape de raionamentul uman aplicat n domeniul matematicii. Este bine fundamentat din punct de vedere matematic. Dintre structurile de programare caracteristic este utilizarea recursiei (despre care, n literatura din domeniu, se susine c este mai apropiat de gndirea uman dect iteraia).

Fa de programarea imperativ, o funcie poate avea ca argument o alt funcie

(observaie nu rezultatul ntors de o alt funcie, chiar funcia n sine). De asemenea, listele de simboluri pot fi manipulate prin operaii care implic alte liste, iar operaiile realizate sunt doar liste de operaii. Din acest motiv se mai numesc i limbaje de procesare de liste simbolice.

Teoria matematic la baza acestor paradigme de programare este calculul lambda

, care provine de la notaia: ..

Avantaje ale utilizrii limbajelor de programare funcionale sunt: abordare simpl din punct de vedere matematic, ordinea execuiei componentelor este implicit, implementeaz modularitate, limbajele sunt extensibile i adaptabile prin posibilitatea definirii de funcii, uor de corectat, implementeaz mecanisme complexe pentru controlul fluxului de operaii.

Exemple de limbaje de programare Lisp, Scheme, Ml, Acml.

1.4.3 Programare logic

Se bazeaz pe faptul c, rezolvarea unei probleme const dintr-o reprezentare corespunztoare a cunotinelor. Limbajele de programare logic se mai numesc i limbaje declarative. Spre deosebire de limbajele procedurale, la care fiecare pas procedural trebuia specificat n detaliu, la limbajele declarative, se specific ceea ce se ateapt n obinerea soluiei (scopul problemei). Nu numai c soluia poate fi furnizat fr specificarea pailor necesari, dar programul poate explica uneori cum a obinut soluia.

Teoria matematic care st la baza acestei paradigme este logica predicatelor de ordin unu, care lucreaz cu entiti logice (nu cu numere). Logica predicatelor este o logic simbolic al crui scop este de a reprezenta tipuri de raionament. Atta timp ct

10

calculul predicatelor are reguli i formaliti matematice definite printr-o teorie, soluia la o problem specific este complet i efectiv.

Problemele care sunt indicate spre a fi rezolvate prin programare logic sunt din domeniul demonstrrii de problemei propagrii de cunotine. Programarea cunotinelor face parte sin metoda soluiei generale, care implic propagarea constrngerilor. Uneori se numete i propagarea adevrului, deoarece implic propagarea constrngerilor care implic valori de adevr. Valorile de adevr pot fi binare (T, F) sau multi-valoare (T, probabil T, posibil T, F).

Exemplu de limbaj de programare este Prolog.

1.4.4 Programare orientat obiect

Programarea imperativ lucreaz cu proceduri active asupra structurilor de date pasive, care sunt abstractizri ale obiectelor lumii reale. Dac se consider structurile de date (obiectele) active n controlarea operaiilor efectuate asupra lor, atunci este programare orientat obiect. Structurile de date, n acest caz, sunt organizate n manier logic n clase, care precizeaz, pe lng organizarea i structura datelor, i funciile care pot manipula acea structur. Organizarea obiectelor se combin cu alte proprieti caracteristice programrii orientat obiect, cum ar fi motenirea caracteristicilor i a resurselor.

11

2. Programare logic - Prolog

Un program scris ntr-un limbaj de programare logic este constituit din enunuri care exprim cunotinele relative asupra problemei pe care ncearc s o rezolve programul. Formularea acestor cunotine se bazeaz pe dou concepte de baz:

Existena de obiecte discrete, exprimate prin piese de cunoatere (cunotine declarative).

Existena de relaii ntre aceste obiecte/enunuri.

Exemple de enunuri declarative prin care se exprim un domeniu (al studenilor la

Calculatoare) i relaii (este student sau cunoate):

a) Orice student la specializarea Calculatoare cunoate programare;

b) Petru este student la Calculatoare;

Din cele dou enunuri declarative se poate raiona concluzia:

c) Petru cunoate programare;

Acest exemplu poate fi implementat n programarea logic, deoarece prin acesta se poate reprezenta un numr infinit de posibile relaii ntre obiecte i se poate aplica un sistem de raionament pentru a obine concluzii.

Toate piesele de cunoatere considerate n contextul unei probleme particulare formeaz domeniul problemei. Astfel de metode de reprezentare prin logic pot fi transpuse prin sisteme de reprezentare simbolice. Piesele de informaie/cunoatere pot fi obiecte, numere, figuri geometrice, ecuaii, etc. Acestor piese de cunoatere li se asociaz nume indivizibile i ne-structurate, numite constante.

Prolog este un limbaj de programare declarativ i este utilizat la modelarea predicatelor de ordin unu (de aici i denumirea de PROgraming in LOGic). Stilul de programare se bazeaz pe noiunea care definete relaii infereniale asupra claselor de obiecte. A fost dezvoltat la nceputul anilor 1970 de ctre Alain Calmerour i Philippe Roussel (Marseille). Primul interpretor a fost scris n ALGOL-w i a fost implementat n

1972. O alt implementare a fost fcut de Borland prin Turbo Prolog n 1986. apoi au aprut versiuni compilate pe lng cele interpretate.

Programarea logic are 3 nivele de abordare a tratamentului informaiilor:

Specificarea cunotinelor permanente relative la domeniul aplicaiei;

Specificarea problemei de rezolvat;

Mecanismul de rezolvare care opereaz asupra primelor dou niveluri.

n Prolog au fost realizate aplicaii din domeniul sistemelor expert i a limbajelor de specificare, demonstrare de teoreme, logic matematic, limbaj natural.

Fundamentele matematice ale programrii logice se gsesc n teoria predicatelor logice.

2.1 Fundamente teoretice logica predicatelor

Logica predicatelor este un limbaj capabil s descrie enunuri matematice i s garanteze corectitudinea raionamentelor. Limbajul predicatelor de ordin unu dispune de instrumente pentru a defini diverse tipuri de obiecte matematice, cum ar fi: numere, variabile numerice, funciii operaii matematice,relaii, propoziii, teoreme matematice.

ncalculul predicatelor, componentele unui enun suntinterpretate pentru determinarea valorilor de adevr ale enunului. Termenul de predicat este folosit n

12

accepiunea de formul deschis. Formulele deschise pot deveni enunuri sau propoziii dac variabilele care intr n componena lor iau valori constante individuale sau sunt cuantificate universal sau existenial. Un enun declarativ se numete n logica simbolic atom. Pentru construirea unui atom n logica predicatelor se folosesc patru tipuri de simboluri logice:

1. simboluri individuale sau constante denumesc obiecte, care pot fi numerice sau nu i sunt notate cu litere mici (de exemplu, popescu, animal, 100);

2. variabile sunt notate cu litere mari (de exemplu, X, Y, Z);

3. simboluri funcionale (funcii, functori) se noteaz cu litere mici i pot reprezenta i operatori (de exemplu, f, factorial , nr-argumente, plus);

4. simboluri predicative (predicate) se noteaz cu litere mari (de exemplu, P, Q, MAIMARE);

Limbajul predicatelor de ordin nti este exprimat printr-un alfabet, i este alctuit din ansamblul tuturor formulelor construite folosind simbolurile alfabetului.

Funciile i predicatele au un numr dat de argumente, iar acest numr se numete aritate. Dac o funcie sau un predicat au n argumente, acestea se numesc n-are.

Enunurile din limbajul natural sunt formate din cuvinte, iar obiectele din domeniul de reprezentare sunt reprezentate prin substantive. ntr-un limbaj formalizat cum este logica predicatelor, obiectele sunt reprezentate prin termeni a cror sintax este explicat n continuare.

Un termen poate fi definit recursiv astfel:

o constant;

o variabil;

o funcie (functor) f(t1,...,tn), unde f este un simbol funcional, ti sunt termeni;

orice termen generat dup regulile de mai sus;

Aspectele sintactice sunt date de alfabetul limbajului predicatelor, care este dat de:

separatori ( ) ,

termeni;

variabile;

atomi;

conectori , , , , ;

cuantificatori existenial i universal care se aplic numai variabilelor;

Un atom este un predicat n-ar P(t1,...,tn), unde ti, i=1,...,n sunt termeni. Un atom pozitiv este un atom care nu conine negaii.

Daca atomul A este pozitiv n formula F, atunci este pozitiv i n formulele

(x)F si ( x)F , F G, F G, F G.

Dac atomul A este pozitiv n formula F, atunci este negativ n formuleleF, FG . Ordinea operatorilor este:

, , nega

sau

si

re, orice, exista

, im

plica, echivalent

Exemple:

-pentru a reprezenta expresia x mai mare dect y se poate folosi atomul maimare(X,Y), n care maimare este un functor, iar X i Y sunt termeni (variabile);

-pentru a reprezenta expresia x mai mare dect 10 se folosete notarea maimare(X,10);

13

-pentru a reprezenta operaia care realizeaz media aritmetic se utilizeaz termenul media(X,Y), n care X i Y sunt variabile, iar media este un simbol funcional;

-expresia media lui x i 7 mai mare dect y se reprezint n logica predicatelor maimare(media(X,7),Y);

-enunul Petru este student la specializarea Calculatoare se formalizeaz n limbajul logicii predicatelor prin predicatul STUDENT(petru, calculatoare). Pentru a exprima c exist cel puin un student la secia Calculatoareutilizm:

( X)STUDENT(X,calculatoare).

-declaraia orice student la Calculatoare cunoate programare se exprim prin

( X) (STUDENT(X,calculatoare) CUNOATE_PROGRAMARE(X)).

-deducia Petrucunoate programarese transform npredicatul CUNOATE_PROGRAMARE(petru). Pentru a reprezenta enunul Petru nu cunoate programare folosim negaia CUNOATE_PROGRAMARE(petru).

-pentru a exprima faptul c un student care a promovat are media notelor mai mare dect 5 utilizm combinaia promovat(X,maimare(media(Z,Y),5)). Dac tim c Petru are notele 6 i 10 i reprezentm promovabilitatea lui atunci folosim un termen compus: promovat(petru,maimare(media(6,10),5)).

n limbajul natural o combinaie de cuvinte alctuiete un enun (propoziie) cu un anumit neles. n logica predicatelor, enunul este construit din termeni care alctuiesc o formul sau o formul bine format.

O formul bine format se definete recursiv astfel:

1. un atom (este un predicat n-ar P(t1,...,tn), unde ti, i=1,...,n sunt termeni);

2. dac F i G sunt formule, atunci F, FG, FG, F G, FG sunt formule;

3. dac F este formul i x este o variabil liber, atunci ( x)F si ( x

formule;

)F sunt

4. formulele se genereaz prin aplicarea de un numr finit de ori a regulilor de mai sus.

Variabilele care apar n formule pot fi libere sau legate.

O variabil dintr-o formul este legat dac apare n formula pe care cuantificatorul respectiv o aplic sau apare chiar n acel cuantificator. Deci, o variabil cuantificat universal sau existenial este o variabil legat n formula prefixat de acel cuantificator.

O variabil este liber dac nu este legat, adic dac are cel puin o apariie liber n acea formul.

O formul care nu conine variabile libere se numete formul nchis.

Un literal este o formul redus la un atom (adic o formul care conine numai predicate). Deci un literal este un atom sau negaia unui atom. Un literal pozitiv este un atom. Un literal negativ este negaia unui atom.

Limbajul logic al predicatelor de ordin unu este o formalizare a enunurilor declarative din limbajul natural. Aceste enunuri se refer la anumite cuvinte i pot fi adevrate sau false n domeniul considerat. nelesul formulelor logice este definit relativ la un

cuvnt abstract numit structur (algebric) i poate fi, de asemenea, adevrat sau fals. Deci, pentru a defini nelesul unei formule trebuie s se stabileasc o legtur ntre limbaj i structur. Enunurile declarative pot face referire la entiti i reprezint relaiile sau funciile dintre acestea. Astfel, abstractizarea matematic a cuvntului numit structur, este o mulime nevid de entiti (numit domeniu), mpreun cu relaiile i funciile definite pe mulime. Legtura dintre limbaj i structur se realizeaz prin semantica limbajului.

14

Aspectele semantice se ocup de urmtoarele caracteristici:

interpretarea formulelor bine formate;

formule valide, inconsistente, echivalente;

consecin logic;

clauze Horn;

demonstrarea teoremelor prin reguli de inferen permite obinerea de formule bine formate plecnd de la una sau mai multe formule bine formate aplicnd modus ponnens, modus tollens, specializrii universale;

n logica predicatelor, deoarece n formule sunt implicate variabile, pentru a defini o interpretare a unei formule trebuiesc definite domeniul i asignarea constantelor, domeniul i asignarea funciilor, domeniul i asignarea predicatelor care apar n formul.

O interpretare a unui limbaj L de ordin unu este constituit din urmtoarele elemente:

o mulime nevid D numit domeniul interpretrii;

fiecrei constante din limbajul L i se asigneaz un element din D;

fiecrui simbol de funcie n-ar din limbajul L i se asigneaz o aplicaie

nD D.

fiecrui simbol de predicat P de aritate n, i se asigneaz o aplicaienD {

T, F} .

Interpretarea constantelor i a simbolurilor de funcii i predicate, constituie baza asignrii valorilor de adevr formulelor din limbaj. Interpretarea unei formule va fi definit ca o funcie a interpretrilor componentelor sale, care sunt termeni (constante, variabile, functori). Deci, trebuie definit interpretarea unui termen. Deoarece termenii pot s conin variabile, se introduce noiunea de evaluare.

Evaluarea unei variabile este o funcie care mapeaz unei variabile dintr-un alfabet o interpretare.

O interpretare a unei formule F const dintr-un domeniu nevid D i asignarea de valori fiecrei constante, funcie sau predicat care apar n F n modul urmtor:

1. fiecrei constante i se asigneaz un element din D;

2. fiecrei funcii n-are i se asigneaz o aplicaie de la Dn la D, unde

Dn={(x1,...,xn)|x1 din D,...,xn din D};

3. fiecrui predicat n-ar i se asociaz o aplicaie de la Dn la {True, False}.

Se spune c formula F are o interpretare peste domeniul D. Cnd se evalueaz valorile

de adevr ale unei formule F peste un domeniu D, ( x

) se interpreteaz ca pentru toate

elementele din D, iar (x

) ca exist cel puin un element din D.

Regulile de evaluare a valorilor de adevr ale unei formule pentru orice interpretare peste domeniul D sunt:

1. dac valorile de adevr ale lui G i H sunt evaluate, atunci se pot evalua i pentru

G, G H, G H , GH, GH;

2. ( x

)G este adevrat T, dac valoarea de adevr a lui G este T pentru orice

element din D, altfel este F;

3. ( x

)G este T dac valoarea de adevr a lui G este T pentru cel puin un element

din D, altfel este F.

O formul care conine variabile libere nu poate fi evaluat. n logica predicatelor, deoarece exist un numr infinit de domenii, exist i un numr infinit de interpretri ale unei formule. Din aceast cauz nu se poate verifica validitatea sau inconsistena unei formule prin evaluarea ei sub toate interpretrile posibile.

Exemplu:

15

considerm limbajul care conine constantele zero i cinci (pentru reprezentarea numerelor naturale 0 i 5), functorul unar incr (pentru reprezentarea incrementrii) i predicatul maimare (reprezint operaia de comparare). Pentru domeniul D reprezentat de mulimea numerelor naturale avem:

zeroD := 0 cinciD := 5 incrD(x) := 1+x

maimareD(x,y) := x>y

Pentru a determina interpretarea formulei 5 mai mare dect zero incrementat peste domeniul D scriem formula ca (maimare(5,incr(zero))) = (maimare(5,1)) care are valoarea de adevr True. Dac, n locul constantei 5 aveam o variabil liber X, formula nu mai putea fi evaluat cu o valoare de adevr. Se tie c n mulimea numerelor naturale, orice numr diferit de zero este mai mare dect acesta. n acest caz, formula

orice X numr natural este mai mare dect zero reprezentat prin (maimare(X,zero))

este adevrat n interpretarea numerelor naturale.

O formul este consistent (realizabil) dac exist cel puin o interpretare n care formula s fie evaluat True.

Dac o formul este consistent ntr-o interpretare se spune c interpretarea este un

model al formulei sau c interpretarea satisface formula.

O formul este inconsistent (nerealizabil) dac i numai dac nu exist nici o interpretare care s satisfac formula.

O formul este valid dac i numai dac orice interpretare a formulei este model al formulei (interpretarea satisface formula).

Relaia dintre valoarea de adevr a formulei i termenii de clasificare ai formulei este:

validinvalid

ntotdeauna adevrat

Uneori adevrat, uneori fals

ntotdeauna fals

contingent

consistent (realizabil)inconsistent

O formul G este consecin logic a formulelor F1,...,Fn dac i numai dac sub orice interpretare, dac 1 nF...F este adevrat, atunci i G este adevrat.

Teorema deduciei arat c fiind date formulele F1,...,Fn i o formul G, G este o consecin logic a formulelor F1,...,Fn dac i numai dac formula (( 1 nF...F )G) este valid sau (( 1 nF...F )G) este inconsistent.

2.1.1 Interpretare i modele

Semantica declarativ a unui program logic este dat de semantica (teoria modelelor) formulelor n logic de ordin unu. Pentru a demonstra o problem este necesar s se porneasc de la axiome i s se deduc o concluzie adevrat. Problema se reprezint cu ajutorul formulelor, care sunt interpretate pentru a clasifica formula n valid, invalid, consistent sau inconsistent.

16

n logica predicatelor de ordin unu, deoarece exist un numr infinit de domenii, exist i un numr infinit de interpretri ale unei formule. Astfel, o formul care descrie un enun ntr-un domeniu, poate descrie alt enun n alt domeniu, rezultnd mai multe modele pentru aceeai formul. Din aceast cauz nu este posibil s se verifice validitatea sau inconsistena unei formule prin evaluarea ei sub toate interpretrile posibile. Astfel, se utilizeaz proceduri Herbrand sau proceduri rezolutive de demonstrare, care sunt proceduri de respingere a formulelor, adic n loc s se demonstreze c o formul este valid, se demonstreaz c negaia formulei este inconsistent. Pentru a se utiliza procedurile Herbrand, trebuie definit universul Herbrand al unei mulimi de clauze.

Clauzele sunt formule transformate n forma standard Skolem, care are forma

unei disjuncii de literali de1 nx ,..., x ( 1L ...Lm ), unde

(nu conine cuantificatorul existenial). Clauzele se mai numesc i clauze Horn.

x1 n,..., x apar n1 mL ,..., L

Pentru a se transforma o formul la forma de mai sus se folosesc urmtoarele reguli:

treceri n formule echivalente. Dou formule sunt echivalente, dac i numai dac au aceleai valori de adevr pentru orice interpretare a oricrei din cele dou formule. Formulele de echivalent din logica propoziiilor sunt:

FG echivalent cu (FG)(FG)

FG echivalent cuFG

F GGF

comutativitate

F GGF

(FG)H F(GH)

asociativitate

(FG)H F(G

H)

F (GH) (F G)(FH)

distributivitate

F (GH)(F G)(FH)

FTrueTrue =

F False = F F TrueF =

F FalseFalse =

F F = False

F F = True

( F )F=

(FG) F G

(FG) F G

de Morgan

La acestea se mai adaug i alte formule echivalente specifice logicii predicatelor de ordin unu:

17

( x)F(x)G( x)(F(x)G)

( x)F(x)G( x) (F(x)G)

( x)F(x)G( x)(F(x)G)

( x)F(x)G( x) (F(x)G)

( x F(x)) x ( F (x))

( xF (x)) x(F(x))

xF(x)xG(x )x(F(x)G(x))

xF(x) xG( x) x(F(x)G(x))

1Q xF(x)Q2 1xG(x)(Q x)(Q2 y )(F(x)G(y))

1 2Q xF(x)Q xG(x)( 1Q x)( 2Q y

)(F(x)G(y))

unde1 2 Q si Q pot fi sau, iar y nu trebuie sa apara in F(x)

transformarea formulei n forma normal prenex:

( 1 1Q x )...(Qn x n )M , unde

Qi , i = 1...n sunt cuantificatorii universal i existenial , iar M este o

formul, numit matrice, care nu conine cuantificatori.

prefixul formulei;

(Qi ix ) formeaz

matricea, deoarece nu conine cuantificatori, poate fi transformat n forma conjunctiv normal (matricea poate fi considerat ca fiind scris n logica propoziiilor pentru c nu conine cuantificatori). n logica propoziiilor exist

dou forme normale conjunctiv1 nF ... F

i disjunctiv 1 nF...F

fr a afecta proprietile de inconsisten, cuantificatorul existenial din prefix poate fi eliminat folosind funciile Skolem. Astfel, fie F o formul n forma

normal prenex

( 1 1Q x )...(Qn x n )M , iar matricea M este n forma normal

conjunctiv.Se presupune n prefixul

rQ , 1rn ca fiind existenial.

( 1 1Q x )...(Qn x n ) , cuantificatorul

odac nici un cuantificator universal nu apare naintea lui

Qr , atunci se

alege o constant C (diferit de cele care apar n M) care nlocuiete pe

x r

i se terger rQ x din prefix;

odac Qs1 ,..., Qsm sunt cuantificatori universali care apar naintea luirQ n prefix, 1s1... smr , atunci se alege o funcie m-ar f (diferit de toate funciile care apar n M) i se nlocuiesc toate apariiile luirx din M cu f (xs1 ,..., xsm ) i se terge Qr rx din prefix;

Dup ce se elimin toi cuantificatorii existeniali din prefix se obine forma standard Skolem a formulei F. Constantele i funciile folosite pentru a nlocui variabilele cuantificate existenial se numesc funcii Skolem.

Etapele n care se obine o transformare a unei formule ntr-o clauz sunt:

se transform formula n forma normal Prenex, n care matricea nu conine nici un fel de cuantificatori, iar prefixul este o secven de cuantificatori.

matricea, deoarece nu conine cuantificatori se aduce la forma conjunctiv

normal.

se elimin cuantificatorii existeniali din prefix folosind funciile Skolem.

Scopul transformrii n forma standard Skolem este pentru a rezolva problemele prin teorema lui Herbrand sau prin metodele rezoluiei.

18

Exemple:

1.formula (x)( y)( z)(u)(v)(w)P

(x, y, z, u, v, w) are forma Skolem

( y)( z)( v )P(a, y, z, f (y, z), v, g(y, z, v)) ;

2.formulax y z ((P(x

, y)Q(x, z))R(x, y, z) se transform n forma

normal conjunctivx y z (

i are forma Skolem

( P(x

, y)R(x, y, z))(Q

(x, z)R(x, y, z)) )

x ( ( P(x, f (x))R (x,f (x), g(x)))(Q(x, g(x))R (x,f (x), g(x))) )

Un program scris n Prolog este o mulime de clauze, care poate fi considerat ca o conjuncie a tuturor clauzelor implicate, iar fiecare variabil este considerat ca fiind guvernat de un cuantificator universal.

Dac se consider S o mulime de clauze, care reprezint forma standard a unei formule F. Pentru a demonstra c formula F e inconsistent este suficient a demonstra c mulimea de clauze ataat acesteia e inconsistent. O mulime de clauze este inconsistent (sau nerealizabil, nesatisfcut), dac este fals n toate interpretrile pe toate domeniile posibile. Deoarece este imposibil s se evalueze formula pentru toate interpretrile, pe toate domeniile posibile, se definete un domeniu special H, astfel nct S este inconsistent dac i numai dac formula F este fals sub toate interpretrile peste domeniul H. Un astfel de domeniu, numit universul Herbrand pentru mulimea de clauze S se definete astfel:

fie HC mulimea constantelor care apar n S. Dac nu exist nici o constant

atunci se consider HC={a}.

pentru i=1,2,, fie Hi+1 reuniunea lui Hi cu mulimea termenilor de forma

n

f (t1 n, ..., t ) , care sunt funcii n-are din S, iar

ti sunt elemente ale mulimii Hi.

Mulimea Hi se numete mulimea de constante de nivel i, iar H se numete universul Herbrand pentru S.

Exemple:

1. Fie S{P(a),P(x)= P(f (x))} . Universul Herbrand este definit astfel:

0H {=

1H {=

a}

a, f (a)}

H2 = {a, f (a), f (f (a))}

...

H = {a, f (a), f (f (a), f (f (f (a))), ...}

2. Fie S{P(x)Q(x), R=

(z), T(y)W(y)}. Universul Herbrand este:

HH0 1H= =...={a}=, deoarece formula nu conine nici un simbol funcional.

3. Fie S = {P(f (x)), a, g(y), b} . Universul Herbrand este dat de mulmile:

0H {=

a, b}

1H

2H

= {a, b, f (a), f (b), g(a), g(b)}

= {a, b, f(a), f (b), g(a), g(b), f (f(a)), f(f(b)), f(g(a)),

f (g(b)), g(f (a)), g(f (b)), g(g(a)), g(g(b))}

19

2.1.2 Inferen logic

Procesul de raionament const n obinerea, pe baza unei mulimi de formule date, numite premise, de noi formule, numite concluzie. n logica simbolic, principiile de raionament, care constau n deducerea de formule valide din alte formule valide, sunt scrise sub forma regulilor de inferen. Astfel, regulile de inferen permit obinerea de consecine logice din premisele asupra crora se aplic inferena. Regulile de inferen uzuale sunt:

Modus ponens consider c dac se tie c F i F->G atunci se poate trage concluzia c G.

F, F -> G

G

Modus tollens consider c dac se tie c G i F->G atunci se poate trage concluzia c F.

G, F -> G

F

Regula eliminrii cuantificatorului universal consider c ntr-o formul de forma X F(X) se poate nlocui apariia variabilei legate X cu un termen t care este liber de variabila X:

X F(X)

F(t)

O mulime de premise se numesc inconsistente, dac orice formul poate fi obinut prin inferen din mulimea de formule.

2.1.3 Substituii

Din punct de vedere formal, o substituie const n nlocuirea variabilelor dintr-un alfabet cu termeni din acelai alfabet. Prin substituie se nelege o mulime de perechi

{X1|t1,...,Xn|tn}, unde ti sunt termeni, Xi sunt variabile astfel nct Xi ti i Xi Xj dac

i j.

Fie substituia dat de {X1|t1,...,Xn|tn} i Este un termen sau o formul. Aplicarea substituie la E este termenul sau formula obinute prin nlocuirea cu ti a fiecrei apariii a variabilei libere Xi n E. E se numete instan a lui E.

Exemple de substituii:

-Fie formula p(f(X,Z), f(Y, a)) i substituia {X|a, Y|Z, W|b}. Instana formulei este p(f(a,Z), f(Z; a)).

-Fie formula p(X, Y ) i substituia {X|a, Y|b}, instana formulei este p(a, b).

Considerm, , substituii i E un termen sau o formul. Proprietile substituiei sunt:

E( , )=(E )

( ) = ( ) (asociativitate)

(nu este comutativ)

20

2.2 Aspecte teoretice aplicate n Prolog

Programarea logic este baza pentru toate celelalte reprezentri de cunotine ale lumii reale. Programele logice pot fi aplicate n multe domenii. Astfel, Web Consortium aadoptat un limbaj logic pentru proiectul Semantic Web. n unele aplicaiile de monitorizare a traficului aerian se folosesc limbaje logice pentru descrierea restriciilor impuse de domeniu. De asemenea, n domeniul nelegerii limbajului natural se folosesc aspecte de programare logic. Logica predicatelor de ordin unu permite modelarea informaiilor generale despre lumea real i este sugestiv fa de limbajul natural i n plus, computaional prin limbajele de programare logice. O caracteristic a limbajelor logice, diferit de a limbajelor de programare, dar care seamn cu limbajul natural, este c permite introducerea de cunotine adevrate despre lumea real fr a fi nevoie s se specifice o modalitate de a fi calculate.

Problemele de rezolvat n programare logic este indicat s aib domenii cu structur logic (cum ar fi sistemele deductive). S poat fi exprimate folosind clauze i

pattern-matching (translare, parsare).

21

Diferite implementri ale Prolog:

DOS-

PROLOGMS-DOS SharewareXXXXX

Edinburgh

Prolog

Open

PrologMac OSFreewareX

Ciao

Prolog

Unix,

Windows GPLXXXXXISO-Prolog

GNU

Prolog

Unix,

Windows GPLXXXXXISO-Prolog

Visual

PrologWindows

Freeware,

comercialXXXXXXX

SWI-

Prolog

Unix,

Windows,

Mac OS

X

LGPLXXXXXXX

ISO-Prolog,

Edinburgh

Prolog

WIN-

PrologWindows

Shareware

comercialXXXXX

ISO-Prolog,

Quintus

Prolog

Tu-Prolog JVMGPLXXXXXXISO-Prolog

Conferine cu specific pe limbajele logice:

INAP - International Conference on Applications of Declarative Programming and Knowledge Management

ICLP - International Conference on Logic Programming

Scopul programrii logice este de a rezolva probleme prin obinerea de concluzii pornind de la descrieri declarative ale condiiilor n care exist soluia, dar fr a arta cum se gsete soluia. Aceste descrieri, numite programe logice, sunt alctuite dintr-o mulime finit de formule logice. Asupra acestor formule se aplic restricii care permit

22

aplicarea principiului rezoluiei. O limitare a variantelor de Prolog clasice este c nu permit definirea de funcii, doar relaii (vzute ca proceduri care nu returneaz nici o valoare). De exemplu, n Prolog clasic nu se poate defini funcia factorial(X) care are ca argument un ntreg i returneaz un ntreg, se poate defini doar relaia boolean factorial(X, Rez) care leag un ntreg X de factorialul su Rez.

Un program logic n Prolog este definit printr-o mulime finit de clauze, n care fiecare variabil este considerat ca fiind guvernat de un cuantificator universal.

O clauz are forma:

A 1 nB ,..., B

sau clauza unitate A , unde A (numit cap) i Bi

(formeaz corpul) sunt formule n care toate variabilele sunt cuantificate universal. Prolog utilizeaz ca regul de inferen rezoluia asupra clauzelor concrete, apoi

generalizat la clauze Horn prin mecanismul de unificare.

Un literal este concret dac nu conine variabile. O clauz concret este o disjuncie de literali concrei.

Fie clauzele concrete

A =1 nA...A i

B =1 2AB ...Bm.1A i

1A se

numesc literali complementari.

Principiul rezoluiei obine clauza rezolvant

C = A2 n...A

B2...Bm

plecnd de la clauzele A i B, prin eliminarea literalilor complementari i prin disjuncia celorlali literali.

Mecanismul de inferen are ca scop cutarea echivalenei ntre dou formule, care se realizeaz prin mecanismul de unificare.

Considerm s i t termeni. Unificatorul lui s i t este o substituie astfel nct s i t sunt identici (se noteaz cu s =t ).

O substituie se spune c este mai general dect o alt substituie dac i numai dac exist o substituie astfel nct = .

Un unificator se numete cel mai general unificator pentru doi termeni, dac i numai dac este mai general dect orice alt unificator al termenilor.

Pentru o formul F unificatorul general cel mai comun se obine dac pentru

toi unificatorii , exist o substituie astfel nct[F

][=[ F]] .

Unificarea caut literalii complementari prin aplicarea de substituiri.

Exemplu: pentru formula F {=

x, y, f (z)} unificatorul general cel mai comun este

p {=

f (z) | x, F(z) | y, z | z} , cu s {=

f (a) | x, f (a) | y, a | z} .

Rezoluia aplicat clauzelor oarecare: fie clauzele A i B, care nu au variabile comune. Se spune c este posibil s se asocieze fiecrui cuantificator un nume de variabil

diferit. A i B sunt compuse dintr-o disjuncie de literali

{Ai } i

{B j} . Dac exist

submulimile

{Ak } i

{Bl } astfel nct

{Ak l} U {B } sunt unificabile prin cel mai

comun unificator general p, atunci rezolventul luiAi B se poate scrie

p[{Ai k} {A }]p[{B j} {Bl }].

Proprietatea fundamental a rezoluiei: dac n urma unei rezoluii, plecnd de la o mulime C de clauze se ajunge la o clauz vid, atunci C este inconsistent.

Exemplu: A P(x, f (a))P(x, f (y))= Q(y), B =P(z, f (a))Q(z) .

Unificatorul general cel mai comun al lui P(x, f (a)) i ( P(z, f (a))) este {x | z} , iar de aici rezult rezolventul P(x, f (y))Q(y)Q(x ) .

Unificatorul general cel mai comun al lui P(x, f (y)) i ( P(z, f (a))) este {x | z, y | a} , iar de aici rezult rezolventul P(x, f (y))Q(y)Q(x ).

23

Unificatorul general cel mai comun al lui Q(y) i( Q

rezult rezolventul P(x, f(a))P(x, f (y))P(y, f(a) ).

(z)) este {y | z} , iar de aici

Se observ astfel c dou clauze pot avea nici unul sau mai muli rezolvani.

2.2.1 Principiul rezoluiei prin respingere

Rezoluia prin respingere este utilizat pentru a demonstra c o formul bine

format A este consecin logic a unei mulimi de formule

astfel:

1. se constituie mulimea de clauze C derivate din S;

=iS {S } . Se procedeaz

2. se adaug la mulimea de clauze C clauza derivat din A ;

3. atta timp ct clauza vid nu este n C se urmeaz paii:

a.se aleg dou clauze distincte din C;

b. dac nu sunt rezolvani, se alege o clauz i se adaug la C.

Se poate demonstra c dac A este consecin logic a lui S, exist un set de alegeri la pasul 3.a care vor conduce la introducerea clauzei vide i la oprirea procedurii. Dar nimic nu garanteaz c aceast pereche, cnd exist, este gsit, deoarece etapele de la pasul 3 sunt nedeterministe. Deci se pun probleme de strategie, cu privire la modalitatea de alegere a clauzelor la pasul 3.a i a literalilor corespunztori la pasul 3.b.

O strategie de rezoluie const n construirea unui arbore de respingere, n care nodurile sunt clauze din S. Arcele sunt legturi ntre clauzele prini i rezolvanii posibili, iar frunzele sunt clauze vide.

2.2.2 Cunotine n Prolog

Nu exist nici o normalizare a limbajului Prolog.

Un program Prolog este o list ordonat de clauze Horn (prin care se formalizeaz

enunuri declarative) care exprim:

reguli1 nS...S R1S...SnR R 1 nS...S;

fapte F;

scopuri1 mB... B .

Regulile sunt clauze Horn complete care au un literal pozitiv unic, (numit i cap) i unul sau mai muli literali negativi, (numii i coad).

Faptele sunt literali pozitivi.

Scopurile sunt clauze care conin doar literali negativi. Unei reguli i se poate asocia:

o interpretare logic dac predicatele din coad sunt adevrate, atunci predicatul din capul regulii este de asemenea adevrat;

o interpretare procedural pentru a rezolva problema capului unei reguli, trebuie s se rezolve succesiv problema cozii.

Rspunsul la un scop care nu conine variabile trebuie s se obin n valorile de adevr T sau F. Rspunsul la un scop cu n variabile este o mulime de n valori, care se pot asocia cu variabilele i care satisfac scopul. Variabilele anonime se noteaz cu _ i valoarea lor este indiferent.

24

Exemple:

1. formula bine formatxP

P(X, a) .

(x, a) are forma cauzal P(x, a) , iar n Prolog se scrie

2. se consider formula bine formatx y

(Q(x, a)R (b, y)) P(x, y) are forma

cauzal P(x, y)Q

(x, a)R

(b, y) . n Prolog se scrie

P(X, Y) : Q(X, a), R (Y, b) .

3. formula bine format x y

R (x, a) S (y, b) are forma cauzal

R(x, a)S(y, b ), iar ca scop n Prolog R (X, a), S(Y, b) , deoarece este negarea lui x yR (x, a)S(y, b) .

2.2.3 Strategii de rezoluie n Prolog

Se aplic rezoluia ntre scopuri i reguli cu B1 i R unificabile prin unificatorul general cel mai comun p, care conduce la clauza

p[

1 2S ] p[

S ]. ..p[

Sn ]p[

B2 ]. .. p[

Bm ] ,

adic noile scopuri p[ 1 nS ], ..., p[S ], p[B2 ], ..., p[Bm ] .

Algoritmul de rezoluie poate fi considerat ca parcurgerea unui arbore, n care fiecare nod este etichetat printr-o list de scopuri i o substituie [ 1 mB , ..., B , s] . Nodul rdcin conine scopurile problemei propuse.

Algoritmul este:

fie nodul [ 1 mB , ..., B , s] ;

dac lista [ 1 mB , ..., B ] este vid

atunciafieaz S ( un succes);

se trece la nodul precedent;

altfel se consider1B ;

se caut prima regul dintre

R 1 nS...Scare nu a fost nc

explorat la acest nod i deci literalul pozitiv se poate unifica prin1B ;

dac nu exist

atunci

dac este un nod rdcin

atunci gata

altfel se urc la nodul precedent

altfel fie p unificatorul general cel mai comun al lui R i1B

coborrea creeaz un nou nod [ p[ 1 nS ], ..., p[S ], p[B2 ], ..., p[Bm ] ]

Interpretorul Prolog genereaz o list de scopuri care se rezolv prin terge folosind unificarea i o list de alegeri n ateptare. Dup un succes sau dac nu exist nici o unificare posibil, se ntoarce napoi la lista de scopuri precedente i ia n considerare ultima alegere n ateptare. Oprirea definitiv se produce cnd nu mai este posibil nici o ntoarcere napoi.

25

2.2.4 Reprezentarea cunotinelor n Prolog

Principalele seciuni

Domeniile descriu tipurile de date care sunt verificate de interpretor sau compilate.

Predicatele cuprind i clasific relaiile cunoscute din spaiul problemei.

Scopul descrie problema de rezolvat i formatul rspunsului ateptat.

Clauzele sunt reprezentate prin fapte logice, reguli i alte construcii.

Subprogramele sunt utile atunci cnd se folosete varianta compilat a Prolog-ului, care permit opiuni de re-compilare la fiecare execuie a unui subprogram (un program poate fi mprit pe subprograme care pot fi rulate separat). Implementrile interpretate ale Prolog accept doar un singur modul de program.

Subrutine sunt predicatele i au acelai scop cu funciile din limbajele de programare procedurale. Predicatele returneaz doar valori de tip boolean (true, false sau fail). Argumentele predicatelor pot fi clasificate c fiind intrri sau ieiri. Dac un argument primete o valoare n timpul apelului predicatului, atunci argumentul este de tip intrare, altfel de tip ieire. Un argument poate fi i intrare i ieire.

Limbajul Prolog are predicate predefinite pentru funciile matematice, pentru operaii de intrare-ieire (read, read-line, write), de lucrur cu iruri de caractere, pentru operaii cu structuri.

Tipuri de date: sunt symbol, integer, real, string, char, list, file, simple, compound. Nu se pot defini tablouri.

Constantele sunt true i fail.

Comentariile dac sunt pe mai multe linii sunt cuprinse ntre /* i */, iar dac sunt pe o singur linie ncep cu %.

Clauzele sunt scrise n Prolog dup sintaxa:

cap :- corp

Scopurile sunt trecute ntr-o list separate prin , sau ;

2.2.5 Rezoluia n Prolog

Strategia de rezolvare n Prolog este n adncime folosind metoda backtracking. Rezolvantul obinut la un pas de inferen este utilizat imediat pentru o nou unificare. Clauzele de unificat cu rezolvantul sunt considerate n ordinea scrierii programului. Unificarea se realizeaz ntotdeauna asupra primului literal al rezolvantului i asupra literalului pozitiv al clauzelor programului.

Exemplu: se dau

Fapte(a)tata(paul, ion)

(b)tata(marian, paul)

Regula(c)bunic(A,B):- tata(A,P), tata(P,B) Scop(d)bunic(X,Y).

-interpretorul ncearc unificarea scopului (d) cu primul literal al lui (a), apoi cu (b), apoi cu (c). Unificarea este posibil pentru (c) cu substituia {X |A, X |B} . Noile scopuri sunt (e) tata(X,P),tata(P,Y).

26

-interpretorul ncearc s unifice primul scop al lui (este) cu primul literal al lui (a),

(b), (c). Unificarea este posibil cu (a) pentru substituia {Paul|X, Ion|P}. Noul scop este (f) tata(Ion,Y).

-interpretorul ncearc unificarea scopului (f) cu primul literal din (a), (b), (c), dar nu este posibil nici o unificare.

-se ntoarce la scopul (e) i se ncearc unificarea cu clauzele n ateptare (b) i (c). Unificarea este posibil cu (b) pentru substituia {Marian|X, Paul|P}. Noul scop este

(g) tata(Paul,X).

-interpretorul ncearc s unifice scopul (g) cu primul literal din (a), apoi din (b) i (c). Unificarea este posibil pentru (a) cu substituia {Ion|Y}. Noul scop este clauza vid. Problema se termin cu un succes i se afieaz substituiile pentru variabilele din scopul iniial, astfel X=Marian, Y=Ion.

d

c

a

e

f

esec

b

a

g

h

succes

Observaie: soluiile nu sunt gsite ntotdeauna; ordinea clauzelor din program este important. Ca regul general ntr-un program se scriu faptele i apoi regulile. Exemplu:

1. a->a a

determin o bucl infinit pentru scopul a, n pofida unui rspuns evident.

2. a

a->a

d un rspuns adevrat.

Sunt variante de limbaj care se opresc la primul scop gsit i altele care caut toate scopurile posibile.

2.2.6 Controlul rezoluiei

n Prolog exist un predicat predefinit ! (sau /) care permite suprimarea explorrii anumitor ramuri din arborele de rezoluie. Acest predicat este ntotdeauna True. n utilizarea metodei backtracking, dac interpretorul ajunge la un nod la care lista de scopuri ncepe cu predicatul de ntrerupere a explorrii arborelui de rezoluie, atunci se ntoarce pn la nodul corespunztor nodului precedent, scop care a declanat apelul regulii care coninea predicatul !.

Acest predicat se utilizeaz de obicei, la sfritul ntrebrii pentru a evita ntoarcerea n cazul unui prim succes. Sau se foreaz un rspuns unic n cazul n care programul are rspunsuri multiple, chiar o infinitate de rspunsuri. Se mai poate utiliza n corpul unei reguli pentru a fora un rspuns pertinent i pentru a mpiedica alte explorri.

27

Exemplu:

1 a:-b, c, d.

2 b:-write(clauza b1), nl.

3 b:-write(clauza b2), nl.

4 c:-c1,!,c2.

5 c:-write(clauza c2), nl.

6 c1:-write(clauza c11), nl.

7 c1:-write(clauza c12), nl.

8 c2:-write(clauza c21), nl.

9 c2:-write(clauza c22), nl.

10 d:-write(clauza d1(succes)), nl, fail.

11 d:-write(clauza d2(succes)), nl, fail. n urma rulrii programul va afia:

clauza b1

c11

c21

d1 (succes) d2 (succes) c22

d1 (succes)

d2 (succes)

b2 /*urc la b din cauza lui !*/

c11

c21

d1 (succes) d2 (succes) c22

d1

d2 /*urc la b i sfrit*/

1

2

4

6

!

8

a

b c d

c d

c1 ! c2 d

! c2 d

c2 d

9

3

4

6

!

8

cd

c1 ! c2 d

! c2 d

c2 d

9

10

d

succes

11

10

d

succes

11

10

d

succes

11

10

d

succes

11

Fr ! n regula 4 se obin urmtoarele rezultate:

clauza b1, c11, c21, d1(succes), d2(succes), c22, d1(succes), d2(succes), c12, (urmeaz

o parte neexplorat), c21, d1(succes), d2(succes), c22, d1(succes), d2(succes), c2,

28

d1(succes), d2(succes),b2, c11,c21, d1(succes), d2(succes), c22, d1(succes), d2(succes), c12, (urmeaz o parte neexplorat), c21, d1(succes), d2(succes), c22, d1(succes), d2(succes), c2, d1(succes), d2(succes).

Exemplu: de calcul al factorialului unui numr ntreg:

/* Program care defineste predicatele pentru calculul factorialului */

factorial(0,1):-!

factorial(N,F) :-

N>0,

N1 is N-1,

factorial(N1,F1),

F is N * F1.

2.2.7 Liste

Listele constituie structura de baz manipulat n Prolog, datorit tratrii recursive. Listele sunt definite ntre [ i ].

Exemple:

[Ion, Paul, Marian]

[X|Y][cap|coada]

Exemplu: de algoritm de ordonare rapid Dijkstra: citestelista([T|Q]):- read_integer(T), !, citestelista(Q). citestelista([]).

scrielista([]).

scrielista([T|Q]):-write(T), nl, scrielista(Q). taie(_, [],[],[]).

taie(X,[Y|L], [Y|L1], L2):-YX, taie(X, L, L1, L2). taie(X,[X|L], [X|L1], L2):- taie(X, L, L1, L2). conc([], L, L).

conc([X|L1], L2, [X|L3]):-conc(L1, L2, L3). tri([],[]).

tri([X|L],LT):-taie(X,L,L1,L2),tri(L1,LT1), tri(L2,LT2), conc(LT1, [X|LT2], LT).

ordonare:-write('Tastati lista'), nl, citestelista(L), tri(L,Lo), write('Lista ordonata este:'), nl, scrielista(Lo), nl.

Predicatele utilizate i semantica acestora sunt:

citestelista(L) citete o list L.

scrielista(L) scrie o list L.

tri(L,L)

taie(I, L1, L2, L3)

conc(L1, L2, L3) concateneaz L1 i L2 rezultnd L3.

ordonare este predicatul care va fi folosit ca scop pentru execuia programului.

29

Exemplu: problema de sortare care ordoneaz cresctor o list de ntregi pozitivi. ntregii pozitivi sunt reprezentai cu ajutorul constantei O i cu funcia unar f(succesor). ntregul pozitiv n este reprezentat prin termenulnf (O) . Lista se reprezint prin simbolul funciei binare ., constanta nil reprezint lista vid. Astfel, lista

[17,22,6,5] se reprezint prin 17.(22.(6.(5.nil))) sau prin 17.22.6.5.nil. predicate folosite n program sunt sort, sorted, perm, delete,