Quelques mots de programmation paresseuse

May 11, 2008 § Leave a comment

Ces jours-ci, je travaille beaucoup avec et sur OCaml, que ce soit pour le projet ExtraPol (dont je finirai bien par vous glisser quelques mots) ou pour Batteries Included (la rénovation en cours de la bibliothèque standard de OCaml). En particulier, je viens de finaliser un module de gestion des listes paresseuses. Paresseuses ? Oui, paresseuses.

Attardons-nous un moment sur le concept de paresse en programmation.

En Java (ou C++ ou C# ou …)

Presque tous les langages de programmation permettent, de manière restreinte, de définir des expressions paresseuses, c’est-à-dire des expressions dont le résultat n’est calculé que s’il peut influencer l’exécution du programme. Ainsi, en Java, nous pourrons définir la méthode isEquals suivante :

bool isEquals(Object x)
{
  return x && x.equals(myObject);
}

Ici, au cours de l’exécution de cette fonction, x.equals(myObject) ne sera ffectivement évalué que si x n’est pas null. Java définit ainsi trois opérateurs paresseux &&, || et ?: : dans chacun des trois cas, à l’exécution du programme, la première opérande est évaluée avant de décider que faire de la deuxième (et de la troisième, dans le cas de ?:). Ces constructions sont très utiles, mais sont loin de couvrir toutes les circonstances dans lesquelles la paresse peut s’avérer utile.

Ainsi, imaginons un instant que nous souhaitons écrire une bibliothèque de journalisation, dont le rôle est d’enregistrer des messages dans un fichier au fur et à mesure de l’exécution du programme. Ajoutons une contrainte : les messages ne doivent être effectivement enregistrés que lorsque le journal est activé, par exemple parce que l’utilisateur est en mode de débogage :

void log(String s)
{
   if(LOG) stream.println(s);
}

La méthode log sera typiquement invoquée des centaines de fois durant l’exécution du code, sous la forme suivante :

void myFunction(int i, int j, int k)
{
   myLog.log("Entering myFunction("+i+", "+j+", "+j+")");
   //...
   myLog.log("Leaving myFunction()");
}

Des centaines de fois, nous aurons donc besoin de calculer le résultat de "Entering myFunction("+i+", "+j+", "+j+")", soit trois conversions d’entiers en chaînes de caractères, 6 concaténations de chaînes de caractères et un gaspillage de mémoire vive que nous pourrions éviter lorsque LOG est false. Comment faire pour éviter ce gaspillage ? La première possibilité consiste à exposer la valeur de LOG à tout le programme et à laisser le programmeur écrire plutôt

void myFunction(int i, int j, int k)
{
   if(LOG) myLog.log("Entering myFunction("+i+", "+j+", "+j+")");
   //...
   if(LOG) myLog.log("Leaving myFunction()");
}

Malheureusement, cette transformation nous oblige à contaminer tout le programme avec ce champ LOG, au détriment de la lisibilité et de l’extensibilité. En C ou C++, on pourrait cacher ce LOG derrière une macro, cette fois au détriment du débogage, de la modularité et de la robustesse. En Java, si nous n’avons pas une telle possibilité, nous pouvons utiliser des classes anonymes pour arriver aux mêmes fins :

Commençons par modifier notre bibliothèque de journalisation :

public interface LazyString
{
   public String toString();
}

void log(Object s)
{
   if(LOG) stream.println(s.toString());
}

L’interface LazyString n’est guère contraignante : elle se contente de promettre que les objets qui l’implantent dispoent bien d’une méthode publique String toString(), qui servira à extraire de l’objet une chaîne de caractères. La différence avec ce qui précède est que nous pouvons nous débrouiller pour que la construction de la chaîne de caractères n’ait lieu qu’au moment où la méthode println est invoquée. En particulier, cette construction n’aura jamais lieu si LOG est false. Pour utiliser cette nouvelle version du journal, nous pourrons réécrire myFunction de la manière suivante :

void myFunction(int i, int j, int k)
{
   myLog.log(new LazyString() { public String toString() { return "Entering myFunction("+i+", "+j+", "+j+")" });
   //...
   myLog.log("Leaving myFunction()");
}

Est-ce la fin de l’histoire ? Pas tout à fait. Pour le moment, en Java, nous ne pouvons pas améliorer la syntaxe lors de l’appel de log — en tant que langage, Java est connu pour sa lourdeur syntaxique. En l’absence d’un préprocesseur digne de ce nom, nous ne pourrons rien faire de ce côté-là. Par contre, nous pouvons nous attaquer à un autre problème, qui se posera dès que nous serons confrontés à une méthode log à peine peu plus complexe :

void log(Object s)
{
   if(LOG_TO_FILE) file_stream.println(s.toString());
   if(LOG_TO_WINDOW) text_pane.out.println(s.toString());
   if(LOG_TO_STATUSBAR) statusbar.setText(s.toString());
}

Ici, s.toString() sera invoqué trois fois et calculera trois fois le même résultat. Pour un exemple aussi simple que le nôtre, ce n’est pas encore bien grave, mais on peut imaginer des contextes dans lesquels le calcul serait suffisamment long pour que ce délai soit inacceptable.

Qu’à cela ne tienne, il suffit de réécrire log de manière à retenir la valeur de s.toString(). Voire mieux, nous pouvons encapsuler tout ceci dans une classe plus générique :

public interface Result<T>
{
   public T getValue();
}
public abstract class Lazy<T>
{
   private boolean computed = false;
   private T value = null;
   /**
    * Proceeds to the actual computation.
    * This method will only be called once.
    */
   protected abstract T value();
   public final synchronized T getValue()
   {
      if(computed == false)
      {
        value       = value();
        computed = true;
      }
      return value;
   }
}

public abstract class LazyString extends Lazy<String>
{
   public String toString()
   {
      return this.getValue();
   }
}

En modifiant myFunction pour utiliser cette nouvelle version de LazyString, nous obtenons :

void myFunction(int i, int j, int k)
{
   myLog.log(new LazyString() { protected String value() { return "Entering myFunction("+i+", "+j+", "+j+")" });
   //...
   myLog.log("Leaving myFunction()");
}

Qu’avons-nous gagné ? Nous avons maintenant sous la main une interface Result<T> qui permet de représenter une opération. Si l’objet qui implante Result<T> est en fait un Lazy<T>, le calcul ne sera effectué que si son résultat est effectivement consulté. Si le résultat est consulté plusieurs fois (potentiellement par plusieurs threads différents), le calcul n’est toujours effectué qu’une seul fois.

Nous venons d’ajouter une dose d’évaluation paresseuse à Java.

Pour aller plus loin, regardons du côté de la programmation fonctionnelle — et des structures de données paresseuses.

Du côté de la programmation fonctionnelle

Commençons par réécrire en OCaml la première version de nos fonctions :

let log s = if should_log then output stream s

Nous venons de définir, comme en Java, une fonction nommée log, qui accepte comme paramètre un argument s — ici, une chaîne de caractères. Le contenu de la fonction log instruit d’écrire s sur un certain flux stream, si une certaine valeur booléenne should_log est vraie. Comme en Java, nous invoquerons cette fonction depuis my_function, à l’aide de :

let my_function i j k =
  log (sprintf "Entering my_function %i %i %i" i j k);
  (* ... *)
  log "Leaving my_function"

Jusque-là, à part les parenthèses et l’utilisation de la fonction sprintf, rien de bien différent. De nouveau, il est nécessaire de convertir i, j et k en chaînes de caractères et de procéder à quelques concaténations.

À partir d’ici, comme en Java, nous pouvons définir équivalent de Lazy<T>, que nous appellerions probablement 'a lazy, doté d’un constructeur qui acceptera en argument une fonction dont le résultat est un 'a, etc. La transformation de notre code pour convertir log en appel paresseux est globalement similaire à ce que nous ferions en Java. De fait, tout ceci n’est pas nécessaire puisque puisque la programmation paresseuse est en fait une primitive du langage. Le mot-clé lazy introduit une expression de type 'a Lazy.t, c’est-à-dire dont le résultat est de type 'a et ne sera calculé que s’il est nécessaire. La fonction force : 'a Lazy.t -> 'a permet alors de consulter le résultat d’une valeur ainsi mise en réserve, en la calculant au passage si nécessaire. De fait, notre version définitive ressemblera à

open Lazy
let log s =
  if should_log_1 then output stream_1 (force s);
  if should_log_2 then output stream_2 (force s);
  if should_log_3 then output stream_3 (force s)

let my_function i j k =
  log (lazy (sprintf "Entering my_function %i %i %i" i j k));
  (* ... *)
  log (lazy "Leaving my_function")

Notons au passage qu’il ne serait pas possible de réécrire directement lazy sous la forme d’une fonction OCaml. Pour réinventer lazy, il serait nécessaire de passer par Camlp4 ou d’accepter des notations légèrement plus lourdes.

Et alors ?

Il va falloir que je vous avoue quelque chose : je me moque complètement de la fonction log. Dans la programmation paresseuse, le plus intéressant, c’est bien les structures de données.

Tenez, en Java, nous pouvons très bien redéfinir la notion d’itérateurs de la manière suivante :

public interface MyIterator<T>
{
  public Lazy<MyIterator<T>> next();
  public T value;
}

Un itérateur est ici un objet capable de contenir une valeur… et de renvoyer un autre itérateur, qui représente la suite de l’itération. On écrira de même en OCaml :

type 'a my_iterator = Iterator of 'a * 'a my_iterator Lazy.t

Complétons cette définition pour nous autoriser à construire des itérations finies :

type 'a node =
 | Nil
 | Cons of 'a * 'a lazy_list
type 'a lazy_list = ('a node) Lazy.t

Nous venons de définir la notion de liste paresseuse. Une liste paresseuse est une valeur paresseuse qui, une fois évaluée, produit soit le résultat Nil (la liste vide), soit un résultat de la forme Cons(h, t)h est une valeur et t est la suite de la liste paresseuse.

À partir de cette définition, nous pouvons construire une fonction range, qui servira à représenter un intervalle d’entiers :

let rec range i j =
 if i >= j then Nil
 else            range (i+1) j

Ainsi, en OCaml, range 0 100000 calculera les nombres 0, 1, …, 100000 au fur et à mesure qu’ils seront demandés.

À partir de là, nous pouvons définir les transformations habituelles sur les structures de données. Ainsi, pour convertir (paresseusement) une liste paresseuse en une autre, comme pour les listes habituelles, nous pouvons définir la fonction map :

let rec map f l = match force l with
  | Nil            -> lazy Nil
  | Cons (h,t) -> lazy Cons (f h, map f t)

Cette fonction map, qui sera l’un des premiers outils que nous placerons dans notre bibliothèque de gestion des listes paresseuses, applique une fonction successivement à chaque élément d’une liste paresseuse, de manière à obtenir une nouvelle liste paresseuse. Pour doubler tous les éléments de notre intervalle précédent, nous écrirons donc

map (( * ) 2) (range 0 100000)

De la même manière, nous pouvons définir le nécessaire pour filtrer les éléments d’une liste afin de n’en garder que ceux qui vérifient une propriété donnée, le tout sous la forme d’une fonction filter, qui rejoindra map dans notre bibliothèque standard.

let rec filter f l = match Lazy.force l with
  | Nil -> lazy Nil
  | Cons(h,t) -> lazy (Cons (f h, filter t))

Et à ce prix-là, définissons une fonction iter, tout aussi standard, qui nous permettra d’appliquer une fonction impérative à tous les éléments d’une liste paresseuse, de la même manière que la boucle for de Python ou la nouvelle boucle for de Java :

let rec iter f l = match force l with
  | Nil            -> ()
  | Cons (h,t) -> f h; iter t

En combinant tout ce qui précède, nous pouvons faire afficher les carrés parfaits de l’ensemble des nombres pairs des nombres de l’intervalle [0; 100000].

let is_square x =
  let y = int_of_float (sqrt (float_of_int x)) in
  x = y * y

iter print_int (filter is_square (map (( * ) 2) (range 0 100000)))

Comme la liste n’est consultée qu’une seule fois, grâce à la magie de la paresse et du ramasse-miettes, tout ceci se fera fait sans avoir à allouer la mémoire vive nécessaire pour retenir tous les entiers entre 0 et 100000.

Jusqu’ici, toutes les opérations que nous avons vues auraient pu être implantées, peut-être avec quelques difficultés, en utilisant des itérateurs ou des générateurs, tels que ceux que définissent les bibliothèques Java, C#, JavaScript, Python, OCaml etc. Tout comme les listes paresseuses, les itérateurs et générateurs permettent de représenter des suites d’informations qui ne seront effectivement calculées que lorsqu’elles seront effectivement consultées. Mais à la différence des listes paresseuses, les itérateurs/générateurs oublient les informations immédiatement après les avoir fournies. Si les itérateurs et générateurs sont très utiles — et probablement plus optimisés que les listes paresseuses pour les exemples précédents — leur champ d’application s’arrête dès que les données peuvent être utilisées plusieurs fois.

Ainsi, considérons l’une des applications majeures des itérateurs/générateurs et des listes paresseuses : l’analyse de langages, et plus particulièrement l’analyse lexicale et syntaxique d’un code source. Le plus fréquemment, on commence par considérer le fichier d’entrée comme un itérateur/générateur de caractères. Un filtre, l’analyseur lexical, s’applique alors à cet itérateur pour le transformer en itérateur de lexèmes — c’est le rôle d’outils tels que Lex, Flex ou, aussi surprenant que cela puisse paraître, Sax. Ce deuxième itérateur est alors consommé par un analyseur syntaxique, dont le rôle est de produire un arbre de syntaxe abstraite, qui représentera le code source en mémoire vive — c’est, cette fois, le rôle d’outils tels que Bison, Yacc ou DOM. Ces derniers, ainsi que [presque tous] leurs concurrents, consultent à l’avance k lexèmes depuis l’itérateur de lexème, pour un certain k fixé lors de la conception de l’analyseur, émettent des hypothèses en partant de ces k lexèmes, et ne peuvent pas revenir en arrière, en cas d’erreur, de plus de k pas. À l’inverse, et de manière très schématique, les combinateurs de parseurs construits sur des listes paresseuses, tels que Parsec (pour Haskell) ou PLC (pour OCaml), ne sont pas limités par ces k lexèmes d’avance, puisqu’ils peuvent à volonté revenir en arrière dans la liste. Un élément ne disparaît de la liste paresseuse que lorsque sa valeur ne peut plus influencer l’exécution du programme. Cette conception à base de listes paresseuses se paye en termes de performances et de consommation de mémoire mais offre beaucoup plus de flexibilité, notamment la possibilité de construire ou de modifier dynamiquement des analyseurs syntaxiques.

Avant de conclure sur la comparaison entre itérateurs et listes paresseuses, précisons brièvement qu’il est aisé de construire l’un par-dessus l’autre : un itérateur est une liste paresseuse qui oublie ses éléments au fur et à mesure qu’ils sont consommés, alors qu’une liste paresseuse est un itérateur qui retient ses éléments jusqu’à intervention du ramasse-miettes. Ainsi, dans la bibliothèque sur laquelle je travaille, la conversion d’une liste paresseuse en itération s’est écrite, jusqu’à une récente optimisation :

let enum l =
  let reference = ref l in
    Enum.from (fun () -> match next !reference with
			 | Cons(x,t) -> reference := t; x
			 | Nil          -> raise Enum.No_more_elements )

Dans cet extrait de code, nous commençons par déclarer une variable modifiable nommée reference et qui désignera initialement le premier élément de la liste. Nous définissons alors une fonction anonyme qui, lorsqu’elle sera appelée, renverra l’élément actuel désigné par reference, ou, si nous avons dépassé la fin de la liste, lancera une exception Enum.No_more_elements pour signaler que l’itérateur est terminé. La fonction Enum.from construit l’itérateur dont le comportement est donné par cette fonction.

À l’inverse, pour convertir un itérateur en liste paresseuse, nous employons la fonction suivante :

let of_enum e =
  let rec aux () =
    lazy (match Enum.get e with
      |	Some x -> Cons (x, aux () )
      | None    -> Nil )
  in aux ()

Dans l’extrait, nous commençons par définir une boucle que nous nommons aux et dons le contenu est paresseux. À chaque fois qu’un nouvel élément de la liste est consulté, nous consommons la valeur du prochain élément de notre itérateur. Si celui-ci existe, nous l’appelons x, et ce x constitue le prochain élément de notre liste, tandis que la suite de la liste sera donnée par le résultat de la prochaine invocation de la boucle aux. Dans le cas contraire, la liste est terminée.

Références :

  • Pour plus de détails sur la distinction entre générateurs, itérateurs et listes paresseuses, je vous invite à consulter Iterators: Signs of Weakness in Object-Oriented Languages, par Henry G. Baker.
  • Pour plus de détails sur le module de listes paresseuses de Batteries Included, le code source est disponible sur OCaml Forge. Le code source du module Enum, qui définit des itérateurs pour OCaml, est disponible avec le reste de la bibliothèque ExtLib, sur Google Code.
  • Pour plus de détails sur la programmation paresseuse en OCaml, le guide de référence est à votre disposition.
  • Enfin, rendons à César ce qui appartient à César. Si l’évaluation paresseuse vous intéresse, vous êtes vivement encouragés à vous informer sur le langage de programmation Haskell, dans lequel toutes les évaluations sont paresseuses par défaut.

Tagged: , , , , , , , , , , , , , , , , , , , , , , ,

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

What’s this?

You are currently reading Quelques mots de programmation paresseuse at Il y a du thé renversé au bord de la table.

meta

%d bloggers like this: