Lazy evaluation ou évaluation différée

La lazy évaluation [1], qui signifie évaluation paresseuse, appelée à plus juste titre évaluation différée (delayed evaluation) est une technique – plus précisément, une implémentation d’une stratégie d’évaluation – qui permet d’évaluer un bloc de code où le contenu d’une variable au moment où celui-ci est effectivement nécessaire. En fait, l’évaluation de ce contenu est uniquement fait lors de l’évaluation de la variable qui y est dépendante. L’évaluation différée s’oppose à l’évaluation stricte qui évalue une expression ou une variable lors de l’affectation même si celle-ci n’est ensuite jamais utilisée. Ces deux types d’évaluation peuvent bien sûr coexister au sein d’un même langage de programmation.

Il sera considéré dans le même registre, la lazy initialization, qui signifie initialisation différée qui, au même titre que l’évaluation différée, a pour rôle d’instancier une classe au moment où celle-ci est réellement nécessaire.

Schéma simplifié

Le schéma ci-dessous présente le processus d’affectation et d’utilisation d’une variable dans le contexte d’évaluation stricte / différée de manière simplifié.

Lazy-eval

  1. Affectation dans un contexte d’évaluation stricte
  2. Affectation dans un contexte d’évaluation différée
  3. Utilisation d’une variable dans un contexte d’évaluation stricte
  4. Utilisation d’une variable dans un contexte d’évaluation différée

Implémentations natives

Selon les concepts introduits par le langage de programmation que l’on utilise, l’évaluation différée peut être le type d’évaluation par défaut, auquel cas il existe généralement des mot-clés qui permettent de forcer cette évaluation si nécessaire. A l’inverse d’autres langages – la plupart – sont principalement basés sur l’évaluation stricte, on trouve alors dans certains cas les mots-clés nécessaires ou bien des objets spécifiques pour introduire de l’évaluation différée.

L’implémentation peut être propre au langage, ou avoir été introduite par le biais d’une librairie ou d’un framework.

Évaluation stricte par défaut (Eager evaluation)

Oz

functor
import
   Application
   System

define

   fun {Inc A}
   		{System.showInfo 'Incrémente'}
   		A+1
   end
   
   {System.showInfo 'Appel fonction incrémentation'}
   X = {Inc 10}
   {System.showInfo 'Affiche résultat'}
   {System.showInfo X}

   {Application.exit 0}
end

Sortie :

Appel fonction incrémentation
Incrémente
Affiche résultat
11

La fonction n’est pas évaluée en différé. On remarque que « Incrémente » s’affiche dans la console dés l’appel de la fonction.

Oz lazy

functor
import
   Application
   System

define

   fun lazy {Inc A}
   		{System.showInfo 'Incrémente'}
   		A+1
   end
   
   {System.showInfo 'Appel fonction incrémentation'}
   X = {Inc 10}
   {System.showInfo 'Affiche résultat'}
   {System.showInfo X}

   {Application.exit 0}
end

Sortie :

Appel fonction incrémentation
Affiche résultat
Incrémente
11

Avec le simple ajout de mot-clé lazy aprés le mot-clé fun – qui permet la définition d’une fonction – le langage Oz propose l’évaluation différée de la fonction. Ici, il faut remarquer que « Incrémente » n’est affiché que après « Affiche résultat », ce qui signifie que la valeur de X dépendante de la fonction Inc n’a été évaluée qu’au moment où elle a été nécessaire, dans ce cas, lors de l’affichage.

OCaml

let inc a = 
	print_string "Incrémente\r\n";
	a + 1;;

print_string "Appel fonction incrémentation\r\n";;
let x = inc 10;;
print_string "Affiche le résultat\r\n";;
print_int x;;

Sortie :

Appel fonction incrémentation
Incrémente
Affiche le résultat
11

OCaml Lazy

let inc a = lazy(
	print_string "Incrémente\r\n";
	a + 1);;

print_string "Appel fonction incrémentation\r\n";;
let x = inc 10;;
print_string "Affiche le résultat\r\n";;
print_int (Lazy.force x);;

 Sortie :

Appel fonction incrémentation
Affiche le résultat
Incrémente
11

Grâce au module lazy de OCaml l’évaluation différée peut-être introduite. On utilise Lazy.force afin de forcer l’évaluation de l’expression.

Évaluation différée par défaut (Lazy evaluation)

Haskell

Haskell, un langage fonctionnel pur, propose l’évaluation différée par défaut.

displayAB a b = print(a+b);

main = do 
	putStrLn "Avant appel";
	let ab = displayAB 10 5;
	putStrLn "Apres appel";
	ab; --evalue a + b

 Sortie :

Avant appel
Apres appel
15

Intérêts de l’évaluation différée

Mémoire et performances

Sachant que l’expression concernée ne sera jamais évaluée inutilement, l’intérêt le plus évident de l’évaluation différée se trouve dans le gain de mémoire et de performances.

Paramètres de fonctions

Les paramètres de fonctions peuvent être passés sans avoir été évalués.

Exemple :

function test(a, b)
{
    if (a > 0)
        return b + 10;
    else
        return 0;
}

Dans l’exemple ci-dessus, la variable a sera évaluée pour le test a > 0, par contre b ne sera évalué que dans le cas où la condition est vérifiée. Dans ce genre de situation, l’évaluation différée apporte donc un gain de performance et de mémoire.

Evaluation Short-Circuit

L’évaluation différée combinée avec l’évaluation short-circuit peut aussi apporter un gain de performance. L’évaluation short-circuit permet à une expression booléenne d’être évaluée terme par terme de gauche à droite (ou peut être de droite à gauche pour certains langages exotique ou non). Dés lors que l’expression booléenne est vérifiée les termes restant ne sont pas évalués.

Exemple :

  • (true && false && true) : les deux premiers termes sont évalués, le deuxième étant faux l’expression est forcément fausse, le dernier terme n’est donc pas évalué.
  • (false || true || false) : les deux premiers termes sont évalués, le deuxiéme étant vrai l’expression est forcément vraie, le dernier terme n’est donc pas évalué.

On comprend bien pourquoi ce mécanisme d’évaluation booléenne peut être intéressant avec l’évaluation différée, dans ce genre de cas :

var a = delayed_inc(10); //Evaluation différée
var b = delayed_inc(11); //Evaluation différée

if (a > 10 || b < 10)
{
    
}

Dans l’exemple ci-dessus, la fonction delayed_inc permet l’incrémentation en différé de la valeur passée en paramètre. L’expression a > 10 est évaluée donc la variable a est évaluée, a étant vrai, la suite de l’expression booléenne ne nécessite pas d’être évaluée. Ainsi la variable b n’est jamais évaluée.

Mémoïsation

Bien qu’il s’agisse de deux mécanismes différents, l’évaluation différée est généralement accompagnée d’une technique d’optimisation de code nommée mémoïsation (memoization) inventée et publiée par Donald Michie en 1968 dans la revue Nature. En fait à chaque demande d’évaluation d’une expression, le programme enregistre le résultat de celle-ci – pour les paramètres qu’ils lui ont été passés – dans une table de correspondance (lookup table). Ainsi lorsque une nouvelle demande effectuée, la table de correspondance sera tout d’abord consultée pour vérifier s’il existe ou non un résultat déjà calculé. Dans le cas où le résultat a été auparavant calculé, celui-ci est simplement retourné, sinon la fonction est exécutée normalement. Le principe de mémoïsation est aussi généralisé par le biais de technique tel que le machine learning, l’approximation ou encore l’interpolation de valeurs.

Elle peut être implémentée nativement par le langage, une librairie ou par le développeur.

Construction de suites potentiellement infinies

Grâce à la définition de générateurs – qui sont aussi des itérateurs – par un système de co-recursion, il est possible de créer une liste infinie, appelée aussi un flux (stream). L’évaluation différée permet dans ce contexte l’évaluation d’un morceau de cette liste plutôt que d’en demander son calcul global qui serait, comme il faut en douter, infiniment long.

Afin de bien comprendre l’idée des suites potentiellement infinies voici quelques définitions.

Quelques définitions :

  • générateur : c’est une routine qui décrit son comportement – le calcul à effectuer – lors de son itération par une boucle. Cette routine peut être ainsi énumérée et fournit à chaque cycle d’énumération – un tour de boucle – une seule valeur. Le générateur est généralement une fonction. Celle-ci se comporte comme un itérateur et est considérée ainsi, il implémente aussi un comportement qui fait de lui un itérable.
  • itérateur : un itérateur est une entité qui sert à traverser un conteneur : une entité itérable. L’itérateur est utilisé implicitement par les structures de contrôles tel que le for each et peut être utilisé explicitement au sein d’une structure while généralement accompagné par des fonctions comme moveNext() (C#, Java…).
  • itérable : un itérable est une entité qui peut être traversée par un itérateur.
  • flux / stream : un flux est une séquence de données qui sont disponibles au fur et à mesure par apport à une ligne de temps. Ce qu’il faut retenir, c’est qu’un flux peut être potentiellement infini et est donc codata c’est à dire qu’il s’agit d’une structure de donnée infinie. Pour comparaison avec les signaux discrets, une fonction appliquée sur un flux qui retourne un flux est appelée un filtre. Le pipelinage dans un tel cas pourrait être considéré comme l’application d’une suite de filtres au flux en question [2].
  • codata : il s’agit d’un type défini co-inductivement, la manipulation de codata peut se faire à travers la co-recursion et l’évaluation différée. Le codata peut servir comme système de preuve.
  • co-recursion : la co-récursion ou l’algorithme co-récursif, est un système qui produit des données en partant d’un cas de base et qui construit sa continuité (sa suite) itérativement sur ses propres valeurs antérieures. C’est cet aspect de construction itératif d’une fonction récursive du bas (cas de base) vers le haut qui permet la construction de suite infinie. Ce système donne au flux – codata – par déduction des nouvelles valeurs sur ses valeurs antérieures sa valeur en tant que système de preuve. La co-récursion permet aussi la définition de fonction ou d’itérateur indexé, ce qui permet d’obtenir le résultat d’un calcul pour un index donné.

Co-récursion

L’exemple le plus simple et le plus courant est celui de la génération de nombre factoriels :

function factorial(k)
{
    var n = 0;
    var f = 1;
    
    while (n < k)
    {
        f = f * (n + 1);
        n = n + 1;
    }
    
    return f;
}

console.log(factorial(5));

Dans l’exemple ci-dessus, la factorielle d’un nombre est calculée en partant du cas de base (la factorielle de 0 vaut 1) et se construit au fur et à mesure sur les valeurs calculés antérieurement – par le biais de la boucle while – jusqu’à atteindre l’index demandé à la manière d’une suite.

Générateurs

Voici la description du générateur en Javascript :

Calling a generator function does not execute its body immediately; an iterator object for the function is returned instead. When the iterator’s next() method is called, the generator function’s body is executed until the first yield expression, which specifies the value to be returned from the iterator […]

Référence : https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Statements/function*

Traduction :

Appeler une fonction de type générateur ne va pas l’exécuter immédiatement, un objet itérateur est retournée à la place pour cette fonction. Elle est exécutée jusqu’à l’expression yield – qui spécifie la valeur à retourner – uniquement lorsque la méthode next() de l’itérateur est appelée.

Il se dessine clairement ici l’esquisse de l’évaluation différée, couplé avec le principe des générateurs (itérateurs). En y associant le principe de co-récursion, il devient alors possible de construire des suites potentiellement infinies.

Exemple d’implémentation en javascript :

function* genFactorial(k){
    var n = 0;
    var f = 1;
    
    while (n < k)
    {
        f = f * (n + 1);
        n = n + 1;
        yield f;
    }
}

for (var n of genFactorial(5))
    console.log(n); //1,2,6,24,120

Cette implémentation n’est pas mémoïsée, par contre vis-à-vis de la citation précédente, elle respecte le mécanisme de lazy evaluation.

 

Les constructions de suites infinies permettent de nombreux calculs intéressants comme le fait de pouvoir traiter des nombres réels exacts sous formes de flux et non comme des valeurs approximatives contenues dans un intervalle fini représentés par des flottants à simple ou double précisions. Ces derniers, par le fait qu’il appartiennent à un intervalle fini, peuvent introduire des erreurs de calculs à la suite de multiples opérations.

Implémentation non native « à la main »

Sans même y introduire de nouveaux mot-clés, les langages de programmation autorisant la définition de fermetures (closures) qui peuvent être retournées – passée vers le haut – ou bien d’itérateur, permettent par ce biais, la création de blocs de code dont le contenu est exécutable en différé.

Lazy évaluation par fonctions

L’évaluation différée peut être facilement introduite grâce à la définition de fermetures. Par contre, l’évaluation doit être explicitement demandée par l’appel de la fonction retournée, ce qui peux poser problème lors d’une évaluation différée « à la chaîne » notamment par le processus de pipeline.

Les exemples qui suivent sont en Javascript.

Exemple simple

function inc(a)
{
    return function()
    {
        return ++a;
    };
};

var x = inc(10);
console.log(x()); //Evaluation forcée

Ci-dessus, un exemple simple de définition d’un système d’évaluation différée grâce aux fonctions. La fonction inc ne fait que préparer le traitement mais ne l’exécute pas. Pour forcer l’évaluation il faut ainsi appeler la fonction reçue. L’inconvénient de cette implémentation et qu’elle n’autorise pas la composition de fonctions lazy – les pipelines entre des fonctions d’évaluation différée – c’est à dire les fonctions du genre : (f\circ g)(x) \Leftrightarrow g(f(x)). Donc ici, il n’est pas possible de faire directement inc(inc(10)), sans avoir préalablement évalué inc(10).

Exemple autorisant le pipelinage

Pour corriger ce problème il est possible d’imaginer ce système :

function inc(a)
{
    return function()
    {
        if (typeof a === 'function')
            return a() + 1;
        else
            return a + 1;
    };
};

var x = inc(inc(inc(10))); //Pipeline
console.log(x()); //Evaluation forcée

Ainsi la composition de fonctions lazy est possible et lors de l’évaluation forcée les autres blocs de code sont évalués en cascade.

Généralisation

Pour généraliser la méthode à toutes les fonctions (en javascript) on peut étendre le prototype Function, il est bien sûr possible d’imaginer un système équivalent dans d’autres langages de programmation :

//Etends le prototype Function avec la fonction lazy
Function.prototype.lazy = function()
{
    var fn = this;
    var args = [];

    //Transforme les arguments en tableau
    for (var i = 0; i < arguments.length; i++)
        args[i] = arguments[i];

    //Retourne un objet lazy    
    return {
        force: function()
        {
            //Force l'évaluation des arguments lazy
            for (var i = 0; i < args.length; i++)
            {
                if (args[i].force !== undefined && 
                    typeof args[i].force === 'function')
                {
                    args[i] = args[i].force();
                }
            }
            
            //Execute la fonction
            return fn.apply(null, args);
        }
    };
};

//Déclaration d'une fonction classique
function inc(a)
{
    console.log('évalue');
    return ++a;    
};

console.log('début');
var a = inc.lazy(10);
var b = inc.lazy(a);
console.log('fin');

console.log(b.force()); // Affiche 12

Sortie :

"début"
"fin"
"évalue"
"évalue"
12

On remarque que les fonctions définies comme lazy, inc.lazy, ne sont pas directement appelées. L’évaluation a lieu uniquement lors de l’appel de la fonction force(). Cette version peut être encore améliorée pour y inclure la mémoïsation.

Dans tout les cas, l’inconvénient des méthodes précédentes est que l’évaluation doit être appelée explicitement par le développeur.

Lazy évaluation par itérables

Les itérables sont des conteneurs qui peuvent être itérés, c’est à dire traversés, par un itérateur. Ces itérables peuvent avoir diverses formes : objets, structures de données, etc.

Il est possible d’implémenter le mécanisme d’évaluation différée en créant des itérables. Comme exemple il sera repris l’implémentation de la fonction filter qui permet de filtrer le contenu d’un tableau selon un prédicat. Le prédicat est une fonction qui indique de quel manière le tableau doit être filtré.

Array.prototype.filter2 = function (predicate)
{
    var array = this;
    var i = 0;
     
    var it={};
    it[Symbol.iterator] = function* () 
    {
        while (i++ < array.length)
        {
            if (predicate(array[i]))
                yield array[i];
        }
    };
     
    return it;
}
 
var test = [1,2,3,7,8];
var filtered = test.filter2(function(e)
{
  return e > 6;
});
 
 
for (var el of filtered)
    console.log(el);

Dans l’exemple ci-dessus, le prédicat de filter2 qui est une fonction n’est évalué que lors de l’itération, c’est à dire au niveau du for..of et non à l’appel de la fonction filter2.

Lazy initialization

Au sein du paradigme orientée objet il peut être utile de différer l’initialisation d’un objet. C’est par exemple ce que propose le framework .NET de Microsoft avec la classe Lazy.

la classe Lazy à été réécrite en C# de manière simplifiée dans l’exemple suivant :

using System;
using System.Reflection;

public class Test
{
	public static void Main()
	{
	
		bool b = true;
		MyLazy<Duck> s = new MyLazy<Duck>();
		
		if (b)
			s.Value.Name = "Daffy";
		
		Console.WriteLine(s.Value.Name);
	}
}

class Duck
{
	public string Name {get;set;}
}

class MyLazy<T>
{
	private T obj;
	
	public T Value
	{
		get {
			if (obj == null)
				obj = Activator.CreateInstance<T>();
			
			return obj;
		}
	}
	
}

La classe Duck n’est initialisée que lorsque son nom est affecté par s.Value.Name. Lors de l’accès à la propriété Value, la classe concernée par la lazy initialization (paramètre T) est instanciée si ce n’est pas déjà le cas et est ensuite retournée.

Pour voir la véritable implémentation de la classe Lazy au sein du framework .NET : classe Lazy .NET


La stratégie d’évaluation considérée lors du développement d’un algorithme peut prendre une place importante par apport à l’optimisation de celui-ci où encore de son bon déroulement. J’espère que cet article rappellera son bien fondé et montre surtout qu’il n’existe pas une seule et unique stratégie d’évaluation (l’évaluation stricte) dans le monde de la programmation.


Notes :

[1] L’appellation lazy evaluation est mal choisie car elle regroupe plusieurs systèmes d’évaluation que l’on peux qualifier de paresseuse, notamment l’évaluation short-circuit.

[2] Ceci est une proposition personnelle et ne dépend pas d’une référence.


Références :

http://www.cs.utexas.edu/~hunt/research/hash-cons/hash-cons-papers/michie-memo-nature-1968.pdf

https://developer.mozilla.org/fr/


One thought on “Lazy evaluation ou évaluation différée

Laisser un commentaire