# 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 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. Several sessions will illustrate the efficiency of this approach to solve some practical instances of various NP-complete problems.

The practical sessions will use 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 TDs are sufficient to prepare the examination.
- The following links can also be consulted:
- SWI-Prolog manual
- Lecture notes
- F. Fages. Programmation Logique par Contraintes. Ellipses, Paris, 1996.

## Schedule 2023-2024 (see also Moodle CSE 307 2023-2024)

- C1 20 Oct.
- Introduction to Datalog: relational databases in Horn clause logic
- TD1 23 Oct.
- Relational databases in Datalog
- C2 27 Oct.
- From Datalog to Prolog: equality constraints in first-order logic term structure
- TD2 6 Nov.
- Symbolic differentiation and list processing in Prolog
- C3 13 Nov.
- From Prolog to CLP(R) with constraints over the real numbers
- TD3 17 Nov.
- Production planning in CLP(R)
- C4 20 Nov.
- CLP(Z): constraint propagation with integer domain filtering, reified constraints
- TD4 24 Nov.
- Programming a constraint solver and solving disjunctive scheduling problems
- C5 27 Nov..
- Search heurisitcs, meta-programming and the Warren Abstract Machine (WAM).
- TD5 1 Dec.
- Theorem proving in Prolog
- C6 4 Dec.
- Formal semantics of CLP(X) languages and abstract interpretations
- TD6 8 Dec.
- Natural language processing in concurrent Prolog
- Exam mid Dec.
- Final written examination

## Previous examinations

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