Programmation logique (Prolog)

Une ligne de train relie Rennes à Laval, une autre Laval au Mans, une troisième Le Mans à Paris. Peut-on aller de Rennes à Paris ? En Python, vous écririez un parcours de graphe avec une pile, une boucle et un ensemble de sommets visités. En Prolog, vous écrivez deux lignes : « il existe un chemin de X à Y s’il y a une liaison directe, ou s’il y a une liaison de X vers Z et un chemin de Z à Y ». Puis vous posez la question, et c’est le moteur qui cherche la réponse.

C’est l’idée de la programmation logique : vous décrivez ce qui est vrai, et non comment le calculer. Ce cours vous apprend à écrire de tels programmes, mais surtout à comprendre ce que fait réellement le moteur, car c’est là que se cachent les boucles infinies, les réponses en double et les résultats surprenants. Vous verrez enfin que ces idées n’ont rien d’exotique : elles vivent aujourd’hui dans les requêtes SQL récursives, les moteurs Datalog et les graphes de connaissances.

Objectifs pédagogiques

À la fin de ce cours, vous serez capable de :

Modéliser un petit domaine sous forme de faits et de règles, et l’interroger comme une base de données.
Dérouler à la main une unification, une résolution et un arbre de recherche avec retour arrière.
Écrire des prédicats récursifs corrects sur des nombres et des listes, en choisissant l’ordre des règles et des buts pour qu’ils terminent.
Utiliser l’arithmétique, les accumulateurs et les prédicats prédéfinis (findall, setof, sort) à bon escient.
Contrôler l’exécution avec la coupure et la négation par l’échec, en distinguant coupures vertes et rouges.
Relier Prolog à Datalog, au SQL récursif et à l’intelligence artificielle symbolique.

Prérequis

Une première pratique de la programmation (variables, fonctions, récursivité), dans n’importe quel langage.
Quelques notions de logique : et, ou, non, implication.
Pour le dernier chapitre, les bases de SQL (sélection, jointure). Le cours Graphes et algorithmes éclaire aussi les chapitres sur la récursivité.

Le plan du cours

Partie 1 · Penser en logique

Découvrez la programmation logique : le style déclaratif, les termes, les faits et les questions.
Écrivez des règles et interrogez une base : règles, conjonction et disjonction, algèbre relationnelle, termes construits.
Comprenez comment Prolog cherche : unification, résolution SLD, arbre de recherche, retour arrière et trace.

Partie 2 · Programmer par récursivité

Définissez des relations récursives : fermeture transitive, ordre des règles et des buts, modes d’utilisation.
Calculez avec les nombres : entiers de Peano, prédicat is, comparaisons et opérateurs.
Manipulez des listes : appartenance, concaténation, longueur, accumulateurs et construction de listes.

Partie 3 · Contrôler et relier

Maîtrisez la coupure : sémantique du !, coupures vertes et rouges, si-alors-sinon.
Raisonnez par l’échec et collectez les solutions : négation par l’échec, monde clos, findall, bagof, setof, entrées-sorties.
Retrouvez la logique en data et en IA : Datalog, SQL récursif, graphes de connaissances et IA symbolique.

Chaque chapitre se termine par un résumé et des exercices corrigés, de difficulté croissante.

D’où vient ce cours

Ce cours reprend l’enseignement de programmation logique suivi en 3e année du cycle ingénieur de l’INSA Rennes, en spécialité informatique (premier semestre), avec des travaux pratiques et un devoir surveillé sous ECLiPSe, un système Prolog. Il s’appuie sur les notes de cours annotées des séances 2 à 5 (bases de données logiques, récursivité, arithmétique, listes, coupure et négation) et sur un sujet de devoir surveillé, dont s’inspirent plusieurs exercices, entièrement réécrits.

Les notes de la première séance n’étaient pas exploitables : les définitions de base (termes, unification, résolution SLD) ont donc été rédigées à partir des présentations standard du langage, en cohérence avec ce que les séances suivantes rappellent. Ont aussi été complétés à partir de sources standard : la syntaxe ( P -> Q ; R ), le prédicat \+, les différences fines entre bagof et setof, et tout le dernier chapitre (Datalog, SQL récursif, graphes de connaissances), qui sort du programme et fait le lien avec la data. Les exemples (crêperie, réseau ferré breton, métro rennais, cinéma, club de football) sont propres à ce cours.