La programmation fonctionnelle en Perl

Partie 3 : étendre le langage

Laurent Rosenfeld

Ce document est le troisième et dernier d'une série de tutoriels visant à montrer comment utiliser certaines techniques de la programmation fonctionnelle en Perl et acquérir ainsi une bien meilleure expressivité. Cette troisième partie montre en particulier comment les fonctions d'ordre supérieur (fonctions de rappel, fermetures, itérateurs, générateurs de fonctions, etc.) abordées dans la seconde partie permettent d'étendre le langage et notamment de créer de nouveaux opérateurs de listes tels que ceux abordés dans la première partie. Il n'est pas indispensable d'avoir lu la première partie de ce tutoriel pour lire cette troisième partie, mais une bonne compréhension des notions abordées dans la deuxième partie est nécessaire.

Commentez

- Titre : La programmation fonctionnelle en Perl

- Auteur : Laurent Rosenfeld

- Parution : 29 juillet 2014

- Mise à jour : 29 juillet 2017

- Public visé :

- Licence : 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 ® 2014 Laurent Rosenfeld. Aucune reproduction, même partielle, ne peut être faite de ce site et 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.

Voir également :

- La programmation fonctionnelle en Perl - Partie 1 : les opérateurs de listes

- La programmation fonctionnelle en Perl - Partie 2 : les fonctions d'ordre supérieur

- Vidéo : une présentation sur la programmation fonctionnelle en Perl, aux Journées Perl 2015 à Paris

Sommaire

- 1. Introduction

- 1-1. Résumé des épisodes précédents

- 2. Des fonctions de listes allant plus loin que map et grep

- 2-1. Une implémentation de map

- 2-1-1. Fonction map : premiers essais

- 2-1-2. Les prototypes Perl

- 2-1-3. Des fonctions my_map et my_grep fonctionnelles

- 2-2. Écrire une fonction sort originale

- 2-3. Une version avec itérateur de map (lazy_map)

- 2-3-1. Le générateur d'itérateurs

- 2-3-2. La fonction lazy_map

- 2-3-2-a. Implémentation de la fonction lazy_map

- 2-3-2-b. Benchmark des fonctions lazy_map et map

- 2-3-3. Une fonction lazy_grep

- 2-3-4. Le problème du semi-prédicat

- 2-3-5. Fonctions lazy_grep et lazy_map : versions finales

- 2-4. Des itérateurs plus versatiles

- 2-4-1. Consommer et renvoyer deux valeurs à chaque demande

- 2-4-2. Consommer une valeur et en renvoyer deux (ou plus)

- 3. Une nouvelle fonction de liste : reduce

- 3-1. Expression du besoin

- 3-1-1. Essais avec une fonction de rappel

- 3-1-2. Un générateur de fermetures anonymes

- 3-2. La fonction reduce, première version

- 3-3. La fonction reduce, nouvelle version

- 3-3-1. Code de la nouvelle version de reduce

- 3-3-2. Le problème de la liste vide

- 3-4. Une bibliothèque de fonctions de listes utilisant reduce

- 3-4-1. Fonctions de listes simples

- 3-4-2. Fonctions de listes composées

- 4. Un cran de plus dans la simplification : la curryfication

- 4-1. L'idée de base de la curryfication

- 4-2. Rien de bien nouveau sous le soleil ?

- 4-3. Curryfication de la fonction parcours_dir

- 4-4. Une version curryfiée de reduce

- 4-5. La curryfication automatique

- 4-6. Prototypes et curryfication automatique : l'exemple de la curryfication de la fonction comb_sort

- 5. Fonctions à deux listes

- 5-1. Utiliser deux listes : la fonction combine

- 5-1-1. La fonction combine

- 5-2. Une fonction intermédiaire de création de fonctions

- 5-2-1. Créer une bibliothèque de fonctions

- 5-2-2. Simplification syntaxique

- 6. Implanter en Perl 5 les fonctions gather et take de Perl 6

- 6-1. Mise en œuvre

- 6-2. Exemples d'utilisation simple

- 6-3. Gather et take pour construire une fonction my_map

- 6-4. … Ou my_grep

- 6-5. Combiner les fonctions map et grep ?

- 6-6. Perspectives avec gather et take

- 7. Conclusion

- 8. Remerciements

1 - Introduction

Ce tutoriel n'est pas destiné à enseigner la programmation Perl à des débutants, mais à introduire des techniques de programmation Perl relativement avancées qui supposent une assez bonne connaissance et une certaine expérience de la syntaxe de base de Perl. Les fonctionnalités un peu avancées utilisées ici ont fait l'objet dans la seconde partie de ce tutoriel de rappels de base pour les plus simples d'entre elles, et de développements approfondis pour d'autres. Si le très bref résumé donné dans cette introduction vous paraît trop ardu, nous ne pouvons que vous conseiller de commencer par lire la seconde partie de ce tutoriel.

Ce tutoriel en trois parties part d'une constatation : beaucoup de développeurs Perl tendent à écrire du Perl comme si c'était du C. C'est dommage, car Perl est bien plus expressif que le C. Perl possède de nombreux concepts et paradigmes avancés empruntés à la programmation fonctionnelle (notamment au langage Lisp) permettant bien souvent d'écrire facilement des programmes bien plus courts, bien plus expressifs, moins bogués et souvent plus lisibles que leurs équivalents en programmation procédurale ou orientée objet. En fait, Perl est bien plus proche du Lisp que du C (même si la syntaxe de base du Perl ressemble évidemment plus au C).

1-1 - Résumé des épisodes précédents

La première partie de ce tutoriel abordait les techniques d'utilisation des opérateurs de listes, qui ne sont pas à proprement parler des concepts de la programmation fonctionnelle, mais sont néanmoins dans une large mesure héritées des langages fonctionnels tels que Lisp.

La seconde partie de ce tutoriel abordait réellement les concepts de la programmation fonctionnelle en Perl. Perl n'est pas à la base un langage fonctionnel, mais il permet d'utiliser de nombreuses notions empruntées aux langages fonctionnels, tout comme il permet aussi de faire de la programmation orientée objet. Le point essentiel est que c'est vous qui décidez du modèle de programmation qui vous désirez choisir, ou même d'une éventuelle combinaison de différents modèles de programmation.

Après un bref rappel sur les références en général, la seconde partie de ce tutoriel montrait comment il est possible d'utiliser des références sur des fonctions (ou coderefs, comme nous les appellerons le plus souvent désormais conformément à l'usage défini dans la seconde partie du tutoriel) et comment cette idée permet par exemple de passer une (référence à une) fonction en paramètre à une autre fonction pour créer des fonctions de rappel (ou callback functions). Inversement, ce même mécanisme permet à une fonction de renvoyer une référence à une fonction à la fonction appelante pour constituer un générateur de fonctions (ou une usine à fonctions). Quand une fonction peut être l'argument d'appel ou le paramètre de retour d'une fonction, on parle souvent, en langage de programmation fonctionnelle, de fonctions d'ordre supérieur ou de fonctions de première classe.

Ces deux mécanismes permettent d'obtenir un niveau d'indirection inexistant ou presque en programmation procédurale ordinaire. Nous avons notamment construit une fonction générique de parcours récursif d'un répertoire : la fonction se contentait de lire les objets d'un répertoire et de s'appeler récursivement si cet objet était lui-même un répertoire ; si en revanche l'objet en question était un fichier, cette fonction appelait la fonction reçue en paramètre pour assurer la partie fonctionnelle du traitement (par exemple mesurer la taille prise sur le disque, archiver les fichiers vieux de plus d'une certaine date ou effacer les fichiers temporaires devenus inutiles).

Nous avons également étudié les tables de distribution, une structure de données (généralement une table de hachage, mais éventuellement un tableau ou autre chose) qui permet de stocker dans une table les actions à effectuer (c'est-à-dire les fonctions à appeler) en fonction de la valeur d'une variable.

Nous avons ensuite étudié les fermetures (closures), un mécanisme extrêmement puissant permettant de créer des fonctions gardant leur environnement d'exécution d'un appel à l'autre. Cela permet notamment de créer des itérateurs (une fonction renvoyant à chaque appel l'élément suivant d'une liste qui n'a pas été nécessairement précalculée) et des usines à fonctions (une fonction qui renvoie à la demande d'autres fonctions utilisables dans la suite du programme).

Nous avons donné de nombreux exemples d'utilisation de ces techniques dans des environnements réels et espérons avoir démontré leur puissance pour simplifier le travail du développeur averti.

Le présent troisième volet de ce tutoriel vise à généraliser ces idées, à montrer comment il est possible d'utiliser toutes ces notions pour étendre le langage Perl en créant de véritables bibliothèques de fonctions génériques abstraites rendant le langage bien plus puissant.

2 - Des fonctions de listes allant plus loin que map et grep

2-1 - Une implémentation de map

Supposons pour commencer que nous voulions implémenter my_map, notre propre version de l'opérateur map, écrite en Perl pur. Il faudra sans doute lui passer en arguments une référence à une fonction et une liste.

2-1-1 - Fonction map : premiers essais

Nous pouvons commencer avec la version triviale suivante :

my_map1

print join " ", my_map (sub{$_ * 2}, 1..5);

sub my_map {
my $code_ref = shift;
return map {$code_ref->($_)} @_;
}
# imprime 2 4 6 8 10

Cela fonctionne bien, mais il faut noter que la syntaxe d'appel avec le mot-clef sub (et les parenthèses) est nécessaire (pour l'instant). L'appel suivant ne fonctionne pas :

print join " ", my_map ({$_ * 2}, 1..5); # faux
# imprime le message d'erreur suivant: Not a CODE reference at my_map.pl line 6.

De toute façon, créer une fonction my_map qui utilise la fonction Perl map ne nous avance pas beaucoup. Pour nous passer de l'opérateur map, nous pouvons par exemple utiliser une boucle while :

my_map2

print join " ", my_map (sub{$_ * 2}, 1..5);

sub my_map {
my $code_ref = shift;
my @d ;
while ($_ = shift ) {
push @d, $code_ref->($_);
}
return @d;
}

Ou encore (mieux à mes yeux) un modificateur for :

my_map3

print join " ", my_map (sub{$_ * 2}, 1..5);

sub my_map {
my $code_ref = shift;
my @d ;
push @d, $code_ref->($_) for @_;
return @d;
}

Mais il serait vraiment plus satisfaisant que la fonction my_map puisse utiliser une syntaxe plus simple comme celle de map, avec des accolades comme ci-dessous :

print join " ", my_map {$_ * 2} 1..5;

En fait, c'est tout à fait possible à condition d'utiliser une fonctionnalité Perl assez peu utilisée et parfois décriée non sans raison, les prototypes.

Je ne compte pas les messages sur les forums dans lesquels, en réponse à une personne selon toutes apparences assez débutante en Perl et présentant un bout de code Perl utilisant les prototypes pour ses appels de fonctions, j'ai écrit quelque chose du genre : « N'utilise pas de prototype en Perl, à moins que tu ne saches vraiment ce que cela fait et que tu en aies vraiment besoin. »

Je maintiens ce point de vue. Les prototypes Perl ne font pas la chose que ce que la plupart des programmeurs issus d'autres langages peuvent imaginer, il faut donc veiller à les utiliser à bon escient et en connaissance de cause (c'est-à-dire, généralement, seulement dans des cas assez particuliers). Ici, nous savons ce que nous faisons et avons de vraies bonnes raisons de les employer, et nous allons commencer à les utiliser assez abondamment.

2-1-2 - Les prototypes Perl

Lorsque les prototypes ont été introduits en Perl, le choix du terme prototype a sans doute été quelque peu malencontreux, parce que, malgré un certain air de famille, ils ne font pas la même chose que le prototype d'une fonction C, C++ ou Java (par exemple)(1). Peut-être aurait-il été plus judicieux de les appeler modèles ou templates. Sans entrer dans le détail, disons qu'un prototype Perl a deux effets principaux et un accessoire :

- il permet d'appeler une fonction définie par l'utilisateur comme les fonctions internes, sans avoir besoin d'utiliser des parenthèses pour englober les arguments passés à la fonction ;(2)

- c'est aussi un opérateur de coercition : il transforme par exemple un tableau passé en argument en une référence à un tableau si le prototype indique que c'est ce que la fonction appelée attend. C'est cette seconde propriété qui lui donne sa puissance, mais le rend un peu dangereux pour ceux qui ne comprennent pas bien cet aspect.

- Il a accessoirement et occasionnellement un rôle de validation du type des arguments passés en paramètres, comme l'envisagent des développeurs issus d'autres langages, mais seulement dans la mesure où la coercition mentionnée au paragraphe précédent n'a pas permis de modifier le type et entraîne donc le rejet du paramètre.

Attention : il faut bien comprendre les effets de la coercition des prototypes. Voici un exemple dans lequel la coercition mal utilisée provoque silencieusement une erreur :

Danger de la coercition

my @a = qw(toto titi);
sub count($@) { my $c = shift; return $c, "suivi de [@_]" }
say count(@a, "tutu", "tata");

Ce qui imprime :

2 suivi de [tutu tata]

Le « $ » du prototype a imposé un contexte scalaire si bien que le premier élément affiché est « 2 », le nombre d'éléments du tableau @a, qui est de plus entièrement consommé.

Les prototypes sont souvent mal compris, nous allons donc ouvrir une parenthèse pour essayer d'expliciter leur rôle par un exemple détaillé.

Prenons l'exemple de la fonction interne push de Perl. Elle prend en paramètres un tableau et une liste de valeurs et ajoute la liste de valeurs à la fin du tableau :

push

use strict;
use warnings;

my @array = qw / 1 2 3 /;
push @array, 4, 5;
print "@array", "\n"; #imprime 1 2 3 4 5

Supposons que nous voulions écrire en Perl une fonction similaire qui ajoute à la fin du tableau les carrés des nombres de la liste. Voici un premier début de tentative :

push_square1

use strict;
use warnings;
use Data::Dumper;

my @array = (1, 4, 9);
push_square(@array, 4, 5);
# print "@array", "\n";

sub push_square {
print Dumper \@_;
# code de la fonction à écrire
}

Le code de la fonction push_square n'est pas écrit pour la bonne raison que c'est impossible. L'utilisation de la fonction Dumper du module Data::Dumper montre le contenu de la variable @_, le tableau des arguments reçus par la fonction :

$ perl push_square.pl
$VAR1 = [
1,
4,
9,
4,
5
];

On constate que l'on obtient un seul tableau et qu'il est impossible de distinguer les éléments du tableau (qui sont déjà des carrés) de la liste des valeurs qu'il faut élever au carré avant de les ajouter à la fin du tableau. On dit que la liste des arguments a été « aplatie » en un seul tableau. Une seconde difficulté est que, même si l'on parvenait à distinguer le tableau d'origine de la liste de valeurs, par exemple en décrétant que cette fonction reçoit toujours en paramètres un tableau et une liste de deux valeurs à élever au carré, cela amenuiserait considérablement l'intérêt de cette fonction. En outre, selon la façon dont ce serait codé, cela pourrait poser des problèmes de sémantique entre copie et alias de tableau, mais l'on sort ici du cadre de ce tutoriel.

On arrivera sans doute à obtenir dans la fonction le tableau voulu (1, 4, 9, 16, 25), mais ces valeurs risquent d'être perdues lors du retour dans la procédure appelante, sauf si la procédure appelée renvoie le tableau résultat et si l'appelante le récupère. Par exemple, ceci fonctionne :

push_square2

my @array = (1, 4, 9);
@array = push_square(@array, 4, 5);
print "@array", "\n";  # imprime 1 4 9 16 25

sub push_square {
my @valeurs = splice @_, $#_ - 1, 2; # retire et récupère les deux dernières valeurs de @_
my @array = @_;
$_ = $_ * $_ foreach @valeurs;
push @array, @valeurs;
return @array;
}

Mais c'est du code d'une grande laideur et les autres solutions envisageables dans ce genre d'idée sont au moins aussi (voire plus) laides. Surtout, la fonction manque totalement de flexibilité, il faudrait en écrire une autre pour ajouter trois éléments au tableau.

L'autre solution, bien meilleure et déjà mentionnée dans la seconde partie de ce document, est évidemment de passer une référence au tableau. Cela résout d'un coup nos deux problèmes : on distingue aisément le tableau (plus exactement la référence à ce tableau) de la liste des valeurs, et le passage par référence permet de modifier directement et sans ambiguïté le tableau d'origine. Ceci peut donner le code suivant :

push_square3

my @array = (1, 4, 9);
push_square(\@array, 4, 5);
print "@array", "\n";   # imprime 1 4 9 16 25

sub push_square {
my $array_ref = shift;
push @$array_ref, map $_ ** 2, @_;
}

C'est nettement plus concis et très largement plus propre et plus lisible, mais si nous comparons la syntaxe d'appel de push_square :

push_square(\@array, 4, 5);

Avec celle de push :

push @array, 4, 5;

il reste de gros progrès de simplification à faire. Prédéclarer push_square permet de se passer des parenthèses :

push_square 4

sub push_square;
my @array = (1, 4, 9);
push_square \@array, 4, 5;
print "@array", "\n";   # imprime 1 4 9 16 25

sub push_square {
my $array_ref = shift;
push @$array_ref, map $_ ** 2, @_;
}

C'est déjà mieux, mais les prototypes vont nous permettre de résoudre les derniers problèmes :

push_square5

sub push_square(\@@);

my @array = (1, 4, 9);
push_square @array, 4, 5;
print "@array", "\n";   # imprime 1 4 9 16 25

sub push_square(\@@) {
my $array_ref = shift;
push @$array_ref, map $_ ** 2, @_;
}

Ici, la fonction a été prédéclarée (c'est nécessaire pour éviter des warnings et souvent des dysfonctionnements) avec son prototype, et définie plus bas. L'autre solution est de la définir avant de l'utiliser (bien souvent, les fonctions faisant appel à ces techniques se trouveront dans un module et seront donc tout naturellement définie avant l'utilisation lors de l'exécution de la ligne use package; au début du code du programme appelant ; le problème est dans ce cas inexistant et, donc, souvent très relatif).

push_square5 bis

sub push_square(\@@) {
my $array_ref = shift;
push @$array_ref, map $_ ** 2, @_;
}

my @array = (1, 4, 9);
push_square @array, 4, 5;
print "@array", "\n";   # imprime 1 4 9 16 25

Le prototype (\@@) signifie que la fonction attend une référence à un tableau suivi d'un tableau ou d'une liste.

Si nous utilisons la fonction Dumper comme précédemment pour visualiser le contenu du tableau @_ au moment de l'entrée dans la fonction push_square, nous obtenons ceci :

Dump du tableau @_

$ perl push_square.pl
$VAR1 = [
[
1,
4,
9
],
4,
5
];
1 4 9 16 25

La fonction reçoit cette fois en paramètre un tableau de trois éléments, dont le premier élément est une référence vers le tableau @array.

Bien que le premier argument effectivement passé à la fonction soit un tableau, Perl « comprend » qu'il doit l'utiliser comme une référence à un tableau (c'est l'aspect coercition) et se débrouille pour résoudre tous les problèmes rencontrés précédemment. Plus besoin de passer une référence au tableau (Perl le gère pour nous), et plus besoin de parenthèses dans la syntaxe d'appel :

push_square @array, 4, 5;

La fonction accède à un rang proche des opérateurs internes.

Les principaux prototypes utilisables sont les suivants.

Prototype

Signification

$

Impose un contexte scalaire. Mettre $$ pour deux scalaires.

@     %

Imposent un contexte de liste. Tous les arguments restants sont consommés.

&

Nécessite une coderef (référence à une fonction).

\$

Référence à un scalaire. L'argument doit commencer par un $.

\@     \%

Références à un tableau ou une table de hachage. L'argument doit commencer par un @ ou un %.

;

Indique que les arguments suivants sont optionnels (les précédents étant obligatoires).

Nous n'expliquerons pas plus en détail les différents prototypes utilisables (la documentation officielle le fait très bien et sans doute mieux que nous et ce n'est pas le sujet de ce document), mais espérons avoir fait comprendre le rôle et l'utilisation des prototypes. Cela devrait être suffisant pour ce qui suit.

2-1-3 - Des fonctions my_map et my_grep fonctionnelles

Il suffit donc de définir un prototype de la fonction my_map en sorte qu'elle reçoive une référence à une fonction et une liste :

sub my_map(&@);

pour que la syntaxe recherchée fonctionne correctement :

my_map4

# version avec proto et sans parenthèse
sub my_map(&@);  # le prototype doit figurer avant l'appel

my @tableau = 1..5;

print join " ", my_map {$_ * 2} @tableau;

sub my_map (&@){
my $code_ref = shift;
my @d;
push @d, $code_ref->($_) for @_;
return @d;
}
# imprime: 2 4 6 8 10

À noter que, comme le map interne de Perl, cette version de my_map modifie le tableau d'origine si le bloc de code passé en paramètre modifie la variable $_. Si l'on désire fabriquer une version fonctionnelle « plus pure » n'ayant pas cet effet de bord, il suffit de faire d'abord une copie du tableau reçu en paramètre et de modifier cette copie en sorte qu'elle ne modifie pas la tableau d'origine :

my_map5

sub my_map(&@);  # le prototype doit figurer avant l'appel

my @tableau = 1..5;

print "Nouveau tableau: ", join " ", my_map {++$_} @tableau;
print "\nTableau d'origine: ", "@tableau", "\n";

sub my_map (&@){
my $code_ref = shift;
my @d = @_;
$_ = $code_ref->($_) for @d;
return @d;
}
# imprime:
# Nouveau tableau: 2 3 4 5 6
# Tableau d'origine: 1 2 3 4 5

On constate que, bien que le bloc de code passé cette fois à la fonction modifie $_, le tableau d'origine reste inchangé, ce qui est plus dans l'esprit de la programmation fonctionnelle (mais un peu plus éloigné du map interne de Perl).

Comme nous l'avons vu dans la première partie de ce tutoriel, les fonctions map et grep de Perl ont une autre syntaxe d'appel, utilisant une expression et non un bloc de code. Cette syntaxe n'est pas accessible avec les techniques décrites ici. Nous devons donc nous en tenir à la syntaxe avec bloc de code, ce qui n'est guère gênant, puisque cela ne nous prive d'aucun pan de la fonctionnalité sous-jacente.

Il est possible, de même, d'écrire une fonction my_grep :

my_grep

sub my_grep (&@) {
my $code_ref = shift;
my @result;
push @result, $code_ref->($_) ? $_: () for @_;
return @result;
}
print join " ", my_grep {not $_ %2} (1..10);
# imprime 2 4 6 8 10

Écrire des fonctions comme my_map et my_grep reproduisant le plus fidèlement possible le fonctionnement des fonctions internes de Perl comme map et grep n'a évidemment aucun intérêt autre que purement pédagogique. Les fonctions internes Perl sont évidemment plus efficaces.

Mais l'on peut imaginer des cas où l'on désire justement obtenir une fonctionnalité proche de map ou de grep, mais faisant quelque chose de plus ou de légèrement différent. La version de my_map n'ayant pas d'effet de bord sur le tableau d'origine pourrait en être un exemple. Nous en verrons bientôt d'autres.

À titre d'exemple plus complet, examinons une mise en œuvre originale de la fonction sort de Perl.

2-2 - Écrire une fonction sort originale

Depuis la version 5.8 de Perl, la fonction sort de Perl implémente par défaut l'algorithme de tri connu sous le nom de tri fusion (mergesort). Les versions antérieures de Perl utilisaient l'algorithme dit du tri rapide (quicksort). La raison principale de ce changement est que, même si le tri rapide est généralement un peu plus rapide que le tri fusion, il y a des cas particuliers pour lesquels le tri rapide est bien moins efficace que le tri fusion (notamment quand les données sont déjà presque triées, en sens direct ou inverse). Et ces cas particuliers sont statistiquement exceptionnels sur des données aléatoires, mais en fait loin d'être rares dans la vie réelle : on doit souvent retrier une liste déjà triée à laquelle on a ajouté quelques éléments ou dont on a modifié seulement quelques-unes des valeurs de tri.

En théorie algorithmique, on dit que, pour trier n éléments, le tri fusion et le tri rapide ont tous les deux une complexité moyenne en O(n log n), avec généralement un léger avantage de rapidité au tri rapide, mais que le tri rapide à une complexité dans le pire des cas en O(n²), alors que le tri fusion a une complexité dans le pire des cas restant en O(n log n). D'où l'avantage d'utiliser le tri fusion, qui reste efficace dans tous les cas.

Supposons maintenant que nous voulions mettre en œuvre un autre algorithme de tri, dont les propriétés seraient hypothétiquement jugées meilleures. Pour cet exemple, nous allons choisir l'algorithme un peu exotique dit du « tri à peigne » (combsort ou tri de Dobosiewicz), décrit par exemple dans cet article sur le tri à peigne de Wikipédia. Cet algorithme possède globalement de bonnes propriétés (généralement supérieures au tri fusion), mais est peu utilisé dans la pratique parce son analyse théorique est extrêmement malaisée (en particulier, il semble qu'il ait un bon comportement dans le pire des cas, mais personne n'a réussi à le démontrer formellement jusqu'à présent). En fait, peu nous importent ici les qualités réelles de ce tri, nous voulons seulement illustrer la mise en œuvre d'une fonction sort particulière utilisant un algorithme de tri différent, nous aurions pu aussi bien choisir un algorithme connu pour avoir généralement de mauvaises performances, comme le tri à bulles. Il n'y a de toute façon aucune chance que cette mise en œuvre en Perl pur du tri à peigne soit plus efficace que le sort interne, écrit en C et très soigneusement optimisé par ses auteurs.

Pour fonctionner de façon analogue à la fonction interne sort, une fonction de tri doit recevoir en paramètres la fonction de comparaison utilisée par le tri et le tableau à trier et cette fonction de comparaison doit utiliser les variables globales spéciales $a et $b. La fonction de tri à peigne peut être mise en œuvre avec la fonction suivante :(3)

Tri à peigne

sub comb_sort (&\@) {
my $code_ref = shift;
my $v_ref = shift;
my $max = scalar (@$v_ref);
my $gap = $max;
while (1) {
my $swapped = 0;
$gap = int ($gap / 1.3);
$gap = 1 if $gap < 1;
my $lmax = $max - $gap - 1;
foreach my $i (0..$lmax) {
local ($a, $b) = ($$v_ref[$i], $$v_ref[$i+$gap]);
($$v_ref[$i], $$v_ref[$i+$gap], $swapped) = ($$v_ref[$i+$gap], $$v_ref[$i], 1)
if $code_ref->($a, $b) > 0;
}
last if $gap == 1 and $swapped == 0;
}
}

Nous affectons les valeurs à comparer aux variables globales spéciales $a et $b avant d'appeler la fonction de comparaison référencée par $code_ref reçue en paramètre (en prenant soin de les déclarer en local pour ne pas risquer d'altérer leur valeur globalement si elles sont utilisées ailleurs). Du coup, l'appel à la fonction comb_sort se fait avec exactement la même syntaxe qu'un appel à la fonction sort interne de Perl :

#!/usr/bin/perl
use strict;
use warnings;

my @v;
my $max = 500;

$v[$_] = int rand(20000) foreach (0..$max);

comb_sort {$a<=>$b} @v;
print "@v";

Ce qui fonctionne et imprime une liste correctement triée :

$ perl   my_sort.pl
23 96 113 133 213 259 279 339 374 391 451 458 553 641 680 728 729 750 772 775 908 920 1034 1038 1096 1099 1134 1269 1293 1303 1588 1673 1738 1742 1809 1840 1882 1967 1985 2023 2068 2112 2131 2184 2206 2206 2216 2229 2277 2323 2369 2383 2414 2442 2445 2448 2635 2672 2686 2687 2840 2859 2884 2934 2988 2998 3055 3057 3113 3167 3239 3240 3314 3421 3430 3468 3528 3586 3606 3609 3649 3667 3670 3756 3764 3789 3921 3931 3951 4000 4033 4044 4077 4190 4248 4308 4346 4379 4459 4501 4519 4564 4596 4597 4609 4625 4641 4715 4747 4791 4824 4840 4949 5035 5081 5086 5101 5125 5310 5409 (...)

2-3 - Une version avec itérateur de map (lazy_map)

On peut désirer combiner la propriété principale de l'opérateur map, à savoir appliquer une certaine transformation à une liste présentée en entrée et renvoyer en sortie les données modifiées par cette transformation, et la propriété principale d'un itérateur, à savoir ne fournir les données en sortie qu'une par une, à la demande de l'appelant. Cette nouvelle fonction ne renverrait pas une liste, mais un seul élément, en sortie, et sa sémantique est donc clairement différente de la fonction map de Perl, on pourrait faire remarquer non sans raison que cette nouvelle fonction n'a plus grand-chose à voir avec map. D'un autre côté, on peut arguer que cette fonction fait bien fondamentalement la même chose, appliquer la transformation considérée aux éléments de la liste fournie en entrée, mais qu'elle le fait simplement de façon dite « paresseuse » (ou avec évaluation retardée), ne renvoyant des valeurs que sur demande. Pour refléter cette vision, nous appellerons cette fonction lazy_map.

Quel est l'intérêt d'une fonction lazy_map ? Imaginons que nous ayons en entrée de cette fonction une liste assez longue d'entiers. Imaginons en outre que, selon les circonstances, notre traitement principal n'utilisera le plus souvent que quelques valeurs produites à partir de cette liste, et, seulement dans quelques cas rares ou exceptionnels, une partie beaucoup plus substantielle de cette liste. Il est peut-être inefficace, voire très inefficace, d'appliquer le traitement de transformation d'un map à une longue liste si, dans la très grande majorité des cas, on n'utilisera en fait que quelques-unes des valeurs calculées. Ce sera particulièrement le cas si le traitement de transformation du map est gros consommateur de ressources. Dans ce genre de cas, nous voudrions que le map ne calcule que les valeurs nécessaires et s'arrête de traiter la liste en entrée dès que la recherche a été fructueuse. C'est exactement ce que ferait lazy_map et ce que ne sait pas faire le map de Perl ou la fonction my_map vue précédemment (alors que l'on sait facilement arrêter une boucle for ou foreach au bon moment, ce qui peut rendre celle-ci bien plus efficace que le map de Perl dans ce genre de cas).

Par exemple, si le traitement effectué par la fonction passée à map est une décomposition en facteurs premiers des nombres de la liste, cela peut devenir coûteux en temps de traitement, surtout si les nombres de la liste deviennent grands. Il est alors bien préférable de ne faire l'opération que quand elle est strictement nécessaire.

2-3-1 - Le générateur d'itérateurs

Une façon simple de réaliser lazy_map est de lui passer non pas une fonction de rappel et un tableau comme à la fonction my_map, mais une fonction de rappel et un itérateur sur le tableau. Construisons d'abord cet itérateur, comme nous avons appris à le faire dans la seconde partie de ce tutoriel, à l'aide d'une fermeture générant une fonction d'itération anonyme. Cette fonction create_iter, qui pourra servir à bien d'autres usages, peut être particulièrement simple : on copie le tableau et renvoie une fonction anonyme dépilant un à un les éléments du tableau.

Générateur d'itérateurs

my @tableau = 1..5;
my $iterateur = create_iter(@tableau);
for (1..4) {
my $val = $iterateur->();
print $val, "\n" if defined $val;
}

sub create_iter {
my @array = @_;
return sub { shift @array}
}

Si nous désirons éviter de consommer de la mémoire (et du temps de traitement) en effectuant une copie du tableau, nous pouvons créer une fermeture qui conservera en mémoire une référence au tableau concerné et l'indice du prochain élément du tableau à utiliser. Comme nous avons également étudié les prototypes (§ #2.1.2.), nous en utiliserons un ici, bien que ce ne soit pas strictement nécessaire, mais cela rendra notre générateur d'itérateurs un peu plus convivial à l'usage, puisque l'utilisateur d'un module contenant ce générateur d'itérateurs pourra lui passer le tableau lui-même, et non une référence vers ce tableau.

Générateur d'itérateurs 2

sub create_iter(\@); # la déclaration avec le prototype doit figurer avant l'appel
my @tableau = 1..5;
my $iterateur = create_iter(@tableau);
for (1..4) {
my $val = $iterateur->();
print $val, "\n" if defined $val;
}

sub create_iter(\@) {
my $array_ref = shift;
my $index = 0;
return sub { $array_ref->[$index++];}
}

2-3-2 - La fonction lazy_map

2-3-2-a - Implémentation de la fonction lazy_map

Une fois l'itérateur mis en œuvre, la fonction lazy_map devient très simple à réaliser. Voici par exemple une fonction renvoyant à la demande et un par un les carrés des nombres contenus dans le tableau. Utilisons à titre d'exemple un tableau de nombres entiers décroissants de 7 à 1.

lazy_map

sub lazy_map(&$);  # le prototype doit figurer avant l'appel
sub create_iter(\@);

my @tableau = reverse 1..7;
my $iterateur = create_iter(@tableau);

for (1..5) {
my $val = lazy_map {$_**2} $iterateur;
print "Itération N° $_ : $val \n" if defined $val;
}

sub lazy_map (&$){
my ($code_ref, $iter) = @_;
local $_ = $iter->(); # lazy_map travaille sur $_ comme map
return unless defined $_;
return $code_ref->();
}

sub create_iter(\@) {
my $array_ref = shift;
my $index = 0;
return sub { $array_ref->[$index++];}
}

À l'exécution, cela donne :

$ perl  lazy_map.pl
Itération N° 1 : 49
Itération N° 2 : 36
Itération N° 3 : 25
Itération N° 4 : 16
Itération N° 5 : 9

Comme nous n'avons appelé la fonction lazy_map que cinq fois, celle-ci n'a fait le travail que pour les cinq premiers éléments du tableau (les nombres entiers naturels décroissants de 7 à 3) et s'est arrêtée là, sans calculer inutilement les valeurs correspondant aux autres éléments du tableau comme l'aurait fait la fonction map. La fonction lazy_map est bien paresseuse, ce qui était le résultat recherché. Vérifions ce que cela donne avec un benchmark.

2-3-2-b - Benchmark des fonctions lazy_map et map

Comparons les performances des fonctions map et lazy_map. La fonction map est écrite en C et hautement optimisée, alors que la fonction lazy_map est écrite en Perl pur et implique plusieurs appels de fonctions successifs à chaque itération, ce qui a forcément un surcoût. La fonction map devrait donc être assez nettement plus rapide quand elle travaille sur à peu près la même quantité de données que lazy_map. En revanche, quand lazy_map peut s'arrêter nettement plus tôt parce qu'elle a trouvé ce qu'elle cherchait, elle pourrait bien reprendre l'avantage.

Voyons ce qu'il en est. Les deux fonctions ayant une sémantique assez différente, il n'est pas si facile d'écrire un benchmark rendant les résultats réellement comparables. Nous avons essayé d'être le plus « juste » possible avec chacune des fonctions, de ne pas en favoriser une par rapport à l'autre.

Voici le code du benchmark :

Benchmark lazy_map

use strict;
use warnings;
use Benchmark;

my @tableau = ();# voir plus bas les deux cas;
my $iterateur = create_iter (@tableau);

sub lazy_map (&$){
my ($code_ref, $iter) = @_;
local $_ = $iter->(); # lazy_map travaille sur $_ comme map
return unless defined $_;
return $code_ref->();
}

sub create_iter {
my $array_ref = \@_;
my $index = 0;
return sub { $array_ref->[$index++];}
}

sub try_map {
my @c = grep {$_ == 15000} map { $_ * 2 } @tableau;
}
sub try_lazy_map {
my $iterateur = create_iter(@tableau);
while (1) {
my $val = lazy_map {$_*2} $iterateur;
last unless defined $val;
last if $val == 15000;
}
}

timethese ( 1000, {
"map"         => sub { try_map(); },
"lazy_map"     => sub { try_lazy_map() },
} );

Voyons maintenant ce qui se passe quand les deux fonctions font à peu près le même travail, en initialisant le tableau à 10000 :

Bench lazy_map 10000

my @tableau = 1..10000;

Voici le résultat :

Résultat bench lazy_map 10000

$ perl  bench_lazy_map.pl
Benchmark: timing 1000 iterations of lazy_map, map...
lazy_map: 12 wallclock secs (11.58 usr +  0.00 sys = 11.58 CPU) @ 86.39/s (n=1000)
map:  2 wallclock secs ( 2.28 usr +  0.00 sys =  2.21 CPU) @ 438.98/s (n=1000)

Dans ce cas, la fonction map est environ 5,1 fois plus rapide que la fonction lazy_map, ce qui n'est nullement surprenant.

Mais si le tableau en entrée est bien plus grand :

Bench lazy_map 100000

my @tableau = 1..100000;

le résultat est très différent :

Résultat bench lazy_map 100000

$ perl  bench_lazy_map.pl
Benchmark: timing 1000 iterations of lazy_map, map...
lazy_map: 13 wallclock secs (12.36 usr +  0.20 sys = 12.56 CPU) @ 79.63/s (n=1000)
map: 22 wallclock secs (22.39 usr +  0.00 sys = 22.39 CPU) @ 44.67/s (n=1000)

Cette fois, c'est lazy_map qui est environ 1,8 fois plus rapide. Avec un tableau en entrée de 1 000 000 d'éléments, lazy_map est environ 7 fois plus rapide.

La paresse a du bon, même si elle nous a en l'occurrence demandé pas mal de travail…

2-3-3 - Une fonction lazy_grep

Forts de notre expérience avec lazy_map, essayons de créer une fonction de filtrage lazy_grep sur le même modèle. Il s'agit de renvoyer la valeur reçue de l'itérateur si le bloc de code passé à lazy_map renvoie vrai. Cela n'est pas bien compliqué, mais cela pose un petit problème dès que l'on veut coder cela. Codons ceci pour récupérer les valeurs impaires du tableau :

lazy_grep 1

my @tableau = reverse 1..10;
my $iterateur = create_iter(@tableau);

sub lazy_grep (&$){
my ($code_ref, $iter) = @_;
local $_ = $iter->();
return unless defined $_;
return $_ if $code_ref->();
return;
}
for (1..9) {
my $val = lazy_grep {$_%2} $iterateur;
print "Itération N° $_ : $val \n" if defined $val;
}

À noter que le return de la dernière ligne de lazy_grep ne sert en fait à rien (la fonction sortirait de toute façon), mais il nous permet d'indiquer explicitement que la fonction retourne une valeur indéfinie si la fonction de rappel renvoie une valeur fausse.

Nous obtenons l'affichage suivant :

$ perl  lazy_grep.pl
Itération N° 2 : 9
Itération N° 4 : 7
Itération N° 6 : 5
Itération N° 8 : 3

Cela peut sembler marcher à toute première vue (nous récupérons bien les valeurs impaires), mais il y a un problème : les itérations 1, 3, 5, 7 et 9 ne font rien, et pour cause : lazy_grep retourne une valeur indéfinie si l'itérateur retourne une valeur paire.

Cela n'est sans doute pas la sémantique que nous souhaitons réellement pour une fonction lazy_grep (bien que nous n'ayons pas défini de façon détaillée le comportement souhaité pour l'instant). Cela est bien sûr discutable, mais l'on désire a priori qu'une telle fonction ne retourne pas la valeur du tableau ou undef selon que le bloc passé à la fonction retourne vrai ou faux, mais plutôt que la fonction retourne la prochaine valeur du tableau pour laquelle la condition dudit bloc est vraie.

Si nous désirons que lazy_grep retourne la prochaine valeur du tableau pour laquelle la condition du bloc est vraie, nous pouvons ajouter une boucle rappelant l'itérateur jusqu'à ce que la condition soit vraie :

lazy_grep 2

sub lazy_grep (&$){
my ($code_ref, $iter) = @_;
while (1) {
local $_ = $iter->() ;
return unless defined $_; # éviter une boucle infinie
return $_ if $code_ref->();
}
}

my @tableau = reverse 1..10;
my $iterateur = create_iter(@tableau);

for my $i (1..8) {
my $val = lazy_grep {$_%2} $iterateur;
print "Itération N° $i : $val \n" if defined $val;
}

Cela fonctionne maintenant comme souhaité :

$ perl  lazy_grep.pl
Itération N° 1 : 9
Itération N° 2 : 7
Itération N° 3 : 5
Itération N° 4 : 3
Itération N° 5 : 1

Le code de cette nouvelle version de lazy_grep est très simple, mais il a fallu faire bien attention de prendre les précautions nécessaires pour éviter que le code ne puisse entrer dans une boucle infinie une fois le tableau épuisé (et s'arrête, dans l'exemple, après l'itération 5) et pour bien distinguer les valeurs fausses renvoyées par l'itérateur (undef si le tableau est épuisé) des valeurs fausses renvoyées par la fonction de rappel référencée par $code_ref.

Ceci nous amène à un second problème plus subtil de notre itérateur, le problème dit du semi-prédicat (semi-predicate problem).

2-3-4 - Le problème du semi-prédicat

Le problème du semi-prédicat se pose lorsqu'une fonction renvoie par exemple une valeur fausse dans deux cas de figure différents : si elle a échoué, ou s'il peut arriver qu'elle renvoie par exemple un zéro qui sera interprété comme une valeur fausse dans de nombreux langages comme Perl ou C. Il n'est alors pas possible de distinguer les deux cas de figure.

Le terme « problème du semi-prédicat » provient à l'origine des langages fonctionnels (en particulier Lisp). Dans un langage fonctionnel tel que par exemple Lisp ou Scheme, un semi-prédicat est une espèce de fonction qui calcule normalement une valeur utile, mais renvoie un booléen faux (ou NIL) si elle n'a pas été en mesure de calculer une valeur utile, ce qui permet par exemple de lever une exception. Cela fonctionne généralement bien, mais pose un problème si la valeur utile recherchée peut, dans certains cas, être une valeur booléenne fausse. Précisons que le problème n'est pas du tout propre aux langages fonctionnels et qu'on le retrouve fréquemment dans beaucoup d'autres langages, mais il se trouve que le nom habituellement donné à ce problème provient historiquement des différentes variantes de Lisp et d'autres langages fonctionnels (même si les langages fonctionnels fortement typés ont été les premiers à apporter une solution élégante à ce problème).

C'est pour éviter le même genre de problème que Perl possède par exemple deux fonctions différentes pour tester la valeur d'un hash : exists et defined. S'il n'y avait pas ces deux fonctions, il serait impossible de distinguer le cas où le hash existe pour une clef, mais la valeur associée est indéfinie de celui où ce hash n'existe pas pour cette clef. De même, il existe dans Perl une chaîne de caractères particulière, « 0 but true », permettant de faire la distinction entre le chiffre 0 et une valeur booléenne fausse : « 0 but true » vaut zéro dans un calcul ou une comparaison numérique, mais est vrai dans un contexte booléen.

Notre itérateur de tableau présente ce problème du semi-prédicat : il renvoie implicitement undef quand le tableau est épuisé et le programme utilisateur de cet itérateur peut donc conclure que le tableau est épuisé s'il reçoit la valeur undef. Mais ce n'est pas nécessairement le cas : on peut très bien avoir dans certains cas une valeur undef dans un tableau sans pour autant avoir atteint la fin du tableau.

Ainsi, si nous initialisons notre tableau comme suit :

my @tableau = reverse 1..10;
@tableau[20..30] = (20..30);

Le tableau aura 31 éléments, mais les éléments d'indices 10 à 19 seront indéfinis, et la fonction lazy_grep ne fonctionnera plus convenablement. Avec 20 itérations, cela donnera le résultat suivant :

Itération N° 1 : 9
Itération N° 2 : 7
Itération N° 3 : 5
Itération N° 4 : 3
Itération N° 5 : 1
Itération N° 16 : 21
Itération N° 17 : 23
Itération N° 18 : 25
Itération N° 19 : 27
Itération N° 20 : 29

Même si la fonction lazy_grep finit par renvoyer toutes les valeurs adéquates, elle ne le fait pas au bon moment : compte tenu de la sémantique de fonctionnement que nous avons choisie, la valeur 21 aurait dû être retournée dès la sixième itération, mais les itérations 6 à 15 ont reçu une valeur undef et n'ont donc pas cherché à aller plus loin. Mais si nous modifions le contenu de la boucle while pour ne pas sortir sur une valeur undef renvoyée par l'itérateur, alors nous risquons d'entrer dans une boucle infinie quand nous atteignons la fin du tableau, ce qui n'est éminemment pas souhaitable. Le problème est donc que lazy_grep n'a aucun moyen de distinguer les deux cas de figure. C'est d'abord l'itérateur qu'il faut modifier. Comme il n'existe pas de valeur analogue à « 0 but true », du genre « undef but true », en Perl, il nous faut un autre moyen de distinguer les trois cas de figure : renvoi d'une valeur définie, renvoi d'une valeur indiquant que l'élément courant du tableau n'est pas défini, et renvoi d'une valeur indiquant que le tableau est épuisé. Si vous commencez à avoir mal à la tête, faites une petite pause !

Une fois le problème identifié, il est facile d'y trouver une solution. Nous pouvons par exemple renvoyer une référence à l'élément courant du tableau tant que le tableau n'est pas épuisé, et renvoyer undef quand nous dépassons les bornes du tableau. La fonction appelante n'aura guère de difficulté à faire la distinction entre une valeur undef et une référence définie à une valeur non définie.

Voici donc une nouvelle version du générateur d'itérateurs :

générateur d'itérateurs 3

sub create_iter(\@) {
my $array_ref = shift;
my $index = 0;
my $max = $#{$array_ref}; # dernier élément du tableau
return sub {
return undef if $index > $max;
\$array_ref->[$index++];
}
}

Maintenant que la fonction de génération d'itérateur est corrigée, nous pouvons la mettre dans un module d'utilitaires de fonctions de listes et l'oublier. Il nous reste cependant à modifier lazy_grep et lazy_map pour tenir compte des valeurs maintenant renvoyées par l'itérateur.

2-3-5 - Fonctions lazy_grep et lazy_map : versions finales

Voici la nouvelle version de lazy_grep :

lazy_grep (finale)

sub lazy_grep (&$){
my ($code_ref, $iter) = @_;
while (1) {
my $iref = $iter->();
return unless $iref; # sort si le tableau est épuisé
local $_ = $$iref;
next unless defined $_; # reboucle si la valeur n'est pas définie
return $_ if $code_ref->();
}
}

Avec le tableau possédant les éléments d'indices 10 à 19 indéfinis utilisé précédemment, le résultat est maintenant conforme aux attentes :

Itération N° 1 : 9
Itération N° 2 : 7
Itération N° 3 : 5
Itération N° 4 : 3
Itération N° 5 : 1
Itération N° 6 : 21
Itération N° 7 : 23
Itération N° 8 : 25
Itération N° 9 : 27
Itération N° 10 : 29

La fonction lazy_map vue précédemment ne souffre pas du problème du semi-prédicat et fonctionne parfaitement même si le tableau contient des valeurs indéfinies. Nous devons cependant l'adapter puisque nous avons modifié l'itérateur (commun à lazy_grep et à lazy_map) qu'elle utilise.

lazy_map (finale)

sub lazy_map (&$){
my ($code_ref, $iter) = @_;
local $_ = ${$iter->()};
return unless defined $_;
return $code_ref->();
}

2-4 - Des itérateurs plus versatiles

L'itérateur utilisé ci-dessus pour la mise en œuvre des fonctions lazy_map et lazy_grep est très simple : il dépile de la source une seule valeur à la fois et renvoie au demandeur une seule valeur à la fois. C'est normal, c'est ce que l'on demande le plus souvent à un itérateur. Mais l'on peut imaginer des cas où il serait souhaitable que l'itérateur renvoie, par exemple, des couples ou des triplets de valeurs. On peut même imaginer des cas un peu plus complexes où l'on souhaite que l'itérateur renvoie deux valeurs, mais n'en dépile qu'une seule : par exemple, si la source des données est la suite des entiers naturels pairs supérieurs à 0, on peut vouloir recevoir à chaque appel un couple de valeurs de la suite suivante : (2,4), (4,6), (6,8), etc.

2-4-1 - Consommer et renvoyer deux valeurs à chaque demande

Premier cas pratique : notre liste en entrée contient en fait des couples (ou triplets ou autres combinaisons) de valeurs, et nous désirons par conséquent consommer et renvoyer deux (ou plusieurs) valeurs à chaque demande.

Traitons cette fois d'entrée de jeu le problème du semi-prédicat examiné précédemment. L'itérateur renverra undef si la liste en entrée est épuisée, et un tableau contenant deux (ou plusieurs) valeurs dans le cas contraire. À charge pour la fonction utilisatrice de vérifier si le tableau reçu en retour est défini ou non.

Le générateur d'itérateurs create_iter_n diffère assez peu de ce que nous avions précédemment. Il reçoit en paramètres deux arguments : le nombre d'éléments à renvoyer à chaque itération et une référence sur le tableau à exploiter. L'itérateur proprement dit utilise le tableau temporaire @return_array qui sera retourné à la fonction appelante.

create_iter_n

sub create_iter_n($\@) {
my ($nb_items, $array_ref) = @_;
my $index = 0;
my $max = $#{$array_ref} + 1; # dernier élément du tableau + 1
# car on teste $index après l'incrémentation
return sub {
my @return_array;
push @return_array, $array_ref->[$index++] for 1..$nb_items;
return undef if $index > $max;
return @return_array;
}
}

Le générateur d'itérateurs permet maintenant de créer par exemple trois itérateurs indépendants, renvoyant des paires, des triplets et des quadruplets de valeurs :

Utilisation de create_iter_n

my @input_array = 1..20;
my $get_2_items = create_iter_n 2, @input_array; # itérateur de paires
my $get_3_items = create_iter_n 3, @input_array; # itérateur de triplets
my $get_4_items = create_iter_n 4, @input_array; # itérateur de quadruplets

print "\nPaires:\n";
for (1..7) {
print join " ", grep defined $_, $get_2_items->();
print "\n";
}
print "\nTriplets:\n";
for (1..5) {
print join " ", grep defined $_, $get_3_items->();
print "\n";
}
print "\nQuadruplets:\n";
for (1..10) {
print join " ", grep defined $_, $get_4_items->();
print "\n";
}

L'exécution montre que les itérateurs sont bien indépendants les uns des autres :

$ perl iter_n.pl

Paires:
1 2
3 4
5 6
7 8
9 10
11 12
13 14

Triplets:
1 2 3
4 5 6
7 8 9
10 11 12
13 14 15

Quadruplets:
1 2 3 4
5 6 7 8
9 10 11 12
13 14 15 16
17 18 19 20

2-4-2 - Consommer une valeur et en renvoyer deux (ou plus)

Supposons que nous voulions trouver, dans un tableau de valeurs numériques croissantes, la première dont l'écart avec la suivante est supérieur à un certain nombre minimal donné. Si nous utilisons un itérateur celui-ci ne devra consommer qu'une seule valeur à chaque appel, mais devra en renvoyer deux, afin que la fonction appelante puisse calculer la différence.

Cela peut se faire avec la version minimaliste suivante :

create_iter_1_2

use strict;
use warnings;

sub create_iter_1_2(\@) {
my $array_ref = shift;
my $index = 0;
my $max = $#{$array_ref} + 1;
return sub {
return undef if $index > $max;
return ($array_ref->[$index++], $array_ref->[$index]);
}
}

my @input_array = (1..5, 7, 11, 18, 34..39);
my $get_2_items = create_iter_1_2 @input_array;

while (1) {
my ($c, $d) = $get_2_items->();
last unless defined $d;
print "$c $d\n" and last if $d - $c > 5;
}

Ce programme affiche ce qui suit :

$ perl iter_1_2.pl
11 18

Bien sûr, s'il s'agit de seulement faire ce qui précède, il y a des moyens plus simples d'arriver au résultat, sans faire appel à des itérateurs. Mais ce code peut-être enrichi à la lumière des exemples précédents. Moyennant quelques modifications, il est facile de rendre entièrement paramétrables aussi bien le nombre d'éléments renvoyés à la procédure appelante que le nombre d'éléments consommés à chaque appel. Cela ne posant aucune difficulté technique, le lecteur pourra expérimenter à sa guise ces versions plus riches fonctionnellement s'il le désire.

3 - Une nouvelle fonction de liste : reduce

3-1 - Expression du besoin

Supposons que nous voulions écrire une fonction calculant l'élément le plus grand d'une liste de nombres. Rien de bien compliqué :

max

sub max {
my $max = shift; # initialise $max au 1er élément du tableau
for (@_) { $max = $_ if $_ > $max; };
return $max;
}

S'il nous faut également une fonction trouvant l'élément le plus petit d'une liste nous pouvons faire de même :

min

sub min {
my $min = shift;
for (@_) { $min = $_ if $_ < $min; };
return $min;
}

Pour calculer la somme des éléments d'une liste :

somme

sub somme {
my $sum = shift;
for (@_) { $sum += $_; };
return $sum;
}

Comme lorsque nous voulions parcourir une arborescence de répertoire (voir la partie 2 de ce tutoriel)), nous nous retrouvons à nouveau à écrire plusieurs fois presque le même code. Et, en bons programmeurs que nous sommes ou avons l'ambition de devenir, quand ce genre de situation se présente, nous nous demandons comment nous pourrions éviter d'écrire plusieurs fois la même chose.

Le lecteur perspicace aura sans doute deviné que, pour résoudre ce genre de problème, nous désirons passer à la fonction une fonction de rappel, donc une référence à une autre fonction.

3-1-1 - Essais avec une fonction de rappel

Faisons un premier essai :

somme avec coderef

use strict;
use warnings;

my @c = 1..10;
my $sum_ref = sub {my $value = shift; for (@_) { $value += $_; }; return $value;};
my $somme = traite($sum_ref, @c);

sub traite {
my $code_ref = shift;
return $code_ref->(@_);
}
print "\n $somme \n";

Certes, cela fonctionne et retourne bien 55, ce qui correspond à la somme des dix premiers entiers, mais nous n'avons fait que déplacer le problème. La fonction traite ne fait pas grand-chose et ne sert pratiquement à rien, toute la logique se retrouve dans la coderef, si bien que le code sera à nouveau dupliqué quand nous écrirons les références aux fonctions max ou min. Peu d'intérêt pratique en définitive.

Essayons alors de déplacer le code dupliqué dans la fonction traite de façon à ce que la coderef ne contienne que le code relatif à la somme proprement dite. Par exemple quelque chose comme cela :

Somme avec coderef 2

use strict;
use warnings;

my @c = 1..10;
my $sum_ref = sub {$value += $_; }; # ne marche pas
my $somme = traite ($sum_ref, @c);

sub traite {
my $code_ref = shift;
my $value = shift;
code_ref->($_) for (@_)
return $value;
}
print "\n $somme \n";

Plus rien ne marche, le programme ne compile même pas. Nous rencontrons un problème analogue avec celui de nos premières tentatives d'itérateurs sur des carrés d'entiers successifs (dans la partie 2 de ce tutoriel) : nous ne savons pas comment déclarer la variable $value pour qu'elle soit définie et persistante.

3-1-2 - Un générateur de fermetures anonymes

Nous avons déjà rencontré ce genre de problème et connaissons une solution possible : les fermetures et les générateurs de fonctions. Au lieu d'utiliser une fonction de rappel appelée par la fonction traite, nous avons besoin de créer un générateur de fonctions fermetures anonymes, ce qui implique une inversion des sémantiques d'appel : on crée une fonction sum qui définit la coderef assurant le traitement fonctionnel et passe cette coderef à une fonction traite (bien différente de la précédente) assurant la partie technique du traitement (l'itération et l'accumulation). Cette logique peut nous donner ceci :

Somme avec sémantique inversée

use strict;
use warnings;

my @c = 1..10;
my $somme = sum(@c);

sub traite {
my $code_ref = shift;
local $a = $code_ref->($_) for @_;
return $a;
}

sub sum {
return traite (sub { $a += $_ }, @_);
}
print "\n $somme \n";

Cette fois, cela marche, le programme affiche bien la somme des 10 premiers entiers positifs (55). Et, surtout, nous avons atteint nos deux objectifs :

- Le code de la fonction spécifique (sum) est court et non dupliqué ;

- Le code technique répétitif est bien déporté dans une fonction générique (traite).

Nous avons utilisé ici la variable $a (une variable déclarée globalement par défaut pour faciliter l'utilisation de la fonction sort). Nous aurions pu utiliser une autre variable déclarée globalement ou lexicalement, mais comme nous allons utiliser dans la suite immédiate les variables spéciales $a et $b dans un contexte analogue à la fonction sort, autant s'habituer dès maintenant à ces variables particulières.

Si nous désirons calculer l'élément le plus grand d'une liste, il suffit d'appeler la fonction max suivante à la place de la fonction sum:

Fonction max

sub max {
local $a = shift;
return traite (sub { $a = $_ if $_ > $a }, @_);
}

La première ligne de la fonction ci-dessus n'est pas réellement indispensable au bon fonctionnement de la fonction, mais elle évite un warning disant que la variable $a n'est pas initialisée lors du premier appel de la coderef.

Cette fois, nous avons le sentiment de « tenir » à peu près la solution, mais on ne peut pas dire que le code présenté soit réellement satisfaisant. Il est un peu laborieux et contraint l'utilisateur de notre fonction traite (celui qui va écrire la fonction max ou sum) à comprendre une syntaxe quelque peu rébarbative, alors que nous voudrions écrire un module simple d'utilisation, même pour un débutant en Perl.

Idéalement, nous aimerions pouvoir utiliser une fonction générique analogue à map ou grep, et lui passer un bloc de code assurant la partie fonctionnelle (le max, le min ou le sum). Dans les langages (généralement fonctionnels) où elle existe, cette fonction s'appelle généralement reduce, car le but est, en définitive, de réduire une liste de valeurs à une seule valeur, qui pourra être, selon l'objectif et la nature des données, le maximum, le minimum, le mot le plus long, le nombre d'éléments, la somme, le produit, la moyenne, la médiane, le quartile (ou décile) inférieur (ou supérieur), la valeur la plus commune, la plus rare, la variance, l'écart-type, etc.

3-2 - La fonction reduce, première version

Forts de ce que nous avons fait pour écrire des versions purement Perl des fonctions map ou grep, nous n'avons guère de difficulté pour écrire une fonction reduce fondée sur le même modèle :

reduce 1

sub reduce(&@) {
my $code_ref = shift;
my $result = shift;
$result = $code_ref->($result, $_) for  @_;
return $result;
}

Le prototype de la fonction indique qu'elle reçoit une coderef et une liste. La fonction dépile la coderef et le premier élément de la liste, puis applique la coderef aux autres éléments de la liste, et renvoie le résultat final. Plus précisément, le premier élément de la liste devient le résultat provisoire, et la coderef est appelée, pour chaque élément de la liste, avec pour paramètres ce résultat provisoire et un nouvel élément de la liste, et la coderef renvoie le nouveau résultat provisoire. Une fois les éléments de la liste épuisés, le résultat provisoire devient le résultat définitif et est renvoyé à l'appelant de la fonction reduce.

L'élément le plus grand d'une liste numérique peut maintenant être trouvé comme suit :

max avec reduce

my $max = reduce {
my ($result, $new_val) = @_;
return $result if $result > $new_val;
return $new_val;
} @tableau;

L'utilisation directe du tableau @_ des paramètres passés à la fonction et de l'opérateur ternaire « ?: » va permettre d'obtenir une syntaxe bien plus compacte. Par exemple, pour trouver le minimum, le maximum et la somme des éléments d'une liste de nombres de 1 à 20, il est maintenant possible d'appeler la fonction reduce comme suit :

Utilisation de reduce 1

sub reduce(&@);

my $max = reduce {$_[0] > $_[1] ? $_[0] : $_[1]} 1..20;
my $min = reduce {$_[0] > $_[1] ? $_[1] : $_[0]} 1..20;
my $sum = reduce {$_[0] + $_[1]} 1..20;

L'objectif recherché est atteint : il n'y a plus de code dupliqué. Et le code utilisé est parfaitement générique et fonctionnera avec une liste numérique quelconque. Si bien que, tant qu'à avoir défini le code pour trouver le maximum, le minimum et la somme des éléments d'une liste, autant mettre ce code dans des fonctions réutilisables :

Fonctions min, max, etc.

sub reduce(&@);

sub max { reduce {$_[0] > $_[1] ? $_[0] : $_[1]} @_}
sub min { reduce {$_[0] > $_[1] ? $_[1] : $_[0]} @_}
sub sum { reduce {$_[0] + $_[1]} @_}

Arrêtons-nous un instant pour réfléchir à ce que nous venons de faire. Nous avons d'abord créé une fonction reduce recevant en paramètres une coderef et une liste. Puis nous avons utilisé cette fonction reduce pour créer de nouvelles fonctions à la demande. Nous venons de découvrir une nouvelle façon de créer dynamiquement de nouvelles fonctions.

Tout cela est bien beau, mais il reste un petit problème : si nous devons demander à l'utilisateur de notre fonction reduce d'utiliser une syntaxe un peu cryptique du genre :

{$_[0] > $_[1] ? $_[0] : $_[1]}

Il n'est pas sûr que nous arrivions à le convaincre. Essayons donc de simplifier l'interface.

3-3 - La fonction reduce, nouvelle version

Le lecteur se souviendra sans doute des variables spéciales $a et $b utilisées par la fonction sort, pas seulement par la fonction sort interne de Perl, mais aussi par celle que nous avons implémentée en Perl pur avec l'algorithme un peu exotique du tri à peigne. Nous sommes ici dans un cas assez similaire : nous aimerions utiliser deux variables, l'une contenant le résultat courant et l'autre la nouvelle valeur à tester. Notre fonction reduce sera un peu plus complexe, mais l'interface offerte à l'utilisateur de notre fonction sera quant à elle plus simple (ce qui va généralement dans la bonne direction si l'on désire voir beaucoup de personnes utiliser nos modules).

3-3-1 - Code de la nouvelle version de reduce

Remplaçons notre précédente version de la fonction reduce:

reduce 1

sub reduce(&@) {
my $code_ref = shift;
my $result = shift;
$result = $code_ref->($result, $_) for  @_;
return $result;
}

par cette nouvelle version plus conviviale (pour son utilisateur):

reduce (2)

sub reduce (&@) {
my $code_ref = shift;
my $result = shift;
for (@_ ) {
local ($a, $b) = ($result, $_ );
$result = $code_ref->($a, $b )
}
return $result;
}

La fonction reduce a maintenant trois lignes de plus, mais au lieu de rechercher le plus grand élément d'un tableau ainsi :

my $max = reduce {$_[0] > $_[1] ? $_[0] : $_[1]}, @_;

L'utilisateur peut maintenant écrire:

my $max = reduce { $a > $b ? $a : $b } @_;

Cela ne change pas le fonctionnement du code, mais c'est tout de même plus lisible et plus facile à coder.

3-3-2 - Le problème de la liste vide

Considérons le morceau de programme suivant utilisant la fonction reduce pour construire les fonctions max et sum:

Fonctions max et sum

my @a = 1..10;
print join " ", max(@a), sum(@a);

sub max { reduce { $a > $b ? $a : $b } @_; }
sub sum { reduce { $a + $b } @_; }

Il imprime bien 10 et 55, le maximum et la somme des éléments du tableau @a.

Que se passe-t-il si le tableau @a est vide ?

On obtient deux fois le message d'erreur suivant sur la ligne effectuant le print join :

Message d'erreur liste vide

Use of uninitialized value in join or string at ...
Use of uninitialized value in join or string at ...

En cas de liste vide, la fonction reduce retourne une valeur non définie. Dans le cas de la fonction max (ou d'une fonction min construite sur le même principe), c'est tout à fait normal : il n'est pas possible de définir la valeur maximale d'une liste vide et il incombe donc au développeur utilisant la fonction max de prendre ses précautions, soit en testant que le tableau n'est pas vide avant d'appeler la fonction max, soit en testant que la valeur retournée par max est définie avant de l'utiliser. Par exemple :

my @a = ();
my $maximum = max(@a);
print $maximum, "\n" if defined $maximum;

sub max { reduce { $a > $b ? $a : $b } @_; }

Cela ne générera plus d'avertissement intempestif.(4)

Dans le cas de la fonction sum, en revanche, il serait plus satisfaisant qu'elle retourne 0, car on peut considérer non sans raison que la somme des éléments d'une liste vide est définie et égale à 0.

Il serait possible d'écrire la fonction sum comme suit :

Fonction sum 1

sub sum {
return 0 unless scalar @_;
reduce { $a + $b } @_;
}

Mais il est plus simple d'ajouter systématiquement 0 en début de la liste passée en paramètre à reduce dans la définition de sum:

sum 2

my @a = ();
print sum(@a);

sub sum { reduce { $a + $b } 0, @_; }

Cette fois, cela fonctionne correctement : la fonction sum retourne bien un zéro

Le problème plus général, même quand la liste n'est pas vide, est que la fonction reduce initialise sa future valeur de retour avec le premier élément de la liste, ce qui marche avec des fonctions comme max, min ou sum (du moins quand la liste n'est pas vide dans le cas de sum), mais n'est pas correct dans tous les cas où l'on voudrait l'utiliser. Il convient alors d'ajouter en tête de la liste l'élément nécessaire pour permettre un calcul correct.

Supposons que nous voulions utiliser la fonction reduce pour créer une fonction destinée à calculer le nombre d'éléments d'une liste ou d'un tableau. Cela ne sert à rien puisque la fonction interne scalar le fait très bien :

scalar

my @a = 1..10;
print scalar @a;  # imprime 10

Si nous voulons quand même, à de seules fins d'expérimentation, utiliser la fonction reduce pour décompter le nombre d'éléments d'une liste, nous pourrions tenter ceci :

Count (erroné)

my $nr_elmnts = count (1..10);
print "$nr_elmnts \n"; # imprime 10

sub count { reduce { $a + 1 } @_; };

Ceci imprime 10, le nombre d'éléments de la liste, mais c'est (presque) un coup de chance. Si l'on modifie la première ligne du code ci-dessus comme suit :

count (erroné)

my $nr_elmnts = count (reverse 1..10);

Cela affiche maintenant 19, ce qui est clairement incorrect. La première version semblait fonctionner parce que le premier élément de la liste était 1. Dans le second cas, la liste commence par 10 et la fonction reduce initialise la première valeur de la variable $a à 10, puis ajoute 1 pour chaque nouvel élément rencontré.

La solution ne pose pas de problème particulier : comme dans le cas de la fonction sum, il suffit d'ajouter un 0 en tête de la liste pour que la fonction count fonctionne correctement :

count (corrigé)

my $nr_elmnts = count (reverse 1..10);
print "$nr_elmnts \n";

sub count { reduce { $a + 1 } 0, @_; };

Nous avons certes ajouté un élément à la liste, mais comme nous l'avons compté à 0, le premier élément de la vraie liste a été compté à 1, et ainsi de suite, et le nombre d'éléments de la liste retourné par reduce est en définitive correct.

La fonction count décrite ici n'a aucun intérêt autre que pédagogique puisque, comme nous l'avons dit, Perl possède en interne le moyen de compter les éléments d'un tableau (affectation du tableau à une variable en contexte scalaire) ou d'une liste (utilisation de la fonction scalar). Cela montre cependant qu'il faut prendre quelques précautions dans l'utilisation de la fonction reduce pour construire des fonctions de listes.

3-4 - Une bibliothèque de fonctions de listes utilisant reduce

3-4-1 - Fonctions de listes simples

Maintenant que nous avons créé cette version finale (ou presque) de la fonction reduce, nous pouvons l'utiliser pour créer toute une bibliothèque de fonctions de listes :

Bibliothèque avec reduce

sub max {
reduce { $a > $b ? $a : $b } @_;
}
sub min {
reduce { $a > $b ? $b : $a } @_;
}
sub sum {
reduce { $a + $b } 0, @_;
}
sub product {
reduce { $a * $b } @_;
}
sub avg {      # moyenne
return undef unless @_; # éviter une division par 0
sum (@_)/scalar @_;
}
sub variance {
return undef unless @_; # éviter une division par 0
my $moyenne = avg (@_);
sum ( map {($_ - $moyenne)**2} @_ )/ scalar @_;
# cette dernière ligne pourrait s'écrire plus simplement:
# avg ( map {($_ - $moyenne)**2} @_ );
}
sub std_dev {      # écart-type
sqrt variance (@_);
}
sub maxstr {
reduce { $a gt $b ? $a : $b } @_;
}
sub minstr {
reduce { $a gt $b ? $b : $a } @_;
}
sub longest_str {
reduce { length $a > length $b ? $a : $b } @_;
}
sub shortest_str {
reduce { length $a > length $b ? $b : $a } @_;
}
sub concatenate {
return reduce { $a . $b } @_;
# si l'on préfère considérer que la concaténation d'une
# liste vide est une chaîne vide, mettre plutôt :
# return reduce { $a . $b } "", @_;
}

On constate que nous avons considérablement étendu les fonctionnalités de Perl relatives aux listes et qu'il est très facile de construire toute une bibliothèque de fonctions très simples agissant sur des listes.

Ne vous lancez cependant pas trop hâtivement dans ce genre de projet, cher lecteur, car je ne suis pas le premier (loin s'en faut) à avoir eu cette idée et cette bibliothèque existe déjà depuis longtemps (du moins en grande partie) dans un excellent module standard Perl, List::Util, d'Adam Kennedy et Tassilo von Parseval (et sans doute quelques autres). Les fonctions de cette bibliothèque sont écrites en C et seront sans doute généralement plus rapides que les fonctions Perl pures écrites ci-dessus. (Il existe également un module supplémentaire offrant des fonctionnalités additionnelles, List::MoreUtils, que nous incitons le lecteur cherchant des fonctionnalités de listes supplémentaires à explorer.) Et si les fonctions que vous désirez employer n'existent pas dans le module List::Util (c'est le cas par exemple des fonctions avg, variance et std_dev (écart-type) ci-dessus), essayez d'utiliser plutôt la version List::Util de reduce que la version Perl pure que nous avons écrite, il y a de bonnes chances que ce soit un peu plus rapide. Ce document est un tutoriel sur l'utilisation des techniques de programmation fonctionnelles pour étendre le langage Perl, pas un document sur la meilleure façon d'obtenir les meilleures performances d'exécution.

Cela dit, la rapidité n'est pas si souvent que cela le critère essentiel (tant que l'on reste dans un domaine de performances acceptable), l'important est généralement qu'un programme fonctionne correctement selon les besoins. Si vous avez besoin d'un fonctionnement particulier inhabituel, n'hésitez pas à employer les techniques ci-dessus, elles peuvent vous épargner beaucoup de travail.

3-4-2 - Fonctions de listes composées

La bibliothèque de fonctions ci-dessus peut être étendue avec des fonctions recevant elles-mêmes des fonctions en paramètres. Supposons par exemple, pour commencer, que nous voulions une fonction any renvoyant vrai si l'un au moins des éléments de la liste satisfait une certaine condition. Un grep dans un contexte scalaire ferait cela aussi bien et plus simplement, mais cela constitue un point de départ intéressant pour la suite.

Cette fonction pourrait être utilisée par exemple comme suit :

utilisation de la fonction any

print "true\n" if any(sub { $_> 10 }, qw /6 4 5 7/); # n'imprime rien
print "true\n" if any(sub { $_> 10 }, qw /12 4 5 7/); # imprime "true"

La mise en œuvre ne pose pas de difficulté particulière :

Fonction any

sub any {
my $code_ref = shift;
reduce { $a or $code_ref->(local $_ = $b) } @_;
}

Nous avons ajouté maintenant un nouveau degré de liberté : certaines fonctions de notre bibliothèque de fonctions de listes vont pouvoir prendre une fonction de rappel en paramètre, ce qui les rend plus génériques. La bibliothèque peut par exemple être enrichie avec les fonctions suivantes :

Nouvelles fonctions de listes génériques

sub any {
my $code_ref = shift;
reduce { $a or $code_ref->(local $_ = $b) } @_;
}
sub all {
my $code_ref = shift;
reduce { $a and $code_ref->(local $_ = $b) } @_;
}
sub none {
my $code_ref = shift;
reduce { $a and not $code_ref->(local $_ = $b) } @_;
}
sub notall {
my $code_ref = shift;
reduce { $a or not $code_ref->(local $_ = $b) } @_;
}

Il est possible, comme nous l'avons fait précédemment, d'utiliser des prototypes pour simplifier quelque peu la syntaxe d'appel de ces fonctions. Par exemple, nous pouvons modifier la fonction any comme suit :

any avec prototype

sub any(&@) {
my $code_ref = shift;
reduce { $a or $code_ref->(local $_ = $b) } @_;
}

Avant de décrire la syntaxe d'appel, notons que nous retrouvons ici le problème décrit au paragraphe ci-dessus. Si nous appelons la fonction any ci-dessus avec cette syntaxe:

Any, syntaxe d'appel erronée

print "true\n" if any { $_> 11 } qw /3 4 5 7/;

Cela ne fonctionnera pas comme prévu et imprimera « true » à tort, car la fonction reduce considérera la première valeur comme vraie. Il faut donc, comme nous l'avons fait précédemment, ajouter une valeur fausse en début de la liste.

Voici une syntaxe d'appel de cette nouvelle fonction any qui fonctionnera correctement :

Appel de la nouvelle fonction any

print "true\n" if any { $_> 11 } 0, qw /3 4 5 7/; # n'imprime rien
print "true\n" if any { $_> 11 } 0, qw /3 12 4 5 7/; # imprime "true"

Mais, comme nous avons cette fois deux appels de fonctions successifs avant d'arriver à l'appel à reduce, nous pouvons aussi faire la même modification au code de la fonction any :

Fonction any modifiée

sub any(&@) {
my $code_ref = shift;
reduce { $a or $code_ref->(local $_ = $b) } 0, @_;
}

Cette seconde solution paraît préférable, car elle décharge l'utilisateur de la fonction de la responsabilité de penser à l'ajout de ce paramètre en tête de la liste.

Appliquons la même modification à nos trois autres nouvelles fonctions :

Nouvelles fonctions génériques, version finale

sub all(&@) {
my $code_ref = shift;
reduce { $a and $code_ref->(local $_ = $b) } 1, @_;
}
sub none(&@) {
my $code_ref = shift;
reduce { $a and not $code_ref->(local $_ = $b) } 1, @_;
}
sub notall(&@) {
my $code_ref = shift;
reduce { $a or not $code_ref->(local $_ = $b) } 0, @_;
}

4 - Un cran de plus dans la simplification : la curryfication

La curryfication est une technique essentielle dans les langages fonctionnels, en particulier dans les langages fonctionnels purs comme Haskell.

Dans un langage fonctionnel réellement pur, non seulement une fonction ne doit pas changer son environnement d'exécution (pas d'effet de bord), mais il faut parfois que la fonction elle-même soit un être mathématique pur qui ne peut prendre qu'un seul argument et ne retourner qu'une seule valeur. Cela présente des avantages certains et des inconvénients indéniables dont nous ne discuterons pas ici. Disons simplement que Perl ne fait pas partie de ce genre de langage et n'est donc nullement concerné par ces limitations, mais il peut néanmoins tirer parti des techniques utilisées par ces langages fonctionnels pour faire face à ces contraintes.

La curryfication tire son nom du mathématicien et logicien américain Haskell B. Curry (1900-1982), l'un des fondateurs des théories mathématiques logiques (lambda-calcul et autres) à l'origine de la plupart des concepts à la base des langages de programmation fonctionnelle. Le langage Haskell a bien sûr été baptisé d'après son prénom. Une partie au moins des idées de Curry provient d'un article très novateur et apparemment unique de Moses Schönfinkel (alias Moisei Isai'evich Sheinfinkel), logicien et mathématicien juif soviétique (1889-1942), qui semble avoir inventé l'idée de curryfication. Certains auteurs ont même proposé de renommer « schönfikelisation » la curryfication. N'étant nullement spécialiste, nous ne prendrons pas parti et nous contenterons d'utiliser le terme le plus courant de curryfication.

4-1 - L'idée de base de la curryfication

La curryfication consiste à remplacer une fonction ayant plusieurs arguments par une fonction n'acceptant qu'un seul argument et renvoyant une autre fonction (généralement une fermeture) chargée de traiter les autres arguments.

L'exemple classique est une fonction d'ajout. Soit une fonction add(x, y) qui prend deux arguments et en renvoie la somme. Une fois curryfiée, on aurait une fonction add(x) qui prend un argument et renvoie une fonction qui prend le deuxième argument. La curryfication permet de réaliser une application partielle : si on appelle la fonction curryfiée avec l'argument 2, on reçoit en retour une fonction unaire qui ajoute 2 à son argument.Voici un exemple en Caml :

let add x y = x + y;; (* définit la fonction add *)
let add_two = add 2;; (* la fonction add_two ajoute 2 à son argument *)
add_two 3;;  (* applique add_two à 3 et retourne 5 *)

Le mécanisme de la fermeture permet de faire la même chose très simplement en Perl :

add_2

sub add {
my $ajout = shift;
return sub {$ajout + shift}
};
my $add_2 =  add(2);
print $add_2->(3); # imprime 5

Ici, la coderef $add_2 est une version curryfiée de la fonction add. On peut bien sûr en créer une autre (ou autant que l'on veut) :

add_3

my $add_3 =  add(3);
print $add_3->(5); # imprime 8

4-2 - Rien de bien nouveau sous le soleil ?

À vrai dire, il n'y a pas grand-chose de bien nouveau dans ce que nous venons de faire.

Plusieurs des fonctions étudiées aux chapitres 3.3 à 3.5 de la partie 2 de ce tutoriel faisaient déjà à peu près le même chose et étaient pour certaines implicitement curryfiées (partiellement ou totalement). Simplement, nous ne l'avons pas dit à l'époque parce que notre objectif était alors autre : expliquer le mécanisme de fonction retournant des fonctions (ou d' « usine à fonctions »). Cette idée était suffisamment nouvelle pour ne pas l'encombrer de considérations théoriques supplémentaires. Implicitement, dès que l'on crée une fermeture qui stocke une partie de ses paramètres dans son environnement d'exécution, on pratique une forme (primaire et peut-être incomplète) de curryfication, même si ce n'est pas le but premier.

Essayons cependant d'utiliser cette notion de façon plus explicite, pour réellement transformer des fonctions à plusieurs arguments en une chaîne de fonctions à un seul argument.

4-3 - Curryfication de la fonction parcours_dir

Vous vous souvenez de la fonction parcours_dir qui nous a permis d'introduire la notion de fonction de rappel au début de la seconde partie de ce tutoriel ? Il s'agissait de parcourir une arborescence de répertoires sur un disque dur et d'appliquer une fonction de rappel passée en paramètre aux objets trouvés dans ce répertoire. Celle-ci s'écrivait à peu près comme suit :

parcours_dir 1

#!/usr/bin/perl
use strict;
use warnings;

my $dir_depart = $ARGV[0];
chomp $dir_depart;

my $imprime_fic = sub { print $_[0], "\n"; };
parcours_dir($imprime_fic, $dir_depart);

sub parcours_dir {
my ($code_ref, $path) = @_;
my @dir_entries = glob("$path/*");
foreach my $entry (@dir_entries) {
$code_ref->($entry) if -f $entry;
parcours_dir($code_ref, $entry) if -d $entry;
}
}

Il n'est pas bien difficile de créer une version curryfiée :

parcours_dir curryfiée

#!/usr/bin/perl
use strict;
use warnings;

sub create_func {
my $code_ref = shift;
my $func;
$func  = sub {
my $path = shift;
my @dir_entries = glob("$path/*");
foreach my $entry (@dir_entries) {
$code_ref->($entry) if -f $entry;
$func->($entry) if -d $entry;
}
}
}
my $print_dir = create_func(sub { print shift, "\n"; });
$print_dir->($ARGV[0]);

Cela marche, mais l'intérêt de l'opération ne saute pas sans doute aux yeux pour l'instant : le code est sans doute un peu plus complexe à comprendre et un peu plus long. Peut-être est-ce marginalement plus rapide parce que la fonction récursive $func prend un paramètre de moins, mais ce n'est même pas sûr et la différence est de toute façon au mieux minime.

Cela nous permet de résoudre en partie le problème de la variable globale que nous utilisions pour mesurer la taille des fichiers présents dans l'arborescence du répertoire :

parcours_dir curryfiée 2

#!/usr/bin/perl
use strict;
use warnings;

sub create_func {
my ($code_ref, $tot_size_ref) = @_;
my $func;
$func  = sub {
my $path = shift;
my @dir_entries = glob("$path/*");
foreach my $entry (@dir_entries) {
$func->($entry) and next if -d $entry;
$code_ref->($tot_size_ref, $entry) if -f $entry;
}
}
}
my $tot_size = 0;
my $size_dir_func_ref = create_func(
sub {my $size_ref = shift; $$size_ref += (-s shift)}, \$tot_size);
$size_dir_func_ref->($ARGV[0]);
print $tot_size, "\n";

Cette version fonctionne, mais est à la vérité un peu maladroite et peu satisfaisante, parce que la fonction create_func n'est plus générique (il faut lui passer un paramètre supplémentaire, la taille), l'appel récursif à $code_ref nécessite également un paramètre supplémentaire et deux des fonctions prennent deux paramètres et ne sont donc pas réellement curryfiées.

En fait, la coderef $func doit être une fermeture sur la coderef de la fonction de rappel, mais n'a pas besoin de se fermer sur la taille, qu'elle n'a pas réellement besoin de connaître. C'est la coderef ($size_dir_func_ref) de la fonction de rappel qui aurait besoin de se fermer sur la taille. Voici donc une nouvelle version répondant à ces besoins et contenant trois fermetures et des fonctions réellement curryfiées :

parcours_dir curryfiée 3

#!/usr/bin/perl
use strict;
use warnings;

sub create_func {
my $code_ref = shift;
my $func;
$func  = sub {
my $path = shift;
my @dir_entries = glob("$path/*");
foreach my $entry (@dir_entries) {
$func->($entry) and next if -d $entry;
$code_ref->($entry) if -f $entry;
}
}
}

sub parcours_dir {
my $tot_size = 0;
my $size_dir_func_ref = create_func( sub { $tot_size += (-s shift)} );
$size_dir_func_ref->($_[0]);
return $tot_size, "\n";
}
print parcours_dir($ARGV[0]);

Cette fois, nous avons atteint tous nos objectifs :

- la fonction create_func est redevenue complètement générique et abstraite, elle peut être réutilisée sans changement pour n'importe quel autre parcours de répertoire, c'est la fonction de rappel qui assure entièrement la logique fonctionnelle à employer ;

- il n'y a plus de variable globale contenant la taille du répertoire et, plus généralement, toutes les variables ne sont accessibles que là où elles ont besoin de l'être ;

- toutes les fonctions ne prennent qu'un seul argument et sont bien complètement curryfiées, il n'y a plus de passage répétitif du même paramètre.

4-4 - Une version curryfiée de reduce

La fonction reduce étudiée précédemment présente encore un petit défaut : la fonction utilisatrice (max, par exemple) reçoit en paramètre une liste et doit repasser cette liste à reduce. N'y a-t-il pas moyen de simplifier cette syntaxe ? Il ne s'agit pas simplement d'ajouter du sucre syntaxique : accessoirement, n'est-il pas possible d'éviter ce double passage de paramètres, qui peut être gourmand en mémoire et en temps CPU ? Est-ce que la curryfication de cette fonction ne pourra pas améliorer les choses ?

Essayons une première tentative :

reduce curryfiée 1

use strict;
use warnings;

sub reduce (&) {
my $code_ref = shift;
my $func = sub {
my $result = shift;
for (@_ ) {
local ($a, $b) = ($result, $_ );
$result = $code_ref->($a, $b );
}
return $result;
};
return $func;
}

my $max = sub { reduce { $a > $b ? $a : $b } };
my $maximum = $max->()->(1..10);
print "Le max est: $maximum \n";

L'écriture de la fonction reduce curryfiée ne présente pas de difficulté particulière. Elle peut être simplifiée comme suit :

reduce curryfiée simplifiée

sub reduce (&) {
my $code_ref = shift;
return sub {
my $result = shift;
for (@_ ) {
local ($a, $b) = ($result, $_ );
$result = $code_ref->($a, $b );
}
return $result;
};
}

Mais le problème est que l'on ne peut pas vraiment dire que l'appel de la coderef $max :

Appel de max

my $maximum = $max->()->(1..10);

soit simplifié, en raison de la double indirection des coderefs. Bref, on est bien loin du sucre syntaxique.

Les syntaxes d'appel alternatives sont à peine plus encourageantes. Par exemple, la syntaxe d'appel suivante :

reduce curryfiée 2

my $max = sub { reduce { $a > $b ? $a : $b } };
my $maximum = &$max->(1..10);

fonctionne également, mais n'est pas beaucoup plus lisible.

La syntaxe suivante :

reduce curryfiée 3

sub max { reduce { $a > $b ? $a : $b } };
my $maximum = max->(1..10);

est déjà un peu plus lisible mais reste assez lourde.

Nous pouvons utiliser un peu de magie blanche et écrire directement dans la table des symboles(5) :

Reduce curryfiée

use strict;
use warnings;

sub reduce (&@) {
my $code_ref = shift;
return sub {
my $result = shift;
for (@_ ) {
local ($a, $b) = ($result, $_ );
$result = $code_ref->($a, $b );
}
return $result;
};
}
*max = reduce { $a > $b ? $a : $b };
my $maximum = max(1..10);
print "Le max est: $maximum \n";  # imprime "Le max est:  10"

La syntaxe d'appel de la fonction max devient très simple, le résultat recherché est atteint, mais expliquer l'utilisation des typeglobs (il s'agit d'utiliser le sigil « * » pour écrire directement des entrées dans la table des symboles du programme) ferait appel à des notions avancées de Perl qui sortiraient du cadre de ce tutoriel. Le but pour nous est de chercher à étendre le langage, ce qui justifie ici d'utiliser la magie des typeglobs, il n'est vraiment pas conseillé de les utiliser pour de la programmation courante.

En tout état de cause, il devient possible d'écrire une bibliothèque de fonctions utilisant cette version de reduce et plus simple que celle que nous avions décrite plus haut :

Nouvelle bibliothèque avec reduce

*max reduce { $a > $b ? $a : $b };
*min reduce { $a > $b ? $b : $a };
*product reduce { $a * $b };
# etc.

4-5 - La curryfication automatique

Si la syntaxe d'appel des fonctions curryfiées nous a posé quelques problèmes de simplification, la curryfication d'une fonction existante est assez simple. La fonction reduce curryfiée est à peine plus complexe que la version de base de reduce. Il suffit d'ajouter une fonction intermédiaire qui se charge de passer les paramètres de façon satisfaisante. Ne serait-il pas possible de le faire de façon automatique ?

Considérons pour commencer le cas simple, étudié au début de ce chapitre, de la fonction add:

Fontion add de base

sub add {
my ($c, $d) = @_;
return $c + $d;
}

Nous pouvons écrire une fonction curry qui transforme automatiquement cette fonction en fonction curryfiée :

Curryfication automatique

use strict;
use warnings;

sub curry (\&@) {
my $code = shift;
my @args = @_;
sub {
unshift @_, @args;
goto &$code;
};
}

my $curried_add = curry(&add, 6);
print $curried_add->(5);  # imprime 11

sub add {
my ($c, $d) = @_;
return $c + $d;
}

S'agissant de curryfier la fonction add, le prototype de la fonction curry pourrait être simplement (\&$), au lieu de (\&@). Mais nous désirons que la fonction curry soit généraliste et puisse curryfier des fonctions ayant plus de paramètres.

Ici encore, nous utilisons un peu de magie (blanche). La ligne suivante :

goto &$code;

est un peu particulière. Nous ne succombons pas ici au plaisir rebelle de transgresser les principes établis par Edsger Dijkstra dans son célèbre article « Go To Statement Considered Harmful » (6) (« L'instruction Go To considérée comme nuisible »), publiée dans les ACM en 1968. Perl possède cette forme de goto critiquée à juste titre par Dijkstra et beaucoup d'autres et permettant de brancher inconditionnellement le programme sur une autre instruction, mais non seulement je ne l'ai jamais utilisée personnellement en Perl, mais je ne l'ai presque jamais vue utilisée ailleurs (du moins en Perl). La forme de goto utilisée ici est très particulière et bien différente. Comme le dit la documentation officielle de Perl : « La forme goto &name est hautement magique et est suffisamment éloignée des formes ordinaires de goto pour exonérer ses utilisateurs de l'opprobre qui leur est habituellement réservé. Cet appel substitue la sous-routine nommée par un appel à la fonction fournie ».

Pour dire toute la vérité, nous écrivons à nouveau dans la table des symboles en sorte que, quand le programme appelle la fonction add, c'est en réalité la version curryfiée de cette fonction qui est appelée.

Il est possible d'utiliser la même fonction curry pour curryfier une fonction subtract:

subtract curryfiée

sub subtract {
my ($c, $d) = @_;
return $c - $d;
}

my $curried_subtr = curry(&subtract, 6);
print $curried_subtr->(5); # imprime 1

Cela fonctionne, mais peut-être pas vraiment comme on pourrait le souhaiter. Le deuxième paramètre passé à la fonction curry est le nombre (le « diminuende ») dont on retranche la valeur (le « diminuateur ») passée à la fonction curried_subtr, alors que l'on pourrait souhaiter l'inverse : que la fonction curryfiée subtract_1, par exemple, retranche 1 de la valeur qui lui est passée en paramètre. Ce comportement est dû à la non-commutativité de la soustraction. On peut facilement contourner ce problème en redéfinissant l'ordre des paramètres passés à la fonction subtract :

subtract_1 curryfiée

sub subtract {
my ($c, $d) = @_;
return $d - $c;
}

my $subtract_1 = curry(&subtract, 1);
print $subtract_1->(4); # imprime 3

4-6 - Prototypes et curryfication automatique : l'exemple de la curryfication de la fonction comb_sort

La fonction curry permet de curryfier automatiquement la fonction comb_sort étudiée au § 2.22 ci-dessus :

comb_sort curryfiée

my @v;
my $max = 500;
$v[$_] = int rand(20000) foreach (0..$max);

my $curried_comb_sort = curry (&comb_sort, sub {$a<=>$b});
$curried_comb_sort->(\@v);
print "@v";

Ce qui imprime bien une liste correctement triée :

$ perl curried_sort.pl
3 25 111 227 241 250 274 280 297 326 334 463 557 585 597 598 605 701 732 734 739 739 797 830 859 864 1063 1081 1108 1118 1145 1167 1170 1222 1243 1302 1321 1337 1346 1379 1424 1470 1492 1511 1517 1542 1543 1628 1649 1718 1719 1721 1721 1723 1727 1842 1892 1950 2000 2050 2079 2094 2124 2165 2194 2298 2311 ...

Il a cependant fallu faire une petite modification syntaxique pour que cela fonctionne correctement. La fonction comb_sort utilisait les prototypes pour permettre l'appel suivant :

appel de comb_sort

comb_sort {$a<=>$b} @v;

Le paramètre @v était transformé en référence au tableau grâce au prototype de la fonction comb_sort. Dans la version curryfiée, comme la fonction intermédiaire curry n'impose pas la transformation en référence au tableau, nous avons dû passer une référence au tableau :

Appel de comb_sort curryfiée

$curried_comb_sort->(\@v);

mais, d'un autre côté, nous avons gagné le fait de ne plus devoir passer le bloc de code assurant le tri numérique.

Ceci n'est qu'un exemple, mais, plus généralement, la curryfication automatique s'accommode parfois assez mal des fonctions prototypées parce que l'interposition d'une fonction anonyme entre la fonction de base et la version curryfiée bat en brèche le but des prototypes. D'un autre côté, on pourrait écrire des fonctions curry distinctes adaptées aux différents prototypes, mais on perdrait alors la généralité d'une fonction curry générique. Bref, il y a une forme d'opposition entre le caractère général recherché pour une fonction générique telle que curry, et le caractère très particulier et coercitif d'un prototype ; on peut trouver assez facilement des solutions, comme le simple passage d'une référence au tableau @v ci-dessus, mais il faut savoir que la cohabitation des deux notions entraîne parfois des contradictions ou difficultés et nécessite parfois un peu de réflexion. On n'est plus, dans ce cas particulier, dans du « tout automatique ».(7)

Cette (petite) limitation pourrait constituer une raison supplémentaire de limiter l'utilisation des prototypes aux fonctions pour lesquelles ils amènent une réelle simplification syntaxique. Cela dit, il faut relativiser, tout le monde n'a pas forcément besoin de la curryfication automatique, une curryfication manuelle ou semi-automatique « sur mesure » peut suffire dans bien des cas.

5 - Fonctions à deux listes

5-1 - Utiliser deux listes : la fonction combine

Il est assez fréquent de devoir utiliser membre à membre deux listes ou deux tableaux différents, par exemple pour les comparer ou les combiner. Il est assez courant d'appeler combine une fonction générique abstraite réalisant ce genre d'opération.

Contrairement à ce que nous avons fait précédemment, nous n'allons plus, cette fois, proposer une première approche naïve, constater qu'elle aboutit à une duplication de code ou à des erreurs syntaxiques et arriver progressivement à la solution générique permettant d'éviter cette duplication. Le lecteur est maintenant habitué à la méthode et aux techniques qu'elle emploie, nous pouvons nous lancer directement dans le grand bain et essayer de créer directement une fonction générique abstraite combine (ce qui n'empêche cependant pas d'améliorer le résultat progressivement).

5-1-1 - La fonction combine

De quoi avons-nous besoin ? D'une fonction recevant en paramètres une fonction et deux listes. Ou, plus exactement, des références à une fonction (une coderef, donc) et à deux listes. La fonction doit ensuite prendre un à un chaque élément de chaque liste, appliquer la coderef à ces deux éléments et stocker le résultat dans une nouvelle liste qui sera renvoyée à la fonction appelante lorsque l'une au moins des deux listes sera épuisée. Ce qui peut nous donner ceci :

combine

sub combine (&\@\@) {
my ($code_ref, $l1_ref, $l2_ref) = @_;
my @result;
while (1) {
local ($a, $b);
($a, $b) = (shift @$l1_ref, shift @$l2_ref);
return @result unless defined $a and defined $b;
push @result, $code_ref->($a, $b);
}
}

Nous pouvons maintenant écrire des fonctions calculant par exemple les sommes membre à membre et les moyennes membre à membre de deux listes :

Somme et moyenne membre à membre

sub add2 (\@\@) {
my ($l1, $l2) = @_;
return combine {$a + $b} @$l1, @$l2;
}

sub avg2(\@\@) {
my ($l1, $l2) = @_;
return combine {($a + $b) /2} @$l1, @$l2;
}

À l'utilisation, cela semble fonctionner plutôt bien :

Ajout membre à membre

use strict;
use warnings;
use Combine qw/combine add2/;

my @list1 = qw /1 5 7 98 32/;
my @list2 = grep $_%2, 1..10; # nombres impairs entre 1 et 10

print join " ", add2(@list1, @list2), "\n";

Ce qui donne :

Exécution de la fonction add2

$ perl add2.pl
2 8 12 105 41

De même, pour calculer la moyenne membre à membre des listes avec la fonction avg2 :

Exécution de la fonction avg2

$ perl avg2.pl
1 4 6 52.5 20.5

Cette fonction souffre cependant d'un grave défaut de conception : les listes passées en paramètres sont vidées de leur contenu. Si nous voulons éviter cet effet de bord somme toute assez fâcheux dans certains cas, nous devons soit modifier nos fonctions add2 et avg2 pour qu'elles fassent une copie temporaire des tableaux reçus en paramètres, soit plus probablement modifier la fonction combine pour qu'elle lise les tableaux sans les modifier.

Modifions donc la fonction combine pour qu'elle ne modifie pas les tableaux reçus en argument, mais se contente de les lire :

combine (2)

sub combine (&\@\@) {
my ($code_ref, $l1_ref, $l2_ref) = @_;
my @result;
my $i = 0;
while (1) {
local ($a, $b) = ($l1_ref->[$i], $l2_ref->[$i++]);
return @result unless defined $a and defined $b;
push @result, $code_ref->($a, $b);
}
}

Cela résout facilement le problème.

5-2 - Une fonction intermédiaire de création de fonctions

Nous voudrions cependant aller plus loin dans la simplification et trouver une syntaxe encore plus simple. La solution peut être de créer une fonction intermédiaire de création de fonctions. Celle-ci peut avoir la forme suivante :

Fonction génératrice de fonctions

sub generate_function2 {
my $code_ref = shift;
return sub {
my ($l1_ref, $l2_ref) = @_;
return combine {&$code_ref} @$l1_ref, @$l2_ref;
}
}

On peut également l'écrire un peu plus brièvement comme suit :

sub generate_function2(&) {
my $code_ref = shift;
return sub  {
return combine {&$code_ref} @{$_[0]}, @{$_[1]};
}
}

Ou même :

sub generate_function2 {
my $code_ref = shift;
sub  { combine {&$code_ref} @{$_[0]}, @{$_[1]};
}
}

Cela marche parfaitement :

my $add2 = generate_function2(sub {$a + $b});

my @list1 = qw /1 5 7 98 32/;
my @list2 = grep $_%2, 1..10;

print join " ", $add2->(\@list1, \@list2), "\n";

sub generate_function2 {
my $code_ref = shift;
sub  { combine {&$code_ref} @{$_[0]}, @{$_[1]};
}
}

Ce qui imprime :

$ perl  generate.pl
2 8 12 105 41

5-2-1 - Créer une bibliothèque de fonctions

Il est maintenant possible d'utiliser ce modèle pour générer très simplement toute une bibliothèque de fonctions de listes du même type :

my $add2       = generate_function2( sub { $a + $b } );
my $avg2       = generate_function2( sub { ( $a + $b ) / 2 } );
my $substr2    = generate_function2( sub { $a - $b } );
my $diff2      = generate_function2( sub { abs( $a - $b ) } );
my $mult2      = generate_function2( sub { $a * $b } );
my $equal_nr   = generate_function2( sub { $a if $a == $b } );
my $equal_str  = generate_function2( sub { $a if $a eq $b } );
my $each_array = generate_function2( sub { $a, $b } );

# ...

Avec ce bout de programme utilisateur :

my @list1 = qw /1 32 5 7 98/;
my @list2 = grep $_%2, 1..10;

print join " ", $add2->(\@list1, \@list2), "\n";
print join " ", $avg2->(\@list1, \@list2), "\n";
print join " ", $substr2->(\@list1, \@list2), "\n";
print join " ", $diff2->(\@list1, \@list2), "\n";
print join " ", $mult2->(\@list1, \@list2), "\n";
print join " ", $equal_nr->(\@list1, \@list2), "\n";
print join " ", $equal_str->(\@list1, \@list2), "\n";
print join " ", $each_array->(\@list1, \@list2), "\n";

On obtient le résultat suivant :

$ perl  generate.pl
2 35 10 14 107
1 17.5 5 7 53.5
0 29 0 0 89
0 29 0 0 89
1 96 25 49 882
1  5 7
1  5 7
1 1 32 3 5 5 7 7 98 9

Ce qui est bien ce qui était attendu.

5-2-2 - Simplification syntaxique

Il subsiste un petit inconvénient, cependant : nous obligeons notre utilisateur à utiliser des coderefs, dont la syntaxe peut être jugée un peu plus rébarbative (pour le débutant) que celle de simples fonctions :

my @list1 = qw /1 5 7 98 32/;
my @list2 = grep $_ % 2, 1 .. 10;
my @sum   = $add2->( @list1, @list2 );

L'inconvénient est assez mineur, mais si l'on veut vraiment l'éliminer, un peu de sucre syntaxique supplémentaire permet d'y remédier :

sub add2 (\@\@) {
my ($list1, $list2) = @_;
return $add2->(\@list1, \@list2);
}

Nous pouvons maintenant faire la somme membre à membre comme suit :

my @list1 = qw /1 32 5 7 98/;
my @list2 = grep $_%2, 1..10;

print join " ", add2(@list1, @list2), "\n";

Ce qui donne le résultat attendu :

$ perl  generate.pl
2 35 10 14 107

Nous avons créé un nouveau niveau d'indirection permettant de simplifier au maximum la syntaxe d'appel de la fonction. Encore une fois, on complique d'un côté (côté codeur du module) et simplifie de l'autre (côté utilisateur du module). À chacun de déterminer jusqu'où aller dans la simplification et le sucre syntaxique.

L'exemple fourni ici montre comment « améliorer » (c'est-à-dire, en réalité, compliquer) petit à petit la façon de faire les choses pour réussir de l'autre côté à simplifier au maximum l'interface de la fonction fournie à l'utilisateur. D'autres façons de faire la même chose sont envisageables, mais la technique proposée rend le service attendu.

On pourra aussi considérer que nous avons un peu « tourné en rond » : il y avait sans doute un moyen moins compliqué de définir la fonction add2. Mais si l'on considère l'utilisation d'un module prédéfinissant les fonctions dont nous avons besoin, le gain est réel, car nous avons réellement évité beaucoup de duplication de code.

6 - Implanter en Perl 5 les fonctions gather et take de Perl 6

Perl 6, une nouvelle version du langage encore en cours de développement qui sera peut-être un jour la nouvelle version de Perl, s'inspire en partie des langages fonctionnels assez récents (comme Haskell) pour définir deux fonctions intimement liées, gather et take, permettant d'effectuer des opérations particulièrement riches sur des listes. Pour simplifier, la fonction gather parcourt la liste et la fonction take décrit ce qui doit être fait sur les éléments retenus de la liste. La fonction take n'a un sens que si elle est appelée dans le cadre d'un gather. Comme nous le verrons, ces deux fonctions associées définissent en quelque sorte un sur-ensemble conceptuel de map et de grep.

La fonction gather offre un moyen de construire une liste de façon procédurale, sans avoir besoin d'utiliser explicitement de variables temporaires. Dans le bloc ou la fermeture contrôlée par un gather, tout appel à take « pousse » (ajoute) la liste d'arguments sur un tableau défini implicitement. À la fin du processus, gather retourne la liste ainsi créée.

Ce n'est pas très clair ? Pas très étonnant, c'est vraiment assez difficile à expliquer. Un exemple sera sans doute plus parlant.

6-1 - Mise en œuvre

Voici une mise en œuvre possible de gather et take:

gather et take

use strict;
use warnings;

{
my @result;

sub gather(&) {
my $code_ref = shift;
@result = ();
$code_ref->();
return @result;
}

sub take(@) {
my @caller = caller 2;
die "Appel à take pas à l'intérieur d'un bloc gather" unless $caller[3] =~ /gather/;
push @result, @_;
return scalar @result;
}
}

Qu'avons-nous ? Nous avons d'abord un tableau lexical @result global aux deux fonctions gather et take (mais local au bloc de code englobant gather et take). La fonction gather reçoit en paramètre une coderef, initialise le tableau @result à vide, appelle la coderef reçue en paramètre qui se charge de remplir le tableau (en appelant pour ce faire la fonction take) et renvoie le tableau.

La fonction take reçoit en paramètre un tableau, vérifie qu'elle a bien été appelée dans le contexte d'un gather (8) (on pourrait s'en passer dans une version minimaliste, mais mieux vaut vérifier que l'utilisateur ne fait pas n'importe quoi), ajoute le tableau reçu en paramètre à @result, et renvoie accessoirement le nombre d'éléments du tableau @result. Pour notre explication du fonctionnement de gather et take, la fonction take pourrait se réduire à la définition minimaliste suivante :

take, version minimaliste

sub take(@) {
push @result, @_;
}

6-2 - Exemples d'utilisation simple

Soit, direz-vous, mais la fonction take n'est même pas appelée par gather. Quel est le lien entre les deux ? En fait, si, la fonction take est (éventuellement) appelée dans la coderef reçue en paramètre et exécutée par gather.

Par exemple, nous pouvons appeler ces deux fonctions avec la simple ligne de code suivante pour simuler la fonction map et renvoyer le double de chacun des nombres d'une liste en entrée :

Simulation de map

print join " ", gather {take $_ * 2 for (1..10)};

Ce qui imprime bien :

$ perl gather_simple.pl
2 4 6 8 10 12 14 16 18 20

Nous pouvons de même simuler un grep et retourner par exemple les nombres impairs d'une liste en entrée:

Simulation de grep

print join " ", gather {$_ % 2 and take $_ for (1..10)};
# imprime 1 3 5 7 9

On le voit, notre paire de fonctions gather et take simule facilement aussi bien map que grep.

Nous pouvons même combiner les fonctionnalités de map et de grep, filtrer et transformer la liste en entrée. Si par exemple nous désirons obtenir le cube des nombres impairs de la liste en entrée :

simulation de map et grep

print join " ", gather {$_ % 2  and take $_ ** 3 for  (1..10)};
# imprime 1 27 125 343 729

Nous pouvons maintenant utiliser gather et take pour construire des fonctions plus complexes.

6-3 - Gather et take pour construire une fonction my_map

À titre d'exemple, considérons cette nouvelle implémentation de my_map utilisant gather et take :

my_map utilisant gather et take

sub my_map (&@) {
my $coderef = shift;
my @list = @_;
return gather {
take $coderef->($_) for @list;
};
}

print join " ", my_map {$_ * 2} 1..10;
print "\n";

Ce qui imprime bien le résultat attendu :

$ perl gather_map.pl
2 4 6 8 10 12 14 16 18 20

Comme dans la version précédente, la fonction my_map reçoit en paramètres une coderef et un tableau. Mais elle appelle cette fois la fonction gather et lui passe en argument une coderef appelant la fonction take sur la valeur de retour de la coderef reçue en paramètre appliquée à chaque élément du tableau. Reconnaissons-le franchement : nous n'avons pas vraiment simplifié les choses par rapport à notre précédente version de my_map, mais nous avons créé un nouvel outil plus flexible et plus riche fonctionnellement.

6-4 - … Ou my_grep

Nous pouvons de même proposer une nouvelle version de my_grep utilisant gather et take :

my_grep utilisant gather et take

sub my_grep (&@) {
my $coderef = shift;
my @list = @_;
return gather {
$coderef->($_) and take $_ for @list;
};
}

print join " ", my_grep {$_ % 2} 1..20;

Ce qui imprime le résultat attendu :

$ perl gather_grep.pl
1 3 5 7 9 11 13 15 17 19

6-5 - Combiner les fonctions map et grep ?

On souhaiterait parfois combiner les comportements de map et de grep, c'est-à-dire à la fois filtrer et transformer les données en une seule opération, comme nous l'avons fait avec le dernier exemple des utilisations simples de gather et take (§ 6.2). Voyons, à titre d'exercice de style, si nos fonctions génériques gather et take nous permettent de le faire en une seule opération. Essayons par exemple d'écrire un petit script qui affiche les carrés des nombres impairs d'une liste. Nous pouvons créer une fonction grep_and_map et faire ceci :

grep_and_map

sub grep_and_map {
my $coderef_grep = shift;
my $coderef_map = shift;
my @list = @_;
return gather {
$coderef_grep->($_) and take $coderef_map->($_) for @list;
};
}

print join " ", grep_and_map ( sub {$_ % 2}, sub {$_ ** 2}, 0..20);
print "\n";
# affiche: 1 9 25 49 81 121 169 225 289 361

Cela fonctionne et nous pourrions de même écrire facilement une fonction map_and_grep qui commence par appliquer une transformation aux données en entrée puis filtre le résultat. Mais ceci n'est pas très utile, car nous sommes conduits à créer des fonctions trop spécialisées qui nous font perdre la généralité et l'expressivité que fournit l'abstraction des fonctions map et grep. Il est surtout tellement facile de remplacer notre fonction grep_and_map ci-dessus par un simple enchaînement des deux opérateurs dans un pipe-line comme nous l'avons fait dans la première partie de ce tutoriel :

grep et map simples

print join " ", map {$_ ** 2} grep {$_ % 2} 0..20;
print "\n";
# affiche: 1 9 25 49 81 121 169 225 289 361

ou même par un simple map sans le grep :

map simple

print join " ", map {$_ % 2 ? $_ ** 2 : ()} 0..20;
print "\n";
# affiche: 1 9 25 49 81 121 169 225 289 361

que nos fonctions grep_and_map et map_and_grep ne seront donc guère utiles. Nous n'irons pas plus loin dans cette voie. Comme nous l'avons dit, il s'agissait uniquement d'un exercice de style destiné à montrer comment les fonctions gather et take permettent de créer un nouveau comportement sur une liste et l'on voit que ça marche, le seul problème est juste que créer ce genre de fonctions n'amène pas grand-chose, nous étions dans une fausse voie.

6-6 - Perspectives avec gather et take

Si nous pouvons créer facilement les fonctions map et grep grâce à gather/take, nous devrions pouvoir créer d'autres fonctions de listes utiles, telles que certaines de celles que nous avons vues précédemment. La seule limite est notre imagination : tant que nous n'avons pas pris un peu l'habitude de les utiliser, tant que nous ne nous les sommes pas vraiment appropriées, nous ne sommes pas trop sûrs de ce que l'on pourrait en faire. Si, comme nous l'espérons, Perl 6 voit le jour prochainement, nous ne doutons pas que, d'ici quelques années, les développeurs Perl 6 auront certainement trouvé des tas d'usages utiles à ces fonctions, mais nous sommes aujourd'hui un peu dans la situation d'une poule ayant trouvé une paire de ciseaux et se demandant à quoi cela peut servir. Peu importe de ne pas avoir un usage immédiat, après tout, on peut aussi très bien mettre cet instrument dans sa boîte à outils et se dire qu'il ne tardera sans doute pas à servir si l'on sait rester vigilant et y penser au bon moment.

Le point important est que la fonction map prend une liste en entrée et applique des transformations à cette liste pour générer une autre liste. La fonction grep prend une liste en entrée et filtre les éléments de cette liste. Avec gather et take, nous pouvons maintenant faire des choses plus variées ou plus complexes sur notre liste en entrée. Les fonctions map et grep ne sont que des cas particuliers limités de gather et take.

7 - Conclusion

Nous sommes arrivés à l'issue de notre voyage dans la programmation fonctionnelle en Perl. Il y aurait beaucoup d'autres choses à ajouter, mais il faut aussi savoir s'arrêter. J'ai travaillé notamment sur deux chapitres supplémentaires de cette troisième et dernière partie, mais j'ai décidé de faire le tri et de renoncer à les inclure, du moins pour l'instant.

La première partie de ce tutoriel montrait comment l'utilisation des opérateurs de listes internes de Perl (map, grep, sort, split, join, for, etc.) permettait d'agir efficacement sur des listes ou tableaux de données et de construire des pipe-lines dans lesquels les données en entrées subissaient une série de transformations successives pour arriver au résultat souhaité. Cela nous a aussi permis de commencer à entrevoir l'utilisation des fonctions d'ordre supérieur (des fonctions qui prennent d'autres fonctions en paramètres ou qui renvoient des fonctions).

La seconde partie a plongé résolument dans le monde des fonctions d'ordre supérieur et a montré comment l'utilisation des références à des fonctions ou coderefs permettait de créer toute une variété de nouveaux concepts issus dans une large mesure de la programmation fonctionnelle : fonctions de rappel, tables de distribution, itérateurs, fermetures, usines à fonctions, etc.

La présente troisième partie décrit comment les concepts étudiés dans la seconde partie permet d'étendre le langage Perl et de créer par exemple de nouveaux opérateurs de listes plus puissants ou plus versatiles et des fonctions génériques abstraites comme reduce ou combine. Comme promis dans la première partie, j'ai fourni des implémentations en Perl pur des fonctions map, grep ou sort, y compris des versions modifiées (par exemple des versions paresseuses, inexistantes en Perl 5, de map et grep).

J'espère que ce voyage dans ces façons différentes de programmer en Perl aura intéressé et stimulé le lecteur et qu'il en tirera profit.

8 - Remerciements

Je remercie Mark-Jason Dominus (MJD), dont l'excellent livre Higher Order Perl (HOP) est incontestablement ma source originelle d'inspiration pour explorer des voies qui forment une bonne partie de ce document (en particulier la partie 2 et la présente partie 3). Ce livre de MJD a réellement changé ma façon de concevoir la programmation, c'est à mon humble avis le meilleur livre d'informatique que j'aie lu ces 15 dernières années. Je le recommande vraiment à tous les lecteurs parlant suffisamment l'anglais (pour les autres, j'espère avoir fourni un bon panorama de quelques-uns de ses concepts essentiels). Ce livre est disponible en téléchargement gratuit au format PDF sur le site de l'auteur (n'hésitez pas, allez voir), mais le sujet est suffisamment ardu pour que je recommande l'acquisition de la version papier. C'est en tous cas ce que j'ai fini par faire, je ne le regrette vraiment pas.

Je remercie vivement Philou67430 et djibril pour leur relecture technique attentive de ce texte et ClaudeLELOUP pour la relecture orthographique qu'il a effectuée comme souvent de son formidable œil de lynx. Je remercie aussi gorgonite pour ses conseils judicieux sur certains points particuliers.

(1)La version 5.20 de Perl, sortie au printemps 2014, introduit la notion de signatures qui ressemble sans doute un peu plus à l'idée de prototype que peut se faire un programmeur C ou Java. Nous n'en dirons pas plus ici, ce n'est pas le sujet.

(2)À vrai dire (et contrairement à ce que dit la documentation officielle sur les prototypes), les prototypes ne sont pas tout à fait indispensables pour se permettre d'éviter d'utiliser les parenthèses. Il suffit de définir la fonction avant de l'utiliser ou même simplement de prédéclarer la fonction pour pouvoir se passer des parenthèses, comme nous le montrons dans l'exemple de code push_square 4 un peu plus loin.

(3)Ne me soupçonnez pas d'avoir honteusement copié le code de la page de Wikipédia citée, je suis l'auteur d'origine de ladite page et du code qui s'y trouve.

(4)On pourrait vouloir modifier la fonction max (ou la fonction reduce) pour qu'elle émette un warning si on lui passe une liste vide, mais cela ne sert en définitive pas à grand-chose dans la mesure où cela ne dispense pas l'utilisateur de la fonction de vérifier si la valeur de retour est définie.

(5)La table des symboles est un hash spécial dans lequel Perl stocke les identifiants globaux (variables de paquetage, filehandlers non lexicaux, formats, noms de fonctions, etc.) d'un programme ou d'un module. Il existe une table de ce type pour chaque paquetage (donc, en simplifiant, pour chaque module chargé) et une pour le programme principal. Vous pouvez éventuellement visualiser le contenu de la table des symboles du programme principal en utilisant la fonction keys sur le hash %::ou %main::. Les typeglobs (variables utilisées avec le sigil *) permettent de lire ou d'écrire directement dans la table des symboles. Utiliser les typeglobs ou écrire d'une autre façon dans la table des symboles est généralement fortement déconseillé pour des programmes ordinaires, mais comme il s'agit ici d'étendre les fonctionnalités du langage, on peut exceptionnellement se permettre un peu de « magie ». Cela permet par exemple de remplacer dynamiquement une fonction par une autre (ou son code par autre chose).

(6) À la vérité, Dijkstra avait choisi un titre un peu plus neutre, c'est Niklaus Wirth, éditeur des ACM, fervent défenseur de la programmation structurée et inventeur notamment des langages Pascal et Modula, qui a choisi ce titre plutôt polémique pour l'époque.

(7)À partir de la version de Perl 5.8.1, il existe la fonction set_prototype du module Scalar::Util qui permet de définir dynamiquement le prototype d'une fonction. Sans entrer dans les détails, elle permet de résoudre ces problèmes, mais on perd un peu en élégance syntaxique.

(8)C'est le rôle de l'appel à la fonction caller qui permet ici de vérifier que la fonction take est bien appelée dans le contexte d'un gather.@result@resultgather