IdentifiantMot de passe
Loading...
Mot de passe oublié ?Je m'inscris ! (gratuit)

La programmation fonctionnelle

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 du fait de ses qualités indéniables d'orateur, mais aussi de la diversité et de la pertinence des sujets traités.

Cette année, Hadi Hariri a décidé de s'attaquer à la programmation fonctionnelle au travers d'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 exemples concrets.

Vous pouvez donner votre avis sur cet article sur notre forum : 2 commentaires Donner une note à l´article (5)

Article lu   fois.

L'auteur

Liens sociaux

Viadeo Twitter Facebook Share on Google+   

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 dans le monde de l'entreprise de langages tels que Scala, Haskell… mais aussi avec l'introduction des lambdas dans Java depuis 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 fonctions comme 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, qui permettent 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 de programmation 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.

 
Sélectionnez
1.
2.
3.
4.
5.
6.
7.
8.
9.
fun basicFunction(parameter: String): String {
    return parameter
}
 
fun singleLineFunction(x: Int, y: Int) = x + y
 
fun higherOrderFunction(func: (Int) -> Int) { ... }
 
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ême ré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 ne change 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 :

 
Sélectionnez
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
fun itDoesSomething(elements: List<String>): Map<String, Int> {
    var i = 0
    val results = hashMapOf<String, Int>()
    while (i < elements.size) {
        val element = results.get(elements[i])
        if (element != null) {
            results.set(elements[i], element + 1)
        } else {
            results.set(elements[i], 1)
        }
        i++
    }
    return results
}

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 code impé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 :

 
Sélectionnez
1.
2.
3.
4.
5.
6.
7.
fun itDoesSomething(elements: List<String>): List<Pair<String, Int>> {
    return elements.groupBy {
        it
    }.map {
        Pair(it.key, it.value.count())
    }
}

Ce code est non seulement plus concis, mais également plus expressif et même sans connaître les fonctions groupBy et map, on peut commencer à en deviner le but : déterminer le nombre d'occurrences de chaque chaîne de caractères de 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.

 
Sélectionnez
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
data class Album(val title: String, val year: Int, val chartUK: Int, val chartUS: Int)
val albums = listOf(
    Album("The Dark Side of the Moon", 1973, 2, 1),
    Album("The Wall", 1979, 3, 1),
    Album("Wish You Were Here", 1975, 1, 1),
    Album("Animals", 1977, 2, 3),
    Album("The Piper at the Gates of Dawn", 1967, 6, 131),
    Album("The Final Cut", 1983, 1, 6),
    Album("Meddle", 1971, 3, 70),
    Album("Atom Hearth Mother", 1970, 1, 55),
    Album("Ummagumma", 1969, 5, 74),
    Album("A Sauceful of Secrets", 1968, 9, 0),
    Album("More", 1969, 9, 153))
 
fun topUSandUK_v1(albums: List<Album>): List<Album> {
    val hits = arrayListOf<Album>()
    for (i: Int in 0..albums.count()-1) {
        if (albums[i].chartUK == 1 && albums[i].chartUS == 1) {
            hits.add(albums[i])
        }
    }
    return hits
}

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'état que l'on peut aisément éliminer en utilisant une structure de type for… in :

 
Sélectionnez
1.
2.
3.
4.
5.
6.
7.
8.
9.
fun topUSandUK_v2(albums: List<Album>): List<Album> {
    val hits = arrayListOf<Album>()
    for (album in albums) {
        if (album.chartUK == 1 && album.chartUS == 1) {
            hits.add(album)
        }
    }
    return hits
}

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

 
Sélectionnez
1.
2.
3.
4.
5.
6.
7.
8.
9.
fun topUSandUK_v3(albums: List<Album>): List<Album> {
    val hits = arrayListOf<Album>()
    albums.forEach {
        if (it.chartUK == 1 && it.chartUS == 1) {
            hits.add(it)
        }
    }
    return hits
}

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 faire le 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 un prédicat :

 
Sélectionnez
1.
2.
3.
4.
5.
fun topUSandUK_v4(albums: List<Album>): List<Album> {
    return albums.filter {
        (it.chartUK == 1 && it.chartUS == 1)
    }
}

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 test de la condition.

Il existe beaucoup d'autres fonctions de ce type qui sont des applications du concept de fonctions 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 de données :

 
Sélectionnez
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
fun topUSandUK_hits_years_v1(albums: List<Album>): List<Int> {
    val hits = albums.filter {
        (it.chartUK == 1 && it.chartUS == 1)
    }
    val years = arrayListOf<Int>()
    hits.forEach {
        years.add(it.year)
    }
    return years
}
 
fun topUSandUK_hits_years_v2(albums: List<Album>): List<Int> {
    return albums.filter {
        (it.chartUK == 1 && it.chartUS == 1)
    }.map {
        it.year
    }
}

Dans cet exemple, on récupère les années correspondant aux tops albums et au lieu d'utiliser une boucle for (le how), on utilise la fonction mapà laquelle on passe la fonction permettant de récupérer la propriété “year” de chaque album (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èques fonctionnelles.

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 les Streams 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 le comportement concret se trouve dans des sous-classes implémentant ces méthodes.

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

 
Sélectionnez
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.
26.
27.
28.
29.
30.
public abstract class Record {
    public abstract fun editRecord()
    public abstract fun persistData()
    public fun checkPermissions() {
        // Check permissions
    }
    public fun edit() {
        checkPermissions()
        editRecord()
        persistData()
    }
}
 
public class CustomerRecord: Record() {
    override fun editRecord() {
        // Edit customer record
    }
    override fun persistData() {
        // Persist customer data
    }
}
 
public class InvoiceRecord: Record() {
    override fun editRecord() {
        // Edit invoice record
    }
    override fun persistData() {
        // Persist invoice data
    }
}

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

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

 
Sélectionnez
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
public class RecordFunctional(val editRecord: () -> Unit, val persistData: () -> Unit ) {
    public fun checkPermissions() {
        // Check permissions
    }
    public fun edit() {
        checkPermissions()
        editRecord()
        persistData()
    }
}

Les fonctions sont ici directement passées en paramètres, ce qui permet d'éliminer tout le code “boilerplate” de l'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 :

 
Sélectionnez
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
public trait SortAlgorithm {
    public fun <T> sort(list: List<T>): List<T>
}
 
public class QuickSort: SortAlgorithm {
    override fun <T> sort(list: List<T>): List<T> {
        // Processing ...
        return sortedList
    }
}
 
public class BubbleSort: SortAlgorithm {
    override fun <T> sort(list: List<T>): List<T> {
        // Processing ...
        return sortedList
    }
}
 
public class Sorter(private val algorithm: SortAlgorithm) {
    public fun <T> sortList(list: List<T>): List<T> {
        return algorithm.sort(list)
    }
}

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

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

 
Sélectionnez
1.
2.
3.
4.
5.
public class SorterFunctional() {
    public fun <T> sortList(list: List<T>, sortFunction: (List<T>) -> List<T>): List<T> {
        return sortFunction(list)
    }
}

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 :

 
Sélectionnez
1.
2.
3.
4.
5.
public class CustomerRepository(val dataAccess: DataAccess) {
    public fun getById(id: Int): Customer {...}
    public fun getByName(name: String): List<Customer> {...}
    public fun getByEmail(email: String): List<Customer> {...}
}

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 :

 
Sélectionnez
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
public class CheckoutController(val cartRepository: CartRepository,
                        val shipmentRepository: shipmentRepository,
                        val taxService: TaxService) {
    public fun index() {
        // Render Shopping cart with checkout buttons
        cartRepository
    }
 
    public fun checkout() {
        // Render checkout page including data for payment
        taxService
    }
     
    public fun shipment() {
        // Render shipment page including data for shimpent options
        shipmentRepository
    }
}

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 est une nouvelle fois possible de refactorer en utilisant une approche fonctionnelle, pour encapsuler ces comportements dans des fonctions :

 
Sélectionnez
1.
2.
3.
4.
public fun checkoutHandler(checkoutDataFunc: (Int) -> List<CartEntry>, id: Int) {
    val data = checkoutDataFunc(id).take(10)
    // Process data
}

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

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 fonctions d'ordre supérieur, qui prennent en 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 :

 
Sélectionnez
1.
2.
3.
albums.filter { x -> x.year >= 1976 }
      .map { x -> Pair(x.title, x.year) }
      .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'infini les 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 des regroupements 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)) :

 
Sélectionnez
1.
2.
3.
4.
public fun sum(x: Int, y: Int): Int = x + y
public fun squared(x: Int): Int = x * x
 
val squaredSum = compose(::sum, ::squared)

Cela permet de respecter :

  • le principe de Single Responsibility Principle (SRP), appliqué aux fonctions en écrivant des fonctions simples, 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 code commun à 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 programmation fonctionnelle :

 
Sélectionnez
1.
2.
3.
4.
5.
6.
7.
8.
9.
val sum = { (x: Int, y: Int) -> x + y }
 
// Partial Function Application
val sumNumberWith10 = sum.partial(10)
println(sumNumberWith10(5)) // -> 15
 
// Currying
val sumCurried = sum.curry()
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 a traversé toute la liste, seul l'accumulateur reste, c'est la valeur scalaire à laquelle on a réduit la liste :

Image non disponible

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

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

La programmation fonctionnelle dispose également de deux outils particulièrement intéressants : le “pattern matching” et la récursivité.

 
Sélectionnez
1.
2.
3.
4.
5.
6.
7.
public fun maximumRecursive(list: List<Int>): Int {
    when (list.count()) {
        0 -> throw IllegalArgumentException("empty list!")
        1 -> return list[0]
        else -> return Math.max(list[0], maximumRecursive(tail(list)))
    }
}

Comme on le voit dans la fonction ci-dessus, le “pattern matching” fournit une manière simple de construire des structures alternatives. On est en effet bien loin des séries de if … else … ifou de switch … case, que nous devons utiliser 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écursives est 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 de variables d'état.

D'ailleurs, afin de limiter ces variables d'état, Hadi Hariri nous conseille également de traiter les listes comme des structures 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é des données, par exemple en créant une nouvelle liste plutôt qu'en modifiant une liste existante lors de l'application d'un traitement 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 :

 
Sélectionnez
1.
2.
3.
4.
5.
6.
7.
public fun fibonacciRecursive(n: Int) : Long {
    if (n == 0 ||n == 1) {
        return n.toLong()
    } else {
        return fibonacciRecursive(n -1) + fibonacciRecursive(n - 2)
    }
}

Une première technique d'optimisation est l'utilisation de la mémoïzation, qui consiste à réduire le temps d'exécution d'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 de récursions intermédiaires :

 
Sélectionnez
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
val cache = hashMapOf<Int, Long>(0 to 0, 1 to 1)
 
public fun fibonacciMemoization(n: Int) : Long {
    if (cache.containsKey(n)) {
        return cache.get(n)!!.toLong()
    } else {
        val result = fibonacciMemoization(n -1) + fibonacciMemoization(n - 2)
        cache.set(n, result)
        return result
    }
}

VI-B. Récursion terminale

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

En effet, dans une procédure récursive, toutes les variables locales sont stockées dans la pile d'exécution et empilées autant 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 une fois 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'à atteindre sa 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.

 
Sélectionnez
1.
2.
3.
4.
5.
6.
public fun factorial(number: Int): Int {
    when (number) {
      0,1 -> return 1
        else -> return number * factorial(number - 1)
    }
}

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 :

 
Sélectionnez
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
public fun factorialTailCall(number: Int): Int {
    return factorialTC(number, 1)
}
 
public fun factorialTC(number: Int, accumulator: Int): Int {
    when (number) {
        0 -> return accumulator
        else -> return factorialTC(number - 1, accumulator * number)
    }
}

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 pile d'exécution.

Ainsi, alors que l'espace consommé sur la pile d'exécution augmente linéairement lors de l'exécution récursive, il reste 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 technique couramment 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 une optimisation de type tail-recursive, appelée Tail Call Optimization :

 
Sélectionnez
1.
2.
3.
4.
5.
6.
7.
tailRecursive
public fun factorialTC1(number: Int, accumulator: Int): Int {
    when (number) {
        0 -> return accumulator
        else -> return factorialTC1(number - 1, accumulator * number)
    }
}

Cela permet d'indiquer au compilateur que l'on souhaite faire cette optimisation et donc de vérifier si celle-ci est effectivement 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 pas disponible dans la JVM, contrairement à Scala où le compilateur est capable de réaliser cette optimisation (via l'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 accessibles dans 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 de la 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 termes habituellement 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 une monade 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.

On peut citer différentes monades usuelles :

  • la monade Option, appelée aussi monade Maybe permettant d'enchaîner des traitements unitaires pouvant potentiellement ne pas retourner de valeur. Scala utilise le type Option permettant de caractériser la pré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 les maî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. Conclusion

En 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'est effectivement une manière différente de coder, mais avec le temps, l'approche fonctionnelle devient de plus en plus naturelle 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 la mise au gabarit.

Vous avez aimé ce tutoriel ? Alors partagez-le en cliquant sur les boutons suivants : Viadeo Twitter Facebook Share on Google+   

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 ni 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.