Memoïsation de fonctions récursives en Scala

Optimiser les appels de fonctions au moyen de la mémoïsation, vous connaissez peut-être. Pourtant très intéressante pour mettre en cache le résultat (réutilisation de ressources externes, calcul long, structures en arbres), appliquer cette technique aux fonctions récursives peut se révéler inefficace ou compliqué.

Dans un article précédent, Sergio Dos Santos nous a expliqué comment réaliser la mémoïsation de fonctions récursives en Kotlin (et JavaScript), nous allons donc nous intéresser à Scala. Nous allons profiter de cet exemple de mise en œuvre pour expliquer ce qui se passe en détail et nous poser la question de la mémoïsation des fonctions tail-recursive (« à récursion terminale »).

La fonction de mémoïsation

Quelques rappels pour ceux qui n’auraient pas lu l’article cité plus haut :

• la mémoïsation consiste à détourner l’appel d’une fonction de manière à ne l’appeler qu’une fois pour un argument donné et à retourner le résultat connu lors des appels suivants
• elle-même est une fonction
• on ne peut appliquer la mémoïsation qu’à des fonctions pures, sinon on perd l’effet de bord sur les appels successifs.

C’est donc une sorte de « fonction cache » pour fonctions.

La syntaxe de déclaration de la classe ci-dessus définit en Scala une fonction à 1 argument. Derrière le extends, T => R est l’abréviation de Function1[T, R].

Ensuite, on doit disposer d’un map muable pour stocker les résultats en fonction des arguments passés.

Enfin, l’appel à la fonction elle-même définit dans apply demande en priorité la valeur dans le cache. En cas d’échec, getOrElseUpdate permet d’enregistrer la valeur réelle dans la map puis de la retourner.

Et pour les fonctions à plusieurs arguments ? On peut les ramener en premier lieu à une fonction à 1 argument au moyen de leur méthode tupled.

La mémoïsation ne marche pas avec les fonctions récursives

Peut-être connaissiez-vous déjà ce principe ou vous pourriez commencer à imaginer des usages concrets (comme la programmation dynamique ?). Puisque ça marche pour toutes les fonctions pures… Et puis finalement, ça fonctionne également sur certaines fonctions avec effet de bord, justement quand on veut l’éviter (exemple : appel à une opération idempotente d’une base de données).

Or, s’il y a bien un cas où l’on voudrait couper les appels, ce sont dans les fonctions récursives. Imaginez un parcours d’arbre, un calcul de Fibonacci ou une factorielle. Généralement, un calcul par récursion implique de rappeler la fonction initiale avec un argument plus proche du résultat ou de l’hypothèse initiale (le premier élément d’une suite, le plus petit nombre qu’on sache calculer, etc.). Or, dans une chaîne d’appels récursifs d’une fonction donnée, on va très souvent rappeler la fonction avec les mêmes arguments. Exemple : fibonacci(3) va appeler fibonacci(2) et fibonnacci(1) car pour calculer le rang N il faut les deux précédents. Or fibonacci(4) va avoir provoqué l’appel les 3 citées précédemment. Et plus le rang augmente, plus je fais d’appels « en double ».

Alors, on mémoïse Fibonacci et ça roule ? Je n’appellerai qu’une seule fois la fonction pour chaque rang…

Ou pas.

La mémoïsation ne fonctionne pas pour les fonctions récursives, car justement la fonction se rappelle elle-même, et pas la version mémoïsée.

Avec cette définition, même si je dispose d’une fonction memoizedFibo = Memoize(fibonacci) et que j’appelle memoizedFibo(5), je vais avoir 9 appels. Dans l’idéal, 5 suffisent. En effet, la ligne 21 appelle deux fois explicitement la fonction fibonacci originale.

Si seulement on pouvait injecter une version mémoïsée d’elle-même à la fonction récursive !

Première étape : un récursivité plus flexible

Pour pouvoir injecter la version mémoïsée d’elle même à une fonction, il faut qu’elle accepte d’appeler une fonction plutôt qu’elle même :

Cette version de fibonnacci ne marche par défaut que si on lui passe sa propre référence en tant que « recurse ». Ainsi, elle s’appelle elle-même comme avant.

Ici, nous devons faire une pause et expliquer une mécanique du langage. Oui, parce qu’à première vue, votre esprit de crafts(wo)man affûté a remarqué 3 horreurs :

1. présence du mot-clé var alors que l’immuabilité sécurisante est préférable habituellement
2. assignation de null dans un langage où on fait tout pour éviter ça et qui, de surcroit, dispose de tous les outils pour ne jamais avoir de null.
3. Mais c’est quoi cette variable nulle passée en paramètre ? Ça sent la NPE, non ?

Précision : c’est bien la fonction fibonnacci qui va être utilisée directement , pas pseudoRecFibonacci.

Autre raison de s’intéresser à cette écriture, nous allons voir un code similaire par la suite. Il faut donc bien comprendre les deux mécanismes à l’œuvre.

L’application partielle

Indépendamment de la référence nulle que nous allons oublier un instant, nous utilisons ici le principe d’application partielle de fonction. Normalement, notre fonction pseudoRecFibonacci prend 2 arguments : un Int, et une fonction Int => Int. Mais comme cette signature est affreuse et qu’on ne veut pas l’exposer à l’utilisateur qui comprend naturellement Fibonacci comme une fonction qui rend un Int quand je lui passe un Int correspondant au rang, on voudrait résoudre un argument avant de lui passer la fonction.

C’est possible en Scala : je peux créer une fonction à N – i arguments en appelant une fonction à N arguments avec seulement i arguments (i < N). Pour cela, il faut remplacer les arguments que je veux laisser à la main de l’utilisateur par des _ (underscore).

L’exemple typique donné dans les tutoriels est l’additionneur :

En résumé, on permet à une fonction « normale » d’être appelée avec seulement certains arguments, comme si elle était curryfiée.

Ainsi fibonacci = pseudoRecFibonacci(_, fibonacci) permet d’obtenir une fonction fibonacci qu’on va appeler avec 1 seul argument, le premier de la signature de pseudoRecFibonacci.

La référence auto-dénullifiable alias reference object

Dans les langages à fonctions de premier ordre, comme Java 8, Scala, Python, Kotlin, Javascript a.k.a ECMAScript etc., lors qu’on passe une fonction à une autre fonction, il se produit un phénomène particulier appelé fermeture (closure). À tel point que par abus de langage, « closure » est utilisé de manière interchangeable avec « lambda » ou « fonction passée en paramètre ».

En effet, afin de simplifier l’écriture des lambda, il est possible d’écrire la fonction passée en argument à l’endroit où on en a besoin. Et pour encore simplifier, on peut faire appel, dans la définition de la lambda, à des variables locales à l’appel ! Toutes les variables accessibles à et utilisées par ma lambda sont « capturées » dans la fermeture. Une « closure » est donc une lambda à laquelle on a passé des arguments masqués, à savoir les références à toutes les variables capturées.

Si vous l’avez expérimenté, vous savez que ce sont bien des références aux variables locales qui sont capturées et non des valeurs. Vous avez peut-être commis, comme moi, l’erreur de créer une closure dans un boucle… toutes les fonctions ainsi créées utilisant les dernières valeurs connues (en fin de boucle) des variables capturées !

Ici, un mécanisme similaire est à l’œuvre. Ma variable de type fonction initialisée à null n’est pas une référence nulle. C’est en réalité un « reference object » dont la valeur interne ne pointe sur rien, mais qui elle a bien une référence.

C’est donc ce reference object qui est passé ligne 101 à pseudoRecFibonacci. Il ne contient rien au début, mais comme il a été défini comme var, l’assignation provoque la mise à jour de la référence. Si on avait écrit :

fibonnacci2 aurait alors été un fonction Int => Int appelant en interne fibonacci, qui étant restée null aurait provoqué une NPE.

Mais grâce à la réassignation de la variable originale, le reference object est mis à jour avec le résultat de l’application partielle. Et dans le résultat de l’application partielle, la référence recurse (qui n’est autre que la variable fibonacci) est mise à jour avec une véritable instance de Int => Int.

Et voilà, quand on utilise une goutte de muabilité et un brun de code impératif, on peut faire de la magie avec les fonctions.

Seconde étape : généralisation au sein du Y Combinator

Rajoutons une fonction Y à l’objet compagnon de notre classe Memoize (qui est une fonction) :

La fonction Y prend en paramètre une fonction pseudo-récursive telle que nous l’avons déjà vue plus haut, et nous retourne sa version « propre », utilisable sans argument superflu. On remarquera que notre Y-combinator est simplifié, car appliqué à Memoize directement. Dans une bibliothèque fonctionnelle, on pourrait avoir un argument supplémentaire, à savoir la fonction combinée (ici la fonction combinée est forcée à « Memoize »).

Au final, j’expose une fonction telle que

CandidateFunctions.PseudoRecursive.fibonacci est la version pseudo-récursive de CandidateFunctions.fibonacci que vous trouverez dans mon dépôt créé pour cet article.

Vous trouverez dans ce dépôt tout le code de l’article, ainsi que les tests démontrant l’efficacité de la mémoïsation d’une part, et le combinateur d’autre part. Les tests s’attachent en particulier à montrer que la mémoïsation est cassée par la fonction récursive normale, mais « réparée » grâce au Y-combinator.

Le Y-combinator en action

Voici une séance de debugging montrant spécifiquement l’exécution de l’application partielle avec la référence nulle.

Ici, on voit que la référence n’est pas nulle, mais un conteneur de référence nulle.

Ensuite, appel au constructeur de Memoize à l’intérieur de apply, avec la fonction f, qui n’est autre que CandidateFunctions.PseudoRecursive.fibonacci appliquée partiellement avec yf, qui est encore une référence vers une fonction nulle à ce moment :

Après appel au constructeur, on revient sur la ligne 17. Memoize.apply a été appelée, yf est toujours « nulle » (juste avant l’assignation) :

Ci-dessous, après l’assignation de sa nouvelle valeur à yf, plusieurs choses se sont produites :

• on n’a plus d’objectRef qui pointe sur null
• on a bien un yf qui est une fonction de type Memoize comme en atteste l’exploration des variables
• la référence yf capturée dans Memoize s’apelle f et est une instance de lambda non nulle désormais !

Ci-dessus, on voit que j’ai ajouté dans le debugger deux expressions observées : yf(5) et yf.cache. On voit ici que l’appel à yf, qui sera après le return de Y assignée à mfibonacci, produit bien 5 entrées dans le cache de Memoize.

Dans les tests, vous verrez que le comptage du nombre d’appel est aussi de 5 pour une fonction récursive mémoïsée avec combinateur, contre 9 sans. Cela montre qu’une fois les 5 entrées de cache produites, fibonnacci n’est plus appelée, les entrées du cache sont retournées à la place.

 

Conclusion

La force du Y-Combinator, c’est à partir d’une fonction dont la signature « décomposée » accepte l’injection de la fonction de rappel, de pouvoir garantir que la combinaison initiale soit reproduite à chaque appel. Avec le bonus d’obtenir en résultat la fonction récursive avec la signature propre qu’on souhaite exposer. En somme, la grande classe de la programmation fonctionnelle, servie par un peu de logique impérative et le mécanisme des closures.

Comme effet de bord, on a également ici une illustration parfaite qu’on peut parfois déroger aux sacro-saints principes du clean code si on sait parfaitement ce que l’on fait. Ici, la fin justifie parfaitement les moyens.