Programmation Logique : Cours complet sur le Langage Prolog (PDF)

Prérequis

Familiarité requise avec la logique du premier ordre (prédicats, quantification) et la récursion sur structures inductives ; usage pratique du shell swipl pour charger et interroger des fichiers .pl.

Un environnement conforme à la norme ISO/IEC 13211-1 est recommandé afin d'assurer la portabilité des clauses, de l'opérateur cut (!), du prédicat fail/0 et des mécanismes d'indexation des prédicats.

Mise en garde : ce cours signale que l'emploi d'extensions non standard de SWI-Prolog (attributs de variables propres à SWI, prédicats multithreading) peut compromettre la portabilité vis-à-vis de ISO/IEC 13211-1.

Introduction à Langage Prolog

Ce cours aborde explicitement le paradigme de programmation déclarative en présentant l'unification, la résolution SLD et le backtracking comme mécanismes d'exécution concrets pour la preuve automatisée.

Le Langage Prolog implémente ce paradigme déclaratif sur la logique du premier ordre en s'appuyant sur des termes composés, des listes (syntaxe [] et [Head|Tail]) et des clauses Horn.

Les notions de faits, de règles (séparateur :- entre tête et corps) et d'unification sont montrées par des exemples exécutables dans SWI-Prolog et des fragments de code testés avec swipl.

Aperçu du cours: Langage Prolog

Le document développe huit thèmes techniques centrés sur les opérateurs et mécanismes de Prolog, avec exemples de code, traces SLD et micro-benchmarks d'exécution.

• Principes fondamentaux : atomes, variables, structures, notation préfixe et contraintes d'arité pour predicate/arity.
• Représentation des connaissances au travers de faits et règles, avec exemples concrets comme parent(alice,bob). et ancestor/2.
• Analyse de la syntaxe et de la sémantique : portée lexicale des variables, clausules Horn et portée des variables anonymes (_).
• Structures de données et unification : présentation de l'algorithme Martelli‑Montanari appliqué à la résolution sur termes imbriqués.
• Listes en pratique — concaténation, sélection, suppression — implémentées par récursion et accumulateurs pour éviter l'épuisement de la pile.
• Recherche de preuves : construction et exploration d'un SLD-tree pour une requête donnée, avec exemple pas à pas montrant substitutions successives.
• Exemples d'exécution dans swipl : capture de traces, utilisation de time/1 pour mesurer des requêtes lourdes et exemples d'optimisation par indexation.
• Contrôle du backtracking par cuts (!), diagnostics avec trace/0 et utilisation de sorties write/1 pour inspecter substitutions partielles.

À la fin de ce cours, vous saurez :

• Concevoir une base de faits et définir l'indexation de prédicats (ex. multi-clause pour edge/2) afin de réduire le temps de recherche.
• Implémenter des algorithmes récursifs sur listes, par exemple un prédicat tail-recursive de map avec accumulateur et complexité linéaire O(n).
• Analyser l'arbre SLD d'une requête complexe en combinant trace/0 et inspection des substitutions appliquées aux variables.
• Optimiser le contrôle du backtracking via l'usage ciblé du cut (!) et par réécriture de clauses pour favoriser l'indexation sur le premier argument.
• Mettre en place un solveur de contraintes simple (coloration de graphe) en exploitant l'unification non déterministe et le retour arrière pour exposer conflits d'affectation.
• Utiliser des outils de diagnostic : spy/1, points d'arrêt et sorties intermédiaires write/1 pour suivre l'évolution des variables pendant la preuve.

Glossaire

• Unification : opération qui rend deux termes identiques en calculant une substitution pour leurs variables, détaillée dans l'exposé de l'algorithme Martelli‑Montanari.
• Dans la résolution, backtracking décrit le processus automatique qui explore alternatives après l'échec d'une clause et se visualise dans la trace SLD via trace/0.
• Fait : assertion atomique telle que parent(alice,bob). utilisée comme entrée de la base de faits au cours de la preuve.
• Règle : clause conditionnelle écrite Head :- Body. permettant d'exprimer relations composées entre prédicats (ex. ancestor(X,Y) :- parent(X,Z), ancestor(Z,Y).).
• Prédicat : entité définie par un nom et une arité (par exemple ancestor/2), servant d'unité d'indexation pour l'interpréteur.

Applications pratiques

La combinaison d'unification et de backtracking facilite l'énumération de solutions : par exemple, écrire un prédicat non déterministe qui génère toutes les permutations d'une liste contenant l'atome a.

• Écrire un prédicat member/2 qui énumère occurrences d'un élément dans une liste et illustrer le comportement non déterministe avec plusieurs retours.
• Exploiter relations parent/2 et ancestor/2 pour inférer liens familiaux par récursion, puis mesurer le coût des requêtes sur une base de 1 000 faits.
• Formuler la coloration de graphe comme problème de contraintes logiques en laissant l'unification et le backtracking identifier rapidement les conflits d'affectation.

L'approche déclarative de Prolog sert de base au prototypage d'outils d'inférence pour l'IA symbolique, avec exemples de règles et jeux de données fournis dans le PDF.

Complémentaire au machine learning, l'intégration de règles Prolog favorise l'IA explicable via représentations symboliques et traces de preuve.

Mis à jour le 03/03/2026