Universitatea Babeş-Bolyai Cluj-Napoca
Facultatea de Matematică şi Informatică
Ciclul de studii: Licenţă
FISA DISCIPLINEI
| MLR5009 | Programare logică şi funcţională |
| Titularii de disciplina |
Prof. Dr. POP Horia Florin, hfpop cs.ubbcluj.roProf. Dr. CZIBULA Gabriela, gabis cs.ubbcluj.roConf. Dr. CSATO Lehel, csatol cs.ubbcluj.roLect. Dr. EGRI Edith, egriedit cs.ubbcluj.ro |
| Obiective |
|
1. Sa deprinda studentul cu noi paradigme de programare (programarea functionala si programarea logica) 2. Sa introduca cate un limbaj de programare pentru fiecare din aceste paradigme (Common Lisp si Prolog) 3. Sa induca ideea utilizarii acestor paradigme in functie de necesitatile aplicatiilor 4. Sa asigure baza necesara urmaririi unor cursuri avansate |
| Célkitűzések |
|
1. Új programozási paradigmák elsajátítása; 2. A programozási paradigmákhoz tartozó programozási nyelvek bemutatása: A logikai programozást a Prolog programozási nyelvvel; A funkcionális programozást a Clean programozási nyelvvel. 3. Az elsajátított programozási nyelvek és módszerek használatának körülményei 4. A programozási technikák elemzése, érdekes feladatok programozása. |
| Aims |
|
To get the student accustomed with new programming paradigms (functional and logic programming) To introduce a programming language for each of these paradigms (Common Lisp and Prolog) To induce the idea of using these programming paradigms based on the applications' necessities To assure the necessary base for approaching certain advanced courses |
| Continutul |
|
Programare Logica. Limbajul PROLOG Elemente fundamentale ale limbajului Prolog. Fapte si reguli Prolog. Intrebari. Strategia de control în Prolog. Variabile si propozitii compuse. Variabile anonime. Reguli de definire a potrivirilor. Model de flux. Sectiunile unui program Prolog. Exemple. [1, ch. 11] (1 curs – S1 + 2 laboratoare – S1, S3) Programul Prolog. Domenii predefinite. Întrebari interne si externe. Predicate cu aritate multipla. Simbolul IF (Prolog) si instructiunea IF (alte limbaje). Directive de compilare. Expresii aritmetice si comparatii. Operatii de intrare / iesire. Siruri de caractere. [1, ch. 12, 13] (1 curs – S2) Backtracking. Controlarea backtracking-ului. Predicatele fail si ! (cut). Utilizarea lui !. Tipuri de taieturi. Predicatul “not”. Liste Prolog. Recursivitate. Exemple de tratare a backtracking-ului. Gasirea tuturor solutiilor în acelasi timp. Exemple de predicate Prolog. Predicate nedeterministe. [1, ch. 14, 15] (1 curs – S3 + 1 laborator – S5) Obiecte compuse si functori. Unificarea obiectelor compuse. Argumente de tipuri multiple; liste eterogene. Compararea obiectelor compuse. Backtracking cu ciclari. Exemple de proceduri recursive. Cadrul stivei. Optimizarea prin recursivitate de coada. Utilizarea taieturii pentru pastrarea recursivitatii de coada. [1, ch. 16] (1 curs – S5) Structuri de date recursive. Arborii ca structuri de date. Construirea si traversarea unui arbore. Arbori de cautare. Baza de date interna a sistemului Prolog. Sectiunea database. Declararea bazei de date interne. Predicate relativ la operatii cu baza de date interna.. [1, ch. 16, 17] (1 curs – S6) Programare Functionala. Limbajul LISP Programare si limbaje de programare. Programare imperativa vs. programare declarativa. Introducere. Importanta programarii functionale ca noua metodologie de programare. Istoric si prezentare a limbajului LISP. [1, ch. 1, 2] (1 curs – S8 + 1 laborator – S9) Elemente de baza Lisp. Structuri dinamice de date. Reguli sintactice si semantice. Clasificarea functiilor Lisp. Functii primitive în Lisp. Predicate de baza în Lisp. Predicate pentru liste; pentru numere. Functii logice si aritmetice. Definirea functiilor utilizator. Ramificarea prelucrarilor. Metoda variabilei colectoare. Exemple. [1, ch. 3, 4] (1 curs – S9 + 1 laborator – S11) Gestiunea simbolurilor. Alte functii de acces la liste. OBLIST si ALIST. Functii cu caracter destructiv. Comparatii. Alte functii interesante. Exemple. [1, ch. 3] (2 cursuri – S10, S11) Mecanisme definitionale evoluate Forma EVAL. Forme functionale; functiile FUNCALL si APPLY. Expresii LAMBDA. Expresii LABEL. Generatori, argumente functionale. Functii MAP. Forme iterative. Exemple. [1, ch. 6, 7] (2 cursuri – S12, S13 + 1 laborator – S13) Alte elemente ale limbajului Lisp. Structuri de date. Macrodefinitii. Argumente optionale. Exemple. [1, ch. 8, 10] (1 curs – S7) Examene scrise Curs 7 – Examen scris Prolog Curs 14 – examen scris Lisp Programarea laboratoarelor Lab 1: Recursivitate Lab 2: Liste in Prolog Lab 3: Arbori in Prolog. Gestiunea listelor in Prolog. Lab 4: Backtracking in Prolog Lab 4 – 1 ora: Proba practica Prolog Lab 5: Programare recursive in Lisp Lab 6: Folosirea functiilor MAP. Lab 7: Programare iterative in Lisp Lab 7 – 1 ora: Proba practica Lisp |
| Tartalom |
|
Logikai programozás és a Prolog programozási nyelv. Imperatív és deklaratív nyelvek, a programozási módszertan (1. hét) Logikai programozási alapfogalmak. Tények a Prolog nyelvben, szabályok, tudásbázis létrehozása. (2. hét) A cél-kifejezés a Prolog-ban, a kiértékelés menete. Változók és összetett predikátumok. (3. hét) Mintaillesztés szabályai, aritmetikai muveletek, logikai muveletek, egy Prolog program. (4. hét) Backtracking, a „!” parancs. Listák Prolog-ban. (5. hét) Rekurzív adatstruktúrák Prolog-ban. (6 hét) Funkcionális programozás és a Clean programozási nyelv. A funkcionális programozási paradigma, A Clean programnyelv bemutatása (7. hét) A Clean függvények, a programnyelv elemei, a rekurzió. (8. hét) Clean listakezelés, a lista-konstruktorok, listák ábrázolása.. (9. hét) Operátorok, függvények aritása, parciális paraméterezés, lambda-függvények, függvénydefiniciók (10. hét) Abstrakt adattípusok, konstruktorok, (11. hét) A lambda-kalkulus és a matematikai programmodell A lamdba-kalkulus alapfogalmai (12. hét) Clean-példák a lambda kalkulus implementációjára (13. hét) Ismétlés és fontos paradigmák felsorolása (14. hét) |
| Content |
|
Schedule of courses Week 1: Programming and programming languages. Imperative programming vs. declarative programming. Introduction. Introduction of logic programming. [1, ch. 1, 2] Week 2: Basic elements of Prolog. Facts and rules in Prolog. Goals. The control strategy in Prolog. Variables and composed propositions. Anonymous variables. Rules for matching. The flux model. Sections of a Prolog program. Examples. [1, ch. 11] Week 3: The Prolog program. Predefined domains. Internal and external goals. Multiple arity predicates. The IF symbol (Prolog) and the IF instruction (other languages). Compiler directives. Arithmetic expressions and comparisons. Input/output operations. Strings. [1, ch. 12, 13] Week 4: Backtracking. The backtracking control. The "fail" and "!"(cut) predicates. Using the "!" predicate. Type of cuts. The "not" predicate. Lists in Prolog. Recursion. Examples for backtracking in Prolog. Finding all solutions in the same time. Examples of predicates in Prolog. Non-deterministic predicates. [1, ch. 14, 15] Week 5: Composed objects and functors. Unifying composed objects. Arguments of multiple types; heterogeneous lists. Comparisons for composed objects. Backtracking with cycles. Examples of recursive procedures. The stack frame. Optimization using the "tail recursion". Using the "cut" predicate in order to keep the "tail recursion". [1, ch. 16] Week 6: Recursive data structures. Trees as data structures. Creating and traversing a tree. Search trees. The internal database of Prolog. The "database" section. Declaration of the internal database. Predicates concerning operations with the internal database. [1, ch. 16, 17] Week 7: Advanced issues on backtracking and efficiency in Prolog [5]. Files management in Prolog. Elements of graphics. [1, ch. 18] Week 8: Basic elements in Lisp. Dynamic data structures. Syntactic and semantic rules. Functions' classification in Lisp. Primitive functions in Lisp. Basic predicates in Lisp. [1, ch. 3, 4] Week 9: Predicates for lists; for numbers. Logic and arithmetic functions. Defining user functions. The conditional form. The collecting variable method. Examples. [1, ch. 3, 4] Week 10: Symbols management. Other functions for lists' accessing. OBLIST and ALIST. Destructive functions. Comparisons. Other interesting functions. Examples. [1, ch. 3] Week 11: Definitional mechanisms. The EVAL form. Functional forms; the functions FUNCALL and APPLY. LAMBDA expressions, LABEL expressions. Week 12: Generators, functional arguments. MAP functions. Iterative forms. Examples. [1, ch. 6, 7] Week 13: Other elements in Lisp. Data structures. Macro-definitions. Optional arguments. Examples. [1, ch. 8-10] Week 14: Other functional and logic languages. Versions of Lisp. Versions of Prolog [1, ch. 19, 20]. Examples of applications. Programs presented comparatively in Lisp, Prolog and in imperative languages. Specific applications [5], [6] Schedule of labs Lab 1: Recursive algorithms in Pseudocode Lab 2: Lists in Prolog Lab 3: Trees in Prolog. Lists management in Prolog. Backtracking in Prolog Lab 4: Practical test in Prolog Lab 5: Recursive programming in Lisp Lab 6: Using MAP functions in Lisp. Iterative programming in Lisp Lab 7: Practical test in Lisp |
| Bibliografie |
|
SERBAN G., POP H.F., Elemente avansate de programare in Lisp si Prolog. Aplicatii in Inteligenta Artificiala, Editura Albastra, Cluj-Napoca, 2004 POP H.F., SERBAN G., Programare in Inteligenta Artificiala - Lisp si Prolog, Editura Albastra, Cluj-Napoca, 2003 * * *, Documentatia produselor: Gold Common Lisp 1.01 si 4.30, XLisp, Free Lisp. * * *, Documentatia produselor: Turbo Prolog 2.0, Logic Explorer, Sicstus Prolog. http://www.ifcomputer.com/PrologCourse, Lecture on Prolog http://www.lpa.co.uk, Logic Programming |
| Evaluare |
| Fiecare student trebuie sa demonstreze ca a atins un nivel acceptabil de cunoastere si intelegere a domeniului, ca este capabil sa exprime cunostintele intr-o forma coerenta, ca are capacitatea de a stabili anumite conexiuni si de a utiliza cunostintele in rezolvarea unor probleme. Nota finala va fi compusa luand in calcul urmatoarele componente: lucrarea scrisa Lisp (30%); lucrarea scrisa Prolog (30%); nota laborator (20%); doua teste practice de laborator in timpul semestrului (10%+10%) ; proiect in domeniul programarii declarative (20%). In notarea activitatii de laborator se vor penaliza intarzierile in predarea lucrarilor si absentele nemotivate. Pentru promovare, este necesara predarea a cel putin 5 teme de laborator si obtinerea notei minime 4 la ambele lucrari scrise. Mai multe detalii legate de evaluarea activitatii se gasesc la http://www.cs.ubbcluj.ro/~gabis/Req_PLF.htm. |
| Felmérés |
|
A félév-végi jegy írásbeli vizsga eredménye. A vizsgán való részvételhez szükséges a labor- illetve gyakorlati órákon kiadott feladatoknak a leadása, ezek a vizsgapontok 40%-át jelentik, az írásbeli a maradék 60%-ot. A félév során lehetoség van szemináriumokon bemutatót tartani. Ezen diákok mentesülnek a vizsga alól, de a laborfeladatokat nekik is be kell mutatniuk. |
| Assessment |
|
Each student has to prove that (s)he acquired an acceptable level of knowledge and understanding of the subject, that (s)he is capable of stating these knowledge in a coherent form, that (s)he has the ability to establish certain connections and to use the knowledge in solving different problems. The final grade will be based on the following components: written paper on Functional Programming (30%); written paper on Logic Programming (30%), laboratory activity, papers and programs (20%) (10 lab problems; lateness in handing the laboratory assignments; missing laboratory activities; papers and programs) practical test in Lisp and Prolog (20%). The grade is computed from a top 100 p. The final grade is awarded only if at least a grade of 4 per written paper is obtained, for each written paper, and at least five out of ten lab problems are submitted; otherwise, the class is failed. Web site of course in Romanian: http://www.cs.ubbcluj.ro/~gabis/plf Web site of course in English: http://www.cs.ubbcluj.ro/~hfpop/pfl |