Universitatea Babeş-Bolyai Cluj-Napoca
Facultatea de Matematică şi Informatică
Ciclul de studii: Licenţă
Domeniul: Calculatoare şi tehnologia informaţiei
Programul de studii: Ingineria informatiei - in limba engleza
Limba de predare: Engleză

SYLLABUS

I. General data
Code	Subject	
MID0005	Functional and Logic Programming	

Semester	Hours: C+S+L	Category	Status	
3	2+1+1	specialty	compulsory	

II. Full status faculty members
Name and	Scientific	Didactic	Chair	Type of activity	
surname	title	title		C	S	L	
POP Horia Florin	Ph.D.	Prof.	Programming  Languages and Methods	*			
MIHAILA Cristina		Assist.	Programming  Languages and Methods			*	

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
1.	Serban G., Pop H. F., Elemente avansate de programare in Lisp si Prolog. Aplicatii in Inteligenta Artificiala, Editura Albastra, Cluj-Napoca, 2006 (library)
2.	Pop H. F., Serban G., Programare in Inteligenta Artificiala - Lisp si Prolog, Editura Albastra, Cluj-Napoca, 2003 (library)
3.	* * *, Products documentations: Gold Common Lisp 1.01, 4.30, XLisp, Free Lisp, GNU CLisp. 
4.	* * *, Products documentations: Turbo Prolog 2.0, Logic Explorer, Sicstus Prolog, GNU Prolog. 
5.	http://www.ifcomputer.com/PrologCourse, Lecture on Prolog 
6.	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. The importance of the functional programming as a new programming methodology. History and presentation of Lisp. [1, ch. 1, 2]
Week 2: 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 3: 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 4: Symbols management. Other functions for lists' accessing. OBLIST and ALIST. Destructive functions. Comparisons. Other interesting functions. Examples. [1, ch. 3]
Week 5: Definitional mechanisms. The EVAL form. Functional forms; the functions FUNCALL and APPLY. LAMBDA expressions, LABEL expressions. 
Week 6: Generators, functional arguments. MAP functions. Iterative forms. Examples. [1, ch. 6, 7]
Week 7: Other elements in Lisp. Data structures. Macro-definitions. Optional arguments. Examples. [1, ch. 8-10]
Week 8: 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 9: 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 10: 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 11: 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 12: 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 13: Advanced issues on backtracking and efficiency in Prolog [5]. Files management in Prolog. Elements of graphics. [1, ch. 18]
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: Lists operations in Pascal or C/C++ using recursive programming
Lab 3: Recursive programming in Lisp
Lab 5: Using MAP functions in Lisp. Iterative programming in Lisp
Lab 7: Practical test in Lisp
Lab 9: Lists in Prolog
Lab 11: Trees in Prolog. Lists management in Prolog. Backtracking in Prolog
Lab 13: Practical test in Prolog
Labs 2, 4, 6, 8, 10, 12, 14: Software project on declarative programming	

VII. Didactic methods used
Expositions: description, explanation, class lectures, dialog-based lectures, lectures with demonstrations, introductive lectures, current lectures, synthesis lectures. 
Conversations: debate, dialog, introductive conversations, conversations for knowledge consolidation, conversations to systematize and synthesize knowledge 
Use of problems: use of problem questions, problems and problem situations. 
Discovery: directed and independent rediscovery, creative discovery, inductive discovery, deductive discovery, discovery by documenting, experimental discovery. 
Other methods: case study; cooperation, simulation, brainstorming, individual study, exercise, homework study.	

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 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.
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/flp 	

IX. Additional references
1.	FIELD A., Functional Programming, Addison Wesley, New York, 1988. (library) 
2.	GIUMALE G., et. al., LISP, 2 Volume, Editura Tehnica, Bucuresti, 1987. (library)
5.	PARV B., Alexandru Vancea, Fundamentele limbajelor de programare, Litografia Universitatii Babes-Bolyai Cluj-Napoca, 1992. (library)
6.	WINSTON P.H., Lisp, Addison Wesley, New York, 2nd edition, 1984. (library)
7.	WINSTON P.H., Artificial Intelligence, Addison Wesley, New York, 2nd edition, 1984. (library)
8.	* * *, http://www.swi-prolog.org/
9.	* * *, http://www.dreamsongs.com/CLOS.html
10.	* * *, http://www.trinc-prolog.com/
11.	* * *, http://www.aiai.ed.ac.uk/~jeff/clos-guide.html	

	Dean,							Chair head,

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