CSE 307: Relational Programming ( CSE307 Moodle )
Bachelor of Science, Ecole Polytechnique
François Fages and Mathieu Hemery
This course presents the relational programming paradigm, also called Constraint Logic Programming (CLP), from its logical foundations for programming with mathematical variables and relations in a declarative fashion, to its relevance to symbolic artificial intelligence with various applications in deductive databases, knowledge representation, symbolic computation, combinatorial optimisation, automated deduction and natural language processing.
From the early days of Logic Programming based on Horn clause logic formulae, towards the holy grail of declarative programming by simply modelling the problem at hand by mathematical variables and constraints, the students will learn how to use a recent dialect of Prolog with constraints over the data structures of first-order logic terms, integers and real numbers. The balance between declarative programming and efficiency will lead us into looking at how things work internally both for constraint solving and for clause resolution in Prolog compilers based on the Warren Abstract Machine. Several sessions will illustrate the efficiency of this approach to solving practical instances of real-life NP-hard problems.
Each lecture of 2h is followed by practicval work session of 2h for illustrating the taught concepts and manipulating the associated tools.
The logic programming language SWI-Prolog with its constraint solving libraries (clpfd.pl, clpr.pl) and a constraint-based modeling library (modeling.pl inspired by the MiniZinc modeling language)
will be used as a unifying framework for both the mathematical modeling of decision making problems and the programming of constraint solvers, and for showing the practical
complexity of different models and different solvers on some NP hard problems.
Grades:
- 50% mean of your best 5 over 6 TPs
- 50% final written examination.
Bibliography:
- mini manual of SWI-Prolog including pointers to pack modeling
- The slides of the lectures and solutions to TDs are sufficient to prepare the examination.
- Yet the following lecture notes can be consulted, as well as the Handbook of Constraint Programming for particular questions on the subject.
Schedule 2024-2025
- C1 4 Nov.
- Introduction to Prolog: deductive databases in first-order logic, term unification, symbolic computation
- TD1 8 Nov.
- deductive databases, symbolic differentiation, constraints over the real numbers
- C2 14 Nov.
- List processing in Prolog, reversibility
- TD2 15 Nov.
- Path finding in a map
- C3 18 Nov.
- From Prolog to CLP(R): linear constraints over the real numbers using Fourier's and Simplex algorithms
- TD3 22 Nov.
- production planning and cost benefit analysis in CLP(R)
- C4 25 Nov.
- Constraint propagation with domain filtering algorithms in CLP(Z)
- TD4 29 Nov.
- Programming a constraint solver over the integers and solving disjunctive scheduling problems
- C5 2 Dec.
- Meta-interpretation, search procedures, computational complexity, search heuristics.
- TD5 6 Dec.
- Heuristics for the N-queens. Meta-interpreter for complete search and theorem proving in group theory
- C6 9 Dec.
- Formal semantics of CLP(X) languages and abstract interpretation
- TD6 10 Dec.
- Natural language processing in concurrent Prolog for querying a database
- 20 Dec.
- Final written examination 2h
Previous examinations
2024 written examination with solutions
2023 written examination with solutions
2022 written examination with solutions
2021 written examination with solutions
2020 online examination
2019 written examination with solutions
Ceremony 17 July 2020: Good bye video