Programmation fonctionnelle

I. Présentation

A. Le λ-calcul

Les langages fonctionnelles sont des langages qui reposent sur le λ-calcul, créé par Church en 1925. Le principe du λ-calcul consiste à considérer les fonctions comme des données comme les autres. Par exemple, la fonction qui consiste à ajouter 1 à un autre s'écrit, en λ-calcul :

λx.(x + 1)

On appelle cela une λ-expression. En mathématiques, on noterait cela x ↦ x+1

On peut appliquer une telle expression à une valeur ainsi :

(λx.(x + 1))(3) = (3 + 1)
                = 4

Une fonction additionnant ses 2 paramètres se représente ainsi :

λ(x,y).(x + y)

Soit en mathématiques : (x, y) ↦ x+y

Mais souvent, on représente plutôt cela sous la forme curryfiée :

λ(x)(λ(y).(x + y))

Autrement dit : x ↦ (y ↦ x+y)

En effet, les fonctions, étant des données comme les autres, une fonction peut très bien renvoyer une autre fonction. C'est le cas ici. On peut en effet passer 1 ou 2 paramètres à cette fonction, avec les résultats suivants :

  (λ(x)(λ(y).(x + y)))(5) = λ(y).(5 + y)
  
  (λ(x)(λ(y).(x + y)))(5)(3) = (λ(y).(5 + y))(3)
                             = 5 + 3
                             = 8
  

Les λ-fonctions sont des fonctions anonymes, et ce n'est pas très pratique. Souvent, on préférera les stocker dans des variables, ce qui reviendra à leur donner un nom. Par ailleurs, pour éviter la profusion de parenthèses, on préférera séparer les paramètres du nom de la fonction et entre eux par des espaces. On pourra donc écrire :

f = λ(x)(λ(y).(x + y))
f 3 5
8
g = f 3
g 5
8

Les langages fonctionnels présentent en général les particularités suivantes :

1. Les données sont immuables : leur valeur n'est jamais modifiée ; les fonctions peuvent créer de nouvelles données, mais pas en modifier. On obtient ainsi un code beaucoup plus sûr ;
2. Les effets de bord (entrées/sorties) sont clairement identifiés et en général séparés du coeur du langage. En effet, ce sont eux qui peuvent entraîner un comportement erratique ;
3. Il est possible de mettre en place un mécanisme d'évaluation paresseuse : les nouvelles données ne sont calculées que lorsque leur valeur devient nécessaire. Cela évite de calculer des données qui, au final, ne serviraient pas ;
4. Un mécanime, appelé inférence de type permet à l'interpréteur du langage de déduire le type des données et fonction sans qu'il soit nécessaire de le spécifier.

Le fait de pouvoir manipuler les fonctions comme de données, et donc par exemple pouvoir les passer en paramètres à d'autres fonctions, est un aspect très pratique des langages fonctionnels. Aussi, de nombreux langages impératifs intègrent maintenant cet aspect. C'est par exemple le cas de Javascript. Java, qui ne l'intégrait pas au départ, a fini par l'intégrer également depuis sa version 8 (2014).

B. Quelques langages fonctionnels

Langage	Date de création	Remarques
LISP	1958	Premier langage fonctionnel. Il a connu est fort succès, notamment avec beaucoup d'application en intelligence artificielle. Par ailleurs, ce fut un des premiers langages pour lequel fut développée la notion de machine virtuelle. C'est un langage réputé pour le nombre colossale de parenthèses qu'il requiert.
ML	1970
CAML	1985	Langage développé par l'INRIA rajoutant quelques aspects impératifs afin de faciliter certaines tâches de programmation. Un peu plus tard est apparu OOCAML, une version orientée objet de CAML.
HASKELL	1990	Langage fonctionnellement très pur, très efficace à l'exécution, et beaucoup moins lourd à utiliser que LISP. Par ailleurs, une bibliothèque très riche est disponible.

II. Exemples avec Haskell

Nous allons maintenant étudier quelques exemples de programmes écrits dans un langage fonctionnel, Haskell en l'occurrence. Vous pourrez tester ces exemples sans installation en utilisant cet interpréteur en ligne. (mais vous pouvez également installer Haskell sur votre machine 😜).

Les exemples qui suivent sont à taper dans l'interpréteur, c'est-à-dire la partie droite de la fenêtre (celle sur fond noir).

A. Typage et inférence de type

L'interpréteur Haskell propose une commande :t pour connaître le type d'une donnée. Commençons par quelques exemples d'utilisation de cette commande :

  :t "toto"
  "toto" :: [Char]
  :t reverse
  reverse :: [a] -> [a]
  :t 2
  2 :: Num p => p
  doubler x = x + x
  :t doubler
  doubler :: Num a => a -> a
  somme x y = x + y
  :t somme
  somme :: Num a => a -> a -> a

Tout ceci mérite quelques commentaires :

ligne 2 : type de "toto"

une chaîne de caractères est une liste de Char

ligne 4 : type de reverse

Cette fonction, qui renverse une liste, produit une liste d'éléments du même type (a) que ceux de la liste qui lui a été passée en paramètre

ligne 6 : type de 2

2 peut être interprété comme un entier, un réel, ... c'est-à-dire comme une donnée de n'importe quel type faisant partie de la classe de type Num

ligne 9 : type de doubler

La fonction doubler prend en paramètre une donnée d'un type numérique et renvoie une valeur du même type

ligne 12 : type de somme

La fonction somme prend en paramètre deux données du même type numérique et renvoie une valeur du même type. Il s'agit de la forme curryfiée. En fait, il faut interpréter ce type comme (a -> (a -> a)) (l'opérateur de typage -> est associatif droit).

B. Définition et application d'une fonction

On peut maintenant tester l'application d'une fonction :

  somme x y = x + y
  somme 2 3
  5
  s2 = somme 2
  :t s2
  s2 :: Num a => a -> a
  s2 3
  5

lignes 4 à 6 : il s'agit d'une application partielle de la fonction somme : s2 est une fonction qui ajoute 2 au nombre qui lui est passé en paramètre.

Il est bien sûr possible de composer les fonctions :

somme x y = x + y
suivant x = x + 1
somme (suivant 3) 4
8
myst x y = somme (suivant x) (suivant y)
myst 2 4
8

En cas de composition de fonctions, l'inférence de type d'Haskell réalise la conjonction des différentes contraintes. Prenons le cas de l'opérateur ++ qui permet de concaténer des listes (on rappelle au passage qu'en Haskell, une chaîne de caractères est une liste de caractères) :

[1,2] ++ [3,4]
[1,2,3,4]
"bon" ++ "jour"
"bonjour"
:t (++)
[a] -> [a] -> [a]
f x = x ++ [1]
:t f
Num a => [a] -> [a]

C. Condionnel

Dans les langages fonctionnels, tout est fonction. C'est notamment le cas du if ... then ... else ... : c'est en fait une fonction d'arité 3 :

• le premier paramètre est la fonction de test
• le deuxième paramètre la fonction calculant la valeur dans le cas ou le test est vrai,
• le troisième paramètre la fonction calculant la valeur dans le cas où le test est faux

Ainsi, if t then g else h renvoie une valeur (celle renvoyée par g ou h suivant que t renvoie vrai ou faux). Exemple :

f x = if (mod x 3 == 0) then (div x 3) else 4 * x - 1
:t f
Integral a => a -> a
f 7
27
f 6
2

N.B. : Integral est la classe des types numériques entiers.

D. Récursivité

Comme les langages fonctionnels ne connaissent que la composition de fonctions, il n'y a pas de boucle, et la répétition s'effectue donc par récursivité. Voici par exemple une définition de la suite de Fibonacci en Haskell :

fibo n = if (n < 2) then 1 else fibo(n-1) + fibo(n-2)
:t fibo
fibo :: (Ord a, Num a, Num p) => a -> p
fibo 6
13

On peut également calculer ainsi la somme des éléments d'une liste :

somme liste = if (length liste == 0) then 0 else head liste + somme (tail liste)
:t somme
somme :: Num p => [p] -> p
somme [1,2,3]
6

Les fonctions sur les listes peuvent également être définies par motif :

{somme [] = 0; somme (tete:queue) = tete + somme queue}

E. Listes

Les Listes sont un élément essentiel des langages fonctionnels. Elles ressemblent aux listes que vous connaissez en Python. Voici un exemple de fonction construisants les termes de la suite de Fibonacci jusqu'à un indice donné :

fibo n = if (n < 2) then 1 else fibo(n-1) + fibo(n-2)
termesFibo n = if n == 0 then [1] else termesFibo (n-1) ++ [fibo n]
:t termesFibo
termesFibo :: (Num t, Num a, Ord t) => t -> [a]
termesFibo 6
[1,1,2,3,5,8,13]

Pour accéder à l'élément d'une liste à un indice donné, on utilise l'opérateur !!. Exemple :

[2,4,6]!!1
4

Il est possible, comme en Python, de définir des listes en compréhension. On peut également définir des listes sous la forme d'un intervalle :

[2..10]
[2,3,4,5,6,7,8,9,10]

Les langages fonctionnels proposent également fréquemment des fonctions de mapping, de filtrage et de réduction. Ces fonctions sont des fonctions qui prennent des fonctions en paramètre, comme vous allez pouvoir le voir dans les sections suivantes.

1. Mapping

Ce type d'opération consiste à appliquer une fonction à tous les éléments d'une liste, et à renvoyer la liste des résultats. Exemple :

doubler x = x + x
map doubler [1,2,3]
[2,4,6]
:t map
map :: (a -> b) -> [a] -> [b]

2. Filtrage

Ce type d'opération consiste à renvoyer une liste constituée des éléments de la liste passée en paramètre qui vérifient un certain critère. Exemple :

pair x = (mod x 2) == 0
filter pair [1,2,3,4,5,6]
[2,4,6]
:t map
map :: (a -> b) -> [a] -> [b]

3. Pliage ou réduction

Le pliage, ou réduction, consiste à appliquer itérativement une fonction sur les termes de la liste, comme dans le cas de la somme des termes d'une liste : on réduit la liste à un entier grâce à l'addition. la fonction foldl d'Haskell permet de faire cela :

foldl (+) 0 [1,2,3]
6
:t foldl
foldl :: Foldable t => (b -> a -> b) -> b -> t a -> b

F. Données infinies et évaluation paresseuse

En Haskell, il est possible de définir des structures infinies. Exemple :

e = [2..]
e!!0
2
e!!100
102

Cela est possible grâce au mécanisme appelé évaluation paresseuse : une donnée n'est calculée que lorsque c'est nécessaire. Ainsi tant que je ne demande pas la centième valeur de la liste e, celle-ci n'est pas calculée. Bien sûr, vous aurez par contre un problème si vous essayez d'afficher la valeur de la variable e...

Cela permet par exemple une définition élégante et efficace de la suite de Fibonacci :

fibonacci = [1,1] ++ [ fibonacci!!(n-1)  + fibonacci!!(n-2)| n <- [2..]]
fibonacci!!6
13