ProgrammationFonctionnelle
Un article de WikiProg.
Sommaire |
Qu'est ce que la programmation fonctionnelle
La Programmation Fonctionnelle désigne l'usage d'un paradigme de programmation respectant certains critères plus ou moins strictes (voir plus loin.) Bien qu'il soit possible de faire de la programmation fonctionnelle dans beaucoup de langage de programmation, on restreint souvent cette notion à l'usage de certains langages dits fonctionnels comme Caml, Lisp ou encore Haskell.
D'un point de vue théorique, la programmation fonctionnelle est issue du lambda calcul un modèle mathématique basé uniquement sur la notion de fonction. Le lambda calcul (et les travaux associés) sert de base à la construction et la description des langages à sémantique bien fondée et est souvent considéré comme le point de départ de toute la théorie des langages modernes.
D'un point de vue pratique, la programmation fonctionnelle se distingue de la programmation impérative par l'usage systématique de fonctions dans un espace immuable: pas de notion de variables, pas d'état, pas d'instruction. Les fonctions sont dites pures (leur comportement est déterministe, i.e. elles donnent toujours le même résultat pour les mêmes arguments.) En règle générale, le monde fonctionnel utilise abondament la récursion et l'OrdreSupérieur.
Les grandes caractèristiques du monde fonctionnel:
- valeurs immuables: il n'y a pas de notion de variable
- pas de boucle
- tout est expression: tout phrase du langage renvoie une valeur
- pas d'effet de bord: le comportement de toutes les expressions est explicite, il n'y a pas de notion d'état et encore moins de modification d'état
- OrdreSupérieur: les fonctions sont des valeurs comme les autres (valeurs de première classe) et à ce titre peuvent être passé en paramètre d'autre fonction ou être renvoyée comme résultat.
- FonctionAnnonyme: les fonctions peuvent décrites sans leur associer de nom et ainsi être utilisée directement sans passer par une définition globale.
- Sémantique bien fondée: en règle général, on décrit le comportement d'un langage fonctionnel indépendament de son implantation à l'aide des outils de la théorie des lanages (sémantique opérationnelle ou dénotationnelle ... )
La programmation fonctionnelle dans le cours
La première partie de l'année sera centrée sur l'usage de la programmation fonctionnelle. Nous utiliserons le langage OCaml de l'INRIA. Certains notions que nous aborderons sortent du monde fonctionnel pure:
- typage fort et polymorphisme
- interraction entre fonctionnel et impératif
- programmation modulaire
- foncteurs
Nous tacherons également de voir en quoi le monde fonctionnel peut être intéressant pour le programmeur généraliste et nous essairons d'exploiter au mieux les qualités de ce modèle, ainsi que celle du langage OCaml.
Typage fort et Polymorphisme
Bien que n'étant pas spécifique au monde fonctionnel (ni même un trait particulier du monde fonctionnel), le typage fort est un outil souvent présent dans les langages fonctionnels. En résumé, le typage est une vérification statique (avant l'exécution) du bon usage des fonctions et des opérateurs dans un programme.
La philosophie du typage est résumé par cette citation de Milner (le père de ML): Well typed programms cannot go wrong.
Techniquement, le typage (fort) fournit une preuve que quelque soit l'évaluation du programme chaque opération s'appliquera à une donnée qu'elle est capable de traiter. De ce fait, lors de la réduction (évaluation formelle pas à pas d'un programme), nous ne tomberons jamais dans une impasse.
Le typage fort en soit peut apparaîre comme une restriction, mais il est souvent couplé à deux notions intéressantes: l'inférence et le polymorphisme. La première consiste a laissé le compilateur (enfin le système de types) retrouver tout seul le type des fonctions (paramètres, résultats, éléments intermédiaires ... ) La seconde est le fait de pouvoir construire des types génériques pouvant s'appliquer à plusieurs cas particulier.
Le polymorphisme est un point important des langages de la famille ML (dont est issue OCaml.)
Exemples en OCaml
(* application d'une fonction à l'ensemble d'une liste *)
let rec map f = function
[] -> []
| h::t -> (f h) :: map f t
(* parcourt de liste intelligent et composition des résultats *)
let rec fold_left f a = function
[] -> a
| h::t -> fold_left f (f a h) t
