Objectif : connaître les langages de programmation dont l'origine repose sur la théorie du lambda-calcul, et les concepts de programmation qui ont évolué à l'aide de cette théorie. Les étudiants maîtriseront un langage de programmation fonctionnel parmi Haskell ou Ocaml.
-
Calcul comme évaluation des expressions.
-
Calculs avec effets de bords et calculs purs. Notion d'état, affectation aux variables, substitution explicite.
-
Distinction entre typage fort et faible.
-
Types élémentaires et dérivés.
-
Types de fonctions, expressions lambda, fonctions d'ordre supérieure.
-
Types paramétrés par variables, classes, polymorphisme et surcharge.
-
Filtrage.
-
Sucres syntactiques: conditions de garde, compréhension sur les listes.
-
Types inductifs, fonctions récursives, preuves de programmes par induction structurelles.
-
Aspects impératifs : affectation, exceptions, entrées-sorties, séquencement, fichiers, références, tableaux, enregistrements. Monades.
-
Lambda calcul (termes, substitution, beta-évaluation) et logique combinatoire.
-
Stratégies d'évaluation des expressions.
Un projet d'implémentation parmi:
Bigliographie:
-
Y. Minsky et A. Madhavapeddy. Real World OCaml, functional programming for the masses.
O'Reilly, 2nd Edition, 2022. https://dev.realworldocaml.org/toc.html
-
G. Hutton. Programming in Haskell. Cambridge University Press, 2008.
-
B. O'Sullivan, D. Stewart, et J. Goerzen. Real World Haskell, O'Reilly, 2008. https://book.realworldhaskell.org/read/
-
J. Dehos. La programmation fonctionnelle - Introduction et applications en Haskell à l'usage de l'étudiant et du développeur, Ellipses, 2019.
Prérequis recommandés :
Logique (L3 Informatique), Calculabilité (L3 Informatique), Sémantique (L3 Maths-Informatique).
