"Babes-Bolyai" University of Cluj-Napoca
Faculty of Mathematics and Computer Science

Functional programming and logic programming
Code
Semes-
ter
Hours: C+S+L
Credits
Type
Section
MI035
4
2+0+1
5
compulsory
Informatică
MI035
6
2+0+1
4
optional
Matematică-Informatică
Teaching Staff in Charge
Lect. SERBAN Gabriela, gabis@cs.ubbcluj.ro
Assoc.Prof. POP Horia Florin, Ph.D., hfpop@cs.ubbcluj.ro
Lect. SOOS Anna, Ph.D., asoos@math.ubbcluj.ro
Aims
1. To get the student acustomed with new programming paradigms (functional and logic programming)
2. To introduce a programming language for each of these paradigms (Common Lisp and Prolog)
3. To induce the idea of using these programming paradigmsbased on the applications' mecessities
4. To assure the necessary base for aproaching certainadvanced courses
Content
1. Functional Programming. The LISP programming language
1.1. Programming and programming languages. Imperative programming vs. declarative programming. Introduction. The importance of the functional programming as a new programming methodology. History and presentation of LISP.
1.2. Basic elements in Lisp. Dynamic data structures. Syntactic and semantic rules. Functions' classification in Lisp. Primitive functions in Lisp. Basic predicates in Lisp. Predicates for lists; for numbers. Logic and arithmetic functions. Defining user functions. The conditional form. The collecting variable method. Examples.
1.3. Symbols' managing. Other functions for lists' accessing. OBLIST and ALIST. Destructive functions. Comparisons. Other interesting functions. Examples.
1.4. Definitional mechanisms. The EVAL form. Functional forms; the functions FUNCALL and APPLY. LAMBDA expressions, LABEL expressions. Generators, functional arguments. MAP functions. Iterative forms. Examples.
1.5. Other elements in Lisp. Data structures. Macro-definitions. Optional arguments. Examples.

2. Logic Programming. The PROLOG programming language.
2.1. 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.
2.2. 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.
2.3. 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.
2.4. 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".
2.5. Recursive data structures. Trees as data structures. Creating and transversing a tree. Search trees. The internal database of Prolog. The "database" section. Declaration of the internal database. Predicates concerning operations with the internal database.
2.6 Backtracking in Prolog.
2.7. Files management in Prolog. Elements of graphic.

3. Other topics
3.1. Other functional and logic languages. Versions of LISP. Versions of PROLOG.
3.2. Examples of applications. Programs presented comparatively in Lisp, Prolog and in imperative languages. Specific applications.
References
1. H.F.Pop, G. Serban, Programare in Inteligenta Artificiala - Lisp si Prolog, Editura Albastra, Cluj-Napoca, 2003
2. A. Field, Functional Programming, Addison Wesley, 1988.
3. C. Giumale et. al., LISP, 2 Volume, Editura Tehnica, 1987.
4. C. J. Hogger, Introduction to Logic Programming, Academic Press, 1984.
5. S. E. Kleene, Object Oriented Programming in Common Lisp, Addison Wesley, 1989.
6. B. Parv, Alexandru Vancea, Fundamentele limbajelor de programare, Litografia Universitatii Babes-Bolyai Cluj-Napoca, 1992.
7. C. Reede, Elements of Functional Programming, Addison Wesley, 1989.
8. I. Streinu, LISP, Editura Stiintifica si Enciclopedica, 1986.
9. A. Walker et. al., Knowledge Systems and Prolog. A Logical Approach to Expert Systems and Natural Processing, Addison Wesley, 1987.
10. P. H. Winston, Lisp, Addison Wesley, 1984, 2nd edition.
11. A. Walker et. al., Knowledge Systems and Prolog. A Logical Approach to Expert Systems and Natural Processing, Addison Wesley, 1987
12. P. Flach, Simply Logical Intelligent reasoning by Example, John Wiley & Sons, Chichester, England, 1994
13. Documentatia produselor: Gold Common Lisp 1.01 si 4.30,XLisp, Free Lisp.
14. Documentatia produselor: Turbo Prolog 2.0, Logic Explorer, Sicstus Prolog.
Assessment
Each student has to prove that (s)he aquired 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 connexions and to use the knowledge in solving different problems. The final grade will be based on the following components: written paper(70%); laboratory activity(30%) (lateness in handing the laboratory assignments; missing laboratory activities).