Programmation logique et fonctionnelle

La programmation impérative décrit comment calculer, pas à pas, en modifiant un état. Les paradigmes déclaratifs décrivent ce que l’on veut obtenir : la programmation fonctionnelle compose des fonctions pures et immuables ; la programmation logique énonce des faits et des règles et laisse un moteur d’inférence chercher les solutions. Ces paradigmes irriguent aujourd’hui tout le génie logiciel : lambdas et streams de Java, fonctions d’ordre supérieur de JavaScript et Python, MapReduce et Spark pour le traitement de données massives, moteurs de règles métier dans les banques, requêtes Datalog et systèmes experts. Ce cours en présente les fondements théoriques (lambda-calcul, unification, résolution SLD) et la pratique en Haskell et en Prolog (SWI-Prolog), avec des cas nigériens : calcul des frais scolaires, traitement de transactions de mobile money, éligibilité à un microcrédit.

Objectifs d’apprentissage

• Situer les paradigmes déclaratifs et en expliquer les avantages (raisonnement équationnel, parallélisme, tests).
• Réduire des lambda-termes et expliquer les stratégies d’évaluation.
• Écrire des programmes fonctionnels typés utilisant récursivité, filtrage par motif et fonctions d’ordre supérieur (map, filter, fold).
• Calculer un unificateur le plus général et dérouler une résolution SLD avec retour arrière.
• Écrire des programmes Prolog sur les listes, maîtriser la coupure et la négation par échec, réaliser un petit système expert.
• Transposer ces idées dans les langages industriels (Java, Python, JavaScript).

Prérequis

Algorithmique, programmation dans un langage impératif, logique propositionnelle et notions de logique des prédicats.

Plan du cours

1. Leçon 1 — Paradigmes déclaratifs et lambda-calcul
2. Leçon 2 — Programmation fonctionnelle : types, récursivité et fonctions d’ordre supérieur
3. Leçon 3 — Programmation logique : faits, règles, unification et résolution
4. Leçon 4 — Prolog avancé : listes, contrôle, systèmes experts et intégration des paradigmes

Modalités d’évaluation

Volume horaire : 10 h de cours (CM), 10 h de TD, 10 h de TP, 30 h de TPE ; 3 crédits. Évaluation : contrôle continu (40 % : TP notés en Haskell et Prolog, quiz) et examen terminal écrit (60 %).

Bibliographie

• Harold Abelson, Gerald Jay Sussman, Structure and Interpretation of Computer Programs, MIT Press.
• Graham Hutton, Programming in Haskell, Cambridge University Press.
• Ivan Bratko, Prolog Programming for Artificial Intelligence, Addison-Wesley / Pearson.
• Leon Sterling, Ehud Shapiro, The Art of Prolog, MIT Press.
• Documentation officielle : www.haskell.org et www.swi-prolog.org.