Functional and Logic Programming (2023-2024)

1. Instructors

The Teams class access code is xf6vua7.

2. Contents


  1. Programming and programming languages. Imperative programming vs. declarative programming. Introduction

Logic Programming. The PROLOG programming language

  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. 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.
  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.
  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".
  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.
  6. Advanced issues on backtracking and efficiency in Prolog.
  7. Files management in Prolog. Elements of graphic.

Functional Programming. The LISP programming language

  1. 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.
  2. Symbols management. Other functions for lists' accessing. OBLIST and ALIST. Destructive functions. Comparisons. Other interesting functions. Examples.
  3. Definitional mechanisms. The EVAL form. Functional forms; the functions FUNCALL and APPLY. LAMBDA expressions, LABEL expressions. Generators, functional arguments. MAP functions. Iterative forms. Examples.
  4. Other elements in Lisp. Data structures. Macro-definitions. Optional arguments. Examples.

Other skills

  1. Other functional and logic languages. Versions of LISP. Versions of PROLOG.
  2. Examples of applications. Programs presented comparatively in Lisp, Prolog and in imperative languages. Specific applications.

3. Bibliography

  1. Gabriela Czibula, H.F. Pop, Elemente Avansate de Programare in Lisp si Prolog. Aplicatii in Inteligenta Artificiala, Editura Albastra, Cluj, 2012

Other references

  1. A. Field, Functional Programming, Addison Wesley, 1988
  2. C. Giumale et. al., LISP, 2 Volume, Editura Tehnica,1987
  3. C. J. Hogger, Introduction to Logic Programming, Academic Press, 1984
  4. B. Parv, A. Vancea, Fundamentele limbajelor de programare, Litografia Universitatii "Babes-Bolyai" ~Cluj-Napoca, 1992
  5. H. F. Pop, Gabriela Serban, Programare in Inteligenta Artificiala - Limbajele Lisp si Prolog, Editura Albastra, Cluj, 2003
  6. H. F. Pop, Programare Functionala si Logica, Litografia Universitatii "Babes-Bolyai", 1998
  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. P. H. Winston, Artificial Intelligence, Addison Wesley, 1984, 2nd edition
  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
  14. Documentatia produselor: Turbo Prolog 2.0, ~SWI-Prolog
  16. - Logic Programming

4. Course schedule

WeekLecture topic
1Introduction. Recursion
2The Prolog program
3Backtracking in Prolog
4Composed objects and functors. Controlling recursion
5Recursive data structures
6Efficient backtracking
7Basic elements of Lisp
8Defining user functions. Ramification of operations
The collector variable method. Examples
9 (*)Objects management. Other functions
Binary trees. Examples
10Evolved definitional mechanisms
11Examples of MAP functions
12Other elements of Lisp
13Written test paper (first half of groups)
14Written test paper (second half of groups)

5. Lab schedule

LabLab topic
11R1Recursive programming
12P1Prolog Lists
23P2Prolog Heterogeneous Lists
34P3Using backtracking in Prolog
 4 Practical test in Prolog (one hour)
45 (*)L1Recursive programming in Lisp (1)
56L2Recursive programming in Lisp (2)
67L3Using Map functions in Lisp
 7 Practical test in Lisp (one hour)

6. Lecture notes

Study resources are available on the UBB Sharepoint platform.

7. Software and resources for Prolog

We will use the SWI Prolog interpreter:


8. Software and resources for Lisp

We will use the Common Lisp dialect. The preferred Lisp interpreter is:


© Prof.dr. Horia F. Pop