Programmation fonctionnelle Sans « pause » et « retour » | de Michel Charpentier | janvier 2023

Comment surmonter votre « break" et « retourner » la dépendance et adopter un style de programmation vraiment fonctionnel

Note: Cet article est adapté de mon livre Programmation fonctionnelle et simultanée : concepts de base et fonctionnalitéspublié par Addison-Wesley. Voir notamment les chapitres 11 et 12.

En tant que programmeur Java, j’ai tendance à abuser break, continueet les sorties précoces des boucles avec return. Lorsque j’ai commencé à programmer en Scala, un langage sans break ou alors continue— Je pensais qu’ils allaient énormément me manquer. Je ne l’ai pas fait (pas de symptômes de sevrage majeurs, comme des secousses), en partie parce que le code Scala a tendance à utiliser moins de boucles que le code Java.

Cette courte note explique à quel point break/return les modèles peuvent être implémentés de manière fonctionnelle. En particulier, l’équivalent fonctionnel de l’utilisation return sortir d’une boucle imbriquée n’est pas tout à fait évident et nécessite d’utiliser une forme d’évaluation paresseuse, un concept de programmation fonctionnelle classique. J’utilise principalement Scala pour démontrer des modèles fonctionnels car je trouve le langage concis et lisible. J’inclurai une variante Java à la fin.

Commençons par un exemple Java simple :

// This is Java
boolean checkLines(List<String> strings) {
for (String str : strings)
if (str.length() > 128)
return true;
return false;
}

Cette fonction vérifie la longueur des chaînes dans une liste et renvoie true si au moins une chaîne contient plus de 128 caractères. UN return L’instruction est utilisée pour terminer la boucle lorsqu’une longue chaîne est trouvée. C’est pour des raisons de performances : une fois qu’une telle chaîne a été trouvée, la fonction peut renvoyer true, et il est inutile de vérifier d’autres chaînes dans la liste.

Bien sûr, il existe un équivalent fonctionnel simple à ce programme, utilisant la fonction standard d’ordre supérieur exists:

// This is Scala
def checkLines(strings: List[String]): Boolean =
strings.exists(_.length > 128)

Une fonction exists est implémenté pour arrêter le traitement de la liste lorsqu’une chaîne de plus de 128 caractères est trouvée, ce qui se traduit par des performances similaires à celles de la version Java impérative.

Qu’en est-il des autres break/return scénarios ? Supposons, par exemple, que savoir qu’une chaîne comporte plus de 128 caractères n’est pas suffisant et que vous deviez récupérer la chaîne réelle, comme dans l’exemple suivant :

// This is Java
String searchLines(List<String> lines) {
for (String line : lines)
if (line.length() > 128)
return line;
return null;
}

(J’utilise null pour le cas où aucune chaîne longue n’est trouvée. On peut dire que c’est un mauvais style de programmation, et il serait préférable que la fonction renvoie une valeur de type Optional<String> au lieu. C’est une discussion pour un autre jour. Les variantes Scala utilisent des options au lieu de nulltout comme l’implémentation Java finale.)

Encore une fois, l’équivalent fonctionnel est facile car il existe une fonction d’ordre supérieur, findqui fait exactement ce dont nous avons besoin ici :

// This is Scala
def searchLines(strings: List[String]): Option[String] =
strings.find(_.length > 128)

Une fonction find ne traitera pas la liste au-delà de la première chaîne de plus de 128 caractères, ce qui se traduira par les mêmes performances que le code Java impératif.

Jusqu’ici tout va bien. Mais qu’en est-il d’un scénario un peu plus complexe ? Que faire si vous recherchez de longues chaînes dans une liste de fichiers ? Vous pouvez utiliser return pour sortir de l’imbrication de deux boucles, une sur les fichiers et une sur les lignes :

// This is Java
String searchFiles(List<Path> files) throws IOException {
for (Path file : files)
for (String line : Files.readAllLines(file))
if (line.length() > 128)
return line;
return null;
}

Si une longue ligne est trouvée, elle est renvoyée immédiatement. Aucune autre ligne du fichier n’est prise en compte et, plus important encore, aucun autre fichier n’est ouvert et lu.

Pour écrire un équivalent fonctionnel, la première idée qui vient à l’esprit est d’utiliser find encore une fois, comme dans ce qui suit :

// This is Scala
def readAllLines(file: Path) = Files.readAllLines(file).asScala
// DON'T DO THIS!
def searchFiles(files: List[Path]) =
files.find(file => readAllLines(file).exists(_.length > 128))

  

Une fonction d’assistance readAllLines est défini pour produire des lignes sous forme de liste Scala au lieu d’une liste Java. Puis, find permet de rechercher un fichier dans lequel existe une ligne de plus de 128 caractères. Mais cela ne fonctionne pas : find produit le fichier où se trouve la ligne, pas la ligne. En effet, le type de retour de searchFiles ci-dessus est Option[Path]ne pas Option[String].

Alors, quel est l’équivalent fonctionnel du programme Java ? L’idée sous-jacente est de réduire chaque fichier à sa première ligne avec plus de 128 caractères, le cas échéant. Fonction d’ordre supérieur map permet de traiter chaque fichier avec une fonction de recherche de ligne, elle-même implémentée à l’aide find:

// This is Scala
// DON'T DO THIS!
def searchFiles(files: List[Path]) = files
.map(file => readAllLines(file).find(_.length > 128))
.find(_.nonEmpty)

Une fonction searchFiles les usages map pour transformer une liste de fichiers en une liste de valeurs de type Option[String] (certains fichiers contiennent de longues lignes, d’autres non), puis utilise find pour trouver la première option non vide dans cette liste. Celui-ci contiendra la première longue chaîne du premier fichier contenant au moins une telle chaîne, comme dans la variante Java.

Il y a deux problèmes avec la fonction searchFiles au dessus. D’abord parce que find renvoie en général une option (pour traiter les cas où rien n’est trouvé) et s’applique ici à une liste d’options (après traitement des fichiers par map), la fonction entière renvoie une valeur de type Option[Option[String]] au lieu de Option[String]. Ceci est facilement résolu en remplaçant map avec flatMap qui, comme son nom l’indique, « aplatira » l’option imbriquée :

// This is Scala
// DON'T DO THIS!
def searchFiles(files: List[Path]) = files
.flatMap(file => readAllLines(file).find(_.length > 128))
.find(_.nonEmpty)

Cette fonction retourne maintenant une valeur de type Option[String] et est fonctionnellement correct. Il produit la même ligne, à partir du même fichier, que la variante Java. Le problème restant concerne les performances : chaque fichier est parcouru jusqu’à sa première longue ligne dans cette implémentation. C’est parce que la fonction map traite tous les fichiers quoi qu’il arrive, même après qu’un fichier avec une longue ligne a été trouvé.

La réponse à cette deuxième difficulté est quelque peu subtile. Il s’agit d’utiliser une forme de flatMap » qui ouvre et recherche des fichiers à la demande si et quand d’autres fichiers doivent être recherchés. Dans Scala, cela peut être réalisé avec une vue (ou, de manière équivalente, un itérateur). Voici à quoi cela ressemble :

// This is Scala
def searchFiles(files: List[Path]) = files.view
.flatMap(file => readAllLines(file).find(_.length > 128))
.find(_.nonEmpty)

Le seul changement par rapport à avant est que flatMap s’applique désormais à files.view au lieu de files (en utilisant files.iterator fonctionnerait aussi ici). Dans Scala, une vue d’une liste est une séquence évaluée paresseusement dans laquelle les éléments ne sont calculés qu’une fois qu’ils sont nécessaires. Sur une vue, la méthode flatMap est une opération à temps constant qui produit une autre vue mais n’y calcule encore rien. Ce n’est qu’avec le dernier appel à find est la vue en cours de traitement, ouvrant et recherchant juste assez de fichiers pour trouver la première ligne avec plus de 128 caractères.

Ce programme s’arrête avec le premier fichier contenant une longue ligne et n’ouvre pas les fichiers restants, tout comme la variante Java. Pour atteindre ces performances, l’utilisation d’un .view la scène est la clé.

Vous pouvez écrire le même programme fonctionnel en Java en utilisant des flux :

// This is Java
Optional<String> searchFiles_alt(List<Path> files) {
return files.stream()
.flatMap(file -> {
try {
return Files.lines(file);
} catch (IOException ex) {
throw new UncheckedIOException(ex);
}
})
.filter(line -> line.length() > 128)
.findFirst();
}

Les flux de Java sont similaires aux vues et aux itérateurs de Scala : ils sont évalués paresseusement et déclenchent juste assez de calculs nécessaires. La notion d’exceptions vérifiées de Java gêne un peu (d’où la nécessité try-catch block), et les flux Java implémentent les fonctionnalités de Scala find sur le plan de filter suivie par findFirst.

Aussi, j’ai remplacé readAllLines avec la méthode lines, qui produit lui-même un flux (de lignes). Par conséquent, une fois qu’une longue ligne est trouvée, le reste du fichier actuel peut même ne pas être lu à partir du disque. À l’exception de ces différences mineures, il s’agit du même programme que la variante précédente de Scala. (C’est un peu plus long, donc je préfère démontrer des modèles fonctionnels dans Scala avant de revenir à Java.)

Une note finale pour les programmeurs Scala. N’écrivez pas ce qui suit :

// This is Scala
// DON'T DO THIS!
def searchFiles(files: List[Path]): Option[String] =
for file <- files; line <- readAllLines(file) do
if line.length > 128 then return Some(line)
None

Dans Scala 2, c’est seulement mal vu. Dans Scala 3, cette utilisation de return est obsolète et vous donne un avertissement. Le problème ici est que Scala for-do n’est pas une boucle. Il est implémenté en termes d’appels à une fonction d’ordre supérieur foreach. Ce qui signifie return ici ne « revient » pas vraiment (vous ne revenez pas de la fonction qui est l’argument de foreach) et est implémenté avec une sale astuce (lancer, puis attraper une exception). Il est obsolète car il est inefficace et sujet aux erreurs (votre code pourrait accidentellement intercepter l’exception utilisée en interne).

De nombreuses boucles, dont certaines sans break ou alors return, peut être remplacé par un équivalent fonctionnel en s’appuyant sur l’utilisation appropriée de l’évaluation paresseuse. A titre d’exercice, comment remplaceriez-vous cette implémentation impérative du classique 3n + 1 problème avec une solution fonctionnelle?

// This is Java
int collatz(int start) {
int n = start, count = 0;
while (n != 1) {
if (n % 2 == 0) // n is even
n = n / 2;
else // n is odd
n = 3 * n + 1;
count++;
}
return count;
}

(Voir Programmation fonctionnelle et concurrenteChapitre 12 pour une réponse Scala et Annexe A pour les variantes Java et Kotlin.)