Pourquoi est l'évaluation paresseuse utile?

Question

J'ai longtemps été intrigué par l'utilité de l'évaluation paresseuse. Je n'ai encore jamais eu quiconque m'expliquer de manière convaincante; la plupart du temps, cela se résume à "fais-moi confiance".

Remarque : Je ne parle pas de mémoïsation.

Answer 1

Principalement parce que cela peut être plus efficace -- les valeurs n'ont pas besoin d'être calculées si elles ne vont pas être utilisées. Par exemple, je peux passer trois valeurs dans une fonction, mais en fonction de la séquence des expressions conditionnelles, seulement un sous-ensemble peut effectivement être utilisé. Dans un langage comme C, les trois valeurs seraient calculées de toute façon ; mais en Haskell, seules les valeurs nécessaires sont calculées.

Cela permet également des choses intéressantes comme les listes infinies. Je ne peux pas avoir une liste infinie dans un langage comme C, mais en Haskell, ce n'est pas un problème. Les listes infinies sont assez souvent utilisées dans certains domaines des mathématiques, donc il peut être utile d'avoir la capacité de les manipuler.

Answer 2

Un exemple utile d'évaluation paresseuse est l'utilisation de quickSort :

quickSort [] = []
quickSort (x:xs) = quickSort (filter (< x) xs) ++ [x] ++ quickSort (filter (>= x) xs)

Si nous voulons maintenant trouver le minimum de la liste, nous pouvons définir

minimum ls = head (quickSort ls)

Cela trie d'abord la liste puis prend le premier élément de la liste. Cependant, en raison de l'évaluation paresseuse, seule la tête est calculée. Par exemple, si nous prenons le minimum de la liste [2, 1, 3,] quickSort va d'abord filtrer tous les éléments plus petits que deux. Ensuite, il effectue quickSort sur cela (retournant la liste singleton [1]) ce qui est déjà suffisant. Grâce à l'évaluation paresseuse, le reste n'est jamais trié, ce qui permet d'économiser beaucoup de temps de calcul.

Il s'agit bien sûr d'un exemple très simple, mais la paresse fonctionne de la même manière pour les programmes très grands.

Cependant, il y a un inconvénient à tout cela : il devient plus difficile de prédire la vitesse d'exécution et l'utilisation de la mémoire de votre programme. Cela ne signifie pas que les programmes paresseux sont plus lents ou prennent plus de mémoire, mais c'est bon à savoir.

Answer 3

Je trouve l'évaluation paresseuse utile pour plusieurs choses.

Premièrement, tous les langages paresseux existants sont purs, car il est très difficile de raisonner sur les effets secondaires dans un langage paresseux.

Les langages purs vous permettent de raisonner sur les définitions de fonctions en utilisant un raisonnement équationnel.

foo x = x + 3

Malheureusement, dans un environnement non paresseux, plus d'instructions échouent à retourner que dans un environnement paresseux, donc cela est moins utile dans des langages comme ML. Mais dans un langage paresseux, vous pouvez raisonner en toute sécurité sur l'égalité.

Deuxièmement, beaucoup de choses comme la 'restriction de valeur' en ML ne sont pas nécessaires dans les langages paresseux comme Haskell. Cela conduit à un grand désencombrement de la syntaxe. Les langages de type ML ont besoin d'utiliser des mots-clés comme var ou fun. Dans Haskell, ces choses se réduisent à une seule notion.

Troisièmement, la paresse vous permet d'écrire un code très fonctionnel qui peut être compris en morceaux. En Haskell, il est courant d'écrire le corps d'une fonction comme suit :

foo x y = if condition1
          then some (ensemble compliqué de combinataires) (impliquant une grosse expression effrayante)
          else if condition2
          then grosse expression effrayante
          else Nothing
  where some x y = ...
        grosse expression effrayante = ...
        condition1 = ...
        condition2 = ...

Cela vous permet de travailler 'de haut en bas' à travers la compréhension du corps d'une fonction. Les langages de type ML vous obligent à utiliser un let qui est évalué de manière stricte. Par conséquent, vous n'osez pas 'lever' la clause let hors du corps principal de la fonction, car si elle est coûteuse (ou a des effets secondaires), vous ne voulez pas qu'elle soit toujours évaluée. Haskell peut 'déplacer' les détails vers la clause where explicitement car il sait que le contenu de cette clause ne sera évalué que si nécessaire.

En pratique, nous avons tendance à utiliser des gardes et à les réduire encore plus à :

foo x y 
  | condition1 = some (ensemble compliqué de combinataires) (impliquant une grosse expression effrayante)
  | condition2 = grosse expression effrayante
  | sinon  = Nothing
  where some x y = ...
        grosse expression effrayante = ...
        condition1 = ...
        condition2 = ...

Quatrièmement, la paresse offre parfois une expression beaucoup plus élégante de certains algorithmes. Un 'quick sort' paresseux en Haskell est une seule ligne et a l'avantage que si vous ne regardez que les premiers éléments, vous ne payez que les coûts proportionnels au coût de sélection de ces éléments. Rien ne vous empêche de le faire strictement, mais vous seriez probablement obligé de recoder l'algorithme à chaque fois pour obtenir les mêmes performances asymptotiques.

Cinquièmement, la paresse vous permet de définir de nouvelles structures de contrôle dans le langage. Vous ne pouvez pas écrire une nouvelle structure de contrôle 'si..alors..sinon..' dans un langage strict. Si vous essayez de définir une fonction comme :

if' True x y = x
if' False x y = y

dans un langage strict, les deux branches seraient évaluées indépendamment de la valeur de la condition. Cela devient pire lorsque vous considérez les boucles. Toutes les solutions strictes nécessitent que le langage vous fournisse une sorte de mise entre guillemets ou une construction explicite de lambda.

Enfin, dans le même ordre d'idées, certains des meilleurs mécanismes pour traiter les effets secondaires dans le système de types, tels que les monades, ne peuvent vraiment être exprimés efficacement que dans un environnement paresseux. Cela peut être constaté en comparant la complexité des Workflows de F# aux Monades de Haskell. (Vous pouvez définir une monade dans un langage strict, mais malheureusement vous échouerez souvent à une ou deux lois de monades en raison du manque de paresse et les Workflows, en comparaison, ramassent une tonne de contraintes strictes.)

Answer 4

Il existe une différence entre l'évaluation de commande normale et l'évaluation paresseuse (comme en Haskell).

square x = x * x

En évaluant l'expression suivante...

square (square (square 2))

... avec une évaluation par impatience :

> square (square (2 * 2))
> square (square 4)
> square (4 * 4)
> square 16
> 16 * 16
> 256

... avec une évaluation de commande normale :

> (square (square 2)) * (square (square 2))
> ((square 2) * (square 2)) * (square (square 2))
> ((2 * 2) * (square 2)) * (square (square 2))
> (4 * (square 2)) * (square (square 2))
> (4 * (2 * 2)) * (square (square 2))
> (4 * 4) * (square (square 2))
> 16 * (square (square 2))
> ...
> 256

... avec une évaluation paresseuse :

> (square (square 2)) * (square (square 2))
> ((square 2) * (square 2)) * ((square 2) * (square 2))
> ((2 * 2) * (2 * 2)) * ((2 * 2) * (2 * 2))
> (4 * 4) * (4 * 4)
> 16 * 16
> 256

Cela est dû au fait que l'évaluation paresseuse examine l'arbre syntaxique et effectue des transformations d'arbre...

square (square (square 2))

           ||
           \/

           *
          / \
          \/
    square (square 2)

           ||
           \/

           *
          / \
          \/
           *
          / \
          \/
        square 2

           ||
           \/

           *
          / \
          \/
           *
          / \
          \/
           *
          / \
          \/
           2

... alors que l'évaluation de commande normale ne fait que des expansions textuelles.

C'est pourquoi, lorsque nous utilisons l'évaluation paresseuse, nous obtenons une puissance supérieure (l'évaluation se termine plus souvent que d'autres stratégies) tout en ayant des performances équivalentes à l'évaluation par impatience (au moins en notation O).

Answer 5

Si vous croyez Simon Peyton Jones, l'évaluation paresseuse n'est pas importante en soi mais seulement comme une 'chemise de poil' qui a forcé les concepteurs à maintenir la pureté du langage. Je me retrouve sympathique à ce point de vue.

Richard Bird, John Hughes, et dans une moindre mesure Ralf Hinze sont capables de réaliser des choses étonnantes avec l'évaluation paresseuse. Lire leurs travaux vous aidera à l'apprécier. De bons points de départ sont le magnifique sudoku de Bird et l'article de Hughes sur Pourquoi la programmation fonctionnelle est importante.