CSE 307: Constraint Logic Programming ( CSE307 Moodle )
Bachelor of Science, Ecole Polytechnique
François Fages and Mathieu Hemery
This course presents the paradigm of Constraint Logic Programming, from its logical foundations for programming with mathematical relations in a declarative fashion, to multiple significant applications in relational 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, finite domains, integers and rational 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.
The course illustrates this approach with TP (from Theory to Practice) sessions using a modern Prolog system called SWI Prolog. The students are invited to install SWI Prolog on their own laptop before the first session.
Bibliography:
- The slides of the lectures given below plus the TPs will be sufficient.
- The following links go a bit beyond what will be taught:
- Lecture notes
- F. Fages. Programmation Logique par Contraintes. Ellipses, Paris, 1996.
- SWI-Prolog manual
Schedule 2021-2022
- C1 5 Nov.
- Introduction to Datalog: relational databases in Horn clause logic
- TP1 8 Nov.
- Relational databases in Datalog Δ
- C2 12 Nov.
- From Datalog to Prolog: equality constraints in first-order logic term structure
- TP2 15 Nov.
- Symbolic computation in Prolog Δ
- C3 19 Nov.
- From Prolog to CLP: constraints in a fixed mathematical structure, CLP(R)
- TP3 22Nov.
- Omnidirectional spreadsheet in CLP(R) Δ
- C4 26 Nov.
- Constraint propagation with domain filtering algorithms: CLP(FD)
- TP4 29 Nov.
- Solving Sudoku and job-shop scheduling problems in CLP(FD) Δ
- C5 3 Dec.
- Reified constraints, meta-programming and the Warren Abstract Machine (WAM).
- TP5 6 Dec.
- Solving traveling salesman problems Δ
- C6 8 Dec.
- Fixpoint semantics of CLP(X)
- TP6 10 Dec.
- Natural language processing in concurrent Prolog Δ
- Exam 14 Dec.
- Final witten examination
2021 written examination with solutions
2020 online examination
2019 writtenexamination with solutions
- Ceremony 17 July 2020
- Good bye video