Sortie du livre « Parallel and Concurrent Programming in Haskell »

Posté par neil le 25 juillet 2013 à 14:04. Édité par tuiu pol, NeoX et patrick_g. Modéré par tuiu pol. Licence CC By‑SA.

Étiquettes :

juil.

2013

Le livre Parallel and Concurrent Programming in Haskell de Simon Marlow est enfin disponible !

Pour ceux qui ne le connaîtraient pas encore, le langage Haskell est un langage de programmation fonctionnel, fortement typé, paresseux et concis. Haskell est issu de l’initiative d’une communauté de chercheurs en langages fonctionnels qui ont décidé, à la fin des années 80, de mettre en commun leurs compétences en utilisant tous un seul langage, qui devrait rester libre. Depuis, le langage est en constante évolution, la dernière version stable est définie dans le rapport Haskell 2010, mais de multiples extensions existent dans le compilateur GHC, dont les plus courantes viendront s’ajouter à la prochaine version du langage.

Pour avoir une idée de sa syntaxe très particulière, voilà l’une des innombrables façons de définir la factorielle :

fac 0 = 1
fac n = n * fac (n-1)

En espérant que cela vous laisse sur votre faim, vous pourrez en apprendre plus dans les livres classiques Learn You a Haskell for Great Good qui est aussi librement accessible en version HTML, y compris en français, et le plus vieux, mais plus développé et appliqué, Real World Haskell, lui aussi accessible en ligne.

L’auteur

Simon Marlow est l’un des développeurs de GHC, le compilateur de facto standard du langage, et l’éditeur du dernier rapport du langage (Haskell 2010). Il travaillait jusqu’il y a peu chez Microsoft Research à Cambridge, notamment avec Simon Peyton Jones, l’un des pères de Haskell, mais vient d’être débauché par Facebook. On peut remarquer que le financement de Microsoft n’a nullement entravé le développement d’un compilateur libre d’une grande qualité (GHC), ni les fondements libres du langage Haskell. Simon Marlow a en particulier travaillé sur les aspects parallèles du compilateur, ce qui en fait l’un des plus aptes à nous en expliquer son fonctionnement.

Le livre

Le livre est disponible en versions électroniques (sans DRM) chez O’Reilly. Il est aussi accessible en ligne dans son intégralité en version HTML. La version papier sortira sous peu.

La lecture de l’ouvrage nécessite d’avoir des connaissances de base du langage Haskell, par exemple au travers des livres cités ci-dessus.

On y retrouve toutes les dernières avancés de Haskell, GHC et des bibliothèques associées, en ce qui concerne le parallélisme, tout ce qui fait d’Haskell un langage fortement parallèle, et va ainsi à l’encontre de son slogan officieux : Avoid success at all cost! On peut ainsi apprendre comment paralléliser très simplement son code :

a <- rpar (f x)
b <- rpar (f y)

Ici, les deux appels à f seront effectués en parallèle grâce à rpar.

On apprend aussi comment utiliser la bibliothèque de tableaux multi-dimensionnels repa, bibliothèque qui interagit avec le compilateur pour optimiser le parallélisme sur plusieurs processeurs, avec fusion de boucles par exemple :

sum3 a b c = a +^ b +^ c

Ici a, b et c sont des tableaux multi-dimensionnels qui verront leurs éléments additionnés de façon parallèle. À noter, il n’y aura pas de création d’un objet intermédiaire a +^ b, contrairement à un programme NumPy par exemple.

Le dernier chapitre de la programmation parallèle est consacré à Accelerate, pour programmer du code qui sera compilé vers le GPU. Il s’agit principalement d’utiliser la plateforme CUDA, même si d’autres backends comme OpenCL ou Repa existent, ils sont bien moins développés.

Enfin, la deuxième partie du livre est dédiée à la programmation concurrente, avec tous les usual suspects : mutex, échange de messages, STM, multi-threading, programmation distribuée, etc. Le tout avec des exemples concrets (serveurs de chat, recherche de fichiers, …).

Toutes ces technologies sont en cours de développement intensif, et l’auteur nous fait non seulement un état de l’art des différentes publications sous-jacentes, mais nous met aussi en garde sur l’instabilité de certains composants.

Aller plus loin

Le livre chez O’Reilly (83 clics)
La version HTML en ligne (195 clics)
Commentaires sur Reddit (41 clics)
Le langage Haskell (74 clics)
Apprendre Haskell vous fera le plus grand bien ! (298 clics)

# Parallélisation automatique ?

Posté par Victor le 25 juillet 2013 à 15:25. Évalué à 8.

Je me suis toujours demandé pourquoi en fonctionnel on ne peut pas paralléliser automatiquement certaines des expressions, par exemple dans le programme suivant (pseudo-code, je connais pas bien haskell) :

val a = f(x)
val b = f(y)
val c = a+b

Pourquoi ne peut-on pas automatiquement paralléliser les appels à f puisque on est dans du pur fonctionnel et que les 2 appels ne dépendent pas l'un de l'autre (contrairement à l'appel à +) ?

Ça m'a semblé être un des avantages de la programmation fonctionnelle, mais je ne l'ai jamais vu dans la pratique, et maintenant je vois qu'on introduit des monades particulières pour faire du parallélisme comme ce que je décris juste au dessus… alors je me dis que j'ai du louper quelque chose ?
- [^] # Re: Parallélisation automatique ?
  
  Posté par kessavdir (site web personnel) le 25 juillet 2013 à 15:56. Évalué à 5.
  
  Parce que ça serait en demander beaucoup trop au compilo ?
  
  Dans ton cas on peut en effet calculer a et b en parallèle. Par contre pour calculer c il faut que les deux traitement parallèles soient terminés. Ça implique du contrôle via des sémaphores ou autres…
  
  Après pour paralléliser automatiquement il faudrait aussi être sûr que le coût du traitement parallèle ne soit pas supérieur au coût de l'exécution séquentielle (allocation de threads, etc.).
- [^] # Re: Parallélisation automatique ?
  
  Posté par hsyl20 (site web personnel) le 25 juillet 2013 à 16:13. Évalué à 9.
  
  On pourrait, mais il faudrait être sûr que ça vaille le coup. Dans le cas général, surtout dans un langage à évaluation non-stricte comme Haskell où il ne faut pas évaluer f(x) ou f(y) si a ou b n'est jamais utilisé, ni x et y si le paramètre de f n'est pas strict, c'est encore plus chaud.
  
  Plus d'info :
  http://www.macs.hw.ac.uk/~dsg/gph/papers/abstracts/par-intro.html
  - [^] # Re: Parallélisation automatique ?
    
    Posté par Victor le 25 juillet 2013 à 16:48. Évalué à 4.
    
    Je vois, merci pour vos commentaires à tout les deux :)
  - [^] # Re: Parallélisation automatique ?
    
    Posté par Jean Parpaillon (site web personnel) le 28 juillet 2013 à 13:25. Évalué à 3.
    
    Effectivement, il est difficile d'estimer à priori le coût de la fonction 'f' et donc le comparer à celui d'une création de threads, etc. En revanche, la programmation fonctionnelle permet effectivement d'avoir une transparence totale des APIs par rapport au parallélisme. Si le développeur décide que 'f' est implémenté par un thread différent du thread principal, l'API ne changera pas. En erlang, par exemple, c'est un usage assez courant de masquer le passage de message vers les serveurs par des appels de fonctions qui seront les seules connues de l'utilisateur.
    
    Je ne sais pas si le terme est juste, mais je dirais que la programmation fonctionnelle offre une parallélisation "implicite" qui permet de la parallélisation automatique. Entre les 2, on peut avoir des différences de performances, difficiles à évaluer, mais au moins pas d'erreur d'algorithme (le résultat sera correct).
    
    "Liberté, Sécurité et Responsabilité sont les trois pointes d'un impossible triangle" Isabelle Autissier
- [^] # Re: Parallélisation automatique ?
  
  Posté par Axioplase ıɥs∀ (site web personnel) le 25 juillet 2013 à 19:31. Évalué à 8.
  
  Parce que ça ne vaut pas le coût/coup : créer un thread/spark/autre peut coûter plus cher qu'évaluer séquentiellement a et b.
  Pour avoir fait de la programmation parallèle en Haskell dans mon précédent job, j'ai bien compris que c'était pas évident de faire un programme parallèle et efficace (et souvent, tu dois aussi jouer avec les directives de forcage d'évaluation (les "bang patterns") afin d'éviter de créer trop de fermetures en mémoire).
# Version HTML

Posté par neil le 25 juillet 2013 à 18:19. Évalué à 2.

D’après l’auteur, la version HTML ne devrait rester que quelques jours en ligne, le temps de l’OSCON. La version définitive librement accessible sera disponible ultérieurement.
# Slides

Posté par hsyl20 (site web personnel) le 25 juillet 2013 à 23:22. Évalué à 3.

A noter que l'auteur a présenté un peu tout ça à une école d'été à Cadarache.

Les slides sont dispo ici :
http://community.haskell.org/~simonmar/slides/cadarache2012/
# Pour paralleliser du code en OCaml, c'est par ici:

Posté par zaurus (site web personnel) le 26 juillet 2013 à 06:08. Évalué à 4.

http://rdicosmo.github.io/parmap/
- [^] # Commentaire supprimé
  
  Posté par Anonyme le 26 juillet 2013 à 06:54. Évalué à -7. Dernière modification le 26 juillet 2013 à 06:58.
  
  Ce commentaire a été supprimé par l’équipe de modération.
  - [^] # Commentaire supprimé
    
    Posté par Anonyme le 26 juillet 2013 à 07:53. Évalué à -6.
    
    Ce commentaire a été supprimé par l’équipe de modération.
    - [^] # Re: Pour paralleliser du code en OCaml, c'est par ici:
      
      Posté par hsyl20 (site web personnel) le 26 juillet 2013 à 09:16. Évalué à 4.
      
      Heureusement qu'ils précisent que ça n'a pas été inventé par Google. Dans leur article de 2004 [1], ils ne s'embarrassent pas avec ça.
      
      Brièvement, la plupart des opérations sur les collections de type liste non vide peuvent s'écrire sous la forme canonique (cf catamorphisme) : reduce f . map g
      Si f est associative, ça se parallélise aisément, d'où MapReduce. Il existe la même chose pour des types de données plus compliqués : ensemble finis, arbres, tableaux à n dimensions… [2] Pour ceux que ça intéresse, les mots-clés sont Bird-Meertens Formalism (BMF) et théorie des catégories.
      
      [1] http://research.google.com/archive/mapreduce-osdi04.pdf
      [2] http://www.amazon.com/Foundations-Programming-Cambridge-International-Computation/dp/0521018560
      - [^] # Commentaire supprimé
        
        Posté par Anonyme le 26 juillet 2013 à 09:49. Évalué à -8. Dernière modification le 26 juillet 2013 à 09:50.
        
        Ce commentaire a été supprimé par l’équipe de modération.
      - [^] # Re: Pour paralleliser du code en OCaml, c'est par ici:
        
        Posté par ckyl le 26 juillet 2013 à 10:07. Évalué à 4.
        
        Dans leur article de 2004 [1], ils ne s'embarrassent pas avec ça.
        
        Attention entre le map-reduce tel qu'on l'utilise en distribué et les map/reduce/fold parallèles il y a quand même un gros fossé. Si l'inspiration vient clairement des langages fonctionnels, et ca n'a jamais été caché vu le nom…, en pratique techniquement ce qui fait que ca marche ce sont tous les à côté. Un map-reduce c'est basiquement un gros tri-distribué suivi d'un groupBy que tu peux tordre dans tout les sens, dans lequel le étape de map & reduce sont "embarassingly parrallel". Toute la mécanique intermédiaire n'existe pas dans le map/reduce/fold au sens fonctionnel.
        
        Autrement c'est étonnant que le par(map|reduce|fold) semblent émerger maintenant sur OCaml/Haskell & autre alors que les collections parallèles et le fork/join sont dispo depuis super longtemps dans Scala/Groovy, et sont dispo dans Java 8.
        
        [^] # Re: Pour paralleliser du code en OCaml, c'est par ici:
        
        Posté par Thomas Douillard le 26 juillet 2013 à 13:19. Évalué à 4.
        
        J'ai vu une vidéo d'une conf sur le présent et l'avenir d'Haskell. Un des mecs dit quelque chose du genre On dit depuis des années que les langages fonctionnels c'est cool parce que c'est facilement vérifiable et parallélisable, mais on le fait pas, faudrait peut être s'y mettre non ?
        
        [^] # Re: Pour paralleliser du code en OCaml, c'est par ici:
        
        Posté par ZankFrappa le 27 juillet 2013 à 10:11. Évalué à 3.
        
        En pratique, c'est un argument assez mauvais pour l'adoption des langages fonctionnels : la programmation parallèle est un sujet compliqué, et les arguments marketing du style de celui que tu énonces sont rarement plus que de la poudre aux yeux (exemple).
        
        [^] # Re: Pour paralleliser du code en OCaml, c'est par ici:
        
        Posté par Zylabon le 27 juillet 2013 à 10:36. Évalué à 3.
        
        Bah, il le dit bien… « on ne le fait pas ».
        
        Please do not feed the trolls
        
        [^] # Re: Pour paralleliser du code en OCaml, c'est par ici:
        
        Posté par ckyl le 27 juillet 2013 à 10:59. Évalué à 6.
        
        En effet ça demande de comprendre ce que l'on fait et comment ça marche. Tout comme en séquentiel tu as besoin de comprendre à la fois la complexité et les performances/implication de l'implémentation, en parallèle tu as besoin de comprendre si tes opérations sont scalable et où/pourquoi l'implémentation va poser problème.
        
        Il n'y a rien de magique. Par contre offrir des outils simples et performants entre le purement séquentiel et le programme purement parallèle et/ou distribué n'est pas stupide. Tu as pas mal d'applis ou il y a à gratter sans sortir des archis compliquées.
        
        Le monde n'est pas binaire:
        
        le GC parallèle (qui tourne en même temps que les threads au lieu de les stopper) a été désactivé car il dégradait les performances soit très bien pour le batch, maintenant comment je garantie que mon appli n'aura jamais un temps de réponse > 20ms ? Comment je minimise mon jitter ? Différents besoins, différentes solutions.
        
        les implémentations qui scalent le mieux (x6 sur 8 cœurs) sont 10 fois plus lentes que la version séquentielle quand elles tournent sur un seul cœur c'est exactement pour ca que ce n'est pas automatique et qu'il faut un cerveau derrière. Maintenant vu la gueule des chiffres, j'ai envie de dire que ca ressemble un problème de l'implem d'Haskell.
        
        l'implémentation la plus rapide utilise 8 cœurs pour multiplier les performances par 3 par rapport à la version séquentielle c'est effectivement un gros problème et c'est pour ca qu'on ne cherche qu'à exposer les patterns qui scalent. D'ailleurs en général les patterns qui scalent en parallèle et distribués sont assez similaires. Ca veut dire que tu vas petit à petit tordre les conceptions des projets pour être distribuable. C'est très bien.
        
        Autre question, ce sont quoi les autres alternatives ? Quel est le coût et la performance d'une approche explicite ? Quel sont les coût et les performance de tout autre approche ? C'est cool, et parfaitement valide, et dire que telle approche a des perfs moisi. Maintenant je fais quoi de mes 7..31 autres cores ? Je fais comment quand l'approche séquentielle ne peut pas tenir les perfs nécéssaire ?
        
        Il est aussi vrai qu'à la base le design en FP se prête mieux à la parallélisation. En OOP la plupart des gens sont encore sur des designs aux états mutables, au partage de donnée, à la synchronisation dont on connait en général les perfs, la complexité et la scalabilité. Maintenant on cherche des solutions, pas magiques mais qui font leur job. Les besoins des utilisateur sont très divers, explorons différentes solutions.
        
        [^] # Re: Pour paralleliser du code en OCaml, c'est par ici:
        
        Posté par neil le 26 juillet 2013 à 19:00. Évalué à 4. Dernière modification le 26 juillet 2013 à 19:03.
        
        Autrement c'est étonnant que le par(map|reduce|fold) semblent émerger maintenant sur OCaml/Haskell & autre alors que les collections parallèles et le fork/join sont dispo depuis super longtemps dans Scala/Groovy, et sont dispo dans Java 8.
        
        Le parallélisme dans Haskell, aussi bien sur architectures à mémoire partagée que distribuée, remonte aux années 90 (par exemple avec GUM).
        
        Ce n’est pas parce qu’un livre sort maintenant en étant uniquement dédié au parallélisme et à la concurrence que ça n’existait pas avant. Une bonne partie de ce qui est écrit dans ce livre n’est que description de l’état de l’art de ce qui se fait depuis des années en Haskell. Même dans l’ancien (bon seulement 5 ans) livre Real world Haskell, un chapitre était déjà dédié à tout ça (parlant aussi du MapReduce de Google), et l’accelération GPU directement en Haskell avec optimisations (Accelerate) existait déjà.
# Tail-call optimization de la factorielle ?

Posté par Christophe Bliard le 26 juillet 2013 à 15:15. Évalué à 3.

Je ne connais pas Haskell mais certaines techniques comme le tail call optimization me séduisent. Du coup sur l'exemple de la fonction fac, je me demande si Haskell sait transformer ça en fonction tail-récursive ou s'il faut l'aider un peu en définissant d'autres fonctions ?

Dans la doc Haskell, le tail call optimization est défini ainsi :

In many programming languages, calling a function uses stack space, so a function that is tail recursive can build up a large stack of calls to itself, which wastes memory. Since in a tail call, the containing function is about to return, its environment can actually be discarded and the recursive call can be entered without creating a new stack frame. This trick is called tail call elimination or tail call optimisation and allows tail-recursive functions to recur indefinitely.
- [^] # Re: Tail-call optimization de la factorielle ?
  
  Posté par ckyl le 26 juillet 2013 à 15:34. Évalué à 7.
  
  Je ne connais pas Haskell mais certaines techniques comme le tail call optimization me séduisent. Du coup sur l'exemple de la fonction fac, je me demande si Haskell sait transformer ça en fonction tail-récursive ou s'il faut l'aider un peu en définissant d'autres fonctions ?
  
  Ca serait triste qu'Haskell n'y arrive pas, alors que ca ne pose aucun problème à gcc ou n'importe quel compilo de n'importe quel langage supportant la fonctionnalité. fac correspond exactement à la définition d'une fonction tail recursive. J'aime bien l'annotation @tailrec de scala qui fait hurler le compilateur si la fonction ne répond pas au contrat. Ca permet d'éviter les énormes surprises à cause d'un petit changement qui casse tout…
  - [^] # Re: Tail-call optimization de la factorielle ?
    
    Posté par Lizzie Crowdagger (site web personnel) le 28 juillet 2013 à 18:08. Évalué à 6.
    
    «fac correspond exactement à la définition d'une fonction tail recursive.»
    
    Heu je dis peut-être une connerie et du coup j'ai un doute, mais telles que je comprends les choses, fac telle qu'est est définie là n'est pas tail-recursive (multiplication par n entre la récursion et le renvoi de la valeur de retour), contrairement à la version qui est donnée dans un commentaire plus bas (avec fac' qui prend un paramètre supplémentaire acc pour ne pas avoir à faire cette multiplication).
- [^] # Re: Tail-call optimization de la factorielle ?
  
  Posté par Zylabon le 26 juillet 2013 à 19:00. Évalué à 5.
  
  Contrairement à scheme, les specs du langage de disent pas que l'optimisation doit être faite. Il ne faut pas compter dessus. C'est comme en C d'ailleurs… J'ai déjà vu des programmes C qui plantaient en mode debug seulement parce que la TCO n'était pas faite.
  
  En pratique, GHC la fait souvent, même si la fonction n'est pas tail récursive. (comme la factorielle définie ci dessus)
  Il est bon de noter que l'optimisation n'est pas toujours une bonne chose, en effet elle empêche toute mémoization ou réutilisation de calculs.
  
  Ceci dit, il y a des cas trivials ou l'optimisation doit être faite, par exemple l'appel récursif à main pour faire boucler un programme. Si elle n'est pas faite, ça plante.
  
  Please do not feed the trolls
- [^] # Re: Tail-call optimization de la factorielle ?
  
  Posté par Axioplase ıɥs∀ (site web personnel) le 26 juillet 2013 à 19:58. Évalué à 6.
  Il y a un risque à cause des règles d'évaluation paresseuses du langage.
  Il faut parfois aider un peu en forçant l'évaluation (eg, via l'extention BangPatterns de GHC) l'évaluation. Sinon, tu crées des thunks en mémoire et risque au final le débordement de pile/tas, pas forcément à cause de l'adresse de retour, mais à cause des paramètres de l'appel récursif.
  Exemple:
  
  fac 100000 met quatre fois plus de tems que fac2 100000 sur mon PC:
```
{-#LANGUAGE BangPatterns #-}

fac n = fac' n 1
  where
  fac' 1 acc = acc
  fac' n acc = fac' (n-1) (n * acc)

fac2 n = fac' n 1
  where
  fac' 1 !acc = acc
  fac' n !acc = fac' (n-1) (n * acc)
```
  Cela dit, c'est ptet plus un débordement de tas que de pile…
  - [^] # Re: Tail-call optimization de la factorielle ?
    
    Posté par neil le 26 juillet 2013 à 23:34. Évalué à 4.
    
    De façon générale, il vaut mieux laisser le compilateur faire son boulot pour des cas triviaux comme celui-là. Sur mon installation (GHC 7.6.3) je n’ai pas de différence notables entre tes deux versions, et la version que j’ai donnée tout en haut est plus rapide en désactivant les optimisations. En activant les optimisations il n’y a pas de différence entre toutes ces versions.
    
    Si tu avais un débordement de pile, le runtime te le dirait avec un message du genre :
    
    Stack space overflow: current size 8388608 bytes.
    Use `+RTS -Ksize -RTS' to increase it.
    
    Effectivement, si on ne comprend pas bien comment marche l’évaluation dans Haskell, ça peut arriver, et l’exemple le plus parlant pour le montrer et la différence entre foldl et foldr.
# C++ std::future

Posté par LupusMic (site web personnel, Mastodon) le 26 juillet 2013 à 16:17. Évalué à 3.

Est-ce que c'est le genre de problème que permettent de résoudre std::future et std::async ?
- [^] # Re: C++ std::future
  
  Posté par ckyl le 26 juillet 2013 à 16:54. Évalué à 10.
  Pas vraiment.
  
  Les collections parallèles, et donc les map/reduce/fold parallèles, permettent de travailler sur des collections de manière parallèle de facon totalement transparente.
  
  L'exemple le plus bateau est de transformer tout les objets d'une liste. Je donne l'exemple en Java par ce que c'est peut être ce qui parlera le plus à quelqu'un qui fait du C++, après entre les différents langage c'est kifkif. En old school tu écrirais:
```
List<String> strings = Arrays.asList("a", "aa", "aaa");
List<Integer> lengths = new ArrayList<>(strings.size());
for (String str: strings) {
    lengths.add(str.length())
}
```
  Avec une API de type stream tu fais ca:
```
List<String> strings = Arrays.asList("a", "aa", "aaa");
List<Integer> lengths = strings.stream()
       .mapToInt(String::length);
```
  Maintenant disons que ta collection fait quelques millions d'éléments. Tu vois aisément que chaque traitement est indépendant, c'est de l'embarassingly parallel, tu peux facilement laisser le runtime dispatcher ca automatiquement sur plusieurs cores:
```
List<String> strings = Arrays.asList("a", "aa", "aaa");
List<Integer> lengths = strings.parallelStream()
       .mapToInt(String::length);
```
  Le seul changement c'est stream contre parallelStream. La première version est séquentiel, la seconde parallèle. C'est totalement transparent pour toi. Évidement tu peux faire des choses un peu plus compliquée avec d'autres opérateurs du même type. Pour te donner une petite idée tu peux regarder les nouveautée de Java8 ca doit être accessible et parlant à n'importe qui qui fait de l'objet (en regardant uniquement ce qui touche les collections/streams). Ou aussi n'importe quel doc sur les collections de Scala.
  
  En fonctionnel, ce type de traitement est la base. Tu passes ton temps à exécuter des fonctions qui transforment des données immutables en d'autres.
  
  Si on va plus loin, on pourrait aussi faire ces opérations de manière distribuée c'est à dire en utilisant plusieurs machines. Comme pour le parallèle, plusieurs cores, cela à un coût (transfert réseau etc.) mais il peut être amorti selon le cas d'utilisation. Très très basiquement, c'est ce permet fait Hadoop. En vrai un système distribué à des contraintes qu'un système parallèle n'a pas donc c'est un peu différent.
  
  std::async et std::future te permettent eux de faire du parallélisme explicite. Tu définis un traitement a effectuer de manière asynchrone et tu récupères un future qui te permet de récupérer le résultat du traitement lorsqu'il est fini (sans bloquer si tu le souhaites). Basiquement c'est du sucre syntaxique au dessus des threads, possiblement d'un threadpool, et d'un objet permettant de communiqué une valeur entre l'appelant et le thread. Ce sont donc deux approches différentes et complémentaire du parallélisme. Tu ne les utilises pas au même endroit ni pour faire la même chose. Il en existe d'autres.
  - [^] # Re: C++ std::future
    
    Posté par LupusMic (site web personnel, Mastodon) le 27 juillet 2013 à 15:35. Évalué à 3.
    
    Je viens de me faire un petit programme pour me rendre compte de ça. Je n'avais, pour l'instant, pas compris std:async et compagnie.
    
    En fait, il y a pas mal de travail à accomplir pour obtenir le même type de traitement qui est fait nativement par Haskell. Mais ce n'est pas insurmontable.
    
    Par contre, je me dis qu'il peut arriver qu'une opération map échoue, et ait besoin d'être retentée. Est-ce que Haskell permet de définir la politique de failover ? Où on s'en fout ? :D
    
    En tout cas, merci pour ta contribution à mon élévation intellectuelle, c'est toujours appréciable.
    - [^] # Re: C++ std::future
      
      Posté par Axioplase ıɥs∀ (site web personnel) le 27 juillet 2013 à 23:58. Évalué à 6.
      
      Map n'échoue pas. Eventuellement, la fonction que tu mappes échoue. Mais alors, t'as un bug dans ton code, et retenter map n'y changera rien.
      - [^] # Re: C++ std::future
        
        Posté par LupusMic (site web personnel, Mastodon) le 28 juillet 2013 à 12:59. Évalué à 0.
        
        Mon premier contact avec map/reduce était avec MongoDB. Le fait qu'un serveur à qui on a délégué un mapping échoue n'est pas quelque chose d'inexistant. C'est pour ça que je pose la question.
        
        Et il y a toujours des bogues, statistiquement. Prétendre qu'il n'y en a pas parce que c'est prouvé mathématiquement, c'est de la branlette universitaire.
        
        [^] # Re: C++ std::future
        
        Posté par Axioplase ıɥs∀ (site web personnel) le 29 juillet 2013 à 01:18. Évalué à 7.
        
        Je réitère: map n'échoue pas en Haskell, ou alors ton programme entier plante, et c'est pas la faute de map, mais de la fonction que tu mappes. Dire que map échoue, c'est un peu comme dire qu'un "IF" échoue. Si c'est le cas, c'est pas la faute du IF lui-même, mais de ce que tu fais dedans (et d'ailleurs, avec map, on garantit trivialement que c'est pas le test du if qui échoue mais le contenu du then ou du else, donc la fonction qu'on applique et pas map lui-même).
        
        Je n'ai aucune idée de ce que map veut dire dans mongodb, mais le map fonctionel, celui d'Haskell, Lisp, ML et consorts, il n'échoue pas, et ça n'a donc aucun sens de vouloir faire un failover.
        
        Quant à ton avis sur les méthodes formelles, sans rentrer dans les débats philosophoques (car il y en a), il me parait bien mal informé. Personellement, je suis bien content que la branlette universitaire prouve l'absence de bugs dans l'informatique embarquée des avions que je prend et dans le matériel médical utilisé pour les radios et scanners que je subis.
    - [^] # Re: C++ std::future
      
      Posté par neil le 28 juillet 2013 à 09:05. Évalué à 2. Dernière modification le 28 juillet 2013 à 09:05.
      Par contre, je me dis qu'il peut arriver qu'une opération map échoue
      
      Ça dépend de ce que tu veux dire. Les fonctions Haskell sont pures (elles n’ont pas d’effet de bord), donc un cas comme celui plus au pour convertir une liste de chaînes de caractères en liste d’entier correspondant à leurs tailles pourra s’écrire :
      
      > map length ["a", "aa", "aaa"] [1,2,3]
      
      Comme length est une fonction pure, elle n’échouera jamais, que son appel soit effectué via un map, ou en parallèle via un parMap.
      
      Maintenant, tu peux vouloir utiliser des fonctions avec des effets de bord, ce qui correspond à la monade IO en Haskell. En imaginant une fonction length' qui peut échouer, une façon standard serait de renvoyer Nothing en cas d’erreur, mais on peut conserver l’entrée avec Left/Right. Le map devient alors un mapM dans la monade IO :
      
      > resultat <- mapM length' ["a", "aa", "aaa"] [Right 1,Right 2,Left "aaa"]
      
      Tu peux remarquer que le code est quasiment identique (dans l‘interpréteur). Relancer le calcul pour les éléments pour lesquels la fonction a échoué se fera avec la même fonction mapM, et un simple encapsuleur pour length', ne ré-exécutant le code qu’en cas d’échec (pour le dernier élément dans l’exemple précédent).
      
      > mapM (wrap length') resultat [Right 1,Right 2,Right 3]
      
      Où wrap est définie comme :
      
      wrap f (Left s) = f s wrap _ r = r
      
      Rappeler plusieurs fois la fonction encapsulée avec mapM relève de la simple politique du programme. Ce qu’on peut conclure, c’est qu’Haskell donne tous les outils pour exprimer ces concepts de façon très concise.
      - [^] # Re: C++ std::future
        
        Posté par Zylabon le 28 juillet 2013 à 11:55. Évalué à 7.
        
        juste une bricole :
        
        Comme length est une fonction pure, elle n’échouera jamais
        
        Si une fonction n'échoue jamais c'est pas parce qu'elle est pure, c'est parce qu'elle est complète. Et ce n'est pas le cas de length. Par exemple length [0..] plante, parce que length n'est définie que pour les listes finies. Comme exemple plus parlant il y a la fonction head qui est pure et foire si son argument est une liste vide.
        
        Please do not feed the trolls
        
        [^] # Re: C++ std::future
        
        Posté par neil le 29 juillet 2013 à 07:48. Évalué à 2. Dernière modification le 29 juillet 2013 à 07:48.
        
        J’assimilais la notion d’échec dans un map de LupusMic à la pureté de la fonction mappée. Ça n’empêche effectivement pas qu’on ait d’autres notions d’échec en Haskell, comme le fait qu’on ait des fonctions partielles, head dans ton exemple (mais on n’a pas trop le choix si on veut que head soit polymorphique, de part le free theorem), ou le fait que les fonctions ne soit évidemment pas toutes calculables vu qu’Haskell, comme tous les langages de programmation utiles, est Turing complet (si on peut calculer length, on peut résoudre le problème de l’arrêt). J’avoue avoir du mal à fusionner ces deux autres notions d’échec (la non-calculabilité et la non-totalité) en une seule comme tu le fait par l’adjectif « complèt[e] ».
        
        [^] # Re: C++ std::future
        
        Posté par Zylabon le 29 juillet 2013 à 13:05. Évalué à 4.
        
        L'existence de fonction non calculable est un "problème" très fondamental, on ne peut pas y faire grand chose. Les fonctions partielles en revanche montrent juste une déficience du système de type. Pour head nous avons head :: forall a. [a] -> a alors que son vrai type est head :: forall a. {[a]} \ {[]} -> a en pseudo code.
        
        Please do not feed the trolls
        
        [^] # Re: C++ std::future
        
        Posté par Perthmâd (site web personnel) le 29 juillet 2013 à 13:39. Évalué à 4.
        
        Au contraire, j'aurais personnellement tendance à dire qu'en pratique, on n'utilise pas tant que ça la Turing-completeness des langages de programmation, sauf à la marge. Ce qui me porte à croire que le futur réside dans la programmation purement fonctionnelle totale, comme implémentée dans Coq ou Agda.
        
        Certes, actuellement on peut difficilement les utiliser comme langages de programmation de tous les jours, mais on peut quand même faire des trucs marrants.
        
        [^] # Re: C++ std::future
        
        Posté par Axioplase ıɥs∀ (site web personnel) le 29 juillet 2013 à 18:16. Évalué à 2.
        
        si on peut calculer length, on peut résoudre le problème de l’arrêt)
        
        Euh, vraiment ? Ça suffit ? Un langage avec uniquement la déconstruction de listes et la création d'entiers naturels par incrémentation, c'est suffisant pour être Turing-complet ? Ça me parait bien insuffisant…
        
        [^] # Re: C++ std::future
        
        Posté par neil le 29 juillet 2013 à 18:56. Évalué à 2. Dernière modification le 29 juillet 2013 à 19:00.
        
        si on peut calculer length, on peut résoudre le problème de l’arrêt
        
        Euh, vraiment ? Ça suffit ?
        
        Oui. Tu peux facilement créer une liste de toutes les instructions effectuées pour une machine de Turing donnée (en terminant la liste quand la machine s’arrête, en ayant une liste infinie, par construction, sinon). Trivialement, une méthode qui te dit si ta liste est infinie ou non (c’est à dire un length dans ℕ∪{∞}) résout le problème de l’arrêt.
        
        [^] # Re: C++ std::future
        
        Posté par neil le 29 juillet 2013 à 19:04. Évalué à 1.
        
        Quand je parle de « calculer length », je sous-entend qu’on ne peut pas, et que length n’est pas calculable, au sens classique du terme.
      - [^] # Re: C++ std::future
        
        Posté par LupusMic (site web personnel, Mastodon) le 28 juillet 2013 à 13:10. Évalué à 3.
        
        Maintenant, tu peux vouloir utiliser des fonctions avec des effets de bord,
        
        C'est exactement ce que j'avais en tête. Du genre, les objets passés à traiter désignent des ressources qui dépendent d'autres ressources. Pour moi, un exemple typique serait de parcourir un système de fichier avec un critère. Si la lecture de la mémoire apparaît comme infaillible aux yeux de certains perdus dans l'idéal programmatique, que le disque dur puisse merder est moins étrange.
        
        Merci en tout cas pour l'exemple de « fail over ».
        
        [^] # Re: C++ std::future
        
        Posté par neil le 29 juillet 2013 à 07:10. Évalué à 2. Dernière modification le 29 juillet 2013 à 07:12.
        
        Mon exemple reste très artificiel, principalement pour montrer qu’on peut considérer du code qui est effectivement utile en Haskell (et pas juste des fonctions pures). On peut suivre en Haskell la démarche du langage fonctionnel distribué de référence, Erlang, où l’échec (dans ton sens) est considéré comme normal (avec du monitoring de processus). Tu trouveras tout ça dans le chapitre 14, dédié à la programmation distribuée. Ça correspond à du Cloud Haskell.
      - [^] # Re: C++ std::future
        
        Posté par reno le 29 juillet 2013 à 09:34. Évalué à 4. Dernière modification le 29 juillet 2013 à 09:36.
        
        Comme length est une fonction pure, elle n’échouera jamais,
        
        Toute fonction peut échouer (débordement de pile) qu'elle soit pure ou pas, je dirais plutôt une fonction totale n'échoue pas quand le programme peut continue a s'exécuter.

Suivre le flux des commentaires

Note : les commentaires appartiennent à celles et ceux qui les ont postés. Nous n’en sommes pas responsables.