Vous êtes ici : FIL > Portail > Licence Info > L3S6 Info > PF

Programmation Fonctionnelle

Objectif

Ce module est une introduction à la programmation fonctionnelle.

L’objectif est ainsi d’appréhender comment concevoir des programmes suivant ce paradigme centré sur l’évaluation de fonctions, et de voir comment cette approche aide à écrire des programmes clairs, concis, corrects et élégants.

Contenu

La programmation fonctionnelle est un paradigme très riche, avec de nombreuses notions liées, notamment :

  • fonctions d’ordre supérieur (combinateurs) ;
  • systèmes de types (vérification et inférence des types) ;
  • structures de données purement fonctionnelles ;
  • filtrage de motifs ;
  • stratégies d’évaluation (en particulier stricte et paresseuse1) ;
  • λ-calcul ;
  • monades.

Le cours s’appuie sur le langage Haskell, le langage purement fonctionnel à évaluation paresseuse.

Références et bibliographie

Voir l’onglet Documents.

Équipe pédagogique

Responsable
Intervenants

Volume horaire

Chaque semaine, 1h30 de cours, 1h30 de TD et 2h de TP.

Crédits

5 ECTS


  1. « This is plainly the way in which God intended reduction to take place, or at least Church. » Simon Peyton Jones

Samuel Hym
dernière modification : 9 octobre 2017

Semainier

Attention : le semainier suivant est prévisionnel, il évoluera suivant les besoins avec l’avancement du cours.

Le support des TDs est disponible depuis l'onglet « Documents ».

Le DSi aura lieu le lundi 13 février à 8h au bâtiment A5. Les documents (notes de cours, TD, TP, mini-haddock) sont autorisés.

SemaineCoursTDTPRemarque
1 2 janv.Introduction. Typage.Premier contactPremier contact
2 9 janv.Définitions de fonctions.Deuxième contact
3 16 janv.Combinateurs.Quelques fonctionsLe L-système et la Tortue
4 23 janv.Déclaration de types.Le L-système et la Tortue, la suite
5 30 janv.Analyse syntaxique.Types algébriquesDes arbres et des couleursFOSDEM
6 6 févr.IO.Des arbres et des couleurs, la suite
7 13 févr.Paresse.Maybe et analyse syntaxiqueDes arbres et des couleurs, la re-suiteDSi
8 27 févr.Parallélisme et concurrence.Interprète
9 6 marsMystère.Interprète, la suite
10 13 marsNothing.Manipulation de matricesInterprète, la re-suite
11 20 marsSoutenances de TP
12 27 marsDSf
Samuel Hym
dernière modification : 15 février 2017

Évaluation

L'évaluation s'effectue suivant une procédure de contrôle continu.

Trois notes seront attribuées à chaque étudiant durant le semestre :

  • DSi : une note d'un premier devoir qui se déroulera en milieu de semestre.
  • DSf : une note d'un second devoir qui se déroulera en fin de semestre.
  • TP : une note de contrôle continu évaluant les travaux pratiques rendus tout au long du semestre et une démonstration de ces travaux réalisée en fin de semestre.

La note finale (N) est calculée comme une moyenne pondérée de ces notes :

ÉCRIT = max(DSf, (DSi + 2 DSf) / 3)
N = 75% ÉCRIT + 25% TP

Pour la session de rattrapage, la note TP est conservée, la note du devoir surveillé de rattrapage remplace la note d’écrit.

L'unité acquise apporte 5 ECTS.

Samuel Hym
dernière modification : 25 août 2014

Installation d’Haskell sur votre machine personnelle

La solution la plus simple dans le cadre du cours est sans doute d’installer un environnement le plus proche possible de celui utilisé au M5, à savoir la distribution Linux Ubuntu (vous pouvez l’installer dans une machine virtuelle). Le compilateur GHC et les bibliothèques que nous allons utiliser sont disponibles dans la distribution.

Distributions Linux Debian & Ubuntu

Debian et Ubuntu (et autres distributions dérivées, sans doute) fournissent les paquets :

  • haskell-platform et haskell-platform-doc qui permettent d’installer tous les outils et bibliothèques de base,
  • libghc-gloss-dev et libghc-gloss-doc pour la bibliothèque Gloss que nous allons utiliser pendant quelques séances de TPs,
  • beaucoup d’autres outils, tels que hlint, stylish-haskell, etc. qui aident au développement du code.

Méthodes proposées par la communauté

Le site web de la communauté propose des instructions d’installation.

Samuel Hym
dernière modification : 4 janvier 2017

Exemples de code vus en cours

Les morceaux de code écrits pendant le cours sont disponibles dans un dépôt git que vous pouvez cloner en tapant :

git clone http://www.fil.univ-lille1.fr/~hym/d/pf.git

Cela crée un répertoire (pf par défaut) contenant un clone local du dépôt en ligne. Vous pourrez par la suite mettre à jour votre copie en lançant, dans le répertoire cloné :

git pull

Supports

Support pour les TDs du semestre.

Un Mini-haddock a été distribué en cours. Les exemplaires supplémentaires sont disponibles auprès de l’AEI.

Références

Les présentations de Simon Peyton Jones sont tout à fait recommandables :

Pour aller plus loin

Un cours est trop court pour faire le tour d’un sujet aussi vaste que la programmation fonctionnelle, ou même juste du langage Haskell.

La communauté Haskell est très active, avec de nombreux sites (blogs, etc.). Quelques liens pour entrer :

  • Hackage : l’archive de bibliothèques créées par la communauté,
  • le wiki de haskell.org, qui contient notamment un petit répertoire de bibliothèques, pour s’y retrouver dans Hackage,
  • 24 Days of Hackage 2012 et 2013,
  • What I Wish I Knew When Learning Haskell : une mine d’informations très diverses, allant d’exemples d’utilisation d’outils comme stack à un panorama de bibliothèques existantes,
  • The Haskell Cast : un balado qui, outre les entretiens, propose de nombreux liens,
  • Haskell from Scratch : une série de vidéos dans lesquelles Chris Forno montre comment écrire un programme complet,
  • Planet Haskell,
  • la conférence ICFP et ses affiliées, qui traitent de langages fonctionnels, à la fois sur les aspects recherche mais aussi usages ; voir les vidéos des exposés, pour un panorama.

Annales

Samuel Hym
dernière modification : 28 février 2017

Plan du cours

Points essentiels abordés dans le cours.

Introduction : qu’est-ce que la programmation fonctionnelle

  • Les fonctions sont des citoyens de première classe
  • Pureté : absence d’effets de bord
    Le calcul est exprimé comme une expression, recombinant des expressions plus simples, plutôt que comme une suite d’instructions qui change un état

Types

Haskell est fortement typé statiquement.

  • Types de « base »
  • Types fonctionnels et curryfication
  • Fonctions polymorphes
  • Surcharge, grâce aux classes de type

Déclarations de fonctions

  • if then else, gardes
  • Filtrage de motifs, décomposition des arguments
  • Fonctions anonymes

Combinateurs

  • map, etc.
  • foldr, foldl
  • Composition de fonctions

Déclaration de types

  • Synonymes, avec type
  • Types de données algébriques, avec data
    Constructeurs

Analyseurs syntaxiques

Création d’une petite bibliothèque de combinateurs pour l’analyse syntaxique.

Illustre comment construire une solution fonctionnelle élégante à ce problème… et introduit quelques schémas qui reviendront dans la suite.

IO

  • Type IO a d’une action qui, quand elle sera effectuée, produira des effets de bord et un résultat de type a
  • Combinaison d’actions par (>>=) et action élémentaire return

Paresse

  • Stratégies d’évaluation : stricte (appel par valeur), ou pas (par exemple, appel par nom)
  • Gain d’expressivité : il est possible de contrôler l’ordre d’évaluation dans le langage
  • Gain de modularité : il est possible de décomposer le programme en du code très générique pour générer les données et du code qui choisit l’ordre d’évaluation

Parallélisme et concurrence

Définition des deux notions.

  • Parallélisme : utilisation de par et pseq pour indiquer à l’environnement d’exécution ce qu’il peut exécuter en parallèle ou pas
  • Concurrence : forkIO, communication-synchronisation par variables partagées ; interface STM pour exprimer de façon plus modulaire le code

Functor, Applicative, Monad

  • Notions très génériques : exemples pour Maybe et []
  • Exemple d’utilisation de (<$>) et (<*>) pour écrire une version sûre de la mini-calculatrice
  • Utilisation de Monad (et de la notation do) pour écrire des programmes de façon très déclarative, par exemple Scotty

λ-calcul

  • Définition rapide
  • Expressivité : permet d’exprimer tout ce qui est calculable ; exemple avec les booléens, les entiers de Church et un combinateur de point fixe
Samuel Hym
dernière modification : 8 mars 2017