1

Programare logică şi funcţională

1. Introducere

1.1 Clasificarea limbajelor de programare

Limbajele de programare sunt împărţite pe diferite niveluri în funcţie de gradul de

interacţiune cu suportul hardware: • Limbaje maşină – corespund unui set de instrucţiuni restrânse pentru o

arhitectură hardware particulară şi sunt dependente de maşină. Instrucţiunile au lungimi de 16, 24, 32, 64 bits. Primii biţi specifică codul operaţiei, iar ceilalţi specifică operanzii sau modurile de adresare. De obicei se exprimă în binar şi realizează operaţii de bază (transfer de date între memoria centrală şi procesor, instrucţiuni de calcul aritmetic şi logic). Este dificil să se programeze la acest nivel, deoarece trebuie să se considere lucrul cu regiştrii, modurile de adresare, maparea memoriei. Datorită acestei modalităţi de programare la detalii sunt des întâlnite erorile.

• Limbajele de asamblare – folosesc mnemonici pentru operaţii şi operanzi, ceea ce face instrucţiunile maşină mai uşor de scris şi de înţeles. Înainte de a rula un program în limbaj maşină codul trebuie transformat într-o formă de limbaj maşină. Programul translator care realizează acest lucru se numeşte „assembler”. Limbajele de asamblare sunt mai uşor de programat decât limbajele maşină, dar au dezavantajul că sunt dependente de maşină. Assemblere-le vin de obicei odată cu partea hardware şi sunt specifice unei configuraţii hardware.

• Limbaje de nivel înalt – subliniază natura unei probleme şi foloseşte proceduri pentru rezolvarea problemei. Aceste limbaje sunt independente faţă de maşină, iar programele pot rula pe orice tip de configuraţie hardware. Limbajele de nivel înalt se clasifică în procedurale (imperative) şi declarative (neprocedurale). Mai mult, se pot clasifica şi în interpretate sau compilate. Sunt posibile oricare combinaţii dintre două din tipurile enumerate mai sus.

• Limbajele de nivel foarte înalt – includ limbajele de generaţia a patra, limbajele de interogări 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) foloseşte o secvenţă logică de paşi pentru a obţine rezultate. Cu alte cuvinte, acest tip de limbaje trebuie să conţină informaţii despre „cum” (how) se poate obţine rezultatul aşteptat. În astfel de limbaje, un program este alcătuit dintr-o secvenţă de declaraţii care specifică acţiuni care arată „cum” se schimbă starea programului.

Limbajele declarative (numite şi limbaje de generaţia a-4-a sau limbaje de procesare simboluri) demonstrează „ce” (what) va fi realizat şi eliberează programatorului de specificarea detaliilor paşilor (exemple, LISP şi variantele sale, Prolog). Într-un program declarativ se specifică definiţiile taskurilor care trebuiesc îndeplinite, dar fără a se urmări detaliile despre cum se îndeplinesc task-urile.

Un interpretor este un program translator, care interpretează individual comenzile şi corespunzător cu configuraţia calculatorului. Translatarea are loc de fiecare dată când este rulat un program. Interpretorul lucrează repetând următoarele trei operaţii la întâlnirea fiecărei linii din program: citeşte linia din codul sursă; analizează, verifică şi

2

codifică binar linia; execută instrucţiunea asociată cu linia interpretată. În acest caz, limbajul se spune că este interpretat (exemple tipice, Basic, LISP, Prolog, TclTk). Este 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 instrucţiuni echivalente. Această modalitate de lucru poate fi uneori ineficientă şi consumatoare de timp.

Un compilator este un program translator care converteşte programul într-un limbaj maşină echivalent. Odată tradus, programul poate rula de oricâte ori se doreşte. În acest caz se spune că limbajul este compilat (exemple C++, Java, Pascal). Compilatoarele produc cod maşină echivalent care poate fi optimizat să ruleze eficient. Dacă se mai adaugă şi facilităţi de testare şi „debugging”, limbajele compilate sunt folosite mai des pentru aplicaţii.

Avantajele la limbajele interpretate: disponibilitatea programului sursă pentru modificări, realizarea rapidă de programe mici şi execuţia lor. Dezavantajele limbajelor interpretate provin din faptul că nu există programe executabile, interpretorul trebuie furnizat cu programul sursă dacă se doreşte executat, sunt mai lente ca programele compilate. Dezvoltarea unui program compilat durează mult mai mult decât unul interpretat.

Sistemele de operare asigură suport prin interpretoare, compilatoare, assemblere, linkeditoare, editoare. Aceste programe sistem pot accesa rutine folosite pentru funcţiile uzuale (de exemplu citirea sau afişarea unor date), care sunt cuprinse în biblioteci.

Etapele de lucru pentru: • Limbajul interpretat

Un ciclu de interpretare constă în citire-decodare-acţiuni-scriere. Primii doi şi ultimii doi paşi pot fi combinaţi. Termenul generic de decodare indică interpretarea unei propoziţii sursă şi analiza lexicală a formurilor sau evaluarea expresiilor. Acţiunea implică transferul datelor şi calculul acestora. În unele cazuri (de exemplu la Lisp pentru ciclul citeşte-interpretează-scrie), pot fi două tipuri de ieşiri, una disponibilă să fie citită din nou, iar alta care satisface cererile cerute de utilizator.

Program sursa

Citeste intrare (comanda)

ciclare

Evalueaza (interpreteaza)

Ruleza (executa)

Afiseaza iesire (rezultate)

Cod sursa (fisier)

Computer Interpretor pentru limbaj

Date de intrare

Date de iesire

3

• Limbajul compilat

Procesul de compilare implică, în mod normal, o secvenţă de paşi sau faze. Aceşti

paşi, care realizează verificarea şi analizarea întregului fişier sursă, sunt etape ale compilării.

1.2 Principiile programării

Se face referire la principiile programării structurate. Scopul acestor principii este

de a ghida programatorul în planificarea şi realizarea programelor complexe. Aceste principii, au ca intenţie prescrierea regulilor aplicabile oricărui tip de programare şi a structurilor de control utilizate în programare (în engleză, constructs).

Principiile programării structurate sunt: • Structura ierarhică top-down; • Modularitatea; • Definirea clară a intrărilor şi ieşirilor; • Intrare simplă, ieşire simplă; • Folosirea exclusivă a structurilor secvenţă, selecţie, case, iteraţie. Funcţiile şi procedurile sunt folosite mai ales în limbajele procedurale. Dar şi

limbajele neprocedurale conţin construcţii similare, cu definiţii diferite şi cu implementări distincte.

O funcţie poate accepta argumente multiple şi poate returna un singur rezultat. Din acest motiv, o funcţie poate accepta ca argument o invocare a altei funcţii (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 funcţii este că primele pot avea rezultate multiple. Pentru operaţiile de intrare-ieşire 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ă aceleaşi principii fundamentale.

Structurile de programare sunt: • Secvenţa – este o comandă simplă sau un grup de comenzi care alcătuiesc un bloc de

program. Blocurile de program sunt delimitate prin simboluri sau prin cuvinte cheie

Program sursa

Analiza lexicala

Analiza sintactica

Generare de cod

Optimizare Modul obiect

Cod sursa (fisier)

Computer Compilator pentru limbaj

Directive de compilare

Date de intrare

Cod echivalent, în limbaj maşina

Date de iesire

4

(de exemplu, , , begi, end, [, ]). Exemplu de comandă simplă atribuirea (lvaloare:=rvaloare). Limbajele de asamblare folosesc comanda MOVE item-sursă to destinaţie.

• Selecţia simplă – permite execuţia condiţională a unei secvenţe de instrucţiuni. Implementarea acestei structuri se face cu ajutorul instrucţiunii if-else sau if-then-else sau formatul simplificat, <conditie>?<expresie1>:<expresie2>.

• Selecţia multiplă (case) – este o formă generală de selecţie, în care, punctele de control au alegeri multiple. Cuvintele cheie folosite sunt switch, case, of, got o, depending on.

• Repetitive – iteraţia şi recursia, care realizează execuţia repetată a unui secvenţe de comenzi. Structura de iteraţie asigură controlul explicit al unei bucle, corespunzător cu condiţiile impuse în instrucţiune. Cuvintele cheie utilizate pentru implementarea iteraţiei sunt do-while, repeat-until, for-next, while. Execuţia repetitivă se poate executa şi cu ajutorul subrutinelor care se apelează în ele însele, procedeul numindu-se recursivitate. Limbajele procedurale folosesc repetiţia cu control explicit, iar cele declarative (logice, procedurale) folosesc recursivitate.

Structurile de programare pot avea interpretări apropiate sau nu în implementările din diferitele limbaje de programare. Majoritatea structurilor din limbaje de programare sunt implementate ca „subprograme”, care sunt fişiere compilate separat (cu excepţia limbajelor interpretate). Subprogramele sunt secţiuni identificabile care servesc scopuri distincte în cadrul unui fişier program. Un subprogram corespunde unui aşa numit modul software, un fişier pe disc, care poate sau nu să fie executat separat. Modulele conţin subrutine, iar în unele cazuri, subrutinele împreună cu structurile de date se numesc „packages”. Termenul de subrutină este folosit pentru proceduri interne şi funcţii care completează un modul. Un subprogram, văzut 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ă distincţie între programul principal „main”, care poate fi doar apelat şi care rulează de sine stătător 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. Implementările structurilor de programare şi declaraţiile 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 adiţionale, construite plecând 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 acelaşi 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 înregistrările („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 rulării programului, de unde şi denumirea de date statice sau dinamice.

5

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 câmpuri:

struct persoana char nume[20]; int varsta; pers;

Lisp – se numeşte „proterty list” şi se defineşte ca o listă de perechi atom-valoare, care are structură de arbore: (SETQ PERSOANA (NUME (Popescu Ion) VARSTA 45))) Prolog – se numeşte „functor” şi se defineşte 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. Nu există o clasificare unică, standardizată, deoarece limbajele actuale nu sunt dezvoltate dintr-un singur limbaj, dar prin combinarea elementelor unor limbaje predecesoare cu adăugarea unor noi caracteristici. Limbajele pot fi clasificate după următoarele 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 restrâns. De exemplu, C – este un limbaj de nivel sistem, uşor de implementat, ştiinţific, folosit şi pentru aplicaţii 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 implementări în inteligenţa artificială; Prolog – este un limbaj de programare logică pentru demonstrare de probleme şi este implementat în aplicaţii de inteligenţă artificială care modelează logica predicatelor.

2. după scopul de aplicare, limbajele de programare pot fi considerate ca fiind: generale, specifice unui domeniu, programare sistem, bazate pe scripturi, concurente, distribuite, educaţionale. O mică listă a domeniilor de aplicabilitate ar fi: - aplicaţii ştiinţifice – programare liniară, analiza regresiilor, soluţii ale ecuaţiilor

diferenţiale, etc.; - procesări de date pentru business – state de salarii, calcule, facturare, inventarieri,

vânzare, informaţii management, etc.; - procesoare de text (editare, formatare, setări de editare, listare, verificări

gramaticale, etc.) sau de documente (oferirea de informaţii într-o formă standard, colectarea de informaţii din surse multiple, incorporarea de informaţii grafice sau media, indexare şi căutare a documentelor, respectarea unor criterii de securitate, etc.);

- multimedia – creare, editare, partajare (jocuri, filme, muzică, etc.); - scripting – controlează sau comunică cu una sau mai multe aplicaţii, deoarece sunt

interpretate de un alt program în timpul rulării;

6

- inteligenţă artificială – prelucrarea limbajului natural, sisteme pentru diagnoză sau predicţie, mişcări roboţi, metode inteligente de rezolvare de probleme, etc.;

- educaţionale – folosite ca instrumente de învăţare (exemple: Squeak, Etoys, BlueJ, Logo, Scheme;

- programare sistem – componente sisteme de operare, compilatoare, interpretoare, assemblere, drivere, sisteme în timp real cu tratări de excepţii, etc.;

3. la acest punct clasificarea se bazează pe modelul teoretic al computaţiei: - imperative – Ada, Basic, C, Cobol, Fortran, Pascal, Java. Controlul este

direcţionat pe acţiuni, iar acţiunile sunt realizate prin proceduri specificate pas cu pas;

- funcţionale (simbolice) – Lisp, Scheme, Ml, Acml. Se bazează pe computaţia funcţională, care implică expresii incluse în alte expresii, iar fiecare expresie utilizează funcţii care pot folosi alte funcţii ca parametri. Teoria matematică implicată este calculul lambda λ.

- logice - Prolog. Implică evaluări 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 părţi din program să ruleze concurent. Are două avantaje: permite programarea condusă de evenimente în care părţi din program sunt rulate ca răspuns la evenimente, şi foloseşte calculabilitatea paralelă pentru creşterea vitezei de execuţie.

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

- vizuale – VisualBasic, VisualC++. Implementează instrucţiuni pentru controlul acţiunilor la interfaţa 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).

• Construcţii sintactice – tipuri de date şi structuri, expresii, variabile scop şi clase de memorare, proceduri, funcţii.

1.3 Concepte de reprezentare

Pentru limbajele de programare sunt scrise specificaţii care permit scrierea de programe. Aceste specificaţii trebuie să respecte conceptele de reprezentare specifice acelui limbaj şi clasei de limbaje din care face parte. Pentru reprezentarea şi implementarea limbajelor de programare este nevoie de limbaje formale, care trebuie să fie precise (să nu permită mai multe interpretări, să nu fie ambigui), expresive, concise (o exprimare să se realizeze printr-un număr finit de expresii), să asigure procedurile prin care se pot folosi expresiile limbajului pentru realizarea de raţionamente. Conceptele fundamentale sunt aceleaşi pentru orice limbaj dintr-o anumită clasă de limbaje ce folosesc aceleaşi metode de programare. Conceptele de reprezentare au în vedere următoarele aspecte:

7

• Sintaxa – stabileşte 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 entităţile primitive (elemente lexicale).

• Semantica – asigură explicaţia, interpretarea sau înţelesul entităţilor sintactice. Prin semantică se urmăreşte ce efecte va avea sintaxa la execuţia unui program.

• Pragmatica – include toate aspectele colaterale în implementarea programării unui limbaj şi stilul de programare (strategiile şi filozofia stilului de programare). Pragmatica se mai numeşte şi paradigmă sau stil de programare. Aceste paradigme pot fi imperative, funcţionale, logice, concurente, orientate obiect, vizuale.

1.3.1 Sintaxa

Este stabilită printr-un set de reguli şi convenţii pentru realizarea corectă de

programe. Gramatica asigură o notaţie formală pentru specificarea sintaxei unui limbaj de programare.

O gramatică independentă (liberă) de context, care se numeşte simplu gramatică (în ştiinţa 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 părţi: • Simboluri terminale – sunt simboluri de sine stătătoare (de exemplu constante). • Simboluri non-terminale – grupări de alte simboluri decât cele terminale. • Producţii – prin care se specifică acţiuni, înlocuiri sau rescrieri (de exemplu,

, =>). • Simboluri de început (iniţiale) – care specifică axiomele gramaticii. O gramatică liberă de context este o gramatică formală în care fiecare regulă de

producţie 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, fără 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 notaţii şi convenţii:

• Backus-Naur Form (BNF) – simbolurile terminale sunt scrise cu litere îngroşate sau italice, cele neterminale sunt include între <, >, atribuirea se specifică prin simbolul ::=.

• Extended BNF – simbolurile neterminale încep cu literă mare fără a fi nevoie de <, >.

• Diagrame de sintaxă. • Formate de codificare.

8

1.3.2 Semantica

Pentru a înţelege semantica unui limbaj de programare este nevoie de documentaţie. Documentaţiile 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 (User’s Guide) – implică aspecte informale asupra implementărilor şi aspectelor caracteristice ale limbajului.

• Manualul programatorului (Programmer’s Reference Manual) – este organizat în jurul sintaxei şi a semanticii limbajului, într-o manieră rigidă şi comprehensivă. De obicei conţine definiţii sintactice formale într-o notaţie formală. Are un grad de detaliere ridicat.

• Definiţii 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 făcută observaţia că toate limbajele implementează structuri sau constructori de bază pentru secvenţiere, selecţie, repetare. Există mai multe modalităţi de programare astfel: • Iteraţia şi Recursia Iteraţia 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, până la obţinerea soluţiei. În limbajele de programare acesta implică proceduri şi funcţii care fac referire la ele însele. Un aspect care caracterizează şi face distincţie între iteraţie şi recursie este numărul de paşi necesari pentru obţinerea soluţiei. Dacă metoda este iterativă, numărul de paşi este cunoscut. Dacă metoda implementată este recursivă, atunci nu se cunoaşte numărul de paşi. Limbajele funcţionale (de exemplu, Lisp, Scheme, ML), utilizează recursivitatea şi descurajează utilizarea iteraţiei. Limbajele logice (de exemplu, Prolog), prin natura lor nu permit iteraţia. Limbajele de programare clasice permit atât iteraţia, cât şi recursia. Exemplu: calculul factorialului scris în limbaj C: double fact-iterativ(int n) int i; double f; for (i=2; i<=n; i++) f+=i; return f; double fact-recursiv(int n) if (n==0 || n==1) return 1; else return (n*fact-recursiv(n-1)); În cele mai multe cazuri implementarea iterativă rulează mai repede. Exemplu de implementări iterativ şi recursiv ale factorialului în Lisp: (defun fact-iteratic(n) (prog (i f) (setq f 1)

9

(setq i 1) loop (cond ((greaterp i n) (return f) ) (t ((setq f (* f i)) (setq i (add1 i)) (go loop) ) ) ) ) ) (defun fact-recursiv( ) (cond ((zerop n) 1) (t (* n (fact-recursiv (1-n) ) ) ) ) ) Apelul în funcţia principală main se face astfel: (defun main ( ) (princ “Introduceti numarul (0-25):”) (let (( N (read))) (let F (fact-iterativ N)) ((prin1 N) (princ “! = “) (prin1 F) (terpri)) (let F (fact-recursiv N)) ((prin1 N) (princ “! = “) (prin1 F) (terpri)) ) În Lisp nu sunt definite tipuri de date, deci tipurile lui N şi F nu se ştiu. Exemplu de implementare recursivă în Prolog (iterativ nu este permis): fact-recursiv(0,1). fact-recursiv(N,F) :- N>0, 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ă independenţa faţă de implementarea hardware.

Cel mai des întâlnite tipuri de date abstracte sunt înregistrările (record). O înregistrare este o grupare eterogenă de tipuri de date diferite. Înregistrările sunt principalul mecanism folosit pentru ierarhizarea datelor prin gruparea pe câmpuri şi subcâmpuri.

Tablourile sunt structuri de date de acelaşi tip, multidimensionale. Listele sunt structuri simbolice folosite în limbajele de procesare de liste (de exemplu Lisp). Listele pot reprezenta simbolic informaţii într-o manieră flexibilă şi uşor utilizabilă, dar sunt greu de manipulat. Tablourile sunt folosite în programe iterative, iar listele încurajează metodele recursive. De obicei, tablourile sunt utilizate pentru manipulări de numere, în special ordonate, în timp ce listele pentru manipulări de simboluri neordonate.

Limbajele procedurale lucrează cu tablouri, iar cele declarative (logice şi funcţionale) lucrează cu liste.

Au fost realizate şi implementări hardware pentru prelucrări simbolice, dar nu au rezistat în timp, spre deosebire de calculatoarele actuale care implementează software prelucrările simbolice.

1.4 Metode de programare

10

Metodele (paradigme) de programare fac parte din aspectele avansate ale programării şi se referă la metodologiile de scriere a programelor (imperativă, funcţională, logică, orientată obiect, paralelă, orientată evenimente). Paradigma de programare reprezintă stilul fundamental de implementare a unui program (având caracteristice elementele de program – variabile, constante, funcţii, obiecte – şi modul de structurare a programului – clase, metode, evaluări de funcţii sau structuri, fluxuri de date, etc.) şi diferă de metodele de inginerie software, care reprezintă stilul de a rezolva o anumită problemă software (trecând prin etapele de proiectare, implementare, testare, etc.).

Unele limbaje de programare sunt hibrizi ai paradigmelor, iar altele suportă mai multe paradigme.

When programming computers or systems with many processors, process-

oriented programming allows programmers to think about applications as sets of concurrent processes acting upon logically shared data structures.

Just as different groups in software engineering advocate different methodologies,

different programming languages advocate different programming paradigms. Some languages are designed to support one particular paradigm (Smalltalk supports object-oriented programming, Haskell supports functional programming), while other programming languages support multiple paradigms (such as Object Pascal, C++, C#, Visual Basic, Common Lisp, Scheme, Python, Ruby and Oz).

Many programming paradigms are as well known for what techniques they forbid

as for what they enable. For instance, pure functional programming disallows the use of side-effects; structured programming disallows the use of the goto statement. Partly for this reason, new paradigms are often regarded as doctrinaire or overly rigid by those accustomed to earlier styles.[citation needed] Avoiding certain techniques can make it easier to prove theorems about a program's correctness—or simply to understand its behavior.

1.4.1 Programare imperativă

Caracteristica acestui tip de programare este că foloseşte proceduri şi funcţii

pentru abstractizarea componentelor funcţionale ale unei probleme. Se alcătuiesc ierarhii de proceduri şi funcţii care acţionează ca structuri de date pasive şi care alcătuiesc mecanisme de control orientat acţiune. Se numeşte orientat acţiune deoarece procedurile conţin informaţii necesare pentru rezolvarea problemei şi informaţii 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.

Pentru a scrie un program se folosesc structuri de programare, de bază (secvenţe, selecţii, repetitive). Procedurile şi funcţiile pot fi structurate pe module. Modulele sunt componente funcţionale. Partiţionarea 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 legătură cu limbajele de programare procedurale este natura sau tipul procedurilor, modul de activare, cum se face transferul parametrilor şi cum sunt obţinute şi transmise rezultatele. Deci la această categorie de limbaje

11

subiectele de atins sunt: definirea funcţiilor şi a procedurilor, invocarea rutinelor, transferul parametrilor, prelucrarea excepţiilor.

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 referinţelor şi a modificărilor) şi lucrează cu tipuri de date (definite în limbaj, împreună cu operatorii şi restricţiile asociate).

1.4.2 Programare funcţională

Se mai numeşte şi programare aplicativă, deoarece aplică o funcţie unei expresii.

Un program funcţional este creat ca o secvenţă de funcţii fără stare care sunt evaluate în rularea programului

Această paradigmă de programare are ca scop formularea problemelor mai aproape de raţionamentul 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 susţine că este mai apropiată de gândirea umană decât iteraţia).

Faţă de programarea imperativă, o funcţie poate avea ca argument o altă funcţie (observaţie – nu rezultatul întors de o altă funcţie, chiar funcţia în sine). De asemenea, listele de simboluri pot fi manipulate prin operaţii care implică alte liste, iar operaţiile realizate sunt doar liste de operaţii. 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 notaţia: λ<variabile-legate>.<corp-functie>.

Avantaje ale utilizării limbajelor de programare funcţionale sunt: abordare simplă din punct de vedere matematic, ordinea execuţiei componentelor este implicită, implementează modularitate, limbajele sunt extensibile şi adaptabile prin posibilitatea definirii de funcţii, uşor de corectat, implementează mecanisme complexe pentru controlul fluxului de operaţii.

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 corespunzătoare a cunoştinţelor. 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 aşteaptă în obţinerea soluţiei (scopul problemei). Nu numai că soluţia poate fi furnizată fără specificarea paşilor necesari, dar programul poate explica uneori cum a obţinut soluţia.

Teoria matematică care stă la baza acestei paradigme este logica predicatelor de ordin unu, care lucrează cu entităţi logice (nu cu numere). Logica predicatelor este o logică simbolică al cărui scop este de a reprezenta tipuri de raţionament. Atâta timp cât calculul predicatelor are reguli şi formalităţi matematice definite printr-o teorie, soluţia la o problemă specifică este completă şi efectivă.

Problemele care sunt indicate spre a fi rezolvate prin programare logică sunt din domeniul demonstrării de probleme şi propagării de cunoştinţe. Programarea cunoştinţelor face parte sin metoda soluţiei generale, care implică propagarea constrângerilor. Uneori se numeşte şi propagarea adevărului, deoarece implică

12

propagarea constrângerilor care implică valori de adevăr. Valorile de adevăr 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 care acţionează asupra structurilor de date pasive, considerate ca fiind abstractizări ale obiectelor lumii reale. Dacă se consideră structurile de date (obiectele) active în controlarea operaţiilor efectuate asupra lor, atunci devine programare orientată obiect. Structurile de date, în acest caz, sunt organizate în manieră logică în clase, care precizează, pe lângă organizarea şi structura datelor, şi funcţiile care pot manipula acea structură. Un program orientat obiect este o colecţie de obiecte care interacţionează prin Organizarea obiectelor se combină cu alte proprietăţi caracteristice programării orientată obiect, cum ar fi moştenirea caracteristicilor şi a resurselor.

A programming language can support multiple paradigms. For example programs written in C++ or Object Pascal can be purely procedural, or purely object-oriented, or contain elements of both paradigms. In object-oriented programming, programmers can think of a program as a collection of interacting objects,

13

2. Programare logică - Prolog

Un program scris într-un limbaj de programare logică este constituit din enunţuri care exprimă cunoştinţele relative asupra problemei pe care încearcă să o rezolve programul. Formularea acestor cunoştinţe se bazează pe două concepte de bază:

• Existenţa de obiecte discrete, exprimate prin piese de cunoaştere (cunoştinţe declarative).

• Existenţa de relaţii între aceste obiecte/enunţuri. Exemple de enunţuri declarative prin care se exprimă un domeniu (al studenţilor la Calculatoare) şi relaţii (este student sau cunoaşte):

a) Orice student la specializarea Calculatoare cunoaşte programare; b) Petru este student la Calculatoare;

Din cele două enunţuri declarative se poate raţiona concluzia: c) Petru cunoaşte programare;

Acest exemplu poate fi implementat în programarea logică, deoarece prin acesta se poate reprezenta un număr infinit de posibile relaţii între obiecte şi se poate aplica un sistem de raţionament pentru a obţine concluzii.

Toate piesele de cunoaştere 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 informaţie/cunoaştere pot fi obiecte, numere, figuri geometrice, ecuaţii, etc. Acestor piese de cunoaştere 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 noţiunea care defineşte relaţii inferenţiale asupra claselor de obiecte. A fost dezvoltat la începutul anilor 1970 de către 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 făcută de Borland prin Turbo Prolog în 1986. apoi au apărut versiuni compilate pe lângă cele interpretate. Programarea logică are 3 nivele de abordare a tratamentului informaţiilor:

• Specificarea cunoştinţelor permanente relative la domeniul aplicaţiei; • Specificarea problemei de rezolvat; • Mecanismul de rezolvare care operează asupra primelor două niveluri.

În Prolog au fost realizate aplicaţii din domeniul sistemelor expert şi a limbajelor de specificare, demonstrare de teoreme, logică matematică, limbaj natural. Fundamentele matematice ale programării logice se găsesc în teoria predicatelor logice.

2.1 Fundamente teoretice – logica predicatelor

Logica predicatelor este un limbaj capabil să descrie enunţuri matematice şi să

garanteze corectitudinea raţionamentelor. Limbajul predicatelor de ordin unu dispune de instrumente pentru a defini diverse tipuri de obiecte matematice, cum ar fi: numere, variabile numerice, funcţii şi operaţii matematice, relaţii, propoziţii, teoreme matematice.

În calculul predicatelor, componentele unui enunţ sunt interpretate pentru determinarea valorilor de adevăr ale enunţului. Termenul de predicat este folosit în accepţiunea de formulă deschisă. Formulele deschise pot deveni enunţuri sau propoziţii

14

dacă variabilele care intră în componenţa lor iau valori constante individuale sau sunt cuantificate universal sau existenţial. Un enunţ declarativ se numeşte î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 funcţionale (funcţii, 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 întâi este exprimat printr-un alfabet, şi este alcătuit din ansamblul tuturor formulelor construite folosind simbolurile alfabetului.

Funcţiile şi predicatele au un număr dat de argumente, iar acest număr se numeşte aritate. Dacă o funcţie sau un predicat au n argumente, acestea se numesc n-are. Enunţurile 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 căror sintaxă este explicată în continuare. Un termen poate fi definit recursiv astfel:

• o constantă; • o variabilă; • o funcţie (functor) f(t1,...,tn), unde f este un simbol funcţional, 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 existenţial ∃ ş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 conţine negaţii. 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 formulele F, F G¬ → . Ordinea operatorilor este:

, , negare, orice, exista

sau

si

, implica, echivalent

¬ ∀ ∃

∨

∧

→ ↔

Exemple: - pentru a reprezenta expresia „x mai mare decât 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 decât 10” se foloseşte notarea

maimare(X,10);

15

- pentru a reprezenta operaţia care realizează media aritmetică se utilizează termenul media(X,Y), în care X şi Y sunt variabile, iar media este un simbol funcţional;

- expresia „media lui x şi 7 mai mare decât y” se reprezintă în logica predicatelor maimare(media(X,7),Y);

- enunţul „Petru este student la specializarea Calculatoare” se formalizează în limbajul logicii predicatelor prin predicatul STUDENT(petru, calculatoare). Pentru a exprima că există cel puţin un student la secţia Calculatoare utilizăm: (∃X)STUDENT(X,calculatoare).

- declaraţia „orice student la Calculatoare cunoaşte programare” se exprimă prin (∀X) (STUDENT(X,calculatoare) ∧ CUNOAŞTE_PROGRAMARE(X)).

- deducţia „Petru cunoaşte programare” se transformă în predicatul CUNOAŞTE_PROGRAMARE(petru). Pentru a reprezenta enunţul „Petru nu cunoaşte programare” folosim negaţia ¬ CUNOAŞTE_PROGRAMARE(petru).

- pentru a exprima faptul că un student care a promovat are media notelor mai mare decât 5 utilizăm combinaţia promovat(X,maimare(media(Z,Y),5)). Dacă ştim că Petru are notele 6 şi 10 şi reprezentăm promovabilitatea lui atunci folosim un termen compus: promovat(petru,maimare(media(6,10),5)).

În limbajul natural o combinaţie de cuvinte alcătuieşte un enunţ (propoziţie) cu un

anumit înţeles. În logica predicatelor, enunţul este construit din termeni care alcătuiesc o formulă sau o formulă bine formată. O formulă bine formată se defineşte 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, F G, F G, F G, F G¬ ∧ ∨ → ↔ sunt formule; 3. dacă F este formulă şi x este o variabilă liberă, atunci ( x)F si ( x)F∃ ∀ sunt

formule; 4. formulele se generează prin aplicarea de un număr 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 existenţial este o variabilă legată în formula prefixată de acel cuantificator.

O variabilă este liberă dacă nu este legată, adică dacă are cel puţin o apariţie liberă în acea formulă.

O formulă care nu conţine variabile libere se numeşte formulă închisă.

Un literal este o formulă redusă la un atom (adică o formulă care conţine numai predicate). Deci un literal este un atom sau negaţia unui atom. Un literal pozitiv este un atom. Un literal negativ este negaţia unui atom. Limbajul logic al predicatelor de ordin unu este o formalizare a enunţurilor declarative din limbajul natural. Aceste enunţuri se referă la anumite „cuvinte” şi pot fi adevărate sau false în domeniul considerat. Înţelesul formulelor logice este definit relativ la un „cuvânt abstract” numit structură (algebrică) şi poate fi, de asemenea, adevărat sau fals. Deci, pentru a defini înţelesul unei formule trebuie să se stabilească o legătură între limbaj şi structură. Enunţurile declarative pot face referire la entităţi şi reprezintă relaţiile sau funcţiile dintre acestea. Astfel, abstractizarea matematică a „cuvântului” numit structură, este o mulţime nevidă de entităţi (numită domeniu), împreună cu relaţiile şi funcţiile definite pe mulţime. Legătura dintre limbaj şi structură se realizează prin semantica limbajului.

16

Aspectele semantice se ocupă de următoarele caracteristici: • interpretarea formulelor bine formate; • formule valide, inconsistente, echivalente; • consecinţă logică; • clauze Horn; • demonstrarea teoremelor prin reguli de inferenţă permite obţinerea de formule

bine formate plecând de la una sau mai multe formule bine formate aplicând modus ponnens, modus tollens, specializării 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 funcţiilor, domeniul şi asignarea predicatelor care apar în formulă. O interpretare a unui limbaj L de ordin unu este constituită din următoarele elemente:

• o mulţime nevidă D numită domeniul interpretării; • fiecărei constante din limbajul L i se asignează un element din D; • fiecărui simbol de funcţie n-ară din limbajul L i se asignează o aplicaţie

nD D→ . • fiecărui simbol de predicat P de aritate n, i se asignează o aplicaţie nD T, F→ .

Interpretarea constantelor şi a simbolurilor de funcţii şi predicate, constituie baza asignării valorilor de adevăr formulelor din limbaj. Interpretarea unei formule va fi definită ca o funcţie a interpretărilor componentelor sale, care sunt termeni (constante, variabile, functori). Deci, trebuie definită interpretarea unui termen. Deoarece termenii pot să conţină variabile, se introduce noţiunea de evaluare. Evaluarea unei variabile este o funcţie ϕ 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 fiecărei constante, funcţie sau predicat care apar în F în modul următor:

1. fiecărei constante i se asignează un element din D; 2. fiecărei funcţii n-are i se asignează o aplicaţie de la Dn la D, unde

Dn=(x1,...,xn)|x1 din D,...,xn din D; 3. fiecărui predicat n-ar i se asociază o aplicaţie de la Dn la True, False.

Se spune că formula F are o interpretare peste domeniul D. Când se evaluează valorile de adevăr ale unei formule F peste un domeniu D, ( x)∀ se interpretează ca „pentru toate elementele din D”, iar ( x)∃ ca „există cel puţin un element din D”.

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

1. dacă valorile de adevăr ale lui G şi H sunt evaluate, atunci se pot evalua şi pentru G, G H, G H, G H, G H¬ ∧ ∨ → ↔ ;

2. ( x)G∀ este adevărată T, dacă valoarea de adevăr a lui G este T pentru orice element din D, altfel este F;

3. ( x)G∃ este T dacă valoarea de adevăr a lui G este T pentru cel puţin un element din D, altfel este F.

O formulă care conţine variabile libere nu poate fi evaluată. În logica predicatelor, deoarece există un număr infinit de domenii, există şi un număr infinit de interpretări ale unei formule. Din această cauză nu se poate verifica validitatea sau inconsistenţa unei formule prin evaluarea ei sub toate interpretările posibile. Exemplu:

17

considerăm limbajul care conţine constantele zero şi cinci (pentru reprezentarea numerelor naturale 0 şi 5), functorul unar incr (pentru reprezentarea incrementării) şi predicatul maimare (reprezintă operaţia de comparare). Pentru domeniul D reprezentat de mulţimea numerelor naturale avem:

zeroD := 0 cinciD := 5 incrD(x) := 1+x maimareD(x,y) := x>y

Pentru a determina interpretarea formulei „5 mai mare decât zero incrementat” peste domeniul D scriem formula ca (maimare(5,incr(zero))) = (maimare(5,1)) care are valoarea de adevăr True. Dacă, în locul constantei 5 aveam o variabilă liberă X, formula nu mai putea fi evaluată cu o valoare de adevăr. Se ştie că în mulţimea numerelor naturale, orice număr diferit de zero este mai mare decât acesta. În acest caz, formula „orice X număr natural este mai mare decât zero” reprezentată prin (maimare(X,zero)) este adevărată în interpretarea numerelor naturale. O formulă este consistentă (realizabilă) dacă există cel puţin 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). Relaţia dintre valoarea de adevăr a formulei şi termenii de clasificare ai formulei este:

O formulă G este consecinţă logică a formulelor F1,...,Fn dacă şi numai dacă sub orice interpretare, dacă 1 nF ... F∧ ∧ este adevărată, atunci şi G este adevărată.

Teorema deducţiei 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 n((F ... F ) G)∧ ∧ →

este validă sau 1 n((F ... 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 adevărată. Problema se reprezintă cu ajutorul formulelor, care sunt interpretate pentru a clasifica formula în validă, invalidă, consistentă sau inconsistentă.

Întotdeauna adevărată

Întotdeauna falsă

Uneori adevărată, uneori falsă

validă invalidă

contingentă

consistentă (realizabilă) inconsistentă

18

În logica predicatelor de ordin unu, deoarece există un număr infinit de domenii, există şi un număr infinit de interpretări ale unei formule. Astfel, o formulă care descrie un enunţ într-un domeniu, poate descrie alt enunţ în alt domeniu, rezultând mai multe modele pentru aceeaşi formulă. Din această cauză nu este posibil să se verifice validitatea sau inconsistenţa unei formule prin evaluarea ei sub toate interpretările 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ă negaţia formulei este inconsistentă. Pentru a se utiliza procedurile Herbrand, trebuie definit universul Herbrand al unei mulţimi de clauze.

Clauzele sunt formule transformate în forma standard Skolem, care are forma unei disjuncţii de literali de 1 n 1 mx ,..., x (L ... L )∀ ∀ ∨ ∨ , unde 1 nx ,...,x apar în 1 mL ,...,L

(nu conţine cuantificatorul existenţial). Clauzele se mai numesc şi clauze Horn.

Pentru a se transforma o formulă la forma de mai sus se folosesc următoarele reguli:

• treceri în formule echivalente. Două formule sunt echivalente, dacă şi numai dacă au aceleaşi valori de adevăr pentru orice interpretare a oricărei din cele două formule. Formulele de echivalentă din logica propoziţiilor sunt: F G echivalent cu (F G) (F G)

F G echivalent cu F G

F G G F comutativitate

F G G F

(F G) H F (G H)asociativitate

(F G) H F (G H)

F (G H) (F G) (F H) distributivitate

F (G H) (F G) (F H)

F True True

F

↔ → ∧ ←

→ ¬ ∨

∨ ≡ ∨

∧ ≡ ∧

∨ ∨ ≡ ∨ ∨

∧ ∧ ≡ ∧ ∧

∨ ∧ ≡ ∨ ∧ ∨

∧ ∨ ≡ ∧ ∨ ∧ ∨ =

∨ False F

F True F

F False False

F F False

F F True

( F) F

(F G) F G de Morgan

(F G) F G

=

∧ =

∧ =

∧¬ =

∨¬ =

¬ ¬ =

¬ ∨ ≡ ¬ ∧¬

¬ ∧ ≡ ¬ ∨¬ La acestea se mai adaugă şi alte formule echivalente specifice logicii predicatelor de ordin unu:

19

1

( 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)

( xF(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))

Q xF(x

∀ ∨ ≡ ∀ ∨

∃ ∨ ≡ ∃ ∨

∀ ∧ ≡ ∀ ∧

∃ ∧ ≡ ∃ ∧

¬ ∀ ≡ ∃ ¬

¬ ∃ ≡ ∀ ¬

∀ ∧∀ ≡ ∀ ∧

∃ ∨ ∃ ≡ ∃ ∨

2 1 2

1 2 1 2

1 2

) Q xG(x) (Q x)(Q y)(F(x) G(y))

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

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

∨ ≡ ∨

∧ ≡ ∧

∀ ∃

• transformarea formulei în forma normală prenex: 1 1 n n(Q x )...(Q x )M , unde

iQ ,i 1...n= sunt cuantificatorii universal ∀ şi existenţial ∃ , iar M este o

formulă, numită matrice, care nu conţine cuantificatori. i i(Q x ) formează

prefixul formulei; • matricea, deoarece nu conţine cuantificatori, poate fi transformată în forma

conjunctivă normală (matricea poate fi considerată ca fiind scrisă în logica propoziţiilor pentru că nu conţine cuantificatori). În logica propoziţiilor există două forme normale conjunctivă 1 nF ... F∧ ∧ şi disjunctivă 1 nF ... F∨ ∨

• fără a afecta proprietăţile de inconsistenţă, cuantificatorul existenţial din prefix poate fi eliminat folosind funcţiile Skolem. Astfel, fie F o formulă în forma normală prenex 1 1 n n(Q x )...(Q x )M , iar matricea M este în forma normală

conjunctivă. Se presupune în prefixul 1 1 n n(Q x )...(Q x ) , cuantificatorul

rQ , 1 r n≤ ≤ ca fiind existenţial.

o dacă nici un cuantificator universal nu apare înaintea lui rQ , atunci se

alege o constantă C (diferită de cele care apar în M) care înlocuieşte pe

rx şi se şterge r rQ x din prefix;

o dacă s1 smQ ,...,Q sunt cuantificatori universali care apar înaintea lui rQ în

prefix, 1 s1 ... sm r≤ ≤ ≤ ≤ , atunci se alege o funcţie m-ară f (diferită de toate funcţiile care apar în M) şi se înlocuiesc toate apariţiile lui rx din M

cu s1 smf (x ,..., x ) şi se şterge r rQ x din prefix;

După ce se elimină toţi cuantificatorii existenţiali din prefix se obţine forma

standard Skolem a formulei F. Constantele şi funcţiile folosite pentru a înlocui variabilele cuantificate existenţial se numesc funcţii Skolem.

Etapele în care se obţine o transformare a unei formule într-o clauză sunt: • se transformă formula în forma normală Prenex, în care matricea nu conţine nici

un fel de cuantificatori, iar prefixul este o secvenţă de cuantificatori. • matricea, deoarece nu conţine cuantificatori se aduce la forma conjunctivă

normală. • se elimină cuantificatorii existenţiali din prefix folosind funcţiile Skolem.

Scopul transformării în forma standard Skolem este pentru a rezolva problemele prin teorema lui Herbrand sau prin metodele rezoluţiei.

20

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. formula x y z(( P(x, y) Q(x,z)) R(x, y,z)∀ ∃ ∃ ¬ ∧ ∨ se transformă în forma

normală conjunctivă x y z( ( P(x, y) R(x, y,z)) (Q(x,z) R(x, y,z)) )∀ ∃ ∃ ¬ ∨ ∧ ∨ şi are forma Skolem

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 mulţime de clauze, care poate fi considerată ca o conjuncţie a tuturor clauzelor implicate, iar fiecare variabilă este considerată ca fiind guvernată de un cuantificator universal. Dacă se consideră S o mulţime de clauze, care reprezintă forma standard a unei formule F. Pentru a demonstra că formula F e inconsistentă este suficient a demonstra că mulţimea de clauze ataşată acesteia e inconsistentă. O mulţime de clauze este inconsistentă (sau nerealizabilă, nesatisfăcută), dacă este falsă în toate interpretările pe toate domeniile posibile. Deoarece este imposibil să se evalueze formula pentru toate interpretările, pe toate domeniile posibile, se defineşte un domeniu special H, astfel încât S este inconsistentă dacă şi numai dacă formula F este falsă sub toate interpretările peste domeniul H. Un astfel de domeniu, numit universul Herbrand pentru mulţimea de clauze S se defineşte astfel:

• fie HC mulţimea 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 mulţimea termenilor de forma n

1 nf (t ,..., t ) , care sunt funcţii n-are din S, iar it sunt elemente ale mulţimii Hi.

Mulţimea Hi se numeşte mulţimea de constante de nivel i, iar H∞ se numeşte

universul Herbrand pentru S. Exemple: 1. Fie S P(a), P(x) P(f (x))= ¬ ∨ . Universul Herbrand este definit astfel:

0

1

2

H a

H a, f (a)

H 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:

0 1H H H ... a= = = = , deoarece formula nu conţine nici un simbol funcţional.

3. Fie S P(f (x)),a,g(y),b= . Universul Herbrand este dat de mulţmile:

0

1

2

H a,b

H a,b, f (a), f (b),g(a),g(b)

H 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))

=

=

=

21

2.1.2 Inferenţă logică

Procesul de raţionament constă în obţinerea, pe baza unei mulţimi de formule date, numite premise, de noi formule, numite concluzie. În logica simbolică, principiile de raţionament, care constau în deducerea de formule valide din alte formule valide, sunt scrise sub forma regulilor de inferenţă. Astfel, regulile de inferenţă permit obţinerea de consecinţe logice din premisele asupra cărora se aplică inferenţa. 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 eliminării cuantificatorului universal – consideră că într-o formulă de

forma ∀X F(X) se poate înlocui apariţia variabilei legate X cu un termen t care este liber de variabila X: ∀X F(X) F(t)

O mulţime de premise se numesc inconsistente, dacă orice formulă poate fi obţinută prin inferenţă din mulţimea de formule.

2.1.3 Substituţii

Din punct de vedere formal, o substituţie constă în înlocuirea variabilelor dintr-un alfabet cu termeni din acelaşi alfabet. Prin substituţie se înţelege o mulţime de perechi X1|t1,...,Xn|tn, unde ti sunt termeni, Xi sunt variabile astfel încât Xi≠ ti şi Xi≠ Xj dacă i≠ j. Fie substituţia θ dată de X1|t1,...,Xn|tn şi Este un termen sau o formulă. Aplicarea substituţie θ la E este termenul sau formula obţinute prin înlocuirea cu ti a fiecărei apariţii a variabilei libere Xi în E. Eθ se numeşte instanţă a lui E. Exemple de substituţii:

- Fie formula p(f(X,Z), f(Y, a)) şi substituţia X|a, Y|Z, W|b. Instanţa formulei este p(f(a,Z), f(Z; a)).

- Fie formula p(X, Y ) şi substituţia X|a, Y|b, instanţa formulei este p(a, b). Considerăm , ,θ ϕ γ substituţii şi E un termen sau o formulă. Proprietăţile substituţiei sunt:

• E( ,θ ϕ )=(Eθ )ϕ

• ( )θϕ γ = ( )θ ϕγ (asociativitate)

• θϕ ≠ ϕθ (nu este comutativă)

22

2.2 Aspecte teoretice aplicate în Prolog

Programarea logică este baza pentru toate celelalte reprezentări de cunoştinţe ale

lumii reale. Programele logice pot fi aplicate în multe domenii. Astfel, Web Consortium a adoptat un limbaj logic pentru proiectul Semantic Web. În unele aplicaţiile de monitorizare a traficului aerian se folosesc limbaje logice pentru descrierea restricţiilor impuse de domeniu. De asemenea, în domeniul înţelegerii limbajului natural se folosesc aspecte de programare logică. Logica predicatelor de ordin unu permite modelarea informaţiilor generale despre lumea reală şi este sugestivă faţă de limbajul natural şi în plus, computaţională prin limbajele de programare logice. O caracteristică a limbajelor logice, diferită de a limbajelor de programare, dar care seamănă cu limbajul natural, este că permite introducerea de cunoştinţe adevărate despre lumea reală fără 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).

Diferite implementări ale Prolog:

Na

me

OS

Lic

ence

Na

tiv

e G

rap

hic

s

Un

ico

de

Ob

ject

Ori

ente

d

Na

tiv

e O

S C

on

tro

l

Sta

nd

Alo

ne

Ex

ecu

tab

le

C I

nte

rfa

ce*

Ja

va

In

terf

ace

*

Inte

ract

ive

Inte

rpre

ter

Deb

ug

ger

Sy

nta

x

DOS-PROLOG

MS-DOS Shareware X X X X X Edinburgh Prolog

Open Prolog

Mac OS Freeware X

Ciao Prolog

Unix, Windows

GPL X X X X X ISO-Prolog

GNU Prolog

Unix, Windows

GPL X X X X X ISO-Prolog

Visual Prolog

Windows Freeware, comercial

X X X X X X X

SWI-Prolog

Unix, Windows, Mac OS

LGPL X X X X X X X ISO-Prolog, Edinburgh Prolog

23

WIN-Prolog

Windows Shareware comercial

X X X X X ISO-Prolog, Quintus Prolog

Tu-Prolog JVM GPL X X X X X X ISO-Prolog

Conferinţe cu specific pe limbajele logice:

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

• ICLP - International Conference on Logic Programming Scopul programării logice este de a rezolva probleme prin obţinerea de concluzii

pornind de la descrieri declarative ale condiţiilor în care există soluţia, dar fără a arăta cum se găseşte soluţia. Aceste descrieri, numite programe logice, sunt alcătuite dintr-o mulţime finită de formule logice. Asupra acestor formule se aplică restricţii care permit aplicarea principiului rezoluţiei. O limitare a variantelor de Prolog clasice este că nu permit definirea de funcţii, doar relaţii (văzute ca proceduri care nu returnează nici o valoare). De exemplu, în Prolog clasic nu se poate defini funcţia factorial(X) care are ca argument un întreg şi returnează un întreg, se poate defini doar relaţia booleană factorial(X, Rez) care leagă un întreg X de factorialul său Rez.

Un program logic în Prolog este definit printr-o mulţime finită de clauze, în care

fiecare variabilă este considerată ca fiind guvernată de un cuantificator universal. O clauză are forma: 1 nA B ,...,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ţă rezoluţia asupra clauzelor concrete, apoi

generalizată la clauze Horn prin mecanismul de unificare. Un literal este concret dacă nu conţine variabile. O clauză concretă este o

disjuncţie de literali concreţi. Fie clauzele concrete 1 nA A ... A= ∨ ∨ şi 1 2 mB A B ... B= ¬ ∨ ∨ ∨ . 1A şi 1A¬ se

numesc literali complementari. Principiul rezoluţiei obţine clauza rezolvantă 2 n 2 mC A ... A B ... B= ∨ ∨ ∨ ∨ ∨

plecând de la clauzele A şi B, prin eliminarea literalilor complementari şi prin disjuncţia celorlalţi literali.

Mecanismul de inferenţă are ca scop căutarea echivalenţei între două formule, care se realizează prin mecanismul de unificare.

Considerăm s şi t termeni. Unificatorul lui s şi t este o substituţie θ astfel încât sθ şi tθ sunt identici (se notează cu sθ =tθ ).

O substituţie θ se spune că este mai generală decât o altă substituţie ϕ dacă şi numai dacă există o substituţie ω astfel încât ϕ = θω .

Un unificator θ se numeşte cel mai general unificator pentru doi termeni, dacă şi numai dacă θ este mai general decât orice alt unificator al termenilor.

Pentru o formulă F unificatorul general cel mai comun ω se obţine dacă pentru toţi unificatorii ϕ , există o substituţie θ astfel încât [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= .

24

Rezoluţia aplicată clauzelor oarecare: fie clauzele A şi B, care nu au variabile comune. Se spune că este posibil să se asocieze fiecărui cuantificator un nume de variabilă diferit. A şi B sunt compuse dintr-o disjuncţie de literali iA şi jB . Dacă există

submulţimile kA şi lB astfel încât k lA B ¬U sunt unificabile prin cel mai

comun unificator general p, atunci rezolventul lui A şi B se poate scrie

i k j lp[A A ] p[B B ]− ∪ − .

Proprietatea fundamentală a rezoluţiei: dacă în urma unei rezoluţii, plecând de la o mulţime 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)∨ ∨¬ . Unificatorul general cel mai comun al lui Q(y) şi ( Q(z))¬ ¬ este y | z , iar de aici rezultă rezolventul P(x, f (a)) P(x, f (y)) P(y, f (a))∨ ∨¬ . Se observă astfel că două clauze pot avea nici unul sau mai mulţi rezolvanţi.

2.2.1 Principiul rezoluţiei prin respingere

Rezoluţia prin respingere este utilizată pentru a demonstra că o formulă bine

formată A este consecinţă logică a unei mulţimi de formule iS S = . Se procedează

astfel: 1. se constituie mulţimea de clauze C derivate din S; 2. se adaugă la mulţimea de clauze C clauza derivată din A¬ ; 3. atâta timp cât clauza vidă nu este în C se urmează paşii:

a. se aleg două clauze distincte din C; b. dacă nu sunt rezolvanţi, 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, când există, este găsită, 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 corespunzători la pasul 3.b. O strategie de rezoluţie constă în construirea unui arbore de respingere, în care nodurile sunt clauze din S. Arcele sunt legături între clauzele părinţi şi rezolvanţii posibili, iar frunzele sunt clauze vide.

2.2.2 Cunoştinţe în Prolog

Nu există nici o normalizare a limbajului Prolog. Un program Prolog este o listă ordonată de clauze Horn (prin care se formalizează enunţuri declarative) care exprimă: • reguli 1 n 1 nS ... S R S ... S R∧ ∧ → ⇔¬ ∨ ¬ ∨ ⇔ 1 nR S ... S∨¬ ∨ ∨¬ ;

• fapte F; • scopuri 1 mB ... B¬ ∨ ∨¬ .

25

Regulile sunt clauze Horn complete care au un literal pozitiv unic, (numit şi cap) şi unul sau mai mulţi literali negativi, (numiţi şi coadă). Faptele sunt literali pozitivi. Scopurile sunt clauze care conţin doar literali negativi. Unei reguli i se poate asocia:

• o interpretare logică – dacă predicatele din coadă sunt adevărate, atunci predicatul din capul regulii este de asemenea adevărat;

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

Răspunsul la un scop care nu conţine variabile trebuie să se obţină în valorile de adevăr T sau F. Răspunsul la un scop cu n variabile este o mulţime de n valori, care se pot asocia cu variabilele şi care satisfac scopul. Variabilele anonime se notează cu „_” şi valoarea lor este indiferentă. Exemple:

1. formula bine formată xP(x,a)∀ are forma cauzală P(x,a) , iar în Prolog se scrie P(X,a) .

2. se consideră formula bine formată x 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 rezoluţie în Prolog

Se aplică rezoluţia între scopuri şi reguli cu B1 şi R unificabile prin unificatorul general cel mai comun p, care conduce la clauza

1 2 n 2 mp[S ] p[S ] ... p[S ] p[B ] ... p[B ]¬ ∨¬ ∨ ∨¬ ∨¬ ∨ ∨¬ ,

adică noile scopuri 1 n 2 mp[S ],..., p[S ], p[B ],..., p[B ] .

Algoritmul de rezoluţie poate fi considerat ca parcurgerea unui arbore, în care fiecare nod este etichetat printr-o listă de scopuri şi o substituţie 1 m[B ,..., B ,s] . Nodul rădăcină

conţine scopurile problemei propuse. Algoritmul este: fie nodul 1 m[B ,..., B ,s] ;

dacă lista 1 m[B ,..., B ] este vidă

atunci afişează S ( un succes); se trece la nodul precedent; altfel se consideră 1B ;

se caută prima regulă dintre 1 nR S ... S∨¬ ∨ ∨¬ care nu a fost încă

explorată la acest nod şi deci literalul pozitiv se poate unifica prin 1B ;

dacă nu există atunci dacă este un nod rădăcină atunci gata altfel se urcă la nodul precedent

26

altfel fie p unificatorul general cel mai comun al lui R şi 1B

coborârea creează un nou nod [ 1 n 2 mp[S ],..., p[S ], p[B ],..., p[B ] ]

Interpretorul Prolog generează o listă de scopuri care se rezolvă prin şterge folosind unificarea şi o listă de alegeri în aşteptare. 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 aşteptare. Oprirea definitivă se produce când nu mai este posibilă nici o întoarcere înapoi.

27

2.2.4 Reprezentarea cunoştinţelor în Prolog

Principalele secţiuni

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

• Predicatele cuprind şi clasifică relaţiile cunoscute din spaţiul problemei. • Scopul descrie problema de rezolvat şi formatul răspunsului aşteptat. • Clauzele sunt reprezentate prin fapte logice, reguli şi alte construcţii.

Subprogramele sunt utile atunci când se foloseşte varianta compilată a Prolog-ului, care permit opţiuni de re-compilare la fiecare execuţie a unui subprogram (un program poate fi împărţit pe subprograme care pot fi rulate separat). Implementările interpretate ale Prolog acceptă doar un singur modul de program. Subrutine sunt predicatele şi au acelaşi scop cu funcţiile din limbajele de programare procedurale. Predicatele returnează doar valori de tip boolean (true, false sau fail). Argumentele predicatelor pot fi clasificate c fiind intrări sau ieşiri. Dacă un argument primeşte o valoare în timpul apelului predicatului, atunci argumentul este de tip intrare, altfel de tip ieşire. Un argument poate fi şi intrare şi ieşire. Limbajul Prolog are predicate predefinite pentru funcţiile matematice, pentru operaţii de intrare-ieşire (read, read-line, write), de lucrur cu şiruri de caractere, pentru operaţii 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 Rezoluţia în Prolog

Strategia de rezolvare în Prolog este în adâncime folosind metoda backtracking. Rezolvantul obţinut 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 substituţia X | A, X | B . Noile scopuri sunt (e) tata(X,P),tata(P,Y).

28

- interpretorul încearcă să unifice primul scop al lui (e) cu primul literal al lui (a), (b), (c). Unificarea este posibilă cu (a) pentru substituţia 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 aşteptare (b) şi (c). Unificarea este posibilă cu (b) pentru substituţia 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 substituţia Ion|Y. Noul scop este clauza vidă. Problema se termină cu un succes şi se afişează substituţiile pentru variabilele din scopul iniţial, astfel X=Marian, Y=Ion.

Observaţie: soluţiile nu sunt găsite î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 răspuns evident.

2. a a->a dă un răspuns adevărat.

Sunt variante de limbaj care se opresc la primul scop găsit şi altele care caută toate scopurile posibile.

2.2.6 Controlul rezoluţiei

În Prolog există un predicat predefinit „!” (sau „/”) care permite suprimarea explorării anumitor ramuri din arborele de rezoluţie. 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 explorării arborelui de rezoluţie, atunci se întoarce până la nodul corespunzător nodului precedent, scop care a declanşat apelul regulii care conţinea predicatul !. Acest predicat se utilizează de obicei, la sfârşitul întrebării pentru a evita întoarcerea în cazul unui prim succes. Sau se forţează un răspuns unic în cazul în care programul are răspunsuri multiple, chiar o infinitate de răspunsuri. Se mai poate utiliza în corpul unei reguli pentru a forţa un răspuns pertinent şi pentru a împiedica alte explorări. Exemplu:

1 a:-b, c, d.

c d

e

f

a

g

b

h a

esec

succes

29

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 rulării programul va afişa: 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 sfârşit*/

Fără ! în regula 4 se obţin următoarele 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, d1(succes), d2(succes), b2, c11, c21, d1(succes), d2(succes), c22, d1(succes),

1 a

b c d

c d

2

4

c1 ! c2 d

! c2 d

6

!

c2 d

d

8

succes

10

c d

3

4

c1 ! c2 d

! c2 d

6

!

c2 d

d

8

succes

10 11 d

9

succes

10 11 11 d

9

succes

10 11

30

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 număr î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ă tratării 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):-Y<X, taie(X, L, L1, L2). taie(X,[Y|L], L1, [Y|L2]):-Y>X, 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) – citeşte 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 rezultând L3. • ordonare – este predicatul care va fi folosit ca scop pentru execuţia programului.

Exemplu: problema de sortare care ordonează crescător o listă de întregi pozitivi. Întregii pozitivi sunt reprezentaţi cu ajutorul constantei O şi cu funcţia unară f(succesor). Întregul pozitiv n este reprezentat prin termenul nf (O) . Lista se reprezintă prin simbolul funcţiei binare „.”, constanta nil reprezintă lista vidă. Astfel, lista

31

[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, <= (scris infixat). Semantica pentru predicate este:

• sort: dacă x şi y sunt liste, y este o permutare a lui x şi y este ordonată, atunci y este versiunea ordonată a lui x.

• sorted: lista vidă este ordonată. • delete(x,z,w) se obţine prin ştergerea lui y din y.z şi y.w.

Pentru a executa programul se fixează scopul sort(17.22.6.5.nil,X).

32

3. Programare funcţională Programarea funcţională este o paradigmă de programare, care se bazează pe evaluarea expresiilor sau termenilor (specific limbajelor declarative) mai mult decât pe evaluarea comenzilor (specific limbajelor procedurale). Expresiile în limbajele funcţionale sunt formate prin funcţii care combină valori de bază (spre deosebire de relaţii care formează baza limbajelor logice). În programarea funcţională, pentru a realiza un program se consideră funcţiile din punct de vedere matematic. Cele mai importante caracteristici ale funcţiilor din acest punct de vedere sunt faptul că nu au memorie şi nu cauzează efecte colaterale (funcţiile furnizează doar rezultate atunci când primesc valori pentru argumente). A doua caracteristică este valabilă pentru limbajele funcţionale pure. Exemplu: de program pentru calculul sumei numerelor întregi de la 1 la 10. Într-un program imperativ (de exemplu limbajele C au Java), se utilizează o structură repetitivă astfel: total=0; for(int i=1;i<=10;i++) total+=i; Într-un program funcţional nu se utilizează recursia pentru definirea funcţiei care calculează suma: în limbaj SML codul este:

let fun sum i total = if i=0 then total

else sum (i-1) (total+i) in sum 10 0 end

unde total şi i sunt parametri formali care transmit explicit starea funcţiei, iar elementul condiţional este considerat o expresie care calculează o valoare şi nu o secvenţă de comenzi. în limbaj Scheme: (define sum (lambda (from total) (if (=0 from) total (sum (- from 1) (+ total from)) ) ) ) (sum 10 0) Programele funcţionale rezolvă problemele prin aplicarea de funcţii. Limbajele de programare funcţionale se împart în stricte (exemple ML, Caml, Scheme, Pizza, Erlang) şi non-stricte (Clean, Gofer, Haskell, Miranda). Se consideră funcţia f care are ca argument o expresie exp, astfel f(exp). Într-un limbaj funcţional strict, argumentele unei funcţii sunt evaluate înainte de apelul funcţiei. Dacă din evaluarea expresiilor implicate în argumentele funcţiei rezultă eroare, atunci funcţia nu se mai evaluează. Într-un limbaj non-strict, argumentele unei funcţii nu sunt evaluate până când nu sunt cerute valorile acestora. Astfel, dacă din evaluarea expresiei exp rezultă eroare, apelul funcţiei f(exp) poate să nu aibă rezultat eronat, dacă valoarea parametrului nu este utilizată în corpul funcţiei.

33

Printre limbajele funcţionale există implementări concurente (exemple Erlang, Pizza, Clean). Aplicaţii pentru programarea funcţională: • Lisp – a fost creat la sfârşitul anilor 1950 de către John McCarthy. Limbajul de

programare poate implementa şi aspecte imperative, ceea ce la vremea respectivă a fost un avantaj.

• Allegro CL- sistem de dezvoltare dinamic şi orientat obiect, creat pentru aplicaţii entreprise. Are la bază Common Lisp şi este ideal pentru aplicaţii critice, extensibile, cum ar fi servere dinamice, managementul cunoştinţelor, controlul producţiei, proiectarea şi realizarea semiconductorilor, data mining. Este realizat de Franz Inc. şi are versiuni free pentru platforme Windows, Linux, MacIntosh.

• ML – este un meta-limbaj care implementează structuri de control funcţionale, module şi care a stat la baza dezvoltării altor implementări. Dintre acestea amintim Standard ML, Lazy ML, CAML. Există variante ale ML pentru mai multe platforme (PC-uri, staţii de lucru, mainframe-uri, sisteme multi-procesor) şi diverse sisteme de operare.

• Scheme – este o variantă a limbajului Lisp. Este simplu şi poate implementa diverse reprezentări de programare abstracte. Este standardizat şi prezintă mai multe implementări, cum ar fi: Chez Scheme, MIT/GNU Scheme, Scheme 98.

Limbajele funcţionale sau aplicative realizează calcule prin evaluarea expresiilor, implementând calculul lambda, care este un prototip de limbaj funcţional, de mici dimensiuni. Limbajele funcţionale sunt indicate de a fi utilizate în analiza şi raţionamentul formal şi pot fi implementate mai uşor pe arhitecturi paralele. Aspectele teoretice întâlnite în limbajele funcţionale sunt funcţiile complexe (recursive, mutual recursive, polimorfice), evaluare slabă (engl. lazy), potrivire (engl. pattern matching), date abstracte.

Calculul lambda poate fi definit ca un sistem formal (structură abstractă utilizată pentru modelare, constituită din o mulţime finită de simboluri utilizate pentru construcţia de formule, o gramatică care permite construirea de formule bine formate, o mulţime de axiome, teoreme şi reguli de inferenţă), utilizat pentru a investiga definiţia şi aplicarea funcţiilor şi a recursiei. Teoria calculului lambda a fost introdusă de Alonzo Church şi de Stephen Cole Kleene în anii 1930. Această teorie poate fi utilizată pentru definirea funcţiilor computabile (calculabile). Calculul lambda a fost construit, din punct de vedere informal, pe sintaxa termenilor şi a regulilor de transformare a termenilor (prin substituţia de variabile) cu scopul de a trata comportamentul funcţiilor (orice funcţie poate fi exprimată şi evaluată cu acest formalism). Funcţiile sunt considerate a fi mulţimi de perechi argument-valoare care pot fi calculate. În teoriile matematice în care funcţiile sunt considerate ca mulţimi nu este permisă recursia, deoarece nu există noţiunea ca o mulţime să se conţină pe sine. Teoria calculului lambda a permis introducerea noţiunii de funcţie recursivă. Din punct de vedere matematic calculul lambda este consistent, deoarece nu conţine paradoxuri sau contradicţii.

Calculul lambda poate fi cu sau fără tip. Varianta fără tip a fost concepută iniţial de Curch. La aceasta s-au adăugat tipuri fiecărui termen, pentru a păstra compatibilitatea în timpul substituţiilor. Astfel, fiecare constantă se consideră a avea un tip de bază, iar fiecare funcţie (considerată o abstracţie lambda) are un tip compus. Tipurile compuse sunt notate cu α→β pentru funcţii definite pe tipul α cu valori de tipul β . Avantajul calculului lambda cu tip este posibilitatea de a reduce fiecare termen la forma normală. Calculul lambda cu tip este baza unor limbaje funcţionale (exemplu, Haskell, Standard ML, Caml).

34

3.1 Sintaxa calculului lambda

Un program funcţional trebuie interpretat ca o expresie care trebuie evaluată.

Expresia care alcătuieşte programul poate fi reductibilă la sub-expresii (eventual reductibile). Exemplu: expresia 5*6+8*3 se scrie în sintaxă funcţională (+ (* 5 6) (* 8 3)) sau ((+ ((*5)6) ((*8)3)), deoarece expresia iniţială se poate reduce la o sumă de alte două expresii, numite radicali.

Această modalitate de notare se numeşte forma prefixată. Scrierea în formatul prefixat a pornit de la ideea de a folosi combinarea mai multor expresii. O expresie poate fi scrisă prin combinarea mai multor aplicaţii (care pot fi diverse funcţii sau operatori). De exemplu dacă se consideră expresiile E1 şi E2, atunci (E1E2) este o expresie validă care arată că E1 se aplică argumentului E2.

Sintaxa unei expresii pentru forma prefixată este: (Kx)y, adică aplicaţia K se aplică lui x şi apoi lui y. Sintaxa pentru expresii este: <expresie>::= <constanta> | <variabila> | λ <variabila>.<expresie>| <expresie><expresie>

Primele trei reguli sunt folosite pentru a genera funcţii, iar a patra regulă descrie aplicarea unei funcţii asupra unui argument. λ semnifică o funcţie abstractă utilizată de obicei, pentru definirea unei funcţii de către utilizator. Variabila sau variabilele care urmează funcţia reprezintă argumentele funcţiei, definite ca parametri formali. Expresia după punct reprezintă corpul funcţiei. Locul punctului poate fi luat de către paranteze. Variabila din argumentul funcţiei se numeşte legată. Celelalte variabile, care apar în corpul funcţiei, dar nu sunt şi argumente se numesc variabile libere. Exemple:

1. funcţia cu un singur argument f(x)=x+5 poate fi reprezentată ca λ x.x+5 (sau varianta echivalentă λ y.y+5 în care s-a înlocuit numele argumentului formal). În forma prefixată funcţia de mai sus se scrie astfel: λ x.+ x 5. Funcţia f(2) se scrie prin următoarele expresii echivalente (λ x.x+5)2 sau (λ x.x 2)(λ x.x+5) sau 2+5

2. funcţia f(x)=x+z se scrie în sintaxa calculului lambda astfel (λ x. x + z) sau în forma prefixată (λ x. + x z). Variabila x este legată, iar variabila z este liberă.

3. funcţia f(x,y)=x+y se scrie în sintaxa calculului lambda astfel (λ x. λ y. x + y) sau în forma prefixată (λ x. λ y. + x y). Variabilele x şi y sunt legate. Pentru a scrie f(2,3)= 2+3 se pot utiliza expresiile echivalente: (λ x. λ y. x + y) 2 3 sau (λ x. x + 3) 2

Nu toate expresiile pot fi scrise asemănător cu exemplele de mai sus. Astfel, expresiile (λ x.x x) (λ x.x x) sau (λ x.x x x) (λ x.x x x) sunt dificil de calculat când se aplică prima funcţie la argumentul său. În astfel de cazuri, se plică logica combinaţională, în care expresia (λ x.x x) se numeşte combinator ω , iar ((λ x.x x) (λ x.x x)) este combinatorΩ .

35

3.2 Semantica operaţională

În funcţia (λ x. + x y), variabila x este legată de λ x, iar y este o variabilă liberă a cărei valoare trebuie cunoscută înainte de apelul funcţiei. Există mai multe reguli care specifică gradul de legare al unei variabile într-o expresie:

• x este liberă în expresia x; • x este liberă în λ y.E, dacă x şi y sunt variabile diferite şi dacă x este liberă în

expresia E; • x este liberă în (E F) dacă x este liberă şi în expresia E şi în expresia F.

În calculul lambda sunt o serie de operaţii de echivalenţă care se pot realiza asupra expresiilor:

• Alpha conversie – realizează redenumirea unei variabile legate. Astfel, în expresia λ x.E se poate scrie λ y.E[x|y] unde x este o variabilă legată în expresia labda E. Fiecare apariţie a variabilei x în E poate fi înlocuită cu y, dacă y nu este variabilă liberă în E şi nu este legată prin λ în expresia E. Astfel, prin alpha-conversie se defineşte o relaţie de echivalenţă. Exemple:λ x.x se poate converti în λ y.y; expresia λ x.(λ x.x)x poate fi convertită în λ y.(λ x.x)y.

• Beta conversie prin reducţie – dându-se o expresie (λ x.A)B se înlocuiesc toate apariţiile lui x în A prin B. Sintaxa este: (λ x.E)M este echivalent cu E[x|M] dacă toate apariţiile libere în M rămân libere şi în E[x|M]. Exemple: (λ x. + x 1) 4 este echivalentă cu (+ 4 1); (λ x.3)5 se reduce la 3.

• Eta conversie – exprimă ideea de extensibilitate în care, două funcţii sunt echivalente dacă şi numai dacă dau acelaşi rezultat pentru toate argumentele. Astfel, considerându-se funcţia F în care apare variabila legată x, expresia (λ x.F x) se poate scrie ca F. Două funcţii F şi G sunt extensional echivalente, dacă F a ==G a pentru orice expresie lambda a. Dacă se consideră a ca fiind variabila legată x în F atunci F x==G x care este echivalent cu λ x.F x==λ x.G x, astfel că F a fost eta convertit prin G. Exemplu: (λ x. + 1 x) este echivalent cu (+ 1).

• funcţii recursive – într-o funcţie Y se caută punctul fix H astfel încât expresia (Y H) să poată fi calculată ca H (Y H).

Scopul conversiilor în calculul lambda este de a transforma expresia în forma normală, care nu conţine alte sub-expresii care pot fi reduse astfel: λ x1 x2...xn . v E1...Em, unde v este o variabilă nelegată. Funcţiile exprimate prin calculul lambda pot fi privite din două puncte de vedere:

• Dinamic sau operaţional – funcţiile sunt o suită de operaţii; • Static sau denotaţional – funcţiile sunt considerate o mulţime finită de

asociaţii între argumente şi valorile corespunzătoare. Expresiile din calculul lambda sunt reprezentate intern în limbajele de programare cu ajutorul arborilor.

3.2.1 Reprezentări aritmetice în calculul lambda

În calculul lambda există mai multe posibilităţi de a defini numere naturale, dar modelul cel mai des utilizat este cu ajutorul întregilor Church astfel: 0=λ f. λ x.x

36

1=λ f. λ x.fx 2=λ f. λ x.f(fx) 3=λ f. λ x.f(f(fx)) Astfel, numărul n se reprezintă printr-o funcţie care are ca argument o funcţie f şi care returnează puterea a n-a lui f. Se definesc operaţiile aritmetice de bază astfel: PLUS m n = λm. λ n. λ f. λ x. m f (n f x) =m+n PLUS 1 n= λ n. λ f. λ x. f (n f x) =n+1 MULT m n = λm. λ n. λ f. λ x. m (n f) =m*n PRED n 1 = λ n. λ f. λ x. n (λ g. λ h.h(g f))(λ u.x)( λ u.u) =n-1 Exemplu: PLUS 1 2 = λ 1. λ 2. λ f. λ x.1 f (2 f x) =λ f. λ x.f(f(f x)) =3 Deoarece λ 1 şi λ 2 nu sunt considerate funcţii, deci nu sunt luate în considerare, iar (2 f x) înseamnă de două ori apelul lui f asupra lui x.

3.2.2 Reprezentări ale logicii predicatelor în calculul lambda

Pentru a defini valorile TRUE şi FALSE se foloseşte modelul Church astfel: TRUE= λ u. λ v.u FALSE= λ u. λ v.v Predicatele sunt considerate funcţii care întorc valori booleene. Un predicat des utilizat este ISZERO care returnează True dacă şi numai dacă argumentul său este zero: ISZERO=λ n.n(λ x.FALSE)TRUE Acest predicat permite definirea structurii condiţionale „if-then-else”.

3.2.3 Arbori cu sintaxă abstractă

În toate implementările bazate pe reducerea la un graf, expresia iniţială trebuie reprezentată în maşină printr-un arbore cu sintaxă abstractă. În aceşti arbori, fiecare nod conţine un operator sau o funcţie, care are ca operanzi valorile sub-expresiilor din nodurile-fii; frunzele conţin literali, variabile, valorile constantelor, funcţiile predefinite. Ca rădăcină are valoarea expresiei. Aplicarea unei funcţii f la un argument x este reprezentată astfel:

@ este un tag, o marcă, pentru a face referire la o aplicaţie. La modul general o lambda expresie se reprezintă prin arborele:

@

f x

@

f x

λ x

corp

37

Exemplu: expresiile (+ 4 2) şi (+ 3 (* 2 8)) se reprezintă prin următorii arbori cu sintaxă abstractă: Prin procesul de reducţie se realizează transformări succesive asupra arborilor cu sintaxă abstractă. Astfel, arborele devine un graf orientat aciclic. În cod maşină, fiecare nod poate fi reprezentat într-o celulă de memorie care conţine:

• Marcă – care memorează tipul de date (aplicaţie, număr, operator predefinit, lambda abstracţie, listă de celule, etc.).

• Cel puţin două câmpuri – numărul de câmpuri diferă în funcţie de implementare. Câmpurile pot memora adresa unei alte celule (pointează) sau valori atomice (date).

Tip de nod Nod abstract Celulă concretă Aplicaţie

Lambda abstracţie

Lista (x y)

Număr 45

Funcţie predefinită +

Exemplu: expresia (+ 4 2) se reprezintă astfel: cu specificare tipului de date de către programator sau fără specificarea explicită a tipului de date:

E

x

lambda

marcă câmp 1 câmp 2

@

+

2 @

4

@

+

2

@

3

@

@

8

*

@

f x

λ x

E

:

x y

@

f x

:

x y

N 45

P +

38

Unde @ reprezintă aplicaţia P este o funcţie predefinită N este un număr Observaţie: unele limbaje funcţionale sunt polimorfe (nu se specifică tipul de obiecte de către programator) şi corespondenţa cu un anumit tip de date se efectuează la compilare (static). În acest caz nu sunt necesare mărcile celulelor pentru a distinge obiectele sistem (nodurile, operatorii şi funcţiile predefinite, lambda abstracţiile) sau obiecte de tipuri diferite construite cu constructori diferiţi. În consecinţă, numărul de mărci nu este mare şi pot fi codificate pe un număr mic de biţi (de exemplu pe 8 biţi). Alte limbaje funcţionale au atribuire dinamică de tipuri de date (de exemplu la execuţie) în care fiecare operator predefinit verifică tipul argumentelor sale înainte de execuţie. Aceste limbaje au, de obicei, un număr fix de tipuri de date.

@

@

N 2

N 4

P +

@

@ + 4

2