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

21

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?

Mario T. Lanza
la source
1
Vous faites référence à un état partagé; l'état partagé sera toujours ce qu'il est et nécessitera toujours une certaine forme de synchronisation, la forme souvent préférée parmi les personnes FP pures est STM qui vous permet de traiter la mémoire partagée comme mémoire locale en ayant une couche d'abstraction qui rend l'accès transactionnel si racial les conditions sont gérées automatiquement. Une autre technique pour la mémoire partagée est le passage de messages où au lieu d'avoir une mémoire partagée, vous avez la mémoire locale et la connaissance d'autres acteurs pour demander leur mémoire locale
Jimmy Hoffa
1
Alors ... vous demandez comment la simultanéité des états partagés est facile à gérer l'état dans une application à un seul thread? D'un autre côté, votre exemple se prête clairement à la concurrence conceptuelle (un thread pour chaque entité contrôlée par l'IA), qu'il soit ou non implémenté de cette façon. Je ne comprends pas ce que vous demandez ici.
CA McCann
1
en un mot, Zippers
jk.
2
Chaque objet aurait sa propre vision du monde. Il y aura éventuellement une cohérence . C'est probablement aussi comment les choses fonctionnent dans notre «monde réel» avec l' effondrement de la fonction d'onde .
herzmeister
1
Vous pouvez trouver des "retrogames purement fonctionnels" intéressants: prog21.dadgum.com/23.html
user802500

Réponses:

15

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é:

De Wikipédia

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.

9000
la source
3
+1: Pour avoir pointé le livre d'Okasaki. Je ne l'ai pas lu mais il est sur ma liste de tâches. Je pense que ce que vous avez décrit est la bonne solution. Comme alternative, vous pouvez considérer les types d'unicité (Clean, en.wikipedia.org/wiki/Uniqueness_type ): en utilisant ce type de types, vous pouvez mettre à jour de manière destructive les objets de données tout en conservant la transparence référentielle.
Giorgio
Les relations peuvent-elles être définies via une référence indirecte via des clés ou des identifiants? Autrement dit, je pensais que moins de contacts réels d'une structure à une autre nécessiteraient moins d'amendements à la structure mondiale lorsqu'un changement se produit. Ou cette technique n'est-elle pas vraiment utilisée en PF?
Mario T. Lanza
9

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

jk.
la source
Je crains que cela ne me prenne un peu de temps pour creuser dans les "fermetures à glissière" car je suis en marge de toute exploration de FP. Je n'ai aucune expérience avec Haskell.
Mario T. Lanza
J'essaierai d'ajouter un exemple plus tard aujourd'hui
jk.
4

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.

Craig Gidney
la source
Cela aide beaucoup. Je peux voir comment, dans un jeu, il serait très avantageux pour les monstres de décider simultanément ce qu'ils feront ensuite.
Mario T. Lanza
4

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.

Mario T. Lanza
la source
0

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.


la source
1
«État mutable» signifie toujours l'état au niveau de l'application et non au niveau de la procédure. L'élimination des pointeurs et le passage des paramètres en tant que valeurs de copie est l'une des techniques intégrées dans FP. Mais toute fonction utile doit muter l'état à un certain niveau - le but de la programmation fonctionnelle est de s'assurer que l'état mutable qui appartient à l'appelant n'entre pas dans la procédure, et les mutations ne sortent de la procédure que par les valeurs de retour! Mais il y a peu de programmes qui peuvent faire beaucoup de travail sans état de mutation du tout, et les erreurs se glissent toujours à nouveau à l'interface.
Steve
1
Pour être honnête, la plupart des langages modernes permettent d'utiliser un style de programmation fonctionnel (avec un peu de discipline), et bien sûr il existe des langages dédiés aux modèles fonctionnels. Mais c'est un modèle moins efficace en termes de calcul, et est populairement surestimé comme solution à tous les maux, tout comme l'orientation des objets l'était dans les années 90. La plupart des programmes ne sont pas liés par des calculs gourmands en CPU qui bénéficieraient de la parallélisation, et de ceux qui le sont, c'est souvent en raison de la difficulté de raisonner, concevoir et implémenter le programme d'une manière qui se prête à une exécution parallèle.
Steve
1
La plupart des programmes qui traitent de l'état mutable le font parce qu'ils doivent le faire pour une raison ou une autre. Et la plupart des programmes ne sont pas incorrects parce qu'ils utilisent un état partagé ou le mettent à jour de manière anormale - c'est généralement parce qu'ils reçoivent des déchets inattendus en entrée (qui déterminent une sortie de déchets), ou parce qu'ils fonctionnent incorrectement sur leurs entrées (incorrectement dans le sens du but) à réaliser). Les schémas fonctionnels ne font pas grand-chose pour y remédier.
Steve
1
@Steve Je pourrais au moins être à mi-chemin d'accord avec vous, car je suis de ce côté-là à explorer des moyens de faire les choses de manière plus sûre pour les threads à partir de langages comme C ou C ++, et je ne pense pas vraiment que nous devions aller de l'avant -soufflé pur fonctionnel pour le faire. Mais je trouve que certains des concepts de FP sont au moins utiles. Je viens de finir par écrire une réponse sur la façon dont je trouve PDS utile ici, et le plus grand avantage que je trouve sur PDS n'est en fait pas la sécurité des threads, mais des choses comme l'instanciation, l'édition non destructive, la sécurité des exceptions, les annulations simples, etc.: