Découvrir la programmation fonctionnelle #2 | Récursivité et Immutabilité

Lorsque l’on débute dans la programmation, le style impératif est ce qui se rapproche le mieux de notre façon de penser. Les langages tels que le C, PHP ou Java intègrent tous ce paradigme. Il permet de créer des algorithmes puissants en séquençant des instructions les unes à la suite des autres afin d’atteindre un objectif déterminé.

Cependant, le style impératif introduit très souvent des effets de bords et rend difficile la maintenance de notre base de code. On parle de code spaghetti. Dans le premier article sur la découverte de la programmation fonctionnelle, nous avons pu définir plusieurs notions en programmation fonctionnelle telles que les fonctions, les fonctions d’ordre supérieur, les fonctions anonymes, la transparence référentielle, les effets de bord, les fonctions pures, la composition de fonctions, la curryfication ainsi que l’arité qui sont des concepts indispensables pour passer d’un style impératif à un style fonctionnel.

Afin d’aller plus loin dans notre apprentissage de la programmation fonctionnelle, nous allons à présent découvrir deux autres concepts très utilisés en programmation fonctionnelle : l’immutabilité et la récursivité.

L’immutabilité

L’immutabilité désigne le caractère d’un objet qui ne peut être modifié après sa création en opposition à la mutabilité. Introduire l’immutabilité dans notre base de code, permet de conserver les objects intacts, privés de tout effet de bord et donc de nous simplifier débogage et maintenance. Dans la suite, nous allons nous intéresser à comment rendre notre code immutable. Pour ce faire, il nous faut comprendre la mutabilité.

La mutabilité

D’une manière générale, lorsque nous créons une variable dans un langage de programmation nous réalisons une affectation qui à la forme: ma_variable = mon_objet.

En Scala on pourrait écrire :

var ma_variable = mon_objet

L’instruction précédente a grossièrement pour effet d’attribuer un espace mémoire à ma_variable et d’y faire pointer mon_objet comme dans le schéma suivant :

Schéma de l’affectation d’une variable au niveau mémoire

Ici, ma_variable joue le rôle de référence et mon_objet joue le rôle d’objet pointé.

La mutabilité peut intervenir à deux niveaux :

• Au niveau de l’objet pointé (c’est-à-dire l’objet qui est stocké).

var ma_variable = mon_objet.update()

Schéma d’une référence qui pointe vers un objet modifié

• Au niveau de la référence (c’est-à-dire les cases mémoires vers lesquelles celle-ci pointe).

var ma_variable = mon_nouvel_objet

Schéma d’une référence qui pointe vers une autre case mémoire

La mutabilité au sein de l’objet, peut toutefois revêtir des formes plus ou moins dangereuses. En effet, nous distinguons deux formes de mutabilité au sein de l’objet : la mutabilité globale et la mutabilité locale.

La mutabilité globale

La mutabilité globale désigne généralement une variable de classe accessible à l’extérieur de cette classe. Par exemple, prenons le code suivant :

class Player() {
  var score: Int = 0

  def incrementScore(): Unit = score += 1
}

Ici, la variable score est publique ce qui la rend accessible à l’extérieur de la classe Player. Elle peut par conséquent être modifiée par n’importe quel autre bout de code, ce qui rend son débogage et les tests plus compliqués.
En effet, on ne peut pas être sûr de la valeur de score sans avoir suivi l’exécution du programme et identifier toutes les méthodes qui modifient cette valeur. Ceci est à proscrire dans vos programmes car on ne maîtrise pas le contenu de la variable score.

La mutabilité locale

La seconde forme de la mutabilité permet d’observer un comportement mutable dans un scope bien défini. L’exemple suivant est une fonction pure utilisant une variable mutable.

def count(l: List[String]): Int {
  var cnt = 0;
  l.foreach( el => cnt += 1)

  cnt
}

Bien qu’utilisant de la mutabilité sur la variable cnt, celle-ci est cachée à l’intérieur de la fonction count. Cette variable ne peut être modifiée par un agent externe à la fonction ce qui la rend moins dangereuse que la mutabilité globale. La fonction count peut être testée sans que cela ne pose de problème particulier. Cette approche constitue une approche plus acceptable car plus ciblée.

Atteindre l’immortalité l’Immutabilité

Afin de résoudre notre problème de mutabilité nous avons 2 soucis à résoudre :

1. fixer les références ;
2. rendre immutables les objets pointés.

Pour fixer les références, la plupart des langages de programmation mettent à notre disposition des instruments permettant de le faire.

Dans un langage comme Scala, nous avons le choix lors de la création d’un objet de créer des valeurs ou des variables. La création de variables se fait en la préfixant de var tandis que la création de valeur se fait en la préfixant de val. Cela permet à la création d’indiquer la nature de l’objet que nous souhaitons manipuler “var” pour un objet mutable et “val” pour des objets immutables et donc de fixer ou pas la référence.

scala> val s = "Hello World"
s: String = Hello World

Si nous tentons de la modifier:

scala> s = "Hello readers"
^
error: reassignment to val

Ici, l’interpréteur renvoie une erreur nous indiquant que nous tentons de modifier une valeur ce qui est interdit car une valeur n’est accessible qu’en lecture seule.

En Java, nous pouvons également fixer nos références en préfixant les variables du mot clé final.

En JavaScript, les mots clés const ou let existent pour atteindre ce résultat.

A ce stade, il nous reste donc à rendre nos objets pointés immutables. C’est là que les choses se corsent car pour rendre un objet immutable, il faut que toutes ses propriétés soient récursivement immutables ou récursivement effectivement immutables.

Comment rendre une classe immutable ?

Nos objets sont amenés à être modifiés tout au long de la durée d’exécution du programme il faut donc prévoir ces variations et les permettre. Afin de respecter le paradigme de la programmation fonctionnelle et celui de l’immutabilité des objets, il faut et il suffit de renvoyer une nouvelle instance de la classe pour toutes modifications avec les modifications déjà incluses.

Prenons l’exemple d’une classe Point désignant des coordonnées (x, y) d’un point :

case class Point(x: Int, y: Int)

Afin d’éviter de modifier la première instance de cette classe, nous devons créer des méthodes qui vont se charger de créer de nouvelles instances à partir de l’ancienne :

case class Point(x: Int, y: Int){
  def deplacementAbcisse(v: Int): Point = copy(x = x + v)
  def deplacementOrdonnee(v: Int): Point = copy(y = y + v)
}

Ces méthodes deplacementAbcisse et deplacementOrdonnee s’appuient sur la méthode copy de Scala qui crée une nouvelle instance de Point à partir de la première instance créée.

L’appel à la méthode copy peut-être remplacé par la création d’une nouvelle instance ce qui nous donnerait le même résultat.

case class Point(x: Int, y: Int){
  def deplacementAbcisse(v: Int): Point = new Point(x + v, y)
  def deplacementOrdonnee(v: Int): Point = new Point(x, y + v)
}

De la même manière, on écrirait en Java :

public final class Point {
  final private int x;
  final private int y;

  public Point(int a, int b){
    x = a;
    y = b;
  }

  public Point deplacementAbcisse(int v){
    return new Point(x + v, y);
  }

  public Point deplacementOrdonnee(int v){
    return new Point(x, y + v);
  }
}

Et les collections dans tout ça

Certains langages de programmation offrent la possibilité d’obtenir des collections immutables par construction. Pour ceux-ci, pas de souci à se faire, il nous suffit de fixer les références. Pour les autres, comme on l’a vu, nous pouvons les utiliser et rendre nos objets immutables en fixant la référence et en forçant une recopie systématique pour toutes modifications.

Exemple :

scala> val l = Array[String]("toto")
l: Array[String] = Array("toto")

scala> val m = Array[String]("titi")
l: Array[String] = Array("titi")

scala> val c = l ++ m
l: Array[String] = Array("toto", "titi")[/scala]

Nous pouvons vérifier que nos collections l et m n’ont pas été modifiées :

[scala]scala> l
l: Array[String] = Array("toto")

scala> m
l: Array[String] = Array("titi")

Comme indiqué plus haut les collections immutables par construction nous protègent en nous évitant toute modification non voulue. En Scala, les collections immutables sont localisées dans le package scala.collection.immutable._ tandis que les collections mutables sont dans scala.collection.mutable._

En Java, il existe des wrappers immutables dans le package Collections.unmodifiable[*] cela nous permet de rajouter un contrôle sur nos collections. Toutefois, l’accès à la liste wrappée nous permettrait d’effectuer des modifications sur celle-ci.

Préférez l’immutabilité !

L’immutabilité nous garantit que l’objet manipulé n’a pas été modifié depuis sa création. Cela permet de réduire considérablement la partie du code à tester et à contrôler.

Toutefois, cette règle n’est pas absolue, la mutabilité peut être utile dans certains cas. Cependant, il faut toujours privilégier la mutabilité locale et proscrire la mutabilité globale.

La récursivité

To understand recursion, one must first understand recursion.

— Stephen Hawking

Un algorithme récursif sert à résoudre un problème complexe en le ramenant à une succession de problèmes plus simples. Elle constitue une manière de résoudre un problème et n’est en aucun cas indispensable.

Pour définir une fonction récursive, il nous faut 2 choses :

1. une condition d’arrêt ou valeur aux bords ;
2. le comportement récursif.

En sachant cela, nous pouvons définir la fonction factorielle comme ci-dessous :

1. valeur au bord : factoriel(0) = 1 ;
2. comportement récursif : factoriel(n) = n * factoriel(n-1).

En Scala, cela donne :

def fact(n: Int): Int = n match {
  case 0 => 1
  case m => m * fact(m - 1)
}

Stack Overflow

Manipuler une fonction récursive n’est pas chose aisée. En effet, il faut comprendre l’imbrication des opérations pour comprendre comment la JVM enchaînera les opérations. Cela jouera un rôle déterminant sur les performances, notamment sur la quantité de mémoire utilisée et nous permettra d’éviter le Stack Overflow.

fact(5) = 5 * (fact(4))
fact(5) = 5 * (4 * fact(3))
fact(5) = 5 * (4 * (3 * fact(2)))
fact(5) = 5 * (4 * (3 * (2 * fact(1))))
fact(5) = 5 * (4 * (3 * (2 * (1 * fact(0)))))
fact(5) = 5 * (4 * (3 * (2 * (1 * 1))))
fact(5) = 5 * (4 * (3 * (2 * (1))))
fact(5) = 5 * (4 * (3 * (2)))
fact(5) = 5 * (4 * (6)))
fact(5) = 5 * (24)
fact(5) = 120

Ici, le calcul de la fonction factoriel ne peut débuter tant que la fonction n’a pas rencontré son cas de base qui est fact(0) à cause de l’imbrication des opérations. Pour cet exemple, cela ne pose pas de problème. Cependant, si la valeur de factoriel que nous souhaitons calculer est trop grande cela peut vite devenir un problème.

fact(10000) = 10000 * (9999 * (... (* fact(0))))

Le fait de « dérouler » cette opération oblige l’interpréteur à garder en mémoire (dans la pile d’exécution) toutes les opérations intermédiaires. Lorsqu’elles sont trop nombreuses, il n’a pas assez de mémoire pour les stocker ce qui crée cette fameuse erreur Stack Overflow, ou débordement de pile.
Nous nous intéresserons au fonctionnement de la pile dans un prochain article.

Cela nous permet donc de distinguer 2 types de récursivité : Head Recursion et Tail Recursion (respectivement la récursivité en tête et la récursivité terminale).

L’exemple que nous avons utilisé pour factoriel s’inscrit dans la première catégorie : Head Recursion.

Tail recursion for the win

Afin de résoudre le problème de récursivité (c’est-à-dire le Stack Overflow) pour de trop grands nombres, la solution est de ré-implémenter la fonction factorielle en tail récursive.

def fact(n: Int): Int = {
  @tailrec
  def go(n: Int, p: Int = 1): Int = n match {
    case 0 => p
    case m => go(m-1, p*m)
  }

  go(n)
}

Reprenons l’exemple plus haut avec cette nouvelle implémentation et déroulons les différentes étapes de l’exécution :

fact(5) = go(5,1)
fact(5) = go(4, 5)
fact(5) = go(3, 20)
fact(5) = go(2, 60)
fact(5) = go(1, 120)
fact(5) = go(0, 120)
fact(5) = 120

Ici, nous notons clairement que le nombre d’opérations intermédiaires stockées est limité (les calculs peuvent être faits immédiatement) ce qui a pour résultat de beaucoup moins utiliser la mémoire et donc de la saturer. En pratique, l’annotation @tailrec permet de garantir par le compilateur que la fonction est tail recursive ce qui lui permet d’optimiser la fonction en la transformant en une boucle while.

Conclusion

Dans cet article, nous avons vu dans un premier temps le concept d’immutabilité. Cela nous a permis de mieux cerner les avantages liés à ceux-ci. Nous avons également vu les caractéristiques de la mutabilité en passant par la mutabilité locale et globale.

Nous nous sommes penchés dans un second temps sur la récursivité avec ses spécificités en tête (Head Recursion) ou en queue (Tail Recursion).

Dans la suite de la série sur l’apprentissage de la programmation fonctionnelle, nous allons explorer les boucles en programmation fonctionnelle, les lambdas ainsi que les fonctions map et flatMap bien connues dans l’univers de la programmation fonctionnelle avant de terminer sur les for-comprehension.

En attendant la suite, n’hésitez pas à poser vos questions en commentaire. Toute remarque est la bienvenue afin de nous permettre d’améliorer la qualité des publications. Nous pourrons également traiter les options scalac dans un prochain article.