Babes-Bolyai University of Cluj-Napoca
Faculty of Mathematics and Computer Science
Study Cycle: Graduate

SUBJECT

Code
Subject
MID0005 Functional and Logic Programming
Section
Semester
Hours: C+S+L
Category
Type
Computer Science
3
2+0+1
speciality
compulsory
Information engineering
3
2+0+1
speciality
compulsory
Teaching Staff in Charge
Prof. POP Horia Florin, Ph.D.,  hfpopcs.ubbcluj.ro
Assoc.Prof. CZIBULA Gabriela, Ph.D.,  gabiscs.ubbcluj.ro
Assoc.Prof. CSATO Lehel, Ph.D.,  csatolcs.ubbcluj.ro
Lect. EGRI Edith,  egrieditcs.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. SERBAN G., POP H.F., Elemente avansate de programare in Lisp si Prolog. Aplicatii in Inteligenta Artificiala, Editura Albastra, Cluj-Napoca, 2006
2. FIELD A., Functional Programming, Addison Wesley, New York, 1988.
3. GIUMALE G., et. al., LISP, 2 Volume, Editura Tehnica, Bucuresti, 1987.
4. HOGER C.J., Introduction to Logic Programming, Academic Press, New York, 1984.
5. KLEENE S.E., Object Oriented Programming in Common Lisp, Addison Wesley, New York, 1989.
6. PARV B., VANCEA Al., Fundamentele limbajelor de programare, Litografia Universitatii Babes-Bolyai Cluj-Napoca, 1992.
7. REEDE C., Elements of Functional Programming, Addison Wesley, New York, 1989.
8. STREINU I., Lisp, Editura Stiintifica si Enciclopedica, Bucuresti, 1986.
9. WALKER A., et. al., Knowledge Systems and Prolog. A Logical Approach to Expert Systems and Natural Processing, Addison Wesley, New York, 1987.
10. WINSTON P.H., Lisp, Addison Wesley, New York, 2nd edition, 1984.
11. WINSTON P.H., Artificial Intelligence, Addison Wesley, New York, 2nd edition, 1984.
12. FLACH P., 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.
15. http://www.ifcomputer.com/PrologCourse, Lecture on Prolog
16. http://www.lpa.co.uk, Logic Programming
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 p); written paper on Logic Programming (30 p), laboratory activity, papers and programs (20 p) (10 lab problems; lateness in handing the laboratory assignments; missing laboratory activities; papers and programs) practical test in Lisp and Prolog (20 p), project (20 p). The grade is computed from a top 100 p. The final grade is awarded only if at least 12 points per written paper are obtained, for each written paper, and at least five out of ten lab problems are submitted; otherwise, the class is failed.

The official webpage of the course taught in English is http://www.cs.ubbcluj.ro/~hfpop/pfl . The official webpage of the course taught in Romanian is http://www.cs.ubbcluj.ro/~gabis/plf .
Links: Syllabus for all subjects
Romanian version for this subject
Rtf format for this subject