Programmation fonctionnelle

Petit historique de la programmation fonctionnelle ¹

Alors que l'origine de la programmation fonctionnelle peut être trouvée dans le lambda-calcul, le langage fonctionnel le plus ancien est Lisp, créé en 1958 par McCarthy. Lisp a donné naissance à des variantes telles que Scheme (1975) et Common Lisp (1984) qui, comme Lisp, ne sont pas ou peu typées. Des langages fonctionnels plus récents tels ML (1973), Haskell (1987), OCaml, Erlang, Clean et Oz, CDuce, Scala (2003), F# ou PureScript (2013), Agda (en) sont fortement typés.

Qu'est ce que la programmation fonctionnelle ?

La programmation fonctionnelle est un paradigme de programmation de type déclaratif qui considère le calcul en tant qu'évaluation de fonctions mathématiques. Comme le changement d'état et la mutation des données ne peuvent pas être représentés par des évaluations de fonctions, la programmation fonctionnelle ne les admet pas, au contraire elle met en avant l'application des fonctions, contrairement au modèle de programmation impérative qui met en avant les changements d'état.

Exemple de programmation fontionnelle

	def majeur(liste:list) -> list:
		return list(filter(lambda x: x>=18, liste))
		
	assert majeur([12, 15, 19, 21, 3, 42]) == [19,21,42]

Les fonctions pures

Pour qu'une fonction soit considérée comme pure, les mêmes données d'entrée doivent toujours produire le même résultat en sortie, tout en n'induisant aucun effet de bord.

Cette propriété rend possible la transparence référentielle, principe selon lequel le résultat d'une opération ne change pas si on remplace une expression par une expression de valeur égale.

Un langage fonctionnel est dit « fonctionnel pur » s'il est sans effet de bord. Par exemple, dans de tels langages, on ne trouve aucune donnée mutable. C'est le cas du langage Haskell.

Effet de bord ou effet secondaire ²

Une fonction est dite à effet de bord (traduction mot à mot de l'anglais side effect, dont le sens est plus proche d'effet secondaire) si elle modifie un état en dehors de son environnement local, c'est-à-dire si elle a une interaction observable avec le monde extérieur autre que retourner une valeur (modification de variables globales par exemple).

Transparence référentielle

Les langages fonctionnels ont comme autre propriété la transparence référentielle. Ce terme recouvre le principe simple selon lequel le résultat du programme ne change pas si on remplace une expression par une expression de valeur égale. Ce principe est violé dans le cas de procédures à effets de bord puisqu'une telle procédure, ne dépendant pas uniquement de ses arguments d'entrée, ne se comporte pas forcément de façon identique à deux instants donnés du programme.

Exemple de fonction non référentiellement transparente

	n = 2
	def inc(k :int) -> int: # incrementation par effet de bord
		n = n + k
		return n
		
	f(inc(1) + inc(1)) # /!\ : différent de f(2*inc(1)) !!!

Au contraire, les fonctions au sens mathématique du terme sont référentiellement transparentes : c'est le cas par exemple de la fonction sin(x) puisqu'elle renvoie toujours le même résultat pour un x donné.

Conséquence de l’utilisation de la programmation fonctionnelle

Parallélisation

La programmation fonctionnelle permet de gérer efficacement la parallélisation. On peut se libérer de contraintes de chronologie. Par exemple si res = f1(a,b) + f2(a,c), on peut effectuer les appels de f1 et f2 dans n'importe quel ordre.

Récurences

Sans affectations, ni boucle, la programmation fonctionnelle passera par les fonctions récursives. Ce qui nécessite de gérer la pile différemment pour éviter les stack overflow.

Des fonctions passées en paramètre.

Les fonctions sont des objets de première classe, ce qui signifie qu'elles sont manipulables aussi simplement que les types de base. Du coup, une fonction peut prendre des fonctions comme arguments ou renvoyer une fonction comme résultat.

Exemple de fonction passée en paramètre

	f1 = lambda x: 2*x
	f2 = lambda x: x**2
	def fonction(f, x):
		return f(x)
		
	assert fonction(f1, 5) == 10
	assert fonction(f2, 5) == 25

---

1. Source : Wikipedia : Programmation fonctionnelle ↩

2. Source : Wikipedia : Effet de bord(informatique) ↩