La programmation fonctionnelle

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

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 :

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.

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 1^er au Royaume-Uni et aux États-Unis.

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 :

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 :

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 :

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 :

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.

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 :

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 :

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.

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

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 :

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.

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 :

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 :

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 :

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.

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 :

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)) :

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 :

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.

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 :

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

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

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.

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

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 :

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
    }
}

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.

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 :

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 :

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

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

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.

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.