Func' programming - un blog homéopathique

Les joies de la procrastination
Je voudrais introduire ici l’évaluation paresseuse (« lazy evaluation ») caractéristique de certains langages fonctionnels, au premier rang desquels Haskell, qui faisait l’objet des deux précédents billets (1 2). Elle consiste, en deux mots, à reporter l’évaluation d’une valeur au moment où elle est devenue nécessaire.

L’évaluation paresseuse n’est pas l’apanage des langages fonctionnels –bon nombre d’entre eux reposent d’ailleurs au contraire sur le principe de l’évaluation stricte, ou immédiate. Inversement, elle peut apparaître dans des langages impératifs : une bibliothèque de traitement des matrices, écrite en C++, en fait d’ailleurs usage, comme du « polymorphisme statique », pour accroître ses performances. Cependant, l’évaluation paresseuse crée plus de problèmes qu’elle n’en résout lorsque le programme est constitué d’une succession d’états : l’état du programme peut avoir changé entre la définition de la valeur et son utilisation. Les principes fonctionnels garantissent en revanche que ce ne sera pas le cas.

Les bœufs et la charrue
L’évaluation paresseuse est une généralisation du bon sens. Bon sens caractéristique du programmeur, qui n’écrira jamais :

Code C :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
pFile = fopen(file) ;
bool ok = grosseFonctionDeLaMort() ; // je vais appeler cette fonction pour rien, peut-être…
if ( pFile && ok) { …

mais :

Code C :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
pFile = fopen(file) ;
if ( pFile && grosseFonctionDeLaMort() ) { … // si pFile n’est pas ouvert, grosseFonction ne sera pas évaluée

Dans un programme paresseux, les appels de fonction et les valeurs non-triviales (ce n’est donc pas le cas des littéraux, par exemple) sont initialement à l’état de « thunk », c’est-à-dire en attente d’évaluation. Les thunks ne sont évalués qu’au moment où c’est nécessaire.

What’s the point ?
Evidemment, la plupart des valeurs définies seront utilisées, et la plupart des thunks évalués. Prenons l’exemple d’une fonction de tri : il est évident que toutes les valeurs de la liste triée seront évaluées à un moment ou à un autre. Le tri est par nature une opération stricte.

Inversement, prenons l’exemple d’une fonction qui renverrait les éléments d’indice pair dans une liste :

Code Haskell :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
evens []  = []
evens [x] = [x]
evens (x:_:xs) = x : evens xs     --les éléments impairs ne seront pas évalués

Vers l’infini et au-delà
Une conséquence particulièrement intéressante de l’évaluation paresseuse est la possibilité de travailler sur des structures infinies –les arbres et les listes, par exemple.

La liste des entiers à partir de 1 peut être définie tout simplement :

posIntegers = [1..] -- les entiers de 1 à 9 pourraient être désignés par [1..9]

Au-delà de ce sucre syntaxique, voici une fonction inifinie :

fib m n = m : (fib n (m+n)) --la suite de Fibonacci

Comment utiliser ces listes ou ces fonctions infinies ? Elles peuvent servir en argument d’une fonction qui définit la portion qu’elle veut utiliser. La fonction la plus simple est take :

take 0 _ = []
take n (x : xs) = x : (take (n-1) xs)

> take 5 $ fib 1 1
[1,1,2,3,5]

Mémoire de l’infini
Autant une valeur, une fois évaluée, pourra être réutilisée sans nouvelle évaluation (le thunk a été remplacé par une valeur à l’adresse pointée par le nom de la variable), autant chaque appel de fonction aboutira à la création d’un nouveau thunk. L’application d’une technique de « mémoïsation » est possible, mais à la charge du programmeur.

Cependant, les structures de données nommées bénéficient automatiquement de cette technique. Les éléments évalués d’une liste infinie, définie par une fonction par exemple, resteront en mémoire.

List comprehension
Les « list comprehensions » dont la traduction littérale, « compréhension de liste », est un peu ambiguë, mettent l’accent sur cette possibilité de mémoïsation. Voici quelques exemples de leur syntaxe :

-- [ fonction | arg <- source ]
puissancesDe2 = [2^x | x <- [1..]]

-- [fonction | arg1 <- source1 , arg2 <- source2]
-- lorsqu’il y a plusieurs sources, fonction est appliquée à leur produit cartésien
ProdCart m n = [ [x, y] | x <- [1..m], y <- [1..n]]

> ProdCart 4 4
[[1,1],[1,2],[1,3],[1,4],[2,1],[2,2],[2,3],[2,4],[3,1],[3,2],[3,3],[3,4],[4,1],[4,2],[4,3],[4,4]]

Une petite torsion de cerveau pour finir
L’évaluation paresseuse permet de créer des compréhensions de listes infinies par récursion. Je vous laisse méditer cet exemple :

fib = 1:1:[x | x <- zipWith (+) fib (tail fib)] -- zipWith f a b crée une liste résultant de l’application de f à chaque élément de a et de b

Exercices :

- rédigez une compréhension de liste définie comme l’ensemble des nombres premiers
- voyez-vous les avantages pratiques à travailler avec des structures inifinies ? expliquez pourquoi
- pourriez-vous implémenter l’évaluation paresseuse dans votre langage favori ? à quel prix ? qu’est-ce que cela dit de l’équivalence de Turing ?