La programmation fonctio-quoi ?

Cet article est une version texte du talk que j’ai donné dans le cadre de l’API Hour #27. Le diaporama de cette présentation est disponible ici.

Vaste sujet que la programmation fonctionnelle. Depuis quelques années, on en entend parler de plus en plus : des langages comme C++ ou Java commencent à introduire des concepts tels que Map, Reduce ou encore Lambdas. On parle de langages purs ou impurs. On dit que les effets de bord sont dangereux.

Bref, la programmation fonctionnelle est un sujet vachement à la mode, et pourtant, cela reste un thème relativement obscur pour de très nombreux développeurs.

Dans cet article, je vous propose d’en apprendre plus sur ce paradigme. D’où vient la programmation fonctionnelle, qu’est-ce que c’est, et pourquoi on en entend autant parler.

Histoire

innovation
L’innovation, par Luc Damas.

Turing et les langages impératifs

Au commencement, il n’y avait rien. Puis, en 1936, un certain Alan Turing, considéré aujourd’hui à juste titre comme le père de l’informatique moderne, propose une théorie passionnante : d’après ses travaux, on pourrait représenter n’importe quelle opération mathématique grâce à sa fameuse machine.

La machine de Turing repose sur un principe simple : elle effectue des opérations les unes à la suite des autres dans le but d’atteindre un état voulu. Ce mode de fonctionnement constitue la base de ce que l’on appelle la programmation impérative.

Turing Machine

L’année 1957 marque l’apparition de Fortran, l’un des premiers langages de programmation ; le code écrit avec ce langage suit plus ou moins la même logique d’une machine de Turing. Dans les décennies qui suivent, de nombreux langages suivant cette même logique font leur apparition, parmi lesquels :

  • Années 1960 — COBOL, BASIC ;
  • Années 1970 — C, Pascal;
  • Années 1980 — C++, Perl ;
  • Années 1990 — Python, Java ;
  • Années 2000 — C#, Go.

Si vous avez la moindre expérience dans le domaine de l’informatique et de la programmation, vous avez déjà entendu la plupart de ces noms, et vous avez sans doute déjà écrit des programmes dans au moins l’un de ces langages.

Church et les langages fonctionnels

En 1936, soit la même année que Turing, un autre mathématicien, Alonzo Church propose une autre théorie permettant de modéliser les opérations mathématiques : le lambda-calcul (souvent écrit λ-calcul). Sans trop entrer dans le détail, il s’agit d’un système permettant de définir des fonctions anonymes (appelées lambdas), d’appliquer ces fonctions ou de les abstraire.

Aussi différents soient-ils, le lambda-calcul et la machine de Turing sont pourtant strictement équivalent. En 1939, Turing et Church publient une thèse (démontrée en 2008) sobrement intitulée la thèse Church-Turing, qui stipule que toute opération possible avec une machine de Turing l’est aussi avec le lambda-calcul, et vice versa.

En 1958, c’est-à-dire à peine un an après l’arrivée sur le marché de Fortran, John McCarthy publie la première version de Lisp, l’un des premiers langages fonctionnels. Ce langage, réputé pour sa syntaxe très riche en parenthèses, repose en grande partie sur la théorie de Church. De la manière que Fortran, Lisp a influencé de nombreux langages fonctionnels durant la seconde moitié du XXème siècle, parmi lesquels :

  • Années 1960 — APL;
  • Années 1970 — ML, Scheme ;
  • Années 1980 — Erlang ;
  • Années 1990 — Haskell, OCaml ;
  • Années 2000 — Scala, F#, Clojure.

Ces langages sont généralement bien moins populaires que leurs confrères impératifs. En effet, les langages fonctionnels ont jusqu’à aujourd’hui plutôt eu du succès auprès des communautés scientifiques et mathématiques plutôt que dans le monde de l’industrie informatique.

Les deux mondes se rejoignent

Néanmoins, il ne faut pas voir ces deux timelines comme complètement séparées l’une de l’autre. Notamment, dans le courant des années 1990 sont apparus quelques langages qui utilisent très largement des concepts présents dans les paradigmes impératif et fonctionnel. C’est notamment le cas de Ruby ou de JavaScript, par exemple.

Plus récemment, en 2011, la norme C++11 introduit de nombreux concepts issus du monde de la programmation fonctionnelle, et en 2014, Java 8 fait de même.

Définition

Bon, c’est bien beau tout ça, mais on ne sait toujours pas de quoi la programmation fonctionnelle retourne réellement.

C’est un paradigme

Voilà qui devrait vous éclairer. Non ? Pour faire simple, en programmation, un paradigme est un ensemble de règles fondamentales qui régissent une famille de langages. L’exemple le plus courant est celui de la programmation orientée objet : dans ce paradigme, toutes les variables sont des objets, définis par leur classe, possédant des attributs et des méthodes. Ce vocabulaire et les concepts associés constituent un paradigme appliqué par les langages de cette famille, et le développeur construit ses algorithmes et son code autour de ces concepts.

Le paradigme fonctionnel, quant à lui, se caractérise par le fait que toutes les opérations sont traitées comme application d’une fonction, au sens mathématique du terme (d’où le nom). C’est tout !

Et la principale différence entre un programme impératif et un programme fonctionne est que ce dernier interdit formellement les mutations. Même si ce terme ne vous est pas familier, il désigne quelque chose que vous utilisez tous à chaque instant lorsque vous programmez : il s’agit d’un effet de bord qui se produit lorsque vous réalisez une affectation, que vous utilisez un compteur, ou que vous appelez un setter.

En d’autres termes, toute fonction écrite dans un langage fonctionnel est considérée pure :

  • Pour une entrée donnée, la fonctionne renverra systématiquement le même résultat ;
  • L’exécution de la fonction n’a aucun impact sur son environnement de programmation.

Exemple

Si vous vous sentez un peu perdu, c’est tout à fait normal. Comment peut-on programmer sans variable, sans compteur, sans boucle ?! Pour vous donner une petite idée, rien de tel qu’un exemple.

Voici un morceau de code que vous avez tous déjà écrit dans votre vie, quelque soit le langage.

def sum(l):
    sum = 0
    for e in l:
        sum += e
    return sum

Vous l’avez bien compris, la fonction sum calcule la somme d’un tableau d’entiers. Si vous avez bien suivi jusqu’ici, l’instruction sum += e constitue une mutation : on modifie l’état interne du programme en attribuant à la variable sum une nouvelle valeur.

Voici ci-dessous la même fonction, écrite en OCaml, un langage fonctionnel auquel je voue une passion sans bornes.

let rec sum l =
    match l with
    | [] -> 0
    | h::t -> h + sum t

La syntaxe doit vous paraître bien étrange, donc voici une rapide explication de ce morceau de code :

  • On définit une fonction récursive qui s’appelle sum et qui prend un argument l ;
  • On réalise un pattern-matching (une sorte de switch en mieux) sur l :
    • Si la liste est vide, on renvoie zéro ;
    • Si la liste se compose d’un premier élément (h pour head) suivi d’une liste d’élément (t pour tail), alors on renvoie h plus la somme de t.

(Même si cette méthode ne vous paraît pas naturelle au premier abord, dites-vous bien que ce n’est qu’une question d’habitude.)

Quoi qu’il en soit, vous pouvez chercher, la fonction OCaml ne comporte aucune mutation.

Enjeux

Les mutations sont nécessaires

La question qui se pose maintenant est la suivante : en quoi supprimer les mutations est une bonne chose ? Quel est l’intérêt de se torturer l’esprit avec des fonctions récursives et des pattern-machin-chose, alors qu’une boucle fait très bien l’affaire ?

En plus, si on veut qu’un programme fasse quelque chose, on est obligé d’avoir recours à des effets de bord. Typiquement, écrire une chaîne de caractères à l’écran, lire un fichier, requêter une base de données sont des opérations qui par définition « ont un impact sur leur environnement d’exécution ».

Certes. À vrai dire, la programmation fonctionnelle n’a pas vocation à éliminer tous les effets de bord ; seulement à les limiter le plus possible.

Haskell
Haskell vu par xkcd.

Les mutations sont dangereuses

Et ça, vous le savez très bien. C’est pas pour rien que tout programmeur qui se respecte vous dira que les variables globales, c’est moche, par exemple.

Voici un petit example très représentatif de ce danger.

Soit une variable x partagée en deux threads. Sa valeur initiale est 0.

La situation initiale.

On lance les deux threads « en même temps ». À partir de là, plusieurs cas de figure :

  • Il se peut que le thread rouge s’exécute avant le thread vert. x vaut alors 1.
  • Il se peut également que le thread vert s’exécute avant le thread rouge. x vaut alors 2.
  • Il existe également un cas bien plus pernicieux, décrit par le schéma ci-dessous. Ici, le thread rouge lit 0, puis le thread vert effectue ses opérations. Ensuite, le thread rouge calcule 2 × 0, et x vaut alors 0.

    Piégeux, pas vrai ?

Au final, malgré que l’exemple soit très simpliste (à des années-lumière d’une application réelle), les mutations peut déjà provoquer des bugs et des chemins d’exécution parfois difficiles à déceler. Bien sûr, la solution ici consiste à verrouiller l’accès à la variable x via une mutex. Mais ce genre de technique nuit à la performance du programme, et, d’une manière générale, constitue une solution à un problème qui ne devrait pas exister.

De par l’absence de mutations, un programme fonctionnel est thread-safe par design. Et ça, c’est beau.

Conclusion

Les avantages de la programmation fonctionnelle ne se limitent pas au simple exemple que j’ai donné, vous vous en doutez bien, mais cet article est déjà bien trop long (bravo à vous, lecteurs courageux qui avez lu jusqu’ici), et rentrer dans plus de détails demanderait bien plus de temps. Néanmoins, je pense que cette introduction donne un bon point de départ pour comprendre la programmation fonctionnelle, et j’espère qu’il vous a donné envie d’en apprendre plus. C’est pourquoi je vous propose ci-dessous une liste de ressources complémentaires à aller consulter :

Voilà ! Bien évidemment, si vous avez des questions ou des remarques, je vous invite à les poster en commentaire de cet article, je me ferai un plaisir d’y répondre !

Laisser un commentaire

Votre adresse de messagerie ne sera pas publiée. Les champs obligatoires sont indiqués avec *