Discussion :

[SpiceGuid]

Le heapsort est un tri sur-place (donc impératif) qui a la même complexité temporelle que le mergesort.

Sinon sur la complexité tu as grosso modo le constat suivant:

• la complexité temporelle est généralement comparable
• comme le dit gorgonite la complexité spaciale est éventuellement un peu supérieure (et dans le pire des cas l'évaluation paresseuse, vu qu'elle est orientée "déforestation", est moins bonne spacialement que l'évaluation stricte)

De toute manière peu de langages sont fonctionnellement purs et la plupart (Scheme,Lisp,Caml,Anubis) possèdent les tableaux sous la forme traditionnelle.
Haskell est fonctionnellement pur, je crois me souvenir qu'il offre des moyens pour, par exemple, créer des matrices en un temps non quadratique, mais je ne suis pas en mesure de te dire si ces moyens compensent complètement l'absence de tableaux traditionnels.

[alex_pi]

Le heapsort est un tri sur-place (donc impératif) qui a la même complexité temporelle que le mergesort.

En même temps, tous les tris sont en n log n, donc spas trop parlant :-) C'est la constante qui compte, et dans quel cas elle se manifeste (pire, moyenne, tous ?)

[gasche]

Sauf les tris quadratiques, le Shell sort, les tris linéaires, etc.

Il y a des intermédiaires entre la complexité et la mesure brute des performances, ou le calcul de la constante de temps. Par exemple l'approche "théorie de l'information" (qui malheureusement ne rend pas compte de la localité et autres détails low-level qui jouent un rôle très important) que j'ai trouvée assez intéressante, et découverte dans cet article/billet.

[HanLee]

Le heapsort est un tri sur-place (donc impératif) qui a la même complexité temporelle que le mergesort.

A noter qu'on peut aussi faire un merge sort sur place, mais c'est très compliqué!

[Jedai]

Sinon sur la complexité tu as grosso modo le constat suivant:

• la complexité temporelle est généralement comparable
• comme le dit gorgonite la complexité spaciale est éventuellement un peu supérieure (et dans le pire des cas l'évaluation paresseuse, vu qu'elle est orientée "déforestation", est moins bonne spacialement que l'évaluation stricte)

Je ne vois pas très bien de quoi tu parles sur l'évaluation paresseuse ? En plus l'évaluation paresseuse n'est pas directement lié à la déforestation, c'est plutôt la pureté du langage qui est en jeu. En tout cas la déforestation réduit toujours l'espace mémoire utilisé par rapport au même code non déforesté.

On pourrait faire, bien que ce ne soit jamais implanté dans les langages réels, des tableaux non modifiables dont les éléments sont accessibles en temps constant.

Haskell le fait (et c'est un langage "réel", de plus en plus). Il faut cependant noter que les tableaux en Haskell sont par défaut paresseux, ce qui permet souvent d'écrire de façon intuitive des tableaux qu'on construirait de façon itérative en impératif ou dans un langage strict (par exemple il est tout à fait possible d'utiliser une valeur d'un tableau lors de l'initialisation d'une case de ce tableau). Ces tableaux immutables ne peuvent être modifiés, mais on peut créer une copie où l'on a modifié certains éléments (évidemment le coût est linéaire).
Cependant, Haskell propose également une variante de ces tableaux qui permet la "modification" en temps constant, pourvu qu'on utilise ce tableau de façon linéaire (autrement dit, on ne modifie jamais une "vieille" version du tableau). La sémantique de ces tableaux (DiffArray) est donc fonctionnelle bien que l'implémentation sous-jacente soit impérative (mais cela est complètement invisible du point de vue de l'utilisateur).

Haskell propose aussi des tableaux classiques (modifiables) dans ses monades ST et IO, ainsi que des moyens de passer de façon sûre de ces tableaux modifiables à des tableaux immutables.

En gros, il est tout à fait envisageable d'utiliser des tableaux fonctionnels en Haskell et j'utilise souvent cette possibilité pour faire de la mémoisation.

Dans le futur, les manipulations de tableaux pourront être déforesté comme le sont les manipulations de listes actuellement, en fait ces capacités sont déjà offertes par certaines librairies sur Hackage.

--
Jedaï

[gasche]

Je ne vois pas très bien de quoi tu parles sur l'évaluation paresseuse ?

Effectivement, je ne vois pas non plus le rapport entre déforestation et augmentation de la complexité spatiale. Il me semble par ailleurs que la déforestation repose sur la pureté du langage (ou des fonctions optimisées), et pas sur l'évaluation paresseuse (elle serait valide aussi dans un langage strict, non ?).

Il arrive fréquemment qu'un programme soit plus couteux en mémoire du fait de l'évaluation paresseuse (tout simplement parce que les thunks ont forcément un surcoût par rapport à une simple valeur), mais aussi que leur complexité mémoire soit supérieure.

Par exemple (pardonnez le Haskell hésitant) :

Code :

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

1
2
3
length li = length' 0 li
  where length' acc [] = acc
        length' acc (_:xs) = length' (1+acc) xs

Cette formulation tail-récursive du calcul de la taille d'une liste a, si je ne me trompe, une complexité spatiale linéaire (je ne prends pas en compte la taille de la liste, que je considère comme "déjà allouée"; si ça pose problème on peut créer un exemple travaillant sur des structures à taille mémoire sublinéaire, comme un calcul de factorielle par exemple).

Évidemment, ce n'est pas la manière idiomatique de faire en Haskell (et pour cause !) et donc personne ne programme length comme cela. Cependant, il existe toujours des cas où ce genre de formulation est la plus naturelle pour le programmeur, et où donc le problème se pose.

Ceci dit, un compilateur intelligent pourrait, pour cette fonction particulière, corriger cela en effectuvant une "strictness analysis" au préalable. Mais reposer sur ce genre d'optimisations est à mon avis trop dangereux : c'est quelque chose de profondément difficile et le compilateur ne le fera jamais parfaitement, on risque donc toujours de rencontrer des cas où "il devrait l'optimiser mais ne le fait pas", et où on se retrouve dans la mouise.

Donc oui, l'évaluation paresseuse peut augmenter la complexité mémoire.

On pourrait faire, bien que ce ne soit jamais implanté dans les langages réels, des tableaux non modifiables dont les éléments sont accessibles en temps constant.

SML le fait aussi ("vect" iirc). Il est trivial d'en produire une implémentation en OCaml, en apposant une interface plus restrictive au module des tableaux modifiables.

[InOCamlWeTrust]

Pour répondre à SpiceGuid et nonpoluant.

Algorithmes de tri :
Si quelqu'un arrive à trouver (c'est-à-dire coder) une fonction de tri plus rapide que le quicksort de la GLibC... et bien il est réellement très très fort ! Donc, quand on vient me parler de différence mergesort/quicksort/flashsort/insertionsort/cacasort/(... mettre ici ce que l'on veut...)/... ça ne vaut que pour les langages fonctionnels, car pour les langages bas niveau et impératifs, la question a été règlée il y a déjà très longtemps.

Modification d'un élément de tableau :
@nonpoluant : pourquoi veux-tu des tableaux fonctionnels (donc non modifiables) dont on pourrait en modifier les éléments ?

@SpiceGuid : on t'avait déjà répondu à propos de la modification d'un élément de tableau : c'est une opération qui est toujours en temps constant. Si tu préfères, ça se traduit, en x86, par l'instruction mov qui prend, si il y a accès à la RAM, exactement 3 cycles d'horloge, et 1 seul cycle si c'est entre registres. Si ton indice dépasse la capacité maximale, l'opération ne peut être supportée par la machine (elle ne pourra jamais la réaliser) car l'adresse mémoire ne sera tout simplement jamais adressable.

Ceci dit, 2^32 ça fait 4Go de RAM, donc ça laisse de la marge, sans compter que certains processeurs Intel (ceux avec la technologie EMT64) portent la mémoire adressable pour l'OS à 64 Go mais seulement 4Go pour un processus, que les nouveaux CPU sont tous 64bits etpossèdent un vrai bus d'adresse de 64bits... donc 16.10^18 octets, soit 16 000 000 000 Go ce qui représente, plus ou moins, toutes les RAM sur Terre mises les unes à la suite des autres.

[Jedai]

Il arrive fréquemment qu'un programme soit plus couteux en mémoire du fait de l'évaluation paresseuse (tout simplement parce que les thunks ont forcément un surcoût par rapport à une simple valeur), mais aussi que leur complexité mémoire soit supérieure.

Il arrive aussi très fréquemment que leur complexité mémoire soit inférieure (cf le post sur powerset dans le forum Haskell).

Par exemple (pardonnez le Haskell hésitant) :

Code :

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

1
2
3
length li = length' 0 li
  where length' acc [] = acc
        length' acc (_:xs) = length' (1+acc) xs

Cette formulation tail-récursive du calcul de la taille d'une liste a, si je ne me trompe, une complexité spatiale linéaire.

Tu veux dire que si l'accumulateur n'est pas strict, cette fonction produira un thunk de taille linéaire. Néanmoins comme je l'ai dit plus haut il y a également des cas où un programme paresseux aura une complexité spatiale constante alors que le programme strict équivalent aura une complexité linéaire. De temps en temps il faut introduire du strict dans le paresseux et de temps en temps il faut réécrire une solution simple en paresseux en une solution complexe en strict pour obtenir la même complexité spatiale...

Évidemment, ce n'est pas la manière idiomatique de faire en Haskell (et pour cause !) et donc personne ne programme length comme cela. Cependant, il existe toujours des cas où ce genre de formulation est la plus naturelle pour le programmeur, et où donc le problème se pose.

Code issue du Prelude GHC :

Code Haskell :

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

1
2
3
4
5
6
7
8
9
-- | 'length' returns the length of a finite list as an 'Int'.
-- It is an instance of the more general 'Data.List.genericLength',
-- the result type of which may be any kind of number.
length                  :: [a] -> Int
length l                =  len l 0#
  where
    len :: [a] -> Int# -> Int
    len []     a# = I# a#
    len (_:xs) a# = len xs (a# +# 1#)

Les # indiquent qu'on utilise des Int#, c'est à dire des entiers stricts mais surtout unboxés (pas de pointeurs autour), en fait aujourd'hui GHC optimiserait ton code automatiquement (avec -O1 en tout cas) mais ce code fonctionnerait pareillement même avec les très vieilles versions de GHC. Ton écriture de length est relativement idiomatique, pas du tout atypique, tu confonds probablement avec d'autres problèmes où en Haskell on n'utilise pas les tail-recursion qu'on utiliserait dans un langage strict parce que de toute façon, on n'a pas besoin de le faire, et en fait ce serait une erreur car même un résultat partiel est déjà exploitable. Int est strict par essence, les résultats partiels d'une fonction comme "length [] = 0; length (_ : xs) = 1 + length xs" ne sont pas exploitables.

Ceci dit, un compilateur intelligent pourrait, pour cette fonction particulière, corriger cela en effectuvant une "strictness analysis" au préalable. Mais reposer sur ce genre d'optimisations est à mon avis trop dangereux : c'est quelque chose de profondément difficile et le compilateur ne le fera jamais parfaitement, on risque donc toujours de rencontrer des cas où "il devrait l'optimiser mais ne le fait pas", et où on se retrouve dans la mouise.

C'est exact, néanmoins à suivre cette logique jusqu'au bout, on devrait probablement s'en tenir à l'assembleur... Même les compilateurs C effectue des optimisations qui peuvent avoir un effet critique sur la complexité d'un programme.

De plus, GHC aujourd'hui est vraiment pas mauvais à ce genre de truc et il est toujours possible de vérifier s'il a bien exécuté une optimisation ou de rajouter des annotations pour l'y obliger.

Donc oui, l'évaluation paresseuse peut augmenter la complexité mémoire.

L'évaluation stricte également.

--
Jedaï

[alex_pi]

La paresse permet aussi de faire des structures de données fonctionnelles et persistantes avec d'excellentes complexités amorties qu'on ne pourrait pas atteindre avec une évaluation strict (à moins de simuler la paresse par création adhoc de suspensions).

[nonpoluant]

@nonpoluant : pourquoi veux-tu des tableaux fonctionnels (donc non modifiables) dont on pourrait en modifier les éléments ?

D'abord par curiosité intelectuelle.
Et pour pouvoir modifier une structure en temps constant afin d'utiliser les algorithmes efficaces qui utilisent cette propriété. (Si tu me demande pour quel algo exactement, j'ai pas d'exemple en tete, je pose vraiment la question que pour bien cerner l'utiliter d'un langage fonctionel. Je connais déjà ses qualité principales, et j'aimerais savoir si ça permetait d'appliquer des algorithmes grossierements aussi efficaces qu'en imperatif.)

[alex_pi]

Et pour pouvoir modifier une structure en temps constant afin d'utiliser les algorithmes efficaces qui utilisent cette propriété. [...] et j'aimerais savoir si ça permetait d'appliquer des algorithmes grossierements aussi efficaces qu'en imperatif.)

Généralement, tu vas surtout employer une structure différentes et des algorithme différent, qui seront sans doute un poil moins efficaces, mais auront d'autres avantages (la persistance en est un gros). Il ne faut pas essayer de traduire ce que tu ferais en impératif vers le fonctionnel. Tu as très peu de chance d'obtenir des résultats valables avec une telle approche.

[gasche]

Il arrive aussi très fréquemment que leur complexité mémoire soit inférieure (cf le post sur powerset dans le forum Haskell).

Le problème c'est qu'il faut 3 PhD pour s'en rendre compte, et un bloggueur acharné pour expliquer ça à tous les gens qui lisent le programme.

Plus sérieusement, c'est vraiment très difficile à mesurer actuellement. Des analyses de petits programmes par des gens bien entraînés ont pu montrer des choses très intéressantes (la lecture de ton exemple d'interleave m'avait beaucoup amusé à l'époque, c'est bien pour ce genre de chose qu'on prend la peine d'apprendre le Haskell à mon avis), mais il faut bien reconnaître que c'est très difficilement prévisible, et qu'on n'a en gros aucune idée de comment ça "scale" sur des programmes plus complexes.

Ton point de vue est tout à fait justifié : la paresse n'a pas que des désavantages côté mémoire (même si les avantages les plus évidents et surtout les plus intuitifs sont sur la complexité temporelle à formulation équivalente). Ceci dit, la forte complexité des cas où la paresse est intéressante, combinée avec la grande difficulté à repérer les cas où elle pose problème fait que l'analyse de programme stricts est beaucoup plus facile.
C'est pas par hasard que c'est à l'intérieur de la communauté Haskell qu'on a vu des aberrations comme le "faux crible d'eratosthène", et ensuite quelques épisodes assez cocasses comme la "crise d'identité du quicksort" ou autres problèmes liés à la difficulté qu'a le commun des mortels à prévoir l'efficacité d'un programme paresseux.

Je pense donc qu'avoir de l'évaluation stricte par défaut, en rajoutant explicitement de la paresse là où c'est nécessaire, est fortement préférable à de la paresse par défaut avec des annotations explicites pour le strict. D'ailleurs il me semble que c'est aussi la conclusion à laquelle de nombreux Haskelliens sont arrivés.

C'est exact, néanmoins à suivre cette logique jusqu'au bout, on devrait probablement s'en tenir à l'assembleur... Même les compilateurs C effectue des optimisations qui peuvent avoir un effet critique sur la complexité d'un programme.

Non, je ne pense pas. La question est "quelle est la quantité d'optimisations du compilateur dont peut dépendre le programmeur, et à quel point peut-il s'y fier ?". En OCaml par exemple, il est communément admis que l'on doit s'occuper de la tail-récursion. C'est une optimisation assez simple, et surtout extrêmement fiable : il y a un cas légèrement tangent qui est celui du "try .. with" autour de l'appel récursif, mais à part celui là (qui est du à une méconception du côté du programmeur et pas à une imperfection du compilateur) on n'est jamais surpris.

En Haskell au contraire, du fait du choix des features du langage (évaluation paresseuse et type classes), il est nécessaire de faire de nombreuses optimisations pour avoir des performances raisonnables, et du fait des features du langage (pureté), il est aussi plus simple de faire certaines optimisations sophistiquées. Du coup, les compilateurs Haskell essaient d'être très intelligents, ce qui est pratique mais peut poser des problèmes.
En effet, si certaines optimisations sont comparables à la tail-récursion en OCaml (simples à comprendre, que l'on peut demander du programmeur, et fiables dans leur application), la plupart des optimisations sont complexes, et assez peu fiables : un petit programme de test sera optimisé, mais un autre programme légèrement différent ou plus complexe ne le sera pas.

C'est un problème parce que cela demande au programmeur d'être plus dépendant du travail du compilateur. C'est aussi délicat dans un contexte "multi-implémentations", car cela peut créer l'equivalent de problèmes de portabilité. Ironiquement, Haskell a longtemps conservé de multiples implémentations (comme caml dans sa jeunesse, ce qui n'est plus le cas aujourd'hui), mais je pense que c'est en passe de devenir un détail historique devant le quasi-monopole de GHC (à part les devs de Yhc, et quelques profs habitués à Hugs, peut-être).

[Garulfo]

Le problème c'est qu'il faut 3 PhD pour s'en rendre compte, et un bloggueur acharné pour expliquer ça à tous les gens qui lisent le programme.

Plus sérieusement, c'est vraiment très difficile à mesurer actuellement. Des analyses de petits programmes par des gens bien entraînés ont pu montrer des choses très intéressantes (la lecture de ton exemple d'interleave m'avait beaucoup amusé à l'époque, c'est bien pour ce genre de chose qu'on prend la peine d'apprendre le Haskell à mon avis), mais il faut bien reconnaître que c'est très difficilement prévisible, et qu'on n'a en gros aucune idée de comment ça "scale" sur des programmes plus complexes.[...]

J'ai lu la discussion de ces derniers jours.
Grosso modo, je suis plutôt d'accord avec Jedai.

Certes il faut être très bon pour comprendre en profondeur les mécanismes permettant les optimisations ultimes d'Haskell. Mais c'est pareil pour n'importe quel langage. Il faut au moins un doctorat ou des années d'expérience pour écrire la grammaire complète du C++ — et ce n'est pas une métaphore — alors pour être capable de comprendre les entrailles de la bête, ça n'est pas une affaire de routine. En fait, c'est vrai quelque soit le langage. C'est d'ailleurs un des problème interne à l'informatique. Dans l'idéal, on ne devrait guère s'intéresser à ça. Mais ce n'est pas le cas.

Reste qu'en général, ce genre de petite optimisation est une affaire de seconde main. Ce n'est pas que ce n'est pas important, mais c'est que ce n'est pas la source des problèmes. Un projet n'échoue pas parce qu'on a écrit un powerset de manière non optimisé n'est-ce pas ?

En tout cas, ceci m'amène à dire que, si ces discussions sont intéressantes, elles n'ont d'intérêt que localement dans un langage. Ce n'est nullement un argument pour comparer un langage à un autre.

[gasche]

Reste qu'en général, ce genre de petite optimisation est une affaire de seconde main. Ce n'est pas que ce n'est pas important, mais c'est que ce n'est pas la source des problèmes. Un projet n'échoue pas parce qu'on a écrit un powerset de manière non optimisé n'est-ce pas ?

GHC Team leaving Darcs, switching to Git
Reason for elimination : persistent performance and algorithmic problems, see above.

En tout cas, ceci m'amène à dire que, si ces discussions sont intéressantes, elles n'ont d'intérêt que localement dans un langage. Ce n'est nullement un argument pour comparer un langage à un autre.

Je prétends au contraire que ce genre de problèmes persistent quand on passe à grande échelle, et qu'ils sont encore accentués par le fait que la complexité de l'analyse des programmes paresseux augmente beaucoup avec la taille et la complexité de ces derniers, contrairement à celle des langages stricts.

Je dirais même au contraire que Haskell se débrouille en général très bien sur les micro-benchmarks (problèmes locaux) et que c'est au moment du passage à l'échelle que cela pose problème. D'ailleurs, mes soupçons ne sont pas infirmés empiriquement par le seul "gros logiciel" Haskell que je connaisse : GHC, qui est objectivement a pain in the ass à compiler (esssayez, vous verrez).

Il faut au moins un doctorat ou des années d'expérience pour écrire la grammaire complète du C++ — et ce n'est pas une métaphore — alors pour être capable de comprendre les entrailles de la bête, ça n'est pas une affaire de routine.

Attention à ne pas se tromper sur la nature de l'argumentation. Je ne prétends même pas que l'évaluation paresseuse est intrisèquement une fonctionnalité compliquée. Le call by need est une stratégie d'évaluation simple et au moins aussi élégante que l'évaluation stricte, et même si le traitement actuel de la paresse (mémoization, etc.) ajoute indéniablement de la complexité, cela reste quelque chose d'harmonieux et agréable à étudier.
Le problème c'est que son utilisation par défaut dans des programmes a tendance à rendre ces derniers difficiles à analyser. On ne parle pas là d'un concept à la complexité non maîtrisée, mais d'un objet simple qui pose des problèmes de passage à l'échelle.
On pourrait vaguement faire un analogue (mais des précautions sont de mise) avec l'idée du changement d'état : c'est un concept simple à comprendre mais qui, utilisé à grande échelle et sans protection, donne des résultats imprévisibles, voire même chaotiques.


Je ne cherche pas à envoyer au bûcher tous les langages paresseux par défaut, et je ne défends certainement pas que "l'évaluation paresseuse, c'est mal". Mais je suis de plus en plus convaincu que, du point de vue d'un créateur de langage, la stratégie "paresse par défaut" n'est pas la bonne (et on peut voir en Miranda puis Haskell une confirmation pratique de cela, c'est d'ailleurs l'expérience que semble en avoir retiré Simon Peyton-Jones), et que faute de mieux (Il existe peut-être, et je l'espère, des stratégies intermédiaires délicieuses à découvrir) une stratégie stricte par défaut avec une paresse explicite est le choix le plus raisonnable, si l'on est prêt à compenser ensuite par un support du langage suffisant, que ce soit au niveau de la syntaxe, des bibliothèques ou de l'implémentation.


Si ça peut permettre de calmer le débat, je me dois de faire remarquer que les partisans des délires théoriques d'ordre supérieur (eg. Coq) m'ont déjà fait remarquer que l'avenir était à la Total Functional Programming, c'est à dire des langages dans lesquels les programment ne divergent jamais, et dans lesquels le choix de stratégie d'évaluation n'avait donc plus grande importance : le troll lazy/strict, ce serait un truc de débutants.

[Garulfo]

À mon avis la « difficulté » lié à la paresse est uniquement dû au fait qu'on commence par voir autre chose. Si on procédait tous par ne travailler que par une évaluation en ordre normal et non en ordre applicatif, il nous semblerait probablement que l'autre est plus tordu.

Je serais curieux de voir si ce raisonnement tiendrait pour qqun qui a appris à programmer avec de l'Haskell (par exemple).

[InOCamlWeTrust]

A mon avis, la paresse est plus difficile à aborder car elle ne correspond pas à un problème de cheminement des calculs, mais à une idée un peu plus haut niveau, de résultat des calculs. L'idée qu'une chose se fait après une autre dans un ordinateur est très naturelle et coïncide avec le mode de pensée naïve, premier degré.

Pour GHC, a pain in the ass, c'est sûr, comme le dit bluestorm, c'est horriblement lent, et plus le temps passe, et plus je me dis que les langages comme Haskell ainsi que les meilleures optimisations des compilateurs comme GCC sont faits pour les idéalistes.

Je m'explique.

La paresse, c'est très bien, mais en général, un bon programmeur ne fait jamais calculer une chose par la machine si cette chose n'est jamais utilisée. Dans ce contexte-là, écrire dans un langage paresseux n'apporte strictement rien. De même pour les dead-code elemination et les super algorithmes de propagation de constante de GCC qui alourdissent énormément le compilateur.

Par contre, la paresse peut être intéressante si on s'autorise des algorithmes inutilisables dans un langage strict, mais, à ma connaissance, rares sont les cas où le changement pourrait s'avérer intéressant.

[Garulfo]

[...]
La paresse, c'est très bien, mais en général, un bon programmeur ne fait jamais calculer une chose par la machine si cette chose n'est jamais utilisée. Dans ce contexte-là, écrire dans un langage paresseux n'apporte strictement rien. De même pour les dead-code elemination et les super algorithmes de propagation de constante de GCC qui alourdissent énormément le compilateur.[...]

Ce n'est pas « en général » que tu dois dire, mais « dans le meilleur des mondes », c'est-à-dire « rarement ». De plus, l'idéal serait que le développeur lorsqu'il s'intéresse à des applications haut-niveaux, comme le sont la très grande majorité des applications dans le monde, n'ai pas à réfléchir à ce jour d'optimisation. Parallèlement, il serait bien que les compilateurs soient mieux optimisés (plus intelligent ?) pour corriger encore plus d'erreurs des développeurs. Car, les erreurs sont inévitables. Les systèmes sont trop complexes pour qu'un humain réussisse à tout appréhender d'un seul coup. Alors, il est certain qu'il serait génial que le concepteur donne un algo et que le programmeur l'optimise pour le langage sans que cela n'ait d'influence sur les autres parties du programme fait par l'équipe de conception. Mais en pratique, ça ne marche pas ainsi. C'est le concepteur qui réfléchit et doit optimiser pour que le développeur ne se concentre que sur sa partie. Pour cela, le concepteur doit évoluer à un niveau plus abstrait que ce que ne lui offre le langage. Sinon, on voit apparaître les défauts qui font échouer les projets : pas ceux de programmation ni d'optimisation mais ceux qui touchent aux besoins.

Finalement, quand tu dis

L'idée qu'une chose se fait après une autre dans un ordinateur est très naturelle et coïncide avec le mode de pensée naïve, premier degré.

c'est naturel uniquement parce que c'est ce qui est enseigné. Si on enseignait que les expressions ne sont évalués qu'au besoin, ça serait naturel. D'ailleurs les premiers algo d'évaluation, historiquement, était en ordre normal donc plus dans l'esprit d'une forme paresseuse. Si c'était les premiers auxquels on a pensé, cela montre bien que la notion de « naturel » n'est pas si évident que ça. Rien que le terme « normal » sous-entend bien qu'il semblait évident.

[gasche]

La paresse, c'est très bien, mais en général, un bon programmeur ne fait jamais calculer une chose par la machine si cette chose n'est jamais utilisée.

Je ne suis pas convaincu. D'une part, c'est avant tout une question de style : évidemment dans un langage strict le bon programmeur évitera les calculs inutiles. Mais dans un langage paresseux ? Ce que tu supposes être le "bon style", c'est le "bon style strict", donc forcément dans ce cadre ton argument est gagné d'avance.

Dans un bon style paresseux il arrive qu'on déclare des choses sans les utiliser. Par exemple, l'utilisation des listes infinies permet parfois d'exprimer un algorithme particulier de manière très élégante, mais surtout claire et compréhensible, et il n'y a pas raison de s'en priver (d'ailleurs de nombreux langages stricts de nos jours ont une librairie de "flots" pour ce cas particulier, et les langages ML permettent de définir très facilement des types (algébriques) partiellement paresseux.

De plus, il existe des cas où l'évaluation paresseuse apporte des avantages "structurels", comme par exemple la complexité (amortie ou dans le pire des cas) de manipulation des structures de données persistentes.

À mon avis la « difficulté » lié à la paresse est uniquement dû au fait qu'on commence par voir autre chose. Si on procédait tous par ne travailler que par une évaluation en ordre normal et non en ordre applicatif, il nous semblerait probablement que l'autre est plus tordu.

Je pense que cet argument ne tient pas. Je le connais bien parce que je l'utilise très régulièrement quand des gens m'expliquent que la programmation fonctionnelle, ce n'est "pas naturel". Il y a beaucoup de gens qui ont des difficultés à passer le cap et apprendre un langage fonctionnel depuis leurs connaissances des langages impératives, mais il y a aussi beaucoup de gens qui s'en sortent très bien, et le nombre de très bons programmeurs fonctionnels est énorme.

Dans le cas de la paresse au contraire, je n'ai jamais entendu parler de quelqu'un qui soit capable d'évaluer "naturellement" les performances d'un programme Haskell un peu gros. L'analyse des programmes paresseux est un talent qui s'entraîne, si on n'a jamais essayé on peut faire des erreurs monumentales (cf. l'histoire du faux crible), et avec de la pratique on peut avoir une idée assez nette pour des petits programmes (en particulier tout ce qu'on appelle "les algorithmes" sont des choses très intéressantes et qui font dans leur forme la plus pure rarement plus de 20/30 lignes, donc largement à portée du bon paresseux, quand les difficultés mathématiques liées à l'analyse (qui peuvent survenir que l'on soit lazy ou strict) ne se mettent pas en travers de la route).

Il existe des gens formidables et je n'exclus pas que quelqu'un développe une capacité à analyser rapidement et complètement des programmes paresseux particulièrement complexes. Mais j'ai l'impression que cela reste de l'ordre de l'exploit intellectuel, et pas de "ce qui est naturel". Si c'était une question de "naturel", on peut supposer que de nombreux programmeurs dans un langage paresseux, ne serait-ce que les plus talentueux, auraient internalisé le modèle et n'auraient plus de problème à analyser de manière fiable (je ne parle pas forcément de la complexité la plus précise, que pour certains programmes on ne connaît pas, mais au moins de s'assurer qu'il n'y a pas de memory leak) les programmes qu'on leur présente.


Bref, je pense qu'on ne peut pas vraiment dire que l'analyse des programmes paresseux est "naturelle". Ça ne veut pas pour autant dire qu'elle est impossible ! Il existe des outils pour faciliter la tâche du programmeur dans ce domaine, qui ont encore des progrès à faire et seront peut-être un jour suffisamment utilisables pour régler ces problèmes (mais je ne suis pas sûr qu'ils arrivent à passer à l'échelle). Je pense donc que les paresseux devraient essayer (et c'est ce qu'il font) de chercher à comprendre/contourner/réduire la difficulté, plutôt que d'atteindre que *flash*, ça devienne naturel (ou de faire incuber des nouveaux-nés spécialement pour leur faire apprendre le Haskell d'abord, afin de les transformer en lazy surhommes).

[Garulfo]

[...]
Dans le cas de la paresse au contraire, je n'ai jamais entendu parler de quelqu'un qui soit capable d'évaluer "naturellement" les performances d'un programme Haskell un peu gros. [...]

Mais connais-tu beaucoup de gens qui commencent à apprendre par des versions paresseuses ? Personnellement je ne connais personne.

[gasche]

Oui enfin il n'y a pas besoin de "commencer par apprendre" pour s'habituer à quelque chose de naturel. Il y a beaucoup d'exemples de gens ayant su changer de culture, y compris en programmation (à ma connaissance il y a beaucoup plus de gens trouvant les langages fonctionnels naturels que de gens trouvant les langages fonctionnels naturels et qui ont commencé par un langage fonctionnel). Dans les quelques centaines d'utilisateurs Haskell on peut supposer que quelques uns auraient été capable de s'adapter.

Mais ça devient un peu hypothétique pour être un débat sérieux.

Par contre, il fallait que je le dise : putain il tue l'url-rewriting. Ça doit être nouveau parce que je viens de m'en rendre compte.