Ce chapitre couvre

• Pourquoi la programmation fonctionnelle?
• Qu’est-ce qui définit la programmation fonctionnelle?
• Programmation déclarative et transparence référentielle
• Directives pour l’écriture de Java dans un style fonctionnel
• Itération vs récursivité

Vous avez vu le terme fonctionnel assez fréquemment tout au long de ce tutoriel. Maintenant, vous pouvez avoir des idées sur ce que signifie être fonctionnel. S’agit-il de lambdas et de fonctions de première classe? Ou s’agit-il de restreindre votre droit de muter des objets? Dans quel cas, que réalisez-vous en adoptant un style fonctionnel? Dans ce chapitre, nous mettons en lumière ces questions. Nous expliquons ce qu’est la programmation fonctionnelle et introduisons une partie de sa terminologie. Nous examinons d’abord les concepts qui sous-tendent la programmation fonctionnelle tels que les effets secondaires, l’immutabilité, la programmation déclarative et la transparence référentielle et faisons le lien à Java 8. Dans le chapitre suivant, nous examinons de plus près les techniques de programmation fonctionnelle. structures de données persistantes, listes paresseuses, correspondance de motifs (pattern matching) et combinateurs.

13.1. Implantation et maintenance de systèmes

Commençons par imaginer que vous avez été invité à gérer une mise à niveau vers un grand système logiciel préexistant, que vous n’avez pas encore vu. Devriez-vous accepter ce travail en maintenant un tel système logiciel? La maxime ironique de l’entrepreneur Java chevronné pour décider est: «Commencez par chercher le mot-clé synchronised; si vous le trouvez, dites simplement non (reflétant la difficulté de corriger les bogues de concurrence); »Nous donnons plus de détails dans les paragraphes suivants, mais remarquons d’abord que, comme vous l’avez vu dans les chapitres précédents, l’ajout de flux de Java 8 vous permet d’exploiter le parallélisme sans vous soucier du verrouillage, à condition que vous adoptiez des comportements sans état (c’est-à-dire que les fonctions de votre pipeline de traitement de flux n’interagissent pas en lisant ou en écrivant dans une variable écrite par un autre).

À quoi d’autre aimeriez-vous que le programme ressemble, à tel point qu’il il sera facile de travailler avec? Vous voudriez qu’il soit bien structuré, avec une hiérarchie de classe compréhensible reflétant la structure du système; il existe même des moyens d’estimer cette structure en utilisant des métriques de couplage (à quel point les parties du système sont interdépendantes) et de cohésion (à quel point les différentes parties du système sont liées).

Mais pour de nombreux programmeurs, la principale préoccupation au jour le jour est le débogage pendant la maintenance: ce code s’est écrasé parce qu’il a observé une valeur inattendue. Pourquoi est-ce ainsi et comment cela s’est-il passé? Pensez seulement au nombre de vos problèmes d’entretien qui entrent dans cette catégorie!  Il s’avère que les idées d’effets secondaires et d’immutabilité, que la programmation fonctionnelle favorise, peuvent aider. Examinons cela plus en détail.

13.1.1. Données mutables partagées

En fin de compte, la raison des problèmes de valeur de variable inattendus dont nous venons de parler est que les structures de données mutables partagées sont lues et mises à jour par plus d’une des méthodes utilisées par votre centre de maintenance. Supposons que plusieurs classes gardent une référence à une liste. Qui possède cette liste? Que faire si une classe la modifie? Est-ce que les autres classes attendent ce changement? Comment les autres classes apprennent-elles ce changement? Doivent-elles être informés de ce changement pour satisfaire à toutes les hypothèses de cette liste, ou devraient-elles en faire une copie défensive? En d’autres termes, les structures de données mutables partagées rendent plus difficile le suivi des changements dans les différentes parties de votre programme. La figure 13.1 illustre cette idée.
Figure 13.1. Un mutable partagé entre plusieurs classes. Il est difficile de comprendre qui la possède

Considérons un système qui ne mute aucune structure de données. Ce serait un rêve à maintenir parce que vous n’auriez pas de mauvaises surprises à propos d’un objet quelque part qui modifie de façon inattendue une structure de données! Une méthode qui ne modifie ni l’état de sa classe englobante, ni l’état de tous les autres objets et renvoie ses résultats entiers en utilisant return, est appelée pure ou sans effets secondaires.

Qu’est-ce qui constitue un effet secondaire plus concrètement? En un mot, un effet secondaire est une action qui n’est pas totalement incluse dans la fonction elle-même. Voici quelques exemples:

• Modification d’une structure de données en place, y compris l’affectation à n’importe quel champ, à l’exception de l’initialisation dans un constructeur (par exemple, les méthodes setter)
• Lancer une exception
• Effectuer des opérations d’E / S telles que l’écriture dans un fichier

Une autre façon de regarder cette idée d’aucun effet secondaire est de considérer les objets immuables. Un objet immuable est un objet qui ne peut pas changer d’état après son instanciation, de sorte qu’il ne peut pas être affecté par les actions d’une fonction. Cela signifie qu’une fois que les objets immuables sont instanciés, ils ne peuvent jamais entrer dans un état inattendu. Vous pouvez les partager sans avoir à les copier, et ils sont thread-safe car ils ne peuvent pas être modifiés.

L’idée d’absence d’effets secondaires peut apparaître comme une restriction assez sévère, et vous pouvez douter que de vrais systèmes puissent être construits de cette manière. Nous espérons vous en convaincre à la fin du chapitre. La bonne nouvelle est que les composants des systèmes qui adoptent cette idée peuvent utiliser le parallélisme multicœur sans utiliser le verrouillage, car les méthodes ne peuvent plus interférer les unes avec les autres. En outre, c’est génial pour comprendre immédiatement quelles parties du programme sont indépendantes.

Ces idées proviennent de la programmation fonctionnelle, vers laquelle nous nous tournons dans la section suivante. Mais d’abord, explorons l’idée de la programmation déclarative, sur laquelle repose la programmation fonctionnelle.

13.1.2. Programmation déclarative

Il y a deux façons de penser à la mise en œuvre d’un système en écrivant un programme. L’une d’elle sur la façon dont les choses sont faites: « d’abord faire ceci, puis mettre à jour cela, alors … » Par exemple, si vous voulez calculer la transaction la plus chère dans une liste, vous exécuterez typiquement une séquence de commandes: prendre une transaction de la liste et la comparer avec la transaction provisoire la plus chère; si c’est plus cher, alors il devient le plus cher provisoire; répétez avec la transaction suivante dans la liste et ainsi de suite.

Ce style de programmation est un excellent choix pour la programmation orientée objet classique, parfois appelée programmation impérative, car elle contient des instructions qui imitent le vocabulaire de bas niveau d’un ordinateur (par exemple, affectation, branchement conditionnel et boucles), comme indiqué dans ce code:

L’inverse se concentre plutôt sur ce qui doit être fait. Vous avez vu dans les chapitres 4 et 5 qu’en utilisant l’API Streams, vous pouvez spécifier cette requête comme suit:

Le détail de la façon dont cette requête est implémentée est laissé à la bibliothèque. Nous nous référons à cette idée comme itération interne. Le grand avantage est que votre requête se lit comme l’énoncé du problème, et à cause de cela, il est clair de comprendre immédiatement par rapport à essayer de comprendre ce que fait une séquence de commandes.

Ce style « quoi » est souvent appelé programmation déclarative. Vous donnez des règles disant ce que vous voulez, et vous vous attendez à ce que le système décide comment l’atteindre. C’est génial car il se lit plus proche de l’énoncé du problème.

13.1.3. Pourquoi la programmation fonctionnelle?

La programmation fonctionnelle illustre cette idée de programmation déclarative (« dites simplement ce que vous voulez, en utilisant des expressions qui n’interagissent pas, et pour lesquelles le système peut choisir l’implémentation ») et le calcul sans effets secondaires expliqué précédemment. Comme nous en avons discuté, ces deux idées peuvent vous aider à mettre en œuvre et à maintenir les systèmes plus facilement.

Notez que certaines fonctionnalités de langage telles que les opérations de composition et les comportements passés en paramètre, que nous avons présentées au chapitre 3 en utilisant des expressions lambda, sont nécessaires pour aider à lire et écrire du code de manière naturelle en utilisant un style déclaratif. En utilisant des flux, vous étiez capable d’enchaîner plusieurs opérations pour exprimer une requête compliquée. Ces caractéristiques caractérisent les langages de programmation fonctionnels; nous les regardons plus attentivement sous le couvert de combinateurs dans le chapitre suivant, à la section 14.5.

Pour rendre les choses tangibles et les relier aux nouvelles fonctionnalités de Java 8, nous définissons concrètement l’idée de la programmation fonctionnelle et de sa représentation en Java. Ce que nous aimerions transmettre est qu’en utilisant le style de programmation fonctionnelle, vous pouvez écrire des programmes sérieux sans se soucier des effets secondaires.

13.2. Qu’est-ce que la programmation fonctionnelle?

La réponse trop simpliste à « Qu’est-ce que la programmation fonctionnelle? » Est « programmation en utilisant des fonctions. » Alors, quelle est une fonction?

Il est facile d’imaginer une méthode prenant un int et un double comme arguments et produisant un double – et ayant aussi l’effet secondaire de compter le nombre de fois où elle a été appelée en mettant à jour une variable mutable, comme illustré à la figure 13.2.

Figure 13.2. Une fonction avec effets secondaires

Mais dans le contexte de la programmation fonctionnelle, une fonction correspond à une fonction mathématique: elle prend zéro ou plusieurs arguments, donne un ou plusieurs résultats et n’a pas d’effets secondaires. Vous pouvez le voir comme une boîte noire, qui prend quelques entrées et produit quelques sorties, comme illustré dans la figure 13.3.

Figure 13.3. Une fonction sans effets secondaires

La distinction entre ce type de fonction et les méthodes que vous voyez dans les langages de programmation comme Java est cruciale. (L’idée des fonctions mathématiques comme log ou sin ayant de tels effets secondaires est impensable.) En particulier, les fonctions mathématiques appelées de façon répétée avec les mêmes arguments retournent toujours les mêmes résultats. Cela exclut des méthodes telles que Random.nextInt, et nous discutons plus tard de cette idée sous le concept de transparence référentielle.

Quand nous disons fonctionnel, nous voulons dire «comme les mathématiques – pas d’effets secondaires». Maintenant, une subtilité de programmation apparaît. Est-ce que nous voulons dire que chaque fonction est construite uniquement en utilisant des fonctions et bien sûr des idées mathématiques telles que if-then-else? Ou pourrions-nous permettre à une fonction de faire des choses non fonctionnelles en interne, tant qu’elle n’expose aucun de ces effets secondaires au reste du système? En d’autres termes, si nous en tant que programmeurs effectuons un effet secondaire qui ne peut pas être observé par les appelants, cet effet secondaire existe-t-il réellement? L’appelant n’a pas besoin de savoir ou de s’en soucier, car il ne peut pas les affecter.

Lorsque nous souhaitons mettre l’accent sur la différence, nous nous référons à la première en tant que programmation fonctionnelle pure (nous y reviendrons plus tard dans le chapitre) et la seconde en tant que style de programmation fonctionnelle.

13.2.1. Style fonctionnel de Java

En pratique, vous ne pouvez pas programmer complètement dans un style purement fonctionnel en Java. Par exemple, le modèle d’E / S de Java consiste en des méthodes d’effets secondaires (l’appel de Scanner.nextLine a pour effet secondaire de consommer une ligne à partir d’un fichier, donc l’appeler deux fois donne généralement des résultats différents). Néanmoins, il est possible d’écrire des composants de base de votre système comme s’ils étaient purement fonctionnels. En Java, vous allez écrire des programmes dans un style fonctionnel. D’abord, il y a une autre subtilité à propos de la personne qui voit vos effets secondaires et donc la signification de fonctionnelle. Supposons qu’une fonction ou une méthode n’a pas d’effets secondaires, sauf qu’elle incrémente un champ juste après l’entrée et le décrémente juste avant la sortie. Du point de vue d’un programme constitué d’un seul fil, cette méthode n’a pas d’effets secondaires visibles et peut être considérée comme un style fonctionnel. D’un autre côté, si un autre thread pouvait inspecter le champ, ou pire, appeler la méthode simultanément, il ne serait pas fonctionnel. Vous pouvez masquer ce problème en enveloppant le corps de cette méthode avec un verrou, ce qui vous permettra à nouveau de faire valoir que la méthode est fonctionnelle. Mais en faisant cela, vous auriez perdu la possibilité d’exécuter deux appels à la méthode en parallèle en utilisant deux cœurs sur votre processeur multicœur. Votre effet secondaire peut ne pas être visible pour un programme, mais il est visible pour le programmeur en termes d’exécution plus lente!

Notre directive est que pour être considéré comme un style fonctionnel, une fonction ou une méthode ne peut muter que des variables locales. De plus, les objets auxquels il fait référence devraient être immuables. Nous entendons par là que tous les champs sont définitifs et que tous les champs de référence se réfèrent de manière transitoire à d’autres objets immuables. Plus tard, vous pouvez également autoriser les mises à jour des champs d’objets nouvellement créés dans la méthode, et qui ne sont donc pas visibles ailleurs, et qui ne sont pas enregistrés pour affecter le résultat d’un appel ultérieur.

Notre ligne directrice précédente est incomplète, et il y a un besoin supplémentaire d’être fonctionnel, ce qui semble moins important au début. Pour être considérée comme un style fonctionnel, une fonction ou une méthode ne doit pas générer d’exception. Il y a une explication simple: vous ne pouvez pas lancer une exception car cela signifie qu’un résultat est signalé autrement que comme un résultat correct via le retour comme dans le modèle de boîte noire discuté précédemment. Mais alors cela semble contré par une utilisation mathématique pratique: bien que légalement une fonction mathématique donne exactement un résultat pour chaque valeur d’argument possible, de nombreuses opérations mathématiques courantes sont ce que nous devrions appeler correctement des fonctions partielles. Autrement dit, pour certaines ou la plupart des valeurs d’entrée, elles donnent exactement un résultat, mais pour d’autres valeurs d’entrée, elles ne sont pas définies et ne donnent aucun résultat. Un exemple est la division lorsque le deuxième opérande est zéro ou sqrt lorsque son argument est négatif. Il peut sembler naturel de modéliser ces situations en lançant une exception comme le fait Java. Certains auteurs avancent que des exceptions non interceptées représentant des erreurs fatales sont correctes, mais il s’agit d’attraper une exception qui représente un flux de contrôle non fonctionnel, en ce sens qu’il casse la simple métaphore de « passer des arguments, renvoyer un résultat » illustré par le modèle de boîte noire, conduisant à une troisième flèche représentant une exception, comme illustré à la figure 13.4.
Figure 13.4. Une fonction lançant une exception

Alors, comment pourriez-vous exprimer des fonctions comme la division sans utiliser d’exceptions? La réponse est d’utiliser des types comme Optional <T>: au lieu de sqrt ayant la signature « double sqrt (double) mais peut lever une exception, » il aurait la signature « Optional <Double> sqrt (double) » – soit il retourne une valeur cela représente le succès ou indique dans sa valeur de retour qu’il n’a pas pu effectuer l’opération demandée. Et oui, cela signifie que l’appelant doit vérifier si chaque appel de méthode peut aboutir à un Optional.empty. Cela peut sembler une affaire énorme, mais pragmatiquement, étant donné nos conseils sur la programmation fonctionnelle par rapport à la programmation fonctionnelle pure, vous pouvez choisir d’utiliser des exceptions localement, mais ne pas les exposer via des interfaces à grande échelle. risque de gonflement du code.

Enfin, pour être considérée comme fonctionnelle, votre fonction ou méthode doit appeler uniquement les fonctions de bibliothèque à effet secondaire pour lesquelles vous pouvez masquer leur comportement non fonctionnel (c’est-à-dire, s’assurer que toute mutation sur les structures de données est cachée à votre interlocuteur, peut-être copier d’abord et en attrapant toutes les exceptions qu’ils pourraient soulever). Dans la section 13.2.4, «Style fonctionnel dans la pratique», vous verrez un exemple où nous cachons l’utilisation de la fonction List.add (elle a des effets secondaire) à l’intérieur de notre méthode insertAll en copiant la liste.

Ces prescriptions peuvent souvent être marquées à l’aide de commentaires ou en déclarant une méthode avec une annotation de marqueur – et correspondent aux restrictions que nous avons placées sur les fonctions que nous avons transmises aux opérations de traitement de flux parallèles telles que Stream.map dans les chapitres 4-7.

Enfin, pour des raisons pragmatiques, il peut être pratique pour le code de style fonctionnel de toujours afficher des informations de débogage dans une forme de fichier de log. Oui, cela signifie que le code ne peut pas être strictement décrit comme fonctionnel, mais en pratique vous retenez la plupart des avantages de la programmation de style fonctionnel.

13.2.2. Transparence référentielle

Les restrictions sur «aucun effet secondaire visible» (pas de structure de mutation visible pour les appelants, pas d’E / S, pas d’exceptions) codent le concept de transparence référentielle. Une fonction est référentiellement transparente si elle renvoie toujours la même valeur de résultat lorsqu’elle est appelée avec la même valeur d’argument. La méthode String.replace est référentiellement transparente car « raoul » .replace (‘r’, ‘R’) produira toujours le même résultat (la méthode replace renvoie une nouvelle String avec tout ‘r’ minuscule remplacé par ‘R’ majuscule) plutôt que de mettre à jour son objet afin qu’il puisse être considéré comme une fonction.

En d’autres termes, une fonction produit toujours le même résultat avec la même entrée, peu importe où et quand elle est invoquée. Cela explique aussi pourquoi nous ne considérons pas Random.nextInt comme fonctionnel. En Java, l’utilisation d’un objet Scanner pour obtenir l’entrée du clavier d’un utilisateur enfreint la transparence référentielle, car l’appel de la méthode nextLine peut produire un résultat différent à chaque appel. Mais l’addition de deux variables int finit toujours par produire le même résultat, car le contenu des variables ne peut jamais changer.

La transparence référentielle est une grande propriété pour la compréhension du programme. Il comprend également une optimisation de sauvegarde au lieu de recalculer pour les opérations coûteuses ou de longue durée, qui passe sous le nom de: mémoization ou la mise en cache. Bien qu’important,  nous verrons ce concept au prochain chapitre, dans la section 14.5.

En Java, il y a une légère complication sur la transparence référentielle. Supposons que vous faites deux appels à une méthode qui renvoie une liste. Ensuite, les deux appels peuvent renvoyer des références à des listes distinctes en mémoire mais contenant les mêmes éléments. Si ces listes devaient être vues comme des valeurs orientées objet mutables (et donc non identiques) alors la méthode ne serait pas référentiellement transparente. Si vous envisagez d’utiliser ces listes comme des valeurs pures (immuables), il est logique de voir les valeurs comme égales et donc la fonction comme référentiellement transparente. En général, dans le code de style fonctionnel, vous choisissez de considérer ces fonctions comme référentiellement transparentes. Nous discuterons de ce problème à nouveau dans le chapitre suivant, à la section 14.5. Nous explorons maintenant la question de savoir s’il faut muter à partir d’une perspective plus large.

13.2.3. Programmation orientée objet ou fonctionnelle

Nous commençons par opposer la programmation fonctionnelle à la programmation orientée objet (extrême) classique avant d’observer que Java 8 voit ces styles comme de simples extrêmes du spectre orienté objet. En tant que programmeur Java, sans y penser consciemment, vous utiliserez certainement certains aspects de la programmation de style fonctionnel et certains aspects de ce que nous appellerons la programmation orientée objet extrême. Comme nous l’avons remarqué dans le chapitre 1, les changements de matériel (par exemple, multicœur) et de programmeur (par exemple, des requêtes de type base de données pour manipuler les données) poussent un peu plus les styles d’ingénierie logicielle Java vers l’extrémité fonctionnelle de ce spectre. L’un des objectifs de ce livre est de vous aider à vous adapter au changement climatique.

À une extrémité du spectre se trouve la vue extrême orientée objet: tout est un objet et les programmes fonctionnent en mettant à jour les champs et les méthodes d’appel qui mettent à jour leur objet associé. À l’autre extrémité du spectre se trouve le style de programmation fonctionnelle référentiellement transparent d’aucune mutation (visible). En pratique, les programmeurs Java ont toujours mélangé ces styles. Vous pouvez traverser une structure de données en utilisant un Iterator contenant un état interne modifiable mais l’utiliser pour calculer, par exemple, la somme des valeurs dans la structure de données de manière fonctionnelle (en Java, cela peut inclure des variables locales mutantes). L’un des objectifs des sections suivantes de ce chapitre et plus généralement du chapitre suivant est de discuter des techniques de programmation et d’introduire des fonctionnalités de programmation fonctionnelle pour vous permettre d’écrire des programmes plus modulaires et plus adaptés aux processeurs multicœurs. Considérez ces idées comme des armes supplémentaires dans votre arsenal de programmation.

13.2.4. Style fonctionnel en pratique

Commençons par résoudre un exercice de programmation donné aux étudiants débutants pour illustrer le style fonctionnel: Avec une valeur List <Integer>, par exemple {1, 4, 9}, construisez une valeur List <List <Integer >> dont tous les membres sont des sous-ensembles de {1, 4, 9} dans n’importe quel ordre. Les sous-ensembles de {1, 4, 9} sont {1, 4, 9}, {1, 4}, {1, 9}, {4, 9}, {1}, {4}, {9} et {}.

Il y a huit sous-ensembles incluant le sous-ensemble vide, écrit {}. Chaque sous-ensemble est représenté par le type List<Integer>, ce qui signifie que la réponse est de type Liste <Liste <Entier >>.

Les élèves ont souvent du mal à penser comment démarrer et ont besoin d’être incités en remarquant que « les sous-ensembles de {1, 4, 9} en contiennent 1 ou n’en ont pas. » Ceux qui ne le sont pas sont simplement des sous-ensembles de {4,9}, et celles qui le sont peuvent être obtenues en prenant les sous-ensembles de {4, 9} et en insérant 1 dans chacun d’eux.

La solution produit {{}, {9}, {4}, {4, 9}, {1}, {1, 9}, {1, 4}, {1, 4, 9}} lorsqu’elle reçoit {1 , 4, 9} en entrée. Essayez-le lorsque vous avez défini les deux méthodes manquantes.

Passons en revue ce que vous venez de faire. Vous avez supposé que les méthodes manquantes insertAll et concat sont elles-mêmes fonctionnelles et déduites que vos sous-ensembles de fonctions le sont également, car aucune opération ne mute une structure existante. (Si vous êtes familier avec les mathématiques, alors vous reconnaîtrez cet argument comme étant établit par induction.)

Maintenant, regardons la définition de insertAll. Voici le premier point de danger. Supposons que vous ayez défini insertAll pour qu’il mute ses arguments, peut-être en mettant à jour tous les éléments de subans à contenir en premier. Ensuite, le programme provoquerait incorrectement la modification des subans de la même manière que subans2, aboutissant à une réponse contenant mystérieusement huit copies de {1,4,9}. Vous définissez plutôt insertAll fonctionnellement comme suit:

Notez que vous créez une nouvelle liste qui contient tous les éléments de subans. Vous profitez du fait qu’un objet Integer est immuable (sinon vous devrez aussi cloner chaque élément). Le focus crée en considérant des méthodes comme insertAll comme fonctionnel vous donne un endroit naturel pour mettre tout ce code copié dans la méthode  insertAll plutôt que dans ses appelants.

Enfin, vous devez définir la méthode concat. Dans ce cas, il existe une solution simple, que nous vous prions de ne pas utiliser (nous la montrons seulement pour que vous puissiez comparer les différents styles):

Au lieu de cela, nous vous suggérons d’écrire ceci:

Pourquoi? La deuxième version de concat est une fonction pure. Il peut utiliser une mutation (ajouter des éléments à la liste r) en interne, mais il renvoie un résultat basé sur ses arguments et ne modifie aucun d’entre eux. En revanche, la première version s’appuie sur le fait qu’après l’appel concat (subans, subans2), personne ne se réfère à nouveau à la valeur des subans. Il s’avère que, pour notre définition des sous-ensembles, c’est effectivement le cas, donc il est préférable d’utiliser la version moins chère de la concaténation. Eh bien, cela dépend de la façon dont vous appréciez votre temps passé plus tard à la recherche de bugs obscurs par rapport au coût supplémentaire de faire une copie.

Peu importe à quel point vous estimez que la fonction impure  concat est « seulement à utiliser quand le premier argument peut être écrasé arbitrairement, et seulement destiné à être utilisé dans la méthode des sous-ensembles, et tout changement aux sous-ensembles doit être revu à la lumière de ce commentaire ,  » quelqu’un le trouvera parfois utile dans un morceau de code où il semble apparemment fonctionner, et votre futur problème cauchemar de débogage vient de naître. Nous revoyons ce problème dans le chapitre suivant de la section 14.2, «Structures de données persistantes».

Point à retenir: penser aux problèmes de programmation en termes de méthodes fonctionnelles qui ne sont caractérisées que par leurs arguments d’entrée, et leur résultat de sortie (c’est-à-dire quoi faire) est souvent plus productif que de penser à comment le faire et quoi muter aussi tôt dans le cycle de conception. Nous passons maintenant à la récursivité plus en détail, une technique promue dans la programmation fonctionnelle pour vous permettre de réfléchir plus en termes de quoi faire.

13.3. Récursion VS itération

Les langages de programmation fonctionnels purs n’incluent généralement pas de constructions itératives comme while et for loops. Pourquoi? Parce que ces constructions sont souvent une invitation cachée à utiliser la mutation. Par exemple, la condition dans une boucle while doit être mise à jour; sinon, la boucle exécutera zéro ou un nombre infini de fois. Mais pour beaucoup de cas d’utilisation les boucles sont parfaitement bien. Nous avons fait valoir que pour être fonctionnel, vous êtes autorisé à subir une mutation si personne ne peut vous voir le faire, ce qui signifie qu’il est acceptable de muter des variables locales. En utilisant la boucle for-each en Java, for (Apple a: apples {} dans l’Iterator montré ici:

Ce n’est pas un problème parce que les mutations (à la fois changer l’état de l’Iterator avec la méthode suivante et l’assigner à la variable apple dans le corps while) ne sont pas visibles pour l’appelant de la méthode où les mutations se produisent. Mais l’utilisation d’une boucle for-each, telle qu’un algorithme de recherche, comme suit est problématique car le corps de la boucle met à jour une structure de données partagée avec l’appelant:

En effet, le corps de la boucle a un effet secondaire qui ne peut être ignoré en tant que style fonctionnel: il mute l’état de l’objet stats, qui est partagé avec d’autres parties du programme.

Pour cette raison, les langages de programmation fonctionnels purs tels que Haskell omettent entièrement ces opérations d’effets secondaires! Comment allez-vous écrire des programmes? La réponse théorique est que chaque programme peut être réécrit pour éviter l’itération en utilisant la récursivité à la place, ce qui ne nécessite pas de mutabilité. L’utilisation de la récursivité vous permet de supprimer les variables d’itération mises à jour étape par étape. Un problème scolaire classique consiste à calculer la fonction factorielle (pour les arguments positifs) de manière itérative et récursive (nous supposons que l’entrée est> 1), comme indiqué dans les deux figures suivantes.

Figure 13.1. Factoriel itératif

Figure 13.2. Factoriel récursif

La première figure montre un formulaire basé sur une boucle standard: les variables r et i sont mises à jour à chaque itération. La deuxième figure montre une définition récursive (la fonction s’appelle elle-même) sous une forme plus mathématiquement familière. En Java, les formes récursives sont généralement moins efficaces, et nous en discuterons sous peu.

Mais si vous avez lu les chapitres précédents de ce tutoriel, alors vous savez que les flux Java 8 offrent une manière déclarative encore plus simple de définir factorielle, comme le montre la liste suivante.

Figure 13.3. Flux factoriel

Passons maintenant à l’efficacité. En tant qu’utilisateurs de Java, vous devriez vous méfier des zélateurs de programmation fonctionnelle qui vous disent que vous devriez toujours utiliser la récursivité au lieu de l’itération. En général, la réalisation d’un appel de fonction récursif est beaucoup plus coûteuse que l’instruction de branchement au niveau machine unique nécessaire pour itérer. Pourquoi? Chaque fois que la fonction factorialRecursive est appelée, un nouveau cadre de pile est créé sur la pile d’appels pour contenir l’état de chaque appel de fonction (la multiplication dont il a besoin) jusqu’à ce que la récursion soit terminée. Cela signifie que votre définition récursive de factorielle prendra de la mémoire proportionnelle à son entrée. C’est pourquoi si vous exécutez factorialRecursive avec une grande entrée, vous risquez de recevoir une erreur StackOverflowError:

Est-ce que cela signifie que la récursivité est inutile? Bien sûr que non! Les langages fonctionnels apportent une réponse à ce problème: l’optimisation de la queue. L’idée de base est que vous pouvez écrire une définition récursive de factorielle où l’appel récursif est la dernière chose qui arrive dans la fonction (nous disons que l’appel est en position de queue). Cette forme différente de style de récursivité peut être optimisée pour fonctionner rapidement. Pour illustrer, voici une définition récursive de la queue de factorielle

Figure 13.4. factoriel récursif en position de fin de queue

La fonction factorialHelper est récursive en queue car l’appel récursif est la dernière chose qui arrive dans la fonction. Par contraste dans notre définition précédente de factorielle-récursive, la dernière chose était une multiplication de n et le résultat d’un appel récursif.

Cette forme de récursivité est utile car au lieu de stocker chaque résultat intermédiaire de la récursivité sur des cadres de pile différents, le compilateur peut décider de réutiliser une seule trame de pile. En effet, dans la définition de factorialHelper, les résultats intermédiaires (les résultats partiels de la factorielle) sont passés directement comme arguments à la fonction. Il n’est pas nécessaire de garder une trace du résultat intermédiaire de chaque appel récursif sur un cadre de pile séparé – il est accessible directement via l’argument de la fonction.

Les figures 13.5 et 13.6 illustrent la différence entre les définitions récursives et récursives en queue de la factorielle.

Figure 13.5. Définition récursive de factorielle, qui nécessite plusieurs cadres de pile

Figure 13.6. Définition récursive en queue de la factorielle, qui peut réutiliser un seul cadre de pile

 

La mauvaise nouvelle est que Java ne supporte pas ce type d’optimisation. Mais l’adoption de la récursion de queue peut être une meilleure pratique que la récursivité classique, car elle ouvre la voie à l’optimisation du compilateur. De nombreux langages JVM modernes tels que Scala et Groovy peuvent optimiser les utilisations de la récursivité, qui sont équivalentes à l’itération (elles s’exécuteront à la même vitesse). Cela signifie que les adhérents purs-fonctionnels peuvent avoir leur gâteau de pureté et le manger aussi efficacement.

Le conseil en écrivant Java 8 est que vous pouvez souvent remplacer l’itération avec des flux pour éviter la mutation. En outre, l’itération peut être remplacée par la récursivité quand elle vous permet d’écrire un algorithme de manière plus concise et sans effets secondaires. En effet, la récursivité peut faciliter la lecture, l’écriture et la compréhension des exemples (par exemple, dans l’exemple des sous-ensembles montré précédemment), et l’efficacité du programmeur est souvent plus importante que de petites différences dans le temps d’exécution.

Dans cette section, nous avons discuté de la programmation fonctionnelle, mais nous avons seulement utilisé l’idée d’une méthode fonctionnelle – tout ce que nous avions dit aurait été appliqué à la toute première version de Java. Dans le chapitre suivant, nous examinons les possibilités étonnantes et puissantes offertes par l’introduction de fonctions de première classe dans Java 8.

13.4. Résumé

Voici les concepts clés que vous devriez retenir de ce chapitre:

• La réduction des structures de données mutables partagées peut vous aider à maintenir et déboguer vos programmes sur le long terme.
• La programmation de style fonctionnel favorise les méthodes sans effets secondaires et la programmation déclarative.
• Les méthodes basée sur un style fonctionnel ne sont caractérisées que par leurs arguments d’entrée et leur résultat de sortie.
• Une fonction est référentiellement transparente si elle renvoie toujours la même valeur de résultat lorsqu’elle est appelée avec la même valeur d’argument.
• Les constructions itératives telles que les boucles while peuvent être remplacées par la récursivité.
• La récursion de queue peut être une meilleure pratique que la récursivité classique en Java, car elle ouvre la voie à l’optimisation du compilateur.