programmation-fonctionnelle

7/21/2019 programmation-fonctionnelle

http://slidepdf.com/reader/full/programmation-fonctionnelle-56d993984f63e 1/14

La programmation fonctionnelle

Par Jerôme Valloire

Date de publication : 9 juin 2015

Les conférences d'Hadi Hariri, développeur et évangéliste technologique chez JetBrains,sont pour moi des conférences à ne pas manquer à Devoxx France, non seulement dufait de ses qualités indéniables d'orateur, mais aussi de la diversité et de la pertinence dessujets traités.

Cette année, Hadi Hariri a décidé de s'attaquer à la programmation fonctionnelle au traversd'une conférence intitulée “Refactoring to Functional ” au cours de laquelle il est revenu sur les avantages de ce paradigme de programmation en s'appuyant sur différents exemplesconcrets.

Vous pouvez donner votre avis sur cet article sur notre forum : Commentez

http://www.developpez.net/forums/showthread.php?t=1535178

https://twitter.com/hhariri

http://www.developpez.com/



La programmation fonctionnelle par Jerôme Valloire

- 2 -Les sources présentées sur cette page sont libres de droits et vous pouvez les utiliser à votre convenance. Par contre, la page de

présentation constitue une œuvre intellectuelle protégée par les droits d'auteur. Copyright ® 2015 Jerôme Valloire. Aucune reproduction,

même partielle, ne peut être faite de ce site et de l'ensemble de son contenu : textes, documents, images, etc. sans l'autorisation

expresse de l'auteur. Sinon vous encourez selon la loi jusqu'à trois ans de prison et jusqu'à 300 000 € de dommages et intérêts.

http://soat.developpez.com/tutoriels/programmation/programmation-fonctionnelle/

I - Introduction : pourquoi se tourner vers la programmation fonctionnelle ?..............................................................3II - Quels langages utiliser ?........................................................................................................................................3III - L'approche fonctionnelle en action....................................................................................................................... 4

III-A - Une première fonction : itDoesSomething…................................................................................................4III-B - Un exemple de refactoring étape par étape................................................................................................5

IV - Et les patterns Object-Oriented dans tout ça ?....................................................................................................6

IV-A - Patron de méthode (“Template Method Pattern“)........................................................................................7IV-B - Stratégie.......................................................................................................................................................7IV-C - Injection de dépendances........................................................................................................................... 8

V - Apprendre à réfléchir « fonctionnel ».................................................................................................................... 9V-A - Des fonctions comme primitives réutilisables du langage............................................................................9V-B - Des données à la recherche de l'immutabilité........................................................................................... 10

VI - Programmation fonctionnelle et performances...................................................................................................11VI-A - Mémoïzation...............................................................................................................................................11VI-B - Récursion terminale...................................................................................................................................12VI-C - Fonctions inline..........................................................................................................................................13

VII - Quid de tous les concepts effrayants de la programmation fonctionnelle ?......................................................13VII-A - Foncteurs (“Functors“).............................................................................................................................. 13

VII-B - Monades................................................................................................................................................... 13VIII - Conclusion........................................................................................................................................................ 14IX - Remerciements...................................................................................................................................................14












I - Introduction : pourquoi se tourner vers la programmation fonctionnelle ?

Pour Hadi Hariri, la programmation fonctionnelle doit permettre aux développeurs :

• d'écrire moins de code ;

• d'écrire du code plus expressif ;• d'écrire du code plus correct ;• d'écrire du code plus performant.

De plus, et il faut bien se l'avouer, la programmation fonctionnelle est à la mode aujourd'hui, avec l'avènement dansle monde de l'entreprise de langages tels que Scala, Haskell… mais aussi avec l'introduction des lambdas dans Javadepuis Java 8.

Ainsi, l'approche fonctionnelle, longtemps considérée comme purement académique, connaît aujourd'hui un essor réel, bouleversant complètement nos habitudes de programmation impérative.

Par conséquent, sa mise en œuvre requiert un effort certain d'apprentissage pour être efficacement utilisée.

II - Quels langages utiliser ?

Un langage fonctionnel se caractérise par plusieurs critères :

• l'utilisation de fonctions en tant qu'objets de première classe (“first-class citizens“), celles-ci étant des données,au même titre que toutes autres données :

• fonctions d'ordre supérieur (“High-Order functions“) : qui peuvent prendre une ou plusieurs fonctionscomme paramètres et renvoyer une nouvelle fonction comme valeur de retour,

• lambda : fonctions anonymes nommées ainsi en référence au Lambda-calcul ;

• la possibilité de manipuler des données immuables.

Il existe de nombreux langages fonctionnels :

• Lisp, l'ancêtre de tous les langages fonctionnels, créé dès 1958 ;• Scheme, un dérivé de Lisp, créé en 1975 ;• La famille des langages ML (Meta Language), qui a vu le jour à la fin des années 70 et dont les principaux

représentants aujourd'hui sont SML (Standard ML) et Caml (avec OCaml) ;• Erlang, créé en 1989 ;• Haskell, créé en 1990 et qui a la particularité d'être un langage « fonctionnel pur » (sans effet de bord), ce qui

en fait LE langage fonctionnel par excellence aujourd'hui.

En plus de ces langages fonctionnels historiques, on trouve également de nombreux langages multiparadigmes, quipermettent une approche fonctionnelle :

• F#, né en 2002, qui est un langage de programmation fonctionnel, impératif et orienté objet pour la plate-forme .NET ;

• Scala, apparu en 2003 dans le but de concilier les paradigmes de programmation orientée objet et deprogrammation fonctionnelle ;

• Clojure, créé en 2007 et qui est un dialecte Lisp pour la plate-forme Java ;• Java 8, mais également les versions précédentes, avec l'ajout de bibliothèques tierces telles que Guava

ou Functional Java ;• et bien d'autres…

Pour sa présentation, Hadi Hariri a utilisé Kotlin, un autre langage basé sur la JVM, qui se rapproche de Scala. Ànoter que ce langage est développé par JetBrains, d'où son choix « naturel » pour cette conférence.


http://www.functionaljava.org/

https://github.com/google/guava

http://fr.wikipedia.org/wiki/Lambda-calcul











1. fun basicFunction(parameter: String): String {

2. return parameter

3. }

4.

5. fun singleLineFunction(x: Int, y: Int) = x + y6.

7. fun higherOrderFunction(func: (Int) -> Int) { ... }

8.

9. val lambda = { (x: Int, y: Int) -> x + y }

Pour qu'une fonction soit considérée comme pure, les mêmes données d'entrée doivent toujours produire le mêmeré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 nechange 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 opération d'affection. C'est le cas du langage Haskell.

III - L'approche fonctionnelle en action

III-A - Une première fonction : itDoesSomething…

Hadi Hariri nous propose tout d'abord la fonction suivante :

1. fun itDoesSomething(elements: List<String>): Map<String, Int> {

2. var i = 03. val results = hashMapOf<String, Int>()

4. while (i < elements.size) {

5. val element = results.get(elements[i])

6. if (element != null) {

7. results.set(elements[i], element + 1)8. } else {

9. results.set(elements[i], 1)

10. }

11. i++12. }

13. return results

14. }

Comme son nom l'indique, cette fonction fait… quelque chose !

Mais vous en conviendrez, il n'est pas particulièrement aisé de comprendre le but de cette fonction sans analyser précisément chacune de ses lignes de code, où s'entremêlent données et opérations sur ces données.

Cependant, il y a fort à parier que, si vous analysez le code des projets sur lesquels vous travaillez, ce type de codeimpératif est légion… tout en espérant que les noms de ces fonctions sont quand même un peu plus explicites !

Une version fonctionnelle de cette fonction est la suivante :

1. fun itDoesSomething(elements: List<String>): List<Pair<String, Int>> {

2. return elements.groupBy {

3. it

4. }.map {5. Pair(it.key, it.value.count())

6. }

7. }




































Ce code est non seulement plus concis, mais également plus expressif et même sans connaître les fonctions groupByet map, on peut commencer à en deviner le but : déterminer le nombre d'occurrences de chaque chaîne de caractèresde la liste passée en paramètre.

III-B - Un exemple de refactoring étape par étape

Nouvel exemple, avec cette fois-ci une fonction visant à filtrer une liste d'albums de Pink Floyd, le groupe préféré de

Hadi Hariri, pour ne conserver que les tops albums, classés 1er au Royaume-Uni et aux États-Unis.

1. data class Album(val title: String, val year: Int, val chartUK: Int, val chartUS: Int)2. val albums = listOf(

3. Album("The Dark Side of the Moon", 1973, 2, 1),

4. Album("The Wall", 1979, 3, 1),

5. Album("Wish You Were Here", 1975, 1, 1),6. Album("Animals", 1977, 2, 3),

7. Album("The Piper at the Gates of Dawn", 1967, 6, 131),

8. Album("The Final Cut", 1983, 1, 6),

9. Album("Meddle", 1971, 3, 70),10. Album("Atom Hearth Mother", 1970, 1, 55),

11. Album("Ummagumma", 1969, 5, 74),12. Album("A Sauceful of Secrets", 1968, 9, 0),13. Album("More", 1969, 9, 153))

14.

15. fun topUSandUK_v1(albums: List<Album>): List<Album> {

16. val hits = arrayListOf<Album>()

17. for (i: Int in 0..albums.count()-1) {

18. if (albums[i].chartUK == 1 && albums[i].chartUS == 1) {

19. hits.add(albums[i])

20. }21. }

22. return hits

23. }

Cette fonction utilise une boucle for classique afin de tester une condition sur chacun des albums de la liste.

Cependant, on note ici la présence de la variable ‘i', utilisée comme index de boucle ; il s'agit d'une variable d'étatque l'on peut aisément éliminer en utilisant une structure de type for… in :


2. val hits = arrayListOf<Album>()

3. for (album in albums) {

4. if (album.chartUK == 1 && album.chartUS == 1) {

5. hits.add(album)

6. }

7. }

8. return hits

9. }

En rajoutant un peu de sucre syntaxique, on obtient la fonction suivante :

1. fun topUSandUK_v3(albums: List<Album>): List<Album> {2. val hits = arrayListOf<Album>()

3. albums.forEach {

4. if (it.chartUK == 1 && it.chartUS == 1) {

5. hits.add(it)

6. }

7. }

8. return hits

9. }

Suite à ces modifications, la boucle for a été remplacée par une fonction forEach, qui reprend le même bloc de code.





























On se rapproche du fonctionnel, mais un problème demeure, car on continue à se concentrer sur la manière de fairele traitement (le how) et non sur ce que l'on veut réellement faire (le what).

Il reste donc à éliminer le bloc conditionnel à base de ifen utilisant une nouvelle fonction, la fonctionfilter avec unprédicat :


2. return albums.filter {

3. (it.chartUK == 1 && it.chartUS == 1)4. }

5. }

Rien de magique dans ce refactoring : on a simplement extrait du code en termes de traitements et de données,puis mis en place une fonction pour les faire interagir, cette fonction filter assurant le parcours de la liste et le testde la condition.

Il existe beaucoup d'autres fonctions de ce type qui sont des applications du concept de f onctions d'ordre supérieur ,et qui prennent en paramètres d'autres fonctions.

Hadi Hariri nous présente également la fonction map, qui permet de réaliser simplement des transformations dedonnées :

1. fun topUSandUK_hits_years_v1(albums: List<Album>): List<Int> {

2. val hits = albums.filter {

3. (it.chartUK == 1 && it.chartUS == 1)

4. }5. val years = arrayListOf<Int>()

6. hits.forEach {

7. years.add(it.year)8. }

9. return years

10. }

11.

12. fun topUSandUK_hits_years_v2(albums: List<Album>): List<Int> {13. return albums.filter {

14. (it.chartUK == 1 && it.chartUS == 1)

15. }.map {16. it.year

17. }

18. }

Dans cet exemple, on récupère les années correspondant aux tops albums et au lieu d'utiliser une boucle for (lehow), on utilise la fonction mapà laquelle on passe la fonction permettant de récupérer la propriété “year ” de chaquealbum (le what).

Ces refactorings nous permettent également de rendre le code plus concis et plus expressif, en déléguant une partie

de l'écriture de code à ceux qui mettent en place les fonctions de base du langage, les frameworks ou les bibliothèquesfonctionnelles.

L'approche fonctionnelle permet donc de se concentrer uniquement sur le what, rendant le code plus compréhensible.

IV - Et les patterns Object-Oriented dans tout ça ?

Jusque-là rien de bien nouveau si vous connaissez un peu de Scala ou si vous avez eu l'occasion d'utiliser lesStreams de Java 8.

Hadi Hariri s'attaque maintenant à certains patterns Object-Oriented, pour nous prouver qu'ils peuvent également

être modifiés en style fonctionnel, grâce à l'utilisation de fonctions.






























IV-A - Patron de méthode (“Template Method Pattern“)

En approche objet, un patron de méthode définit le squelette d'un algorithme à l'aide de méthodes abstraites dont lecomportement concret se trouve dans des sous-classes implémentant ces méthodes.

Voici un exemple d'implémentation traditionnelle de ce pattern :

1. public abstract class Record {

2. public abstract fun editRecord()

3. public abstract fun persistData()

4. public fun checkPermissions() {

5. // Check permissions

6. }

7. public fun edit() {

8. checkPermissions()

9. editRecord()

10. persistData()11. }

12. }

13.

14. public class CustomerRecord: Record() {15. override fun editRecord() {16. // Edit customer record

17. }

18. override fun persistData() {

19. // Persist customer data20. }

21. }

22.

23. public class InvoiceRecord: Record() {

24. override fun editRecord() {

25. // Edit invoice record26. }

27. override fun persistData() {

28. // Persist invoice data

29. }30. }

Une telle hiérarchie de classes est-elle réellement nécessaire alors que les seules parties qui diffèrent entre les deuxclasses d'implémentation sont les fonctions ?

En approche fonctionnelle, l'implémentation de ce pattern devient beaucoup plus simple :

1. public class RecordFunctional(val editRecord: () -> Unit, val persistData: () -> Unit ) {

2. public fun checkPermissions() {

3. // Check permissions

4. }

5. public fun edit() {

6. checkPermissions()7. editRecord()

8. persistData()

9. }10. }

Les fonctions sont ici directement passées en paramètres, ce qui permet d'éliminer tout le code “boilerplate” del'implémentation initiale.

IV-B - Stratégie

Nouvel exemple, avec cette fois le pattern stratégie appliqué à des classes définissant différents algorithmes de tris :

1. public trait SortAlgorithm {

2. public fun <T> sort(list: List<T>): List<T>





















3. }4.

5. public class QuickSort: SortAlgorithm {

6. override fun <T> sort(list: List<T>): List<T> {

7. // Processing ...

8. return sortedList

9. }

10. }11.

12. public class BubbleSort: SortAlgorithm {

13. override fun <T> sort(list: List<T>): List<T> {

14. // Processing ...

15. return sortedList

16. }

17. }18.

19. public class Sorter( private val algorithm: SortAlgorithm) {

20. public fun <T> sortList(list: List<T>): List<T> {

21. return algorithm.sort(list)

22. }

23. }

En approche objet, on définit une interface (trait en Kotlin) et différentes classes d'implémentation correspondantaux différents types de tris.

Là encore, on peut utiliser une approche fonctionnelle pour passer directement la fonction, et donc le comportementsouhaité, à la méthode de tri du Sorter :

1. public class SorterFunctional() {

2. public fun <T> sortList(list: List<T>, sortFunction: (List<T>) -> List<T>): List<T> {

3. return sortFunction(list)

4. }

5. }

La fonction sortFunction permet tout simplement de définir l'algorithme de tri, éliminant une fois de plus la nécessité

de définir les différentes classes de l'approche objet.

IV-C - Injection de dépendances

L'utilisation de l'injection de dépendances est monnaie courante aujourd'hui dans nos développements.

Voici un exemple de Repository dans lequel on injecte DataAccess, une classe assurant la configuration de l'accèsà la base de données :

1. public class CustomerRepository(val dataAccess: DataAccess) {

2. public fun getById(id: Int): Customer {...}

3. public fun getByName(name: String): List<Customer> {...}

4. public fun getByEmail(email: String): List<Customer> {...}

5. }

Jusque-là rien d'anormal, les différentes méthodes utilisant DataAccess pour réaliser les différentes requêtes.

Cependant, voyons ce qui se passe lorsque le nombre de dépendances augmente, par exemple dans un Controller :

1. public class CheckoutController(val cartRepository: CartRepository,

2. val shipmentRepository: shipmentRepository,3. val taxService: TaxService) {

4. public fun index() {

5. // Render Shopping cart with checkout buttons

6. cartRepository

7. }8.

9. public fun checkout() {



















10. // Render checkout page including data for payment11. taxService

12. }

13.

14. public fun shipment() {

15. // Render shipment page including data for shimpent options16. shipmentRepository

17. }

18. }

Ici, chaque méthode utilise une dépendance différente, mais il nous faut quand même définir toutes les dépendances.Cela n'est pas vraiment en accord avec les principes SOLID, non ?

En fait, nous n'avons pas réellement besoin de ces dépendances, simplement de leurs comportements, ce qu'il estune nouvelle fois possible de refactorer en utilisant une approche fonctionnelle, pour encapsuler ces comportementsdans des fonctions :

1. public fun checkoutHandler(checkoutDataFunc: (Int) -> List<CartEntry>, id: Int) {

2. val data = checkoutDataFunc(id).take(10)

3. // Process data

4. }

Hadi Hariri nous démontre ainsi que l'approche fonctionnelle est parfaitement utilisable dans des scénariosclassiques, que nous avons l'habitude de traiter de manière totalement différente dans un style de programmationobjet.

V - Apprendre à réfléchir « fonctionnel »

V-A - Des fonctions comme primitives réutilisables du langage

Dans la programmation fonctionnelle, les fonctions sont au cœur du langage.

Elles sont des briques essentielles qu'il est possible de combiner via des f onctions d'ordre supérieur, qui prennenten entrée des fonctions et qui peuvent retourner d'autres fonctions :

• filter avec un prédicat (une condition) ;• map avec une fonction de transformation ;• groupBy avec une fonction de regroupement par index.

Il est également possible de réaliser du pipeliningpour mettre en place des chaînes de traitement :

1. albums.filter { x -> x.year >= 1976 }

2. .map { x -> Pair(x.title, x.year) }

3. .groupBy {x -> x.second }

À ce niveau, Hadi Hariri nous met en garde vis-à-vis de ce principe de pipelining afin d'éviter de multiplier à l'infiniles fonctions dans le pipeline, ce qui aurait pour effet de limiter la lisibilité du code.

Il nous encourage à découper le pipeline en créant de nouvelles fonctions, aux noms explicites, pour extraire desregroupements de fonctions de base du pipeline.

Un autre aspect proche du pipelining est la possibilité de réaliser des compositions de fonctions de type f(g(x)) :

1. public fun sum(x: Int, y: Int): Int = x + y

2. public fun squared(x: Int): Int = x * x

3.4. val squaredSum = compose(::sum, ::squared)





















http://fr.wikipedia.org/wiki/SOLID_%28informatique%29











Cela permet de respecter :

• le principe de Single Responsibility Principle (SRP), appliqué aux fonctions en écrivant des fonctionssimples, puis en les composant pour réaliser des traitements plus complexes ;

• le principe Don't Repeat Yourself (DRY), en créant une nouvelle fonction permettant d'extraire du codecommun à plusieurs fonctions, puis en utilisant la composition pour appeler cette nouvelle fonction.

Les notions d'application partielle et de curryfication sont également très présentes en programmationfonctionnelle :

1. val sum = { (x: Int, y: Int) -> x + y }

2.3. // Partial Function Application

4. val sumNumberWith10 = sum.partial(10)

5. println(sumNumberWith10(5)) // -> 15

6.7. // Currying

8. val sumCurried = sum.curry()

9. println(sumCurried(3)(2)) // -> 5

La curryfication, du nom du mathématicien Haskell Curry, désigne l'opération qui permet, à partir d'une fonction àplusieurs arguments, d'obtenir une fonction à un argument retournant une fonction prenant le reste des arguments,permettant ainsi l'application partielle.

V-B - Des données à la recherche de l'immutabilité

Après s'être principalement intéressé aux fonctions, Hadi Hariri souhaite désormais revenir sur la notion de données.

Ces données peuvent être de différents types dans une approche fonctionnelle :

• des scalaires : âge, date de naissance, montant… ;• des collections de types abstraits (“Abstract Data Type“) : liste de clients, liste de factures…

Ces listes sont les entrées et les sorties des fonctions vues précédemment (map, filter…) et les scalaires peuventêtre obtenus à partir de listes via d'autres fonctions (first, last, find, aggregate…).

Hadi Hariri nous présente alors plus particulièrement la fonction fold, qui permet d'appliquer une transformation sur les éléments d'une collection, en collectant les résultats au fur et à mesure via un accumulateur. Une fois que l'on atraversé toute la liste, seul l'accumulateur reste, c'est la valeur scalaire à laquelle on a réduit la liste :

Par exemple, pour déterminer le maximum dans une liste d'entiers :

1. public fun maximumFold(list: List<Int>) : Int {2. return list.fold(0, {x, y -> Math.max(x, y)})

3. }






http://blog.soat.fr/wp-content/uploads/2015/05/fold.png



















La programmation fonctionnelle dispose également de deux outils particulièrement intéressants : le “pattern

matching” et la récursivité.

1. public fun maximumRecursive(list: List<Int>): Int {

2. when (list.count()) {

3. 0 -> throw IllegalArgumentException("empty list!")

4. 1 -> return list[0]

5. else -> return Math.max(list[0], maximumRecursive(tail(list)))

6. }

7. }

Comme on le voit dans la fonction ci-dessus, le “pattern matching” fournit une manière simple de construire desstructures alternatives. On est en effet bien loin des séries de if … else … if ou de switch … case, que nous devonsutiliser en Java pour répondre à ce type de problématique.

La récursivité n'est quant à elle pas limitée à la programmation fonctionnelle, mais l'utilisation de structures récursivesest beaucoup plus courante dans ce type de programmation que dans le style de programmation impérative, oùl'utilisation des boucles de type for est plus habituelle.

L'utilisation de la récursivité permet également de favoriser l'immutabilité des données, en évitant l'utilisation devariables d'état.

D'ailleurs, afin de limiter ces variables d'état, Hadi Hariri nous conseille également de traiter les listes comme desstructures infinies, rendant possibles l'évaluation paresseuse (“Lazy evaluation“) et la programmation réactive.

Lorsque l'on fait de la programmation fonctionnelle, nous devons toujours rechercher à privilégier l'immutabilité desdonnées, par exemple en créant une nouvelle liste plutôt qu'en modifiant une liste existante lors de l'application d'untraitement sur celle-ci.

VI - Programmation fonctionnelle et performances

Hadi Hariri s'intéresse maintenant à l'aspect performance de la programmation fonctionnelle.

VI-A - Mémoïzation

Il utilise tout d'abord l'exemple du calcul de la suite de Fibonacci, résolu ici dans un style purement récursif :

1. public fun fibonacciRecursive(n: Int) : Long {

2. if (n == 0 ||n == 1) {

3. return n.toLong()

4. } else {

5. return fibonacciRecursive(n -1) + fibonacciRecursive(n - 2)

6. }7. }

Une première technique d'optimisation est l'utilisation de la mémoïzation, qui consiste à réduire le temps d'exécutiond'une fonction en mémorisant ses résultats d'une fois sur l'autre.

Pour ce faire, on introduit tout simplement un cache qui va éviter le recalcul des valeurs déjà calculées lors derécursions intermédiaires :

1. val cache = hashMapOf<Int, Long>(0 to 0, 1 to 1)

2.

3. public fun fibonacciMemoization(n: Int) : Long {

4. if (cache.containsKey(n)) {

5. return cache.get(n)!!.toLong()6. } else {

7. val result = fibonacciMemoization(n -1) + fibonacciMemoization(n - 2)



















http://fr.wikipedia.org/wiki/M%E9%AD%AF%EF%B3%A1tion











8. cache.set(n, result)

9. return result

10. }

11. }

VI-B - Récursion terminale

Comme on a déjà pu l'évoquer précédemment, la programmation fonctionnelle utilise de nombreuses structuresrécursives, ce qui peut poser des problèmes de gestion de la pile, la zone mémoire réservée à l'exécution d'unprogramme.

En effet, dans une procédure récursive, toutes les variables locales sont stockées dans la pile d'exécution et empiléesautant de fois qu'il y a d'appels récursifs, avant d'être désempilées au fur et à mesure qu'on remonte les niveaux unefois la condition de sortie rencontrée.

Ainsi, si on ne fait pas attention à la profondeur de la récursivité, la pile se remplit progressivement jusqu'à atteindresa limite de taille, ce qui entraîne le problème bien connu de débordement de pile : “stack overflow“.

Afin de limiter ces impacts, on peut utiliser la technique de récursion terminale (tail recursion). Une fonction àrécursivité terminale (tail-recursive) est une fonction où l'appel récursif est uniquement la dernière instruction à êtreévaluée.

1. public fun factorial(number: Int): Int {

2. when (number) {

3. 0,1 -> return 1

4. else -> return number * factorial(number - 1)

5. }6. }

La fonction de calcul de factorielle ci-dessus ne l'est pas, car le résultat de l'appel récursif factorial (number - 1)

est utilisé par la fonction *. À cause de cela, le résultat de factorial (number - 1) doit être conservé dans la pile

d'exécution pour être utilisé par *.

Cependant il est possible de modifier l'implémentation de cette fonction pour la rendre tail-recurvive :

1. public fun factorialTailCall(number: Int): Int {

2. return factorialTC(number, 1)

3. }

4.

5. public fun factorialTC(number: Int, accumulator: Int): Int {

6. when (number) {

7. 0 -> return accumulator

8. else -> return factorialTC(number - 1, accumulator * number)

9. }

10. }

Ici, la fonction factorialTC s'appelle elle-même uniquement lors de sa dernière instruction, ce qui permet d'économiser de l'espace mémoire, car aucun état, sauf l'adresse de la fonction appelante, n'a besoin d'être sauvé sur la piled'exécution.

Ainsi, alors que l'espace consommé sur la pile d'exécution augmente linéairement lors de l'exécution récursive, ilreste constant après l'optimisation tail-recursive, diminuant ainsi nettement l'empreinte mémoire.

Le recours à un accumulateur (accumator dans l'implémentation tail-recursive de factorielle) est une techniquecouramment utilisée pour l'écriture de fonctions tail-recursive.

À noter qu'en Kotlin, il est nécessaire de préciser via une annotation tailRecursive que l'on souhaite utiliser uneoptimisation de type tail-recursive, appelée Tail Call Optimization :
















1. tailRecursive

2. public fun factorialTC1(number: Int, accumulator: Int): Int {

3. when (number) {

4. 0 -> return accumulator

5. else -> return factorialTC1(number - 1, accumulator * number)

6. }

7. }

Cela permet d'indiquer au compilateur que l'on souhaite faire cette optimisation et donc de vérifier si celle-ci esteffectivement réalisable afin d'alerter le développeur si ce n'est pas le cas.

Attention néanmoins, car tous les langages fonctionnels ne prennent pas en charge ce type d'optimisation ! Par exemple, Java supporte les appels tail-recursive, mais il n'y apporte aucune optimisation, car celle-ci n'est pasdisponible dans la JVM, contrairement à Scala où le compilateur est capable de réaliser cette optimisation (vial'annotation @tailrec).

VI-C - Fonctions inline

Enfin, Hadi Hariri avoue que les fonctions d'ordre supérieur peuvent avoir des impacts négatifs sur les performances.

En effet, en Kotlin, chaque fonction est un objet qui capture une closure, l'ensemble des variables qui sont accessiblesdans le corps de la fonction. L'allocation mémoire pour ces fonctions et ces variables, ainsi que les appels virtuels,introduisent donc inévitablement un surcoût à l'exécution.

Afin de limiter cet impact, il est possible de déclarer ces fonctions comme inline ; dans ce cas, le code complet dela fonction (ainsi que des lambdas utilisés) est inséré dans le code de l'appelant à l'exécution.

Là encore, tous les langages ne disposent pas de cette possibilité de déclarer des fonctions comme inline.

En Java, il n'est pas possible de suggérer au compilateur qu'une fonction doit être inline, mais la JVM

réalise néanmoins ses propres optimisations à l'exécution, ce qui permet de limiter les impacts du paradigme« fonctionnelle ».

VII - Quid de tous les concepts effrayants de la programmation fonctionnelle ?

Comme vous avez pu vous en rendre compte, mis à part la curryfication et l'application partielle, aucun des termeshabituellement utilisés par les puristes de la programmation fonctionnelle n'a été cité dans cette présentation.

Avant de conclure sa présentation, Hadi Hariri décide néanmoins d'évoquer rapidement certains de ces termes.

VII-A - Foncteurs (“Functors“)

Les foncteurs sont des éléments sur lesquels on peut réaliser une transformation, par exemple une collection de a

où l'on peut appliquer une fonction a -> b pour retourner une collection de b.

La fonction map est donc un exemple simple de foncteur que nous avons déjà eu l'occasion de manipuler précédemment.

VII-B - Monades

Une monade permet d'encapsuler une valeur, un traitement ou un résultat potentiel. Il est ainsi possible de voir unemonade comme une boîte, vide ou ayant un contenu, qui nous fournit des abstractions et des opérations au-dessus

de la valeur éventuellement encapsulée.








présentation constitue une œuvre intellectuelle protégée par les droits d'auteur Copyright ® 2015 Jerôme Valloire Aucune reproduction

On peut citer différentes monades usuelles :

• la monade Option, appelée aussi monade Maybe permettant d'enchaîner des traitements unitaires pouvantpotentiellement ne pas retourner de valeur. Scala utilise le type Option permettant de caractériser laprésence ou l'absence de valeur via deux sous-types, Some[T] ou None ;

• la monade List, permettant d'appliquer des opérations unitaires sur des ensembles de valeurs. On peut ici

citer le type IEnumerable<T> de C# ;• les Futures,permettant d'encapsuler un résultat qui arrivera plus tard et qui sont utilisés pour réaliser des

opérations asynchrones ou en programmation réactive.

Ces termes théoriques cachent des concepts mathématiques, mais comme le souligne Hadi Hariri, nul besoin de lesmaîtriser pour adopter les concepts de la programmation fonctionnelle présentés lors de sa conférence et commencer ainsi à refactoriser votre code.

Si vous êtes intéressé par ces concepts, je vous invite à parcourir le web où les ressources sont plus que nombreuses,mais encore une fois, le plus important, c'est de savoir les mettre en pratique de manière concrète.

VIII - ConclusionEn conclusion, Hadi Hariri nous encourage fortement à expérimenter la programmation fonctionnelle et ainsi à arrêter de réfléchir uniquement en termes d'objets en adoptant les fonctions comme des éléments primitifs du langage.

L'utilisation de fonctions devrait nous permettre de nous concentrer sur différents points :

• écrire moins de code ;• écrire du code plus descriptif (le what plutôt que le how) ;• écrire du code plus facile à comprendre en séparant données et traitements ;• écrire du code plus déterministe en favorisant l'immutabilité et en limitant les effets de bord.

It is not Rocket science !!! (Hadi Hariri)

Pourquoi chercher continuellement à opposer programmation orientée objet et programmation fonctionnelle ? Pour moi, les deux paradigmes ne sont pas là pour s'opposer, mais pour se compléter, libre au bon développeur d'utiliser le bon outil pour résoudre le bon problème.

Tout comme Hadi Hariri, je ne peux que vous conseiller d'expérimenter la programmation fonctionnelle. C'esteffectivement une manière différente de coder, mais avec le temps, l'approche fonctionnelle devient de plus en plusnaturelle et si cela peut faire de vous un meilleur codeur, alors pourquoi ne pas essayer ?

IX - Remerciements

Cet article a été publié avec l'aimable autorisation de SOAT, société d'expertise et de conseil en informatique.

Nous tenons à remercier Claude LELOUP pour la relecture orthographique et Marie-Hélène Delacroix pour lamise au gabarit.


http://www.developpez.net/forums/u861957/marie-helene/

http://www.developpez.net/forums/u124512/claudeleloup/

http://www.soat.fr/


Documents

programmation-fonctionnelle