Comment la programmation fonctionnelle gère-t-elle la situation où le même objet est référencé à partir de plusieurs endroits?

10

Je lis et j'entends que les gens (également sur ce site) font régulièrement l'éloge du paradigme de la programmation fonctionnelle, soulignant à quel point il est bon d'avoir tout immuable. Notamment, les gens proposent cette approche même dans les langages OO traditionnellement impératifs, comme C #, Java ou C ++, non seulement dans les langages purement fonctionnels comme Haskell qui forcent cela sur le programmeur.

J'ai du mal à comprendre, car je trouve la mutabilité et les effets secondaires ... pratiques. Cependant, étant donné la façon dont les gens condamnent actuellement les effets secondaires et considèrent que c'est une bonne pratique de s'en débarrasser autant que possible, je crois que si je veux être un programmeur compétent, je dois commencer mon mandat pour une meilleure compréhension du paradigme ... D'où mon Q.

Un endroit où je rencontre des problèmes avec le paradigme fonctionnel est quand un objet est naturellement référencé à partir de plusieurs endroits. Permettez-moi de le décrire sur deux exemples.

Le premier exemple sera mon jeu C # que j'essaie de faire pendant mon temps libre . C'est un jeu en ligne au tour par tour où les deux joueurs ont des équipes de 4 monstres et peuvent envoyer un monstre de leur équipe sur le champ de bataille, où il affrontera le monstre envoyé par le joueur adverse. Les joueurs peuvent également rappeler des monstres du champ de bataille et les remplacer par un autre monstre de leur équipe (de la même manière que Pokemon).

Dans ce cadre, un seul monstre peut être référencé naturellement depuis au moins 2 endroits: l'équipe d'un joueur et le champ de bataille, qui fait référence à deux monstres "actifs".

Examinons maintenant la situation où un monstre est touché et perd 20 points de vie. Dans les limites du paradigme impératif, je modifie le healthchamp de ce monstre pour refléter ce changement - et c'est ce que je fais maintenant. Cependant, cela rend la Monsterclasse mutable et les fonctions (méthodes) associées impures, ce qui, je suppose, est considéré comme une mauvaise pratique pour l'instant.

Même si je me suis donné la permission d'avoir le code de ce jeu dans un état moins qu'idéal afin d'avoir tout espoir de le finir à un moment donné dans le futur, je voudrais savoir et comprendre comment il devrait être écrit correctement. Par conséquent: s'il s'agit d'un défaut de conception, comment y remédier?

Dans le style fonctionnel, si je comprends bien, je ferais plutôt une copie de cet Monsterobjet, en le gardant identique à l'ancien sauf pour ce seul champ; et la méthode suffer_hitretournerait ce nouvel objet au lieu de modifier l'ancien en place. Ensuite, je copierais également l' Battlefieldobjet, en gardant tous ses champs identiques, à l'exception de ce monstre.

Cela vient avec au moins 2 difficultés:

  1. La hiérarchie peut facilement être beaucoup plus profonde que cet exemple simplifié de simplement Battlefield-> Monster. Je devrais faire une telle copie de tous les champs sauf un et retourner un nouvel objet tout au long de cette hiérarchie. Ce serait du code passe-partout que je trouve ennuyeux, d'autant plus que la programmation fonctionnelle est censée réduire le passe-partout.
  2. Un problème beaucoup plus grave, cependant, est que cela entraînerait la désynchronisation des données . Le monstre actif du champ verrait sa santé réduite; cependant, ce même monstre, référencé par son joueur contrôlant Team, ne le ferait pas. Si j'adoptais plutôt le style impératif, chaque modification des données serait instantanément visible de tous les autres endroits du code et dans de tels cas comme celui-ci, je le trouve vraiment pratique - mais la façon dont j'obtiens les choses est précisément ce que les gens disent est mal avec le style impératif!
    • Il serait désormais possible de régler ce problème en effectuant un voyage vers l' Teamaprès chaque attaque. C'est un travail supplémentaire. Cependant, que se passe-t-il si un monstre peut soudainement être référencé plus tard depuis encore plus d'endroits? Et si je viens avec une capacité qui, par exemple, permet à un monstre de se concentrer sur un autre monstre qui n'est pas nécessairement sur le terrain (j'envisage en fait une telle capacité)? Vais-je sûrement me souvenir de faire également un voyage vers des monstres concentrés immédiatement après chaque attaque? Cela semble être une bombe à retardement qui explosera à mesure que le code deviendra plus complexe, donc je pense que ce n'est pas une solution.

Une idée pour une meilleure solution vient de mon deuxième exemple, quand j'ai rencontré le même problème. Dans le milieu universitaire, on nous a dit d'écrire un interprète d'une langue de notre propre conception à Haskell. (C'est aussi comme ça que j'ai été forcé de commencer à comprendre ce qu'est la PF). Le problème est apparu lorsque je mettais en œuvre des fermetures. Une fois de plus, la même portée peut désormais être référencée à partir de plusieurs endroits: via la variable qui contient cette portée et comme portée parent de toutes les étendues imbriquées! De toute évidence, si une modification est apportée à cette étendue via l'une des références qui la pointent, cette modification doit également être visible à travers toutes les autres références.

La solution que j'ai trouvée consistait à attribuer un ID à chaque étendue et à tenir un dictionnaire central de toutes les étendues de la Statemonade. Désormais, les variables ne contiendraient que l'ID de l'étendue à laquelle elles étaient liées, plutôt que l'étendue elle-même, et les étendues imbriquées contiendraient également l'ID de leur étendue parent.

Je suppose que la même approche pourrait être tentée dans mon jeu de combat de monstres ... Les champs et les équipes ne font pas référence aux monstres; ils détiennent à la place des identifiants de monstres qui sont enregistrés dans un dictionnaire de monstres central.

Cependant, je peux encore une fois voir un problème avec cette approche qui m'empêche de l'accepter sans hésitation comme la solution au problème:

C'est encore une fois une source de code passe-partout. Cela rend les lignes simples nécessairement 3 lignes: ce qui était auparavant une modification sur place d'une ligne d'un seul champ nécessite désormais (a) la récupération de l'objet du dictionnaire central (b) la modification (c) la sauvegarde du nouvel objet dans le dictionnaire central. En outre, la détention d'ID d'objets et de dictionnaires centraux au lieu d'avoir des références augmente la complexité. Étant donné que FP est annoncé pour réduire la complexité et le code standard, cela indique que je me trompe.

J'allais également écrire sur un deuxième problème qui semble beaucoup plus grave: cette approche introduit des fuites de mémoire . Les objets inaccessibles seront normalement récupérés. Cependant, les objets contenus dans un dictionnaire central ne peuvent pas être récupérés, même si aucun objet accessible ne fait référence à cet ID particulier. Et bien qu'une programmation théoriquement prudente puisse éviter les fuites de mémoire (nous pourrions prendre soin de supprimer manuellement chaque objet du dictionnaire central une fois qu'il n'est plus nécessaire), cela est sujet aux erreurs et FP est annoncé pour augmenter l'exactitude des programmes, donc cela peut encore une fois pas la bonne façon.

Cependant, j'ai découvert à temps que cela semble plutôt être un problème résolu. Java fournit WeakHashMapqui pourrait être utilisé pour résoudre ce problème. C # fournit une fonctionnalité similaire - ConditionalWeakTable- bien que selon les documents, il est destiné à être utilisé par les compilateurs. Et à Haskell, nous avons System.Mem.Weak .

Le stockage de tels dictionnaires est-il la solution fonctionnelle correcte à ce problème ou y en a-t-il une plus simple que je n'arrive pas à voir? J'imagine que le nombre de tels dictionnaires peut facilement augmenter et mal; donc si ces dictionnaires sont censés être également immuables, cela peut signifier beaucoup de passage de paramètres ou, dans les langues qui prennent en charge cela, des calculs monadiques, car les dictionnaires seraient conservés en monades (mais encore une fois, je le lis en purement fonctionnel les langues le moins de code possible devraient être monadiques, tandis que cette solution de dictionnaire placerait presque tout le code à l'intérieur de la Statemonade; ce qui me fait encore une fois douter que ce soit la bonne solution.)

Après réflexion, je pense que j'ajouterais une autre question: qu'avons-nous à gagner en construisant de tels dictionnaires? Selon de nombreux experts, ce qui ne va pas avec la programmation impérative, c'est que les changements dans certains objets se propagent à d'autres morceaux de code. Pour résoudre ce problème, les objets sont censés être immuables - précisément pour cette raison, si je comprends bien, que les modifications qui leur sont apportées ne devraient pas être visibles ailleurs. Mais maintenant, je suis préoccupé par d'autres morceaux de code fonctionnant sur des données obsolètes, alors j'invente des dictionnaires centraux pour que ... une fois de plus, les changements dans certains morceaux de code se propagent à d'autres morceaux de code! Ne sommes-nous donc pas revenus au style impératif avec tous ses inconvénients supposés, mais avec une complexité accrue?

gaazkam
la source
6
Pour donner une certaine perspective, les programmes fonctionnels immuables sont principalement destinés aux situations de traitement de données impliquant la concurrence. En d'autres termes, les programmes qui traitent les données d'entrée via un ensemble d'équations ou de processus qui produisent un résultat de sortie. L'immutabilité aide dans ce scénario pour plusieurs raisons: les valeurs lues par plusieurs threads sont garanties de ne pas changer au cours de leur durée de vie, ce qui simplifie considérablement la possibilité de traiter les données de manière non verrouillée et d'expliquer le fonctionnement de l'algorithme.
Robert Harvey
8
Le sale petit secret de l'immuabilité fonctionnelle et de la programmation de jeux est que ces deux choses sont en quelque sorte incompatibles l'une avec l'autre. Vous essayez essentiellement de modéliser un système dynamique en constante évolution à l'aide d'une structure de données statique et inamovible.
Robert Harvey
2
Ne prenez pas la mutabilité contre l'immuabilité comme un dogme religieux. Il y a des situations où chacune est meilleure que l'autre, l'immuabilité n'est pas toujours meilleure, par exemple l'écriture d'une boîte à outils GUI avec des types de données immuables sera un cauchemar absolu.
whatsisname
1
Cette question spécifique à C # et ses réponses couvrent la question du passe-partout, résultant principalement de la nécessité de créer des clones légèrement modifiés (mis à jour) d'un objet immuable existant.
rwong
2
Un aperçu clé est qu'un monstre dans ce jeu est considéré comme une entité. De plus, le résultat de chaque bataille (composé du numéro de séquence de bataille, des identifiants d'entité des monstres, des états des monstres avant et après la bataille) est considéré comme un état à un certain moment (ou pas de temps). Ainsi, les joueurs ( Team) peuvent récupérer le résultat de la bataille et donc les états des monstres par un tuple (numéro de bataille, ID d'entité monstre).
rwong

Réponses:

19

Comment la programmation fonctionnelle gère-t-elle un objet référencé à partir de plusieurs endroits? Il vous invite à revisiter votre modèle!

Pour expliquer ... regardons comment les jeux en réseau sont parfois écrits - avec une copie "source dorée" centrale de l'état du jeu, et un ensemble d'événements clients entrants qui mettent à jour cet état, puis sont retransmis aux autres clients .

Vous pouvez lire sur le plaisir que l'équipe Factorio a eu à faire en sorte que cela se comporte bien dans certaines situations; voici un bref aperçu de leur modèle:

Le fonctionnement de base de notre mode multijoueur est que tous les clients simulent l'état du jeu et ne reçoivent et n'envoient que l'entrée du joueur (appelée Actions d'entrée). La principale responsabilité du serveur est de procuration des actions d'entrée et de s'assurer que tous les clients exécutent les mêmes actions dans le même tick.

Étant donné que le serveur doit arbitrer lorsque des actions sont exécutées, une action de joueur déplace quelque chose comme ceci: Action de joueur -> Client de jeu -> Réseau -> Serveur -> Réseau-> Client de jeu. Cela signifie que chaque action du joueur n'est exécutée qu'une fois qu'il effectue un aller-retour sur le réseau. Cela rendrait le jeu vraiment lent, c'est pourquoi le masquage de la latence était un mécanisme ajouté dans le jeu presque depuis l'introduction du multijoueur. Le masquage de la latence fonctionne en simulant l'entrée du joueur, sans tenir compte des actions des autres joueurs et sans tenir compte de l'arbitrage du serveur.

Dans Factorio, nous avons l'état du jeu, c'est l'état complet de la carte, le joueur, les droits, tout. Il est simulé de manière déterministe sur tous les clients en fonction des actions reçues du serveur. C'est sacré et s'il est différent du serveur ou de tout autre client, une désynchronisation se produit.

En plus de l'état du jeu, nous avons l'état de latence. Il contient un petit sous-ensemble de l'état principal. L'état de latence n'est pas sacré et représente simplement la façon dont nous pensons que l'état du jeu ressemblera à l'avenir en fonction des actions d'entrée effectuées par le joueur.

L'essentiel est que l'état de chaque objet soit immuable à la graduation spécifique de la ligne de temps . Tout dans l'état multijoueur mondial doit finalement converger vers une réalité déterministe.

Et - cela pourrait être la clé de votre question. L'état de chaque entité est immuable pour un tick donné, et vous gardez une trace des événements de transition qui produisent de nouvelles instances au fil du temps.

Si vous y réfléchissez, la file d'attente des événements entrants du serveur doit avoir accès à un répertoire central d'entités, juste pour pouvoir appliquer ses événements.

En fin de compte, vos méthodes de mutation à une ligne simples que vous ne voulez pas compliquer ne sont que simples parce que vous ne modélisez pas vraiment le temps avec précision. Après tout, si la santé peut changer au milieu de la boucle de traitement, les entités antérieures de cette coche verront une ancienne valeur, et les suivantes verront une valeur modifiée. Gérer cela avec soin signifie au moins différencier les états actuels (immuables) et suivants (en construction), qui ne sont en réalité que deux ticks dans la grande chronologie des ticks!

Donc, en tant que guide général, envisagez de briser l'état d'un monstre en un certain nombre de petits objets qui se rapportent, par exemple, à l'emplacement / la vitesse / la physique, la santé / les dommages, les actifs. Construisez un événement pour décrire chaque mutation qui pourrait se produire et exécutez votre boucle principale comme suit:

  1. traiter les entrées et générer les événements correspondants
  2. générer des événements internes (par exemple en raison de collisions d'objets, etc.)
  3. appliquer des événements aux monstres immuables actuels, pour générer de nouveaux monstres pour le prochain tick - la plupart du temps copier l'ancien état inchangé si possible, mais créer de nouveaux objets d'état si nécessaire.
  4. rendre et répéter pour le prochain tick.

Ou quelque chose comme ça. Je trouve penser "comment pourrais-je faire distribuer cela?" est un assez bon exercice mental, en général, pour affiner ma compréhension lorsque je ne sais pas où les choses vivent et comment elles devraient évoluer.

Grâce à une note de @ AaronM.Eshbach, soulignant qu'il s'agit d'un domaine de problème similaire à Event Sourcing et au modèle CQRS , où vous modélisez les changements d'état dans un système distribué comme une série d'événements immuables au fil du temps . Dans ce cas, nous essayons très probablement de nettoyer une application de base de données complexe, en séparant (comme son nom l'indique!) La gestion des commandes du mutateur du système de requête / vue. Plus complexe bien sûr, mais plus flexible.

SusanW
la source
2
Pour plus de référence, voir Event Sourcing et CQRS . Il s'agit d'un domaine de problème similaire: la modélisation change d'état dans un système distribué comme une série d'événements immuables au fil du temps.
Aaron M. Eshbach
@ AaronM.Eshbach c'est celui-là! Cela vous dérange si j'inclus vos commentaires / citations dans la réponse? Cela donne un son plus autoritaire. Merci!
SusanW
Bien sûr que non, veuillez le faire.
Aaron M. Eshbach
3

Vous êtes encore à moitié dans le camp impératif. Au lieu de penser à un seul objet à la fois, pensez à votre jeu en termes d'histoire de jeux ou d'événements

p1 - send m1 to battlefield
p2 - send m2 to battlefield
m1 - attacks m2 (2 dam)
m2 - attacks m1 (10 dam)
p1 - retreats m1

etc

Vous pouvez calculer l'état du jeu à tout moment en enchaînant les actions pour produire un objet d'état immuable. Chaque jeu est une fonction qui prend un objet d'état et renvoie un nouvel objet d'état

Ewan
la source