Discussion :

[Jedai]

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

Oui et ? GHC est un projet énorme, qui effectivement atteint les frontières de ce qu'il est possible de gérer avec darcs... Mais les problèmes fondamentaux de darcs sont de nature algorithmique ! Paresseux ou strict, un langage ne transforme pas magiquement un algorithme à complexité exponentielle en algorithme rapide...

Par ailleurs Darcs lui même est assez gros et a été l'un des pionniers des DVCS, il a ouvert une bonne partie de la route au concept, maintenant repris par des outils populaires comme git. Il continue à être utilisé pour pas mal de projets.
Il me semble que contrairement à ce que tu dis, Darcs est plutôt une preuve de l'efficacité d'Haskell pour des projets de taille réelle (surtout si l'on considère que par rapport à d'autres projets similaires, il n'a jamais attiré une foule de développeurs pour ses entrailles).

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).

Là, je ne vois pas l'argument... GHC est lent à compiler, oui, difficile ? Pas tellement ! (tant que vous n'essayez pas de compiler le HEAD actuel : Changement de VCS, de système de build, de système d'exceptions... ça fait beaucoup en même temps)
Et une fois compilé, GHC lui-même est un compilateur pas si lent si l'on considère la quantité d'optimisations qu'il doit effectuer pour obtenir les excellentes performances qu'il obtient (il y a bien pire, GHC est parfaitement utilisable, même pour développer un gros projet, la compilation séparée marche très bien).
Il faut voir aussi que GHC est un très gros projet, avec des centaines de milliers de lignes de codes.

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.

Les supporters informés de l'évaluation paresseuse n'ont jamais prétendu qu'elle permettait d'écrire des programmes plus rapides parce qu'elle évitait les calculs inutiles... Comme tu le dis, dans un style strict, le programmeur évite généralement de faire des choses inutiles. Mais pour cela, il doit souvent introduire de la complexité dans son algorithme, voire en changer complètement parce qu'il n'arrive pas à ne calculer que le nécessaire... En bref, le vrai argument en faveur de l'évaluation paresseuse c'est qu'en général elle permet d'exprimer plus simplement les algorithmes (et c'est un avantage parce que ça réduit le nombre d'erreurs potentielles) et permet plus de modularité, de flexibilité en fournissant des interfaces uniques qui peuvent servir à de multiples usages, là où un langage strict aurait obligé pour des raisons de performances à fournir plusieurs interfaces différentes dépendant plus directement du code l'utilisant.

--
Jedaï

[InOCamlWeTrust]

Non. Le fait d'être strict ou paresseux n'a rien à voir avec les interfaces, commes tu sembles le dire. Ce sont deux choses différentes. Si tu fais allusion aux classes Haskell, rien n'interdirait de les incorporer au système de type de OCaml, par exemple ; c'est une chose qui n'a rien à voir avec le mode d'évaluation, strict ou paresseux. Ou alors, si tu parles des monades, je doute fort qu'elles soient un exemple de modularité, contrairement à ce que l'on peut voir dans beaucoup de "papiers".

[alex_pi]

Non. Le fait d'être strict ou paresseux n'a rien à voir avec les interfaces, commes tu sembles le dire.

Si, parce qu'un valeur paresseuse va "s'adapter" à l'utilisation qui en est faite, en ne calculant que ce dont l'utilisateur a besoin.

[SpiceGuid]

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.

La paresse c'est aussi de ne produire qu'au bon moment (le moment où on consomme), ça n'est pas seulement faire moins d'effort c'est aussi mieux répartir cet effort pour ne pas sursoliciter les ressources.
Avec le GC tu libères au plus tôt.
Avec la paresse tu alloues au plus tard.
Dans le principe je ne vois pas en quoi c'est une mauvaise idée, l'intention est bonne.

En bref, le vrai argument en faveur de l'évaluation paresseuse c'est qu'en général elle permet d'exprimer plus simplement les algorithmes (et c'est un avantage parce que ça réduit le nombre d'erreurs potentielles) et permet plus de modularité, de flexibilité en fournissant des interfaces uniques qui peuvent servir à de multiples usages, là où un langage strict aurait obligé pour des raisons de performances à fournir plusieurs interfaces différentes dépendant plus directement du code l'utilisant.

Tout à fait, c'est l'argument du Why Functional Programming matters.
La paresse est la solution du paradigme fonctionnel aux problèmes qui, en Caml, attendent habituellement une solution impérative.
C'est la solution inventée par les purs pour les purs, celle qui exige des doigts de fée pour placer des petits lutins malins là où il faut pour faire ce qu'il faut au moment où il faut (tout en restant fonctionnel).

[LLB]

Dans un certain nombre de cas, on peut implémenter un objet à comportement paresseux dans un langage strict. Par exemple, le type Seq de F# peut décrire une liste infinie (avec les opérations de map, filter... paresseuses) ; ça peut aussi servir à lire un fichier à la demande.

C'est peut-être plus simple et plus courant en Haskell, mais ça me semble aussi puissant, au niveau des structures de données (quelqu'un a un contrexemple ?).

[Jedai]

Dans un certain nombre de cas, on peut implémenter un objet à comportement paresseux dans un langage strict. Par exemple, le type Seq de F# peut décrire une liste infinie (avec les opérations de map, filter... paresseuses) ; ça peut aussi servir à lire un fichier à la demande.

C'est peut-être plus simple et plus courant en Haskell, mais ça me semble aussi puissant, au niveau des structures de données (quelqu'un a un contrexemple ?).

Non, c'est tout à fait aussi puissant, c'est souvent nettement moins performant que l'équivalent en Haskell par contre, et c'est généralement moins pratique à manipuler. C'est tout de même mieux que de n'avoir aucun support pour l'évaluation paresseuse. A priori, rien n'interdit d'avoir un langage strict par défaut avec un bon support pour le paresseux, mais c'est juste rarement le cas.

--
Jedaï

[InOCamlWeTrust]

Si, parce qu'un valeur paresseuse va "s'adapter" à l'utilisation qui en est faite, en ne calculant que ce dont l'utilisateur a besoin.

Et en quoi c'est modulaire d'après toi ?

Je ne remets pas en cause le principe ni le bien-fondé, c'est juste que je trouve que, pour les programmes d'aujourd'hui et la façon de programmer des gens, c'est prendre un fusil pour tuer une mouche.

[alex_pi]

Et en quoi c'est modulaire d'après toi ?

Parce que ça permet de penser une fonction plus indépendament de son utilisation.

[gasche]

Je ne vois pas vraiment de quel avantage de modularité vous parlez. L'idée de l'interface que l'on peut utiliser pour des choses différentes parce que ce n'est pas grave si certaines parties ne servent pas, pourquoi pas, ce n'est pas idiot mais je ne connais pas d'exemple concret.

Le seul exemple "d'interface polyvalente" que je connaisse à ce sujet c'est le type liste en Haskell, qui est utilisé à la fois pour représenter des listes finies et des listes infinies. Ça n'est pas idiot mais je ne trouve pas cela génial non plus : cela permet effectivement une reprise du code entre les deux idées (contrairement à OCaml qui par exemple doit implémenter map deux fois, pour les listes finies et pour les listes infinies), mais en même temps cela peut aussi poser des problèmes (ne serait-ce que de clarté) parce que ce sont deux objets profondément différents. En pratique je vois beaucoup de gens utiliser un type spécifique pour les listes infinies (nommé Stream en général), et je trouve que c'est une méthode pertinente.
En clair, l'avantage du flou sur les listes ne me paraît pas si net, et sert à mon avis plutôt à masquer les problèmes qu'on les langages actuel en matière de méta-programmation (si on savait faire mieux dans ce domaine on pourrait programmer map, fold et compagnie une fois pour toutes sur tous les types récursifs covariants en leur paramètre, filter pour toutes les énumérations, etc., et l'argument de la réutilisation des fonctions ne tiendrait plus).

Oui et ? GHC est un projet énorme, qui effectivement atteint les frontières de ce qu'il est possible de gérer avec darcs... Mais les problèmes fondamentaux de darcs sont de nature algorithmique ! Paresseux ou strict, un langage ne transforme pas magiquement un algorithme à complexité exponentielle en algorithme rapide...

Tout à fait, et je n'ai jamais dit ça. Je répondais à Garulfo qui a dit « Un projet n'échoue pas parce qu'on a écrit un powerset de manière non optimisé n'est-ce pas ?» . Si darcs est en passe d'échouer maintenant (comprendre : de perdre sa presque-place parmis les DCVS utilisés par les vrais gens et d'être relégué au stade d'honorable ancêtre historique par git, hg et bzr), c'est bien principalement à cause d'algorithmes non optimisés et plus généralement de problème de performance.

Je suis profondément désolé du problème fondamental de nature algorithmique (les maths c'est injuste... darcs est un projet que j'apprécie et utilise quotidiennement), mais ce n'est pas, contrairement à ce que tu dis, le seul problème de darcs. La deuxième page que j'ai mise en lien (DarcsEvaluation) cite de nombreux problèmes de vitesse qui ne sont, me semble-t-il, pas tous liés à ce problème fondamental. Les développeurs de GHC se sont plaints de nombreux problème de performances et c'est vrai qu'il est notablement plus lent que git ou hg (qui est codé en Python, sans message subliminal) sur la plupart des opérations.

Alors oui, je pense que ce sont les problèmes de performances qui ont plombé darcs en tant que projet, ainsi que des problèmes de communication (tu peux aller lire l'annonce de la 2.0, c'est édifiant), et que donc c'est un bon exemple à montrer à Garulfo de projet qui est en danger pour des problèmes à la fois d'algorithmique et de performances. Qui plus est relavitement pertinent parce que c'est codé dans un langage fonctionnel (à la base si j'ai choisi darcs plutôt que git, hg ou un autre, c'est bien parce qu'il est codé en Haskell).

Là, je ne vois pas l'argument... GHC est lent à compiler, oui, difficile ? Pas tellement ! (tant que vous n'essayez pas de compiler le HEAD actuel : Changement de VCS, de système de build, de système d'exceptions... ça fait beaucoup en même temps)

GHC est très lent à compiler (plusieurs heures sur un ordinateur bateau), et demande beaucoup de mémoire vive pendant le processus. De tous les compilateurs que j'aie compilés c'est de loin le plus pénible (bon, un compilateur fortran ne marchait pas et j'ai du fixer des trucs à la main, c'est pas cool mais c'est pas un problème du même ordre et c'était du code un peu âgé). J'ai été assez frustré, alors que je demandais à des gens d'installer darcs pour participer à un de mes projets, je voir des gentooistes me répondre qu'ils ne voulaient pas parce qu'ils n'avaient pas envie de devoir compiler GHC. L'argument vaut ce qu'il vaut (il y a des versions binaires disponibles, et il y a d'autres implémentations de Haskell, mais je ne suis pas sûr que darcs n'utilise pas de features GHC-spécifiques, il y en a tellement...) mais il montre bien à mon avis qu'il y a un problème.

[InOCamlWeTrust]

Parce que ça permet de penser une fonction plus indépendament de son utilisation.

[alex_pi]

En bref, le vrai argument en faveur de l'évaluation paresseuse c'est qu'en général elle permet d'exprimer plus simplement les algorithmes (et c'est un avantage parce que ça réduit le nombre d'erreurs potentielles) et permet plus de modularité, de flexibilité en fournissant des interfaces uniques qui peuvent servir à de multiples usages

Parce que ça permet de penser une fonction plus indépendament de son utilisation.

Si une fonction s'adapte "automatiquement" à l'utilisation qui en est faite, elle est utilisable dans plus de situation, donc il est plus facile d'écrire des modules réutilisables (c'est bien le but de la modularité non ?). Qu'est ce qui te parrait si "" ?

[gasche]

Ben, tu as un exemple ? Parce que c'est vrai que comme ça, c'est pas évident.

[LLB]

Il n'y a pas longtemps, j'avais écrit ce code en F#. Voici une fonction qui renvoie l'ensemble des diviseurs (entre 2 et la racine carrée) :

Code :

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

1
2
3
let div x =
  let n = float x |> sqrt |> int
  { for i in 1 .. n when x % i = 0 -> i }

Cette fonction effectue les calculs de façon paresseuse. Si l'on souhaite savoir si un nombre est premier, on peut réutiliser cette fonction :

Code :

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

let prime = not << Seq.nonempty << div

Puisque tout est fait à la demande : la fonction prime arrête de chercher des diviseurs dès qu'elle en trouve un. Dans un monde entièrement strict, il ne serait pas concevable de générer entièrement la liste des diviseurs, si on veut juste savoir s'il y en a un. Il vaudrait mieux avoir deux fonctions, seulement pour des raisons de performances.

Cet exemple est un cas jouet, mais je suis sûr qu'on peut en trouver dans la vraie vie. Par exemple, lire un fichier à la demande et manipuler ses lignes comme une liste classique est assez sympa (il n'y a pas de manipulation de fichier à faire dans l'algo principal).

[gasche]

Ok, c'est un bon exemple. Tu construis une structure paresseuse et tu peux te contenter, pour certains usages, d'une évaluation seulement partielle.

Ceci dit, dans ce cas, on peut reproduire cette méthode dans un langage strict (et sans utiliser les fonctionnalités du langage), en encapsulant les données du problème, non mais dans la structure formée par le filtrage des éléments intéressants, mais dans le prédicat de choix des éléments intéressants.

Code :

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

1
2
3
4
let is_mult n i = n mod i = 0

let divs n = List.find_all (is_mult n) [1..n]
let is_prime n = not (List.exists (is_mult n) [1..n])

Cette méthode est clairement aussi bonne d'un point de vue de modularité, elle représente juste différemment la "connaissance du problème".

Elle repose sur deux fonctions (List.find_all et List.exists) qui encapsulent la différence du choix, et on pourrait argumenter que la "laideur" due à la duplication a été déplacée dans le code de ces fonctions, mais je ne suis pas convaincu, et la version paresseuse utilise aussi une fonction auxiliaire (Seq.nonempty). On ne voit pas la deuxième (correspondant à mon find_all) parce que la représentation paresseuse de div/is_mult lui correspond exactement, mais je pense que c'est un artefact lié à la situation.

D'ailleurs, si l'on compare les deux représentations, la paresseuse a l'avantage de donner immédiatement la liste des diviseurs, mais elle ne permet pas de savoir rapidement si un nombre donné est diviseur (il faut utiliser l'appartenance à la liste). Je pense donc que même dans un contexte paresseux, l'approche par prédicat est en réalité plus flexible.

Si vous avez d'autres exemples, c'est intéressant.

Edit : j'ai oublié de prendre en compte la racine carrée. C'est un petit détail mais c'est intéressant parce que ça fait partie de la connaissance du problème, et qu'elle est plus facile à intégrer dans le modèle "liste paresseuse" quand dans le modèle prédicat.

Voici ce que j'ai de mieux pour l'instant :

Code :

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

1
2
3
4
let max_div n = truncate (sqrt (floor n))

let divs = List.find_all is_div [1 .. max_div n]
...

Qu'est-ce que ça veut dire ? La représentation paresseuse de ce problème permet d'intégrer plus facilement les deux données importantes (à côté, la solution stricte fait un peu ad hoc, mais en fait c'est la même chose). Ceci dit ce n'est pas forcément une propriété générale des approches paresseuses par rapport aux approches strictes (en tout cas rien ici ne nous permet de savoir si c'est lié au choix de l'exemple ou pas), et le fait que la représentation stricte ait aussi un avantage notable (la facilité du test d'un wannabe-diviseur arbitraire) me pousse à penser que c'est plutôt un cas particulier.

[nonpoluant]

• Dans un arbre binaire le chemin qui mène de la racine à un certain noeud est de la forme (left|right)*, alors qu'un entier en base 2 est de la forme (0|1)*. L'astuce consiste à considérer l'indice dans un tableau d'abord comme un entier en base 2 puis comme un chemin dans un arbre binaire, bit à 0 aller à gauche, bit à 1 aller à droite. Pour modifier un élément il suffit alors de dupliquer le chemin depuis la racine jusqu'à la feuille et de n'y changer que la valeur de la clé concernée.

Après réfléxion, je crois que tu te trompes. Cet entier que tu donnes comme constante, est un max. Vu comme ça, alors une liste est accessible en 2^32 (ou 2^64) etapes, et 2^32 (ou 2^64) est bien une constante, donc les éléments d'une liste sont accessibles en temps constant...
Non, je n'suis pas convaincu que ce soit exacte. En conséquence je crois plutot que la solution que tu donnes permet un acces seulement en temps logarithmique (ce qui est déjà bien tu m'diras, mais qui ne répond pas à la question.)

[alex_pi]

Après réfléxion, je crois que tu te trompes. Cet entier que tu donnes comme constante, est un max. Vu comme ça, alors une liste est accessible en 2^32 (ou 2^64) etapes, et 2^32 (ou 2^64) est bien une constante, donc les éléments d'une liste sont accessibles en temps constant...
Non, je n'suis pas convaincu que ce soit exacte. En conséquence je crois plutot que la solution que tu donnes permet un acces seulement en temps logarithmique (ce qui est déjà bien tu m'diras, mais qui ne répond pas à la question.)

De toutes évidences, c'est bien en "log n". Mais il est quand même bien plus raisonnable de dire qu'un algo en log n est en temps constant (32 est une constante raisonnable) que de dire la même chose pour un algo en temps linéaire...

[SpiceGuid]

En conséquence je crois plutot que la solution que tu donnes permet un acces seulement en temps logarithmique (ce qui est déjà bien tu m'diras, mais qui ne répond pas à la question.)

En effet, le temps d'accès est logarithmique sur la longueur de la clé.
Mais le tableau est creux, persistant, et sans borne supérieure.
En impératif le tableau est plein, non persistant, avec une borne supérieure.
Et je doute que tu puisses faire sauter une de ces trois limitations tout en préservant un temps d'accès constant.

Concernant ta question, on a qu'une équivalence théorique sur la calculabilité, il n'existe pas (à ma connaissance) de résultat théorique sur les performances relatives de l'approche impérative et de l'approche fonctionnelle pure.
D'une certaine façon le paradigme impératif dit le "comment", c'est une façon de privilégier la performance, tandis que le paradigme fonctionnel dirait le "quoi", c'est une façon de privilégier la qualité.

Empiriquement on constate que l'approche fonctionnelle pure n'est pas impraticable. Aucun langage n'est pleinement satisfaisant, comme presque partout il y a des compromis à faire entre qualité et performance.

Tout ce tapage actuel autour du paradigme fonctionnel me semble avant tout une affaire d'actualité: la force véritable d'un langage ML c'est son système de typage

[InOCamlWeTrust]

Yaisse

[avator]

Les languages fonctionnels servent a me donner des cauchemards

Autrement, je me souviens d'une application fait en concurrent Clean pour créer des petits jeux videos genre Mario, super intéressant. Ca ce trouve encore sur le web.

http://cleangl.sourceforge.net/

sinon voir sa page

http://www.wieringsoftware.nl/