Lambda-calcul et programmation fonctionnelle
(janvier-mars 2025)
Enseignants :
-
Tiago de Lima (responsable)
Email : tiago.delima@univ-artois.fr
Bureau : UFR de Sciences C306
-
Juliete Rossie
Email : rossie@cril.fr
-
Arthur Marzinkowski
Email : marzinkowski@cril.fr
Description
| Niveau : | 3ème année de la licence |
| Crédits : | 5 ECTS |
| CM : | 15 h (10 × 1,5 h) |
| TD : | 15 h (10 × 1,5 h) |
| TP : | 16 h (8 × 2 h) |
La programmation fonctionnelle est un paradigme de programmation, c'est-à-dire, un mode de programmation et aussi une démarche indépendante du langage utilisé.
Dans un langage impératif (ex.: C, Java, Python) nous donnons à l'ordinateur une séquence d'instructions à être exécutées.
Nous avons à notre disposition la possibilité de changer la valeur des variables (affectation) et de contrôler le flux d'exécution du programme (ex.: if, while, for).
Dans un langage purement fonctionnel (ex.: Haskell), nous pouvons définir des variables, mais nous ne pouvons pas changer leurs valeurs.
Nous ne pouvons pas contrôler le flux d'exécution non plus.
Dans ce paradigme, nous construisons un programme en décrivant ce qu'il est, au lieu de ce qu'il doit faire.
Par exemple,
'le factoriel de n est le produit de tous les nombres entre 1 et n',
au lieu de,
'pour chaque i de 1 jusqu'à n, calcule x = x * i, etc..'
La programmation fonctionnelle est de plus en plus présente dans les langages modernes. Les dites expressions lambda sont maintenant présentes dans des langages comme C++, Java, Python et Javascript. Ceci atteste l'intérêt grandissant motivé par les diverses qualités de ce paradigme de programmation.
Nous allons utiliser le langage fonctionnel Haskell pour mettre en pratique les notions théoriques du cours.
Thèmes abordés:- Programmer avec des fonctions
- Récursivité
- Types
- Types structurés
- Schémas de programme
- Monades, entrées et sorties
- Lambda-calcul
Objectifs
À la fin de ce cours vous serez capable de:- Savoir situer le paradigme fonctionnel par rapport aux autres paradigmes de programmation.
- Écrire des programmes récursifs et démontrer sa correction et terminaison.
- Réfléchir de manière fonctionnelle, écrire et comprendre des algorithmes dans ce paradigme.
- Écrire des programmes dans le langage fonctionnel Haskell.
- Utiliser le lambda-calcul pour manipuler des lambda-expressions.
Pré-requis
Des notions d'algorithmique et programmation. L'étudiant est supposé capable d'écrire, compiler et exécuter des programmes dans un langage impératif ou orienté objet.Contenu des enseignements
Consultez régulièrement les emplois du temps sur ADE. Les horaires et salles peuvent être différents d'une semaine à l'autre.
La page Moodle de la discipline sera utilisée pour les annonces, la soumission des devoirs et pour communiquer les notes.
Les travaux pratiques seront notés. Ils doivent être réalisés en suivant le Guide de style de Haskell. La collaboration entre les collègues pour les TP est encouragée. Pourtant, les solutions doivent être écrites individuellement.
Téléchargez la polycopie (avec les exercices).
| date | cours | devoirs |
|---|---|---|
| 8 jan |
Notions élémentaires Récursivité |
— |
| 15 jan | Récursivité (cont.) | — |
| 22 jan | Types | Cartes de payement (30 jan 2025) |
| 29 jan | Types (cont.) | Listes (6 fév 2025) |
| 5 fév | Types structurés | The Matrix (13 fév 2025) |
| 12 fév | Schémas de programme | Arbre binaire de recherche (27 fév 2025) |
| 26 fév | Classes de types | Projet (25 mar 2025) |
| 5 mar | Monades, entrées et sorties | |
| 12 mar | Lambda-calcul | |
| 19 mar | Lambda-calcul (cont.) | |
| 20 mar | Examen (16:00 salle E7) |
Modalités du contrôle des connaissances
L'évaluation sera basée sur les devoirs (TP), un projet final (PF) et un examen (EX).
Chaque TP sera noté sur 20 points, selon le barème suivant:
- 25% pour le style.
- 75% pour la correction.
La note des devoirs sera la somme des notes deux devoirs tirés au hasard et divisée par 2 :
À partir de la semaine 7, les séances de TP seront dédiées à la réalisation du projet final.
La note de contrôle continu sera la moyenne pondérée du projet avec les devoirs :
La note de la session 1 sera calculée avec la note de du contrôle continu et de l'examen :
La note de la session 2 sera calculée de façon similaire :
Ressources
- Haskell download
- Page web officielle pour téléchargement du Glalgow Haskell Compiler (GHC).
Ceci est le compilateur Haskell que nous utiliserons dans les TP et le projet ! - Mini-manuel de programmation fonctionnelle (par Éric Violard)
- Un petit livre de programmation fonctionnelle qui a inspiré plusieurs de nos cours. (Disponible à la BU.)
- Try Haskell
- Un petit tutoriel qui utilise un interpréteur Haskell dans le navigateur.
- Haskell wikibook
- Une description complète du langage.
-
Real World Haskell
(par Bryan O’Sullivan, Don Stewart et John Goerzen)
- Une description longue et très détaillée de Haskell. Vous pouvez lire le livre en-ligne ou télécharger le PDF gratuitement.
- Apprendre Haskell vous fera le plus grand bien ! (par Miran Lipovača, version française de Valentin Robert)
- Un tutoriel amusant de Haskell.
- Programmation fonctionnelle (par Julien Dehos)
- Un cours de programmation fonctionnelle enseigné à l'Université Littoral Côte d'Opale (très bien fait).
- Learn You a Haskell for Great Good
- Un tutoriel gratuit très amusant.
- Introduction to Haskell
- par Brent Yorgey. Un cours de Haskell enseigné à l'Université de Pennsylvanie en 2013. Très bien fait.
- Haskell comme un vrai !
- par Yann Esposito. Un tutoriel très court mais très dense pour pour apprendre Haskell.
- Haskell Documentation
- Une longue liste de livres, cours, tutoriels, sites web, forums, etc., pour apprendre la programmation fonctionnelle et Haskell.
- Le théorème de Godël
- Une petite vidéo sur le résultat de Gödel sur l'indécidabilité de l'arithmétique.
Blagues
(Ce n'est pas sérieux. C'est juste pour rigoler.)- Programming jokes
- En programmation fonctionnelle, les variables sont immuables.
- Logicians find a genie (à propos de récursivité et ces paradoxes).
- Map, filter and reduce.
- and this is how we write "Hello World" in Haskell.
