Universitatea Babeş-Bolyai Cluj-Napoca
Facultatea de Matematică şi Informatică
Ciclul de studii: Licenţă
Domeniul: Informatică
Programul de studii: Informatică - în limba engleză
Limba de predare: Engleză

SYLLABUS

I. General data
Code	Subject	
MID0005	Functional and Logic Programming	

Semester	Hours: C+S+L+P	Category	Status	
3	2+0+1+0	speciality	compulsory	

II. Full status faculty members
Name and	Scientific	Didactic	Department	Type of activity	
surname	title	title		C	S	L	
POP Horia Florin	Ph.D.	Prof.	Computer Science	*			

Associated faculty members
Name and	Scientific	Institution	Type of	Type of activity	
surname	title		position	C	S	L	

III. Course objectives
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	

IV. Course contents
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 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.
  2.6 Backtracking in Prolog. 
  2.7. Files management in Prolog. Elements of graphics.

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.	

V. Bibliography
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	

VI. Thematic of didactic activities per weeks
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	

VII. Didactic methods used

VIII. 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 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 	

IX. Additional references

	Dean,							Chair head,

	Date,							Course responsible,
	October 1, 2011					Prof. POP Horia Florin, Ph.D.