Programmation fonctionnelle: bonnes idées sur la concurrence et l'état?

Les partisans de la PF ont affirmé que la simultanéité est facile parce que leur paradigme évite l'état mutable. Je ne comprends pas.

Imaginez que nous créons une exploration de donjon multijoueur (un roguelike) en utilisant FP où nous mettons l'accent sur les fonctions pures et les structures de données immuables. Nous générons un donjon composé de chambres, couloirs, héros, monstres et butin. Notre monde est effectivement un graphe objet des structures et de leurs relations. À mesure que les choses changent, notre représentation du monde est modifiée pour refléter ces changements. Notre héros tue un rat, ramasse une épée courte, etc.

Pour moi, le monde (la réalité actuelle) porte cette idée d'état et je ne vois pas comment FP peut surmonter cela. Alors que notre héros agit, les fonctions modifient l'état du monde. Il semble que chaque décision (IA ou humaine) doit être basée sur l'état du monde tel qu'il est dans le présent. Où autoriserions-nous la simultanéité? Nous ne pouvons pas avoir plusieurs processus modifiant simultanément l'état du monde de peur qu'un processus ne base ses résultats sur un état expiré. Il me semble que tout contrôle devrait se produire dans une seule boucle de contrôle afin que nous traitions toujours l'état actuel représenté par notre graphique d'objet actuel du monde.

Il existe clairement des situations parfaitement adaptées à la concurrence (c'est-à-dire lors du traitement de tâches isolées dont les états sont indépendants les uns des autres).

Je ne vois pas comment la simultanéité est utile dans mon exemple et c'est peut-être le problème. Je peux déformer la réclamation d'une manière ou d'une autre.

Quelqu'un peut-il mieux représenter cette affirmation?

Je vais essayer de faire allusion à la réponse. Ce n'est pas une réponse, seulement une illustration introductive. La réponse de @ jk pointe vers la vraie chose, les fermetures éclair.

Imaginez que vous ayez une structure arborescente immuable. Vous souhaitez modifier un nœud en insérant un enfant. En conséquence, vous obtenez un tout nouvel arbre.

Mais la plupart du nouvel arbre est exactement le même que l'ancien. Une implémentation intelligente réutiliserait la plupart des fragments d'arbre, acheminant des pointeurs autour du nœud modifié:

Le livre d'Okasaki est plein d'exemples comme celui-ci.

Donc, je suppose que vous pouvez raisonnablement modifier de petites parties de votre monde de jeu à chaque coup (ramasser une pièce) et ne changer que de petites parties de la structure de données de votre monde (la cellule où la pièce a été ramassée). Les pièces qui n'appartiennent qu'à des états antérieurs seront récupérées à temps.

Cela prend probablement une certaine considération dans la conception de la structure mondiale du jeu de données d'une manière appropriée. Malheureusement, je ne suis pas expert en la matière. Certainement, cela doit être autre chose qu'une matrice NxM que l'on utiliserait comme structure de données mutable. Il devrait probablement se composer de plus petits morceaux (couloirs? Cellules individuelles?) Qui pointent les uns vers les autres, comme le font les nœuds d'arbre.

La réponse du 9000 est la moitié de la réponse, les structures de données persistantes vous permettent de réutiliser des parties inchangées.

Vous pensez peut-être déjà cependant "hé et si je veux changer la racine de l'arbre?" en l'état avec l'exemple donné, cela signifie maintenant changer tous les nœuds. C'est là que les fermetures éclair viennent à la rescousse. Ils permettent de modifier l'élément d'un focus dans O (1), et le focus peut être déplacé n'importe où dans la structure.

L'autre point avec les fermetures à glissière est qu'une fermeture à glissière existe pour à peu près n'importe quel type de données que vous voulez

Les programmes de style fonctionnel créent de nombreuses opportunités comme celle-ci pour utiliser la concurrence. Chaque fois que vous transformez, filtrez ou agrégez une collection, et que tout est pur ou immuable, l'opération peut être accélérée par concurrence.

Par exemple, supposons que vous exécutiez des décisions d'IA indépendamment les unes des autres et sans ordre particulier. Ils ne se relaient pas, ils prennent tous une décision simultanément, puis le monde avance. Le code pourrait ressembler à ceci:

func MakeMonsterDecision curWorldState monster =
    ...
    ...
    return monsterDecision

func NextWorldState curWorldState =
    ...
    let monsterMakeDecisionForCurrentState = MakeMonsterDecision curWorldState
    let monsterDecisions = List.map monsterMakeDecisionForCurrentState activeMonsters
    ...
    return newWorldState

Vous avez une fonction pour calculer ce qu'un monstre fera dans un état mondial, et l'appliquer à chaque monstre dans le cadre du calcul du prochain état mondial. C'est une chose naturelle à faire dans un langage fonctionnel, et le compilateur est libre d'effectuer en parallèle l'étape «l'appliquer à chaque monstre».

Dans un langage impératif, vous seriez plus susceptible d'itérer sur chaque monstre, en appliquant leurs effets au monde. C'est juste plus facile de le faire de cette façon, car vous ne voulez pas gérer le clonage ou l'aliasing compliqué. Dans ce cas, le compilateur ne peut pas effectuer les calculs de monstres en parallèle, car les premières décisions de monstre affectent les décisions de monstre ultérieures.

L'écoute de quelques discussions de Rich Hickey - celle-ci en particulier - a atténué ma confusion. Dans l'un, il a indiqué qu'il est normal que les processus simultanés n'aient pas l'état le plus récent. J'avais besoin d'entendre ça. Ce que j'avais du mal à comprendre, c'était que les programmes seraient en fait d'accord pour baser leurs décisions sur des instantanés du monde qui ont depuis été remplacés par des plus récents. Je n'arrêtais pas de me demander comment la PF concurrente pouvait contourner la question de fonder les décisions sur l'ancien état.

Dans une application bancaire, nous ne voudrions jamais baser une décision sur un instantané de l'état qui a depuis été remplacé par un plus récent (un retrait s'est produit).

Cette concurrence est facile car le paradigme FP évite l'état mutable est une affirmation technique qui n'essaie pas de dire quoi que ce soit sur les mérites logiques de baser les décisions sur un état potentiellement ancien. La PF modélise encore finalement le changement d'état. Il n'y a pas moyen de contourner cela.

Les partisans de la PF ont affirmé que la simultanéité est facile parce que leur paradigme évite l'état mutable. Je ne comprends pas.

Je voulais parler de cette question générale en tant que quelqu'un qui est un néophyte fonctionnel mais qui a été à la hauteur de mes globes oculaires en ce qui concerne les effets secondaires au fil des ans et je voudrais les atténuer, pour toutes sortes de raisons, y compris plus faciles (ou spécifiquement "plus sûres, moins sujette aux erreurs "). Quand je jette un coup d'œil à mes pairs fonctionnels et à ce qu'ils font, l'herbe semble un peu plus verte et sent mieux, du moins à cet égard.

Algorithmes série

Cela dit, à propos de votre exemple spécifique, si votre problème est de nature série et que B ne peut pas être exécuté tant que A n'est pas terminé, conceptuellement, vous ne pouvez pas exécuter A et B en parallèle quoi qu'il arrive. Vous devez trouver un moyen de briser la dépendance à l'ordre comme dans votre réponse en effectuant des mouvements parallèles en utilisant l'ancien état du jeu, ou utiliser une structure de données qui permet à certaines parties d'être modifiées indépendamment pour éliminer la dépendance à l'ordre comme proposé dans les autres réponses , ou quelque chose de ce genre. Mais il y a certainement une part de problèmes de conception conceptuelle comme celui-ci où vous ne pouvez pas nécessairement tout simplement multithreader si facilement parce que les choses sont immuables. Certaines choses vont être de nature sérielle jusqu'à ce que vous trouviez un moyen intelligent de briser la dépendance à l'ordre, si cela est même possible.

Accès simultané plus facile

Cela dit, il y a beaucoup de cas où nous ne parvenons pas à paralléliser les programmes qui impliquent des effets secondaires dans des endroits qui pourraient améliorer considérablement les performances simplement en raison de la possibilité qu'il pourrait ne pas être thread-safe. L'un des cas où l'élimination de l'état mutable (ou plus précisément des effets secondaires externes) aide beaucoup, comme je le vois, c'est qu'il transforme "peut ou non être thread-safe" en "définitivement thread-safe" .

Pour rendre cette déclaration un peu plus concrète, considérez que je vous donne une tâche pour implémenter une fonction de tri en C qui accepte un comparateur et l'utilise pour trier un tableau d'éléments. Il est censé être assez généralisé, mais je vais vous donner une hypothèse simple qu'il sera utilisé contre des entrées d'une telle échelle (des millions d'éléments ou plus) qu'il sera sans aucun doute avantageux de toujours utiliser une implémentation multithread. Pouvez-vous multithread votre fonction de tri?

Le problème est que vous ne pouvez pas parce que les comparateurs que votre fonction de tri appelle peuventprovoquer des effets secondaires, sauf si vous savez comment ils sont mis en œuvre (ou à tout le moins documentés) pour tous les cas possibles, ce qui est impossible sans dégénéraliser la fonction. Un comparateur pourrait faire quelque chose de dégoûtant comme modifier une variable globale à l'intérieur d'une manière non atomique. 99,9999% des comparateurs peuvent ne pas le faire, mais nous ne pouvons toujours pas multithreader cette fonction généralisée simplement en raison de 0,00001% de cas qui pourraient provoquer des effets secondaires. En conséquence, vous devrez peut-être proposer à la fois une fonction de tri monothread et multithread et confier la responsabilité aux programmeurs qui l'utilisent pour décider laquelle utiliser en fonction de la sécurité des threads. Et les gens peuvent toujours utiliser la version à un seul thread et manquer des opportunités de multithread, car ils ne savent pas non plus si le comparateur est compatible avec les threads,

Il y a beaucoup de cerveaux qui peuvent être impliqués dans la rationalisation de la sécurité des threads sans jeter de verrous partout, ce qui peut disparaître si nous avions juste des garanties solides que les fonctions ne causeront pas d'effets secondaires pour l'instant et pour l'avenir. Et il y a la peur: la peur pratique, car quiconque a dû déboguer une condition de course trop souvent hésiterait probablement à multithreader tout ce dont il ne peut pas être sûr à 110% qu'il est thread-safe et le restera. Même pour les plus paranoïaques (dont je suis probablement au moins à la limite), la fonction pure fournit ce sentiment de soulagement et de confiance que nous pouvons l'appeler en parallèle en toute sécurité.

Et c'est l'un des principaux cas où je le vois comme si bénéfique si vous pouvez obtenir une garantie solide que ces fonctions sont thread-safe que vous obtenez avec des langages fonctionnels purs. L'autre est que les langages fonctionnels favorisent souvent la création de fonctions exemptes d'effets secondaires en premier lieu. Par exemple, ils peuvent vous fournir des structures de données persistantes où il est raisonnablement assez efficace de saisir une structure de données massive, puis d'en sortir une toute nouvelle avec seulement une petite partie de celle-ci modifiée sans toucher à l'original. Ceux qui travaillent sans de telles structures de données pourraient vouloir les modifier directement et perdre une certaine sécurité des threads en cours de route.

Effets secondaires

Cela dit, je ne suis pas d'accord avec une partie avec tout le respect que je dois à mes amis fonctionnels (qui, je pense, sont super cool):

[...] parce que leur paradigme évite l'état mutable.

Ce n'est pas nécessairement l'immuabilité qui rend la concurrence si pratique que je le vois. Ce sont des fonctions qui évitent de provoquer des effets secondaires. Si une fonction entre un tableau pour trier, le copie, puis mute la copie pour trier son contenu et génère la copie, elle est toujours aussi sécurisée pour les threads que celle qui fonctionne avec un type de tableau immuable même si vous passez la même entrée tableau à partir de plusieurs threads. Je pense donc qu'il y a toujours une place pour les types mutables dans la création de code très concurrentiel, pour ainsi dire, bien qu'il y ait beaucoup d'avantages supplémentaires aux types immuables, y compris les structures de données persistantes que j'utilise pas tant pour leurs propriétés immuables que pour élimine le coût d'avoir à tout copier en profondeur afin de créer des fonctions sans effets secondaires.

Et il y a souvent des frais généraux pour rendre les fonctions exemptes d'effets secondaires sous forme de mélange et de copie de données supplémentaires, peut-être un niveau supplémentaire d'indirection, et peut-être un GC sur des parties d'une structure de données persistante, mais je regarde un de mes copains qui a une machine à 32 cœurs et je pense que l'échange en vaut probablement la peine si nous pouvons faire plus de choses en toute confiance en parallèle.