Programmation fonctionnelle

Posted by alpheccar - Feb 11 2005 at 22:37 CEST

Pourquoi les langages comme LISP, Scheme, Ocaml ou Haskell sont infiniments supérieurs à C, C++, Java ? Ou, qu'est-ce qu'un langage fonctionnel ?

Avant de démarrer une guerre de religion, je précise que si ce texte se focalise essentiellement sur Ocaml ce n'est pas parce que les autres langages fonctionnels seraient mauvais. Ils ont chacun des avantages et des inconvénients. Selon le type d'application que l'on vise, on pourra être amené à faire un choix différent. J'ai choisi Ocaml et donc ce texte parle surtout des langages fonctionnels (purs ou non) statiquement et fortement typés.

Fonctionnel

En maths,

f(x) + f(x) = 2f(x)

De même,

f(x) + g(x) = g(x) + f(x)

Avec des langages comme Java ou C, ce n'est pas forcément vrai. En effet, toutes les fonctions, dans ces langages, sont implicitement dépendantes de l'état du monde (de la machine). Une fonction f(x) doit ainsi être considéré comme signifiant f(x,W) où W est l'état de la machine (variable globales, contenu du heap ...).

Après exécution de f, l'état global peut avoir été modifié : on appelle cela un effet de bord. C'est pourquoi f(x) + f(x) n'est pas forcément égal à 2f(x).

Ainsi, le problème fondamental dans les langages comme le C est la notion d'état qui rend la mise au point des programmes très difficile. Cette notion d'état est directement liée à la notion de temps. Dans les langages traditionnels (C, Java etc...) on interprète une fonction (au sens C ou Java) comme un processus s'exécutant dans le temps et modifiant peu-à-peu l'état de la machine.

Or, en maths, une fonction f ne dépendant pas implicitement d'un état ou du temps:

f(x) + f(x)  

est

2f(x) 
f(x) + g(x) 

est

g(x) + f(x)

Il n'y a pas d'effet de bord. Le passage de f(x) + f(x) à 2f(x) ne s'interprète plus comme un processus s'exécutant dans le temps mais comme une simplification algébrique. La notion de temps disparaît.

Un langage fonctionnel est un langage qui permet de manipuler des objets qui se comportent comme des fonctions mathématiques au sens où il n'y pas d'effets de bord et où il ne faut plus interpréter l'exécution d'un programme comme un processus qui s'exécute dans le temps mais comme un processus de simplification algébrique (même si au niveau implémentation on a vraiment un processus s'exécutant dans le temps. Dans ce texte, je ne m'intéresse pas à la façon dont les langages fonctionnels sont implémentés mais juste à leur sémantique).

Certains langages fonctionnels (Haskell) sont purs et la notion d'état est totalement absente du langage. D'autres langages (Ocaml) permettent, lorsque le programmeur le décide, d'utiliser la notion d'état avec tous les risques liés aux effets de bord que cela comporte.

Lorsque on utilise la partie pure du langage (sans état) on a la propriété de transparence réferentielle : on peut remplacer f(x) par sa définition n'importe où et sans risque. C'est une façon différente de dire qu'"exécuter" un langage fonctionnel c'est procéder à une simplification algébrique.

Voyons sur des exemples ce que cela implique:

Si je définis la fonction add par:

 let add x y = 2 + x + y ;;

add 3 4 peut-être remplacé par sa définition ce qui donne : 2 + 3 + 4

Le premier + peut-être remplacé par sa définition, ce qui donne 5 + 4

Ce dernier + peut-être remplacé par sa définition, ce qui donne 9.

Si j'insiste sur la vision simplification algébrique plutôt que sur une vision classique de processus s'executants dans le temps c'est parce que c'est la bonne façon de voir les choses. En effet, si j'écris:

let g = add 3 ;;

Comment interpréter g ? C'est la fonction obtenue en simplifiant add 3. Donc, g est équivalent à la fonction suivante:

let g y = 5 + y ;;

On a une évaluation partielle de add qui permet de construire g. Cette possibilité d'évaluation partielle explique aussi qu'en programmation fonctionnelle on écrira add x y plutôt que add (x y).

Essayons quelque chose de plus compliqué:

let incr a = function x -> x + a ;;
let add3 = incr 3 ;;

Que font donc ces fonctions ?

La première retourne une fonction dont le rôle est d'additioner a à son argument. Ainsi, incr 3 est une fonction qui ajoute 3 à son argument.

On peut le vérifier en utilisant une simplification algébrique:

 add3 4 

est équivalent à

(incr 3) 4 

(incr 3) 4 

est équivalent à :

 (function x -> 3 + x) 4

qui est équivalent à

 3 + 4

Ainsi, dans les langages fonctionnels, les fonctions sont des types primitifs que l'on peut utiliser comme n'importe quel autre objet. Une fonction peut calculer (construire) une nouvelle fonction et la retourner comme résultat.

Mais, une fonction peut aussi utiliser des fonctions en arguments:

 let rond f g = function x - > f (g x) ;;

rond est la fonction qui à f et g associe la nouvelle fonction f o g définie par (f o g)(x) = f (g x). C'est une fonction d'ordre supérieur.

Ainsi, en langage fonctionnel : une fonction est non seulement un type primitif qui peut-être manipulé mais une fonction mais aussi un objet algébrique qui est simplifié pour parvenir au résultat final que le logiciel est censé calculer.

Là où cela devient intéressant c'est lorsqu'on essaie d'interpréter les structures de test (if/then/else) et la récursivité dans ce cadre. Tout ce que je viens de dire est en effet totalement généralisable et on peut définir une algèbre des programmes où le programme est un objet algébrique qui peut-être manipulé, simplifié etc...

Pour en savoir plus, il y a le fameux livre : Algebra of Programming.

Cette algèbre des programmes fait fortement usage de la théorie des catégories. Or, comme on le sait, les flèches en théorie des catégories sont typées. Ce qui nous mène au point suivant.

Fortement typé

Le but d'un type est de donner statiquement une approximation du comportement dynamique. C'est de pouvoir, rien qu'en regardant le source code, déterminer ce qui va se passer lorsqu'on va l'exécuter (le simplifier). Le but est bien entendu de pouvoir détecter des erreurs avant même que le logiciel soit exécuté.

En raison de résultats théoriques, on sait que l'analyse statique ne permettra jamais de savoir tout ce qui est susceptible de se produire en pratique. Donc, il faut trouver un compromis : un système de type trop faible laissera passer trop d'erreurs mais un système de type trop fort risque d'interdire certains programmes parfaitement corrects mais rejetés par le système de type car il n' a pas pu déterminer avec certitude que le programme fonctionnerait une fois exécuté. Dans ce dernier cas : le système de type va réduire l'expressivité du langage.

Le problème avec les types c'est qu'il faut souvent annoter le source code.

Mais, il existe un système de type particulier (Hindley-Milner) qui ne nécessite pas d'annotations : le compilateur est capable de déterminer les types tout seuls. C'est le système utilisé par Ocaml.

Ainsi, si je tape:

 let add x y = x + y ;;

Ocaml retourne:

 val add : int -> int -> int

La signification est la suivante : le premier argument est un entier, le deuxième aussi et le résultat aussi. Ocaml n'écrit pas le type sous la forme (int,int) -> int et nous en avons vu les raisons précédemment.

Si j'écris maintenant:

 let id x = x ;;

Ocaml va retourner :

 val id : 'a -> 'a 

Autrement dit, Ocaml génére une variable de type 'a et une contrainte : le résultat de la fonction a le même type que son argument. On dit qu'on a un type polymorphe. Ces contraintes vont être résolues ailleurs dans le source code.

Par exemple, si plus loin, Ocaml rencontre:

id 1, il va en déduire que 'a vaut int dans ce cas. Si plus loin il rencontre id "hello", il va en déduire que 'a vaut string dans ce cas.

Le vérificateur de type de Ocaml va donc résoudre des équations de type.

Ainsi, dans le système de type Ocaml, on n'a aucune annotation à écrire et les types sont inférés par le système. Grâce au polymorphisme on a une grande flexibilité et donc, tout en étant fortement typé, ce langage est beaucoup plus simple à écrire qu'un langage comme Java ou C ou les casts de type et les annotations font perdre en productivité.

Le système de type d'Ocaml est incroyablement efficace. A tel point que, en pratique, le plus difficile est de compiler le logiciel qui fonctionne en général du premier coup. Et si c'est le cas, c'est certes parce que le système de type est bien conçu. Mais, il ne détecte pas tous les problèmes possibles. L'autre raison de son efficacité est que, par les contraintes qu'il impose, il force en général le programmeur à mieux penser. Il le guide vers les bon concepts et les bonnes abstractions.

Le système de types d'Ocaml est donc consistant. Mais qu'est-ce que cela veut dire ?

On a vu que le type de id est 'a -> 'a.

En fait, le type de id est:

Forall x, x => x

Le type de id est un prédicat logique.

Appliquer id à un argument, cela revient à se servir d'un axiome particulier du calcul des prédicats qui permet de spécialiser la variable x.

Ainsi, chaque expression de type est une expression logique. Chaque construction du programme correspond à une règle de la logique correspondante. Le programme est donc l'encodage d'une preuve logique permettant de passer de certaines expressions de types à d'autres.

Faire une vérification de type du programme c'est vérifier que la preuve est correcte. Cela n'est possible que si la logique est consistante ce qui n'est pas le cas avec les systèmes de type du C par exemple.

Ainsi, chaque logique consistante peut-être vue comme un système de type particulier à partir duquel on peut construire un langage de programmation. C'est la correspondance de Curry-Howard mais c'est une autre histoire.

Conclusion

Ce qui fait donc la supériorité d'un langage fonctionnel c'est d'avoir les fonctions comme type primitif ce qui permet un plus haut niveau d'abstraction et une plus grande expressivité. Le programmeur n'a pas à se soucier de détails d'implémentation (comme le risque d'avoir des effets de bord) et il peut se reposer sur des propriétés algébriques vérifiées par son code.

Le style fonctionnel est plus déclaratif qu'impératif. Au lieu de devoir ordonner (style impératif) à l'ordinateur de changer des états dans un certain ordre, on se contente plus d'exprimer des relations (fonctionnelles) entre des grandeurs. Les moyens fournis pour exprimer ces relations sont plus variés et plus abstraits ce qui rend les algorithmes plus élégants et plus concis.

J'ai gardé le meilleur pour la fin : les langages fonctionnels comme Scheme ou Ocaml génèrent du code qui est rapide ! Ce n'est pas parce que les langages fonctionnels permettent de coder à un niveau plus élevé d'abstraction qu'ils sont plus lents.

Les logiciels

• Ocaml
• Haskell
• Scheme

No tags