Pourquoi utilisons-nous des structures de données persistantes dans la programmation fonctionnelle?

La programmation fonctionnelle utilise des structures de données persistantes et des objets immuables. Ma question est pourquoi est-il crucial d'avoir de telles structures de données ici? Je veux comprendre à un bas niveau ce qui se passerait si la structure des données n'était pas persistante? Le programme planterait-il plus souvent?

Lorsque vous travaillez avec des objets de données immuables, les fonctions ont la propriété que chaque fois que vous les appelez avec les mêmes entrées, elles produisent les mêmes sorties. Cela facilite la conceptualisation des calculs et leur correction. Cela les rend également plus faciles à tester.

Ce n'est qu'un début. Étant donné que les mathématiques fonctionnent depuis longtemps avec les fonctions, il existe de nombreuses techniques de raisonnement que nous pouvons emprunter aux mathématiques et les utiliser pour un raisonnement rigoureux sur les programmes. L'avantage le plus important de mon point de vue est que les systèmes de types pour les programmes fonctionnels sont bien développés. Donc, si vous faites une erreur quelque part, les chances sont très élevées qu'elle apparaisse comme une incompatibilité de type. Ainsi, les programmes fonctionnels typés ont tendance à être beaucoup plus fiables que les programmes impératifs.

Lorsque vous travaillez avec des objets de données mutables, en revanche, vous devez d'abord avoir la charge cognitive de se souvenir et de gérer les multiples états traversés par l'objet pendant un calcul. Vous devez prendre soin de faire les choses dans le bon ordre, en vous assurant que toutes les propriétés dont vous avez besoin pour une étape particulière sont satisfaites à ce stade. Il est facile de commettre des erreurs et les systèmes de saisie ne sont pas assez puissants pour détecter ces erreurs.

Les mathématiques n'ont jamais fonctionné avec des objets de données mutables. Il n'y a donc aucune technique de raisonnement que nous puissions leur emprunter. Il existe de nombreuses techniques développées en informatique, en particulier Floyd-Hoare Logic . Cependant, celles-ci sont plus difficiles à maîtriser que les techniques mathématiques standard, la plupart des élèves ne peuvent pas les manipuler, et elles sont donc rarement enseignées.

Pour un aperçu rapide de la différence entre les deux paradigmes, vous pouvez consulter les premiers documents de mes notes de cours sur les principes des langages de programmation .

Il est plus facile de travailler correctement avec des structures de données persistantes que de travailler avec des structures de données mutables. C'est, je dirais, le principal avantage.

Bien sûr, théoriquement, tout ce que nous faisons avec des structures de données persistantes, nous pouvons également le faire avec des structures mutables, et vice versa. Dans de nombreux cas, les structures de données persistantes entraînent des coûts supplémentaires, généralement parce que certaines d'entre elles doivent être copiées. Ces considérations auraient rendu les structures de données persistantes beaucoup moins attrayantes il y a 30 ans, lorsque les superordinateurs avaient moins de mémoire que votre téléphone mobile. Mais de nos jours, les principaux goulots d'étranglement dans la production de logiciels semblent être le temps de développement et les coûts de maintenance. Nous sommes donc prêts à sacrifier une certaine efficacité dans l'exécution pour une efficacité dans le développement.

Pourquoi est-il plus facile d'utiliser des structures de données persistantes? Parce que les humains sont vraiment mauvais pour suivre l' aliasing et d'autres types d'interactions inattendues entre les différentes parties d'un programme. Ils pensent automatiquement cela parce que deux choses sont appelées xet yn'ont alors rien en commun. Après tout, il faut des efforts pour comprendre que "l'étoile du matin" et "l'étoile du soir" sont vraiment la même chose. De même, il est très facile d'oublier qu'une structure de données peut changer parce que d'autres threads fonctionnent avec elle, ou parce que nous avons appelé une méthode qui arrive à changer la structure de données, etc. Beaucoup de ces problèmes ne sont tout simplement pas présents lorsque nous travaillons avec structures de données persistantes.

Les structures de données persistantes présentent également d'autres avantages techniques. Il est généralement plus facile de les optimiser. Par exemple, vous êtes toujours libre de copier une structure de données persistante sur un autre nœud de votre cloud si vous le souhaitez, il n'y a aucun souci de synchronisation.

En ajoutant aux réponses des autres et en renforçant une approche mathématique, la programmation fonctionnelle a également une belle synergie avec l'algèbre relationnelle et Galois Connections.

Ceci est extrêmement utile dans le domaine des méthodes formelles.
Par exemple:

• Les preuves formelles dans la vérification de programme sont simplifiées avec la vérification statique étendue;
• Un certain nombre de propriétés de l'algèbre relationnelle sont utiles dans la résolution SAT, avec des outils tels que l'alliage;
• Galois Connections permet une approche calculatrice de la spécification logicielle, comme on le voit dans ce blog , avec une référence à un article , par Shin-Cheng Mu et José Nuno Oliveira.
• Les connexions Galois (et la programmation fonctionnelle) peuvent être utilisées de façon Design by Contract, car elles sont un concept plus général que Hoare Logic.

Exemple

$\{p\} P \{q\}$$[P] \cdot \phi_p \subseteq \phi_q \cdot [P]$

• $[P]$$P$
• $\phi_p$$\phi_q)$$p$$q$

Cette approche permet également un calcul de pré-condition et de post-condition le plus faible , ce qui est utile dans un certain nombre de situations.

Je veux comprendre à un bas niveau ce qui se passerait si la structure des données n'était pas persistante?

Regardons un générateur de nombres pseudo-aléatoires avec un immense espace d'état (comme " Twister Mersenne " avec un état de 2450 octets) comme structure de données. Nous ne voulons pas vraiment utiliser un nombre aléatoire plus d'une fois, donc il semble y avoir peu de raisons de l'implémenter comme une structure de données persistante immuable. Maintenant, demandons-nous ce qui pourrait mal se passer dans le code suivant:

mt_gen = CreateMersenneTwisterPRNGen(seed)
integral = MonteCarloIntegral_Bulk(mt_gen) + MonteCarloIntegral_Boundary(mt_gen)

La plupart des langages de programmation ne spécifient pas l'ordre dans lequel MonteCarloIntegral_Bulket MonteCarloIntegral_Boundaryseront évalués. Si les deux prennent une référence à un mt_gen mutable comme argument, le résultat de ce calcul peut dépendre de la plateforme. Pire encore, il peut y avoir des plates-formes où le résultat n'est pas du tout reproductible entre différentes exécutions.

On peut concevoir une structure de données mutable efficace pour mt_gen de telle sorte que tout entrelacement de l'exécution de MonteCarloIntegral_Bulket MonteCarloIntegral_Boundarydonnera un résultat "correct", mais un entrelacement différent conduira généralement à un résultat "correct" différent. Cette non-reproductibilité rend la fonction correspondante "impure" et entraîne également d'autres problèmes.

La non-reproductibilité peut être évitée en appliquant un ordre d'exécution séquentiel fixe. Mais dans ce cas, le code pourrait être organisé de telle sorte qu'une seule référence à mt_gen soit disponible à un moment donné. Dans un langage de programmation fonctionnel typé, des types d'unicité pourraient être utilisés pour imposer cette contrainte, permettant ainsi des mises à jour mutables sûres également dans le contexte de langages de programmation fonctionnels purs. Tout cela peut sembler agréable et dandy, mais au moins en théorie, les simulations de Monte-Carlo sont parallèlement embarrassantes, et notre «solution» vient de détruire cette propriété. Ce n'est pas seulement un problème théorique, mais un problème pratique très réel. Cependant, nous devons modifier (la fonctionnalité offerte par) notre générateur de nombres pseudo-aléatoires et la séquence de nombres aléatoires qu'il produit, et aucun langage de programmation ne peut le faire automatiquement pour nous. (Bien sûr, nous pouvons utiliser une autre bibliothèque de numéros pseudo-aléatoires qui offre déjà les fonctionnalités requises.)

À un faible niveau, les structures de données mutables conduisent facilement à la non-reproductibilité (et donc à l'impureté), si l'ordre d'exécution n'est pas séquentiel et fixe. Une stratégie impérative typique pour traiter ces problèmes consiste à avoir des phases séquentielles avec un ordre d'exécution fixe, au cours desquelles les structures de données mutables sont modifiées, et des phases parallèles avec un ordre d'exécution arbitraire, au cours desquelles toutes les structures de données mutables partagées restent constantes.

Andrej Bauer a soulevé la question de l'aliasing pour les structures de données mutables. Chose intéressante, différents langages impératifs comme Fortran et C ont des hypothèses différentes sur l'aliasing autorisé des arguments de fonction, et la plupart des programmeurs ne savent pas du tout que leur langage a un modèle d'aliasing.

L'immuabilité et la sémantique des valeurs peuvent être légèrement surévaluées. Ce qui est plus important, c'est que le système de type et le cadre logique (comme le modèle de machine abstraite, le modèle d'alias, le modèle de concurrence ou le modèle de gestion de la mémoire) de votre langage de programmation offrent un support suffisant pour travailler "en toute sécurité" avec des données "efficaces" structures. L'introduction de "déplacer la sémantique" dans C ++ 11 pourrait ressembler à un énorme pas en arrière en termes de pureté et de "sécurité" d'un point de vue théorique, mais en pratique, c'est le contraire. Le système de types et le cadre logique du langage ont été étendus pour éliminer d'énormes parties du danger associé à la nouvelle sémantique. (Et même s'il reste des bords rugueux, cela ne signifie pas que cela ne pourrait pas être amélioré par un "meilleur"

Uday Reddy a soulevé la question du fait que les mathématiques n'ont jamais fonctionné avec des objets de données mutables et que les systèmes de types pour les programmes fonctionnels sont bien développés pour les objets de données immuables. Cela m'a rappelé l'explication de Jean-Yves Girard selon laquelle les mathématiques ne sont pas utilisées pour travailler avec des objets changeants, lorsqu'il essaie de motiver la logique linéaire.

On pourrait se demander comment étendre le système de types et le cadre logique des langages de programmation fonctionnels pour permettre de travailler "en toute sécurité" avec des structures de données mutantes "efficaces" non persistantes. Un problème ici pourrait être que la logique classique et les algèbres booléennes pourraient ne pas être le meilleur cadre logique pour travailler avec des structures de données mutables. Peut-être que la logique linéaire et les monoïdes commutatifs pourraient être mieux adaptés à cette tâche? Peut-être devrais-je lire ce que Philip Wadler a à dire sur la logique linéaire comme système de type pour les langages de programmation fonctionnels? Mais même si la logique linéaire ne devrait pas être en mesure de résoudre ce problème, cela ne signifie pas que le système de type et le cadre logique d'un langage de programmation fonctionnel ne pourraient pas être étendus pour permettre "sûr" et "efficace"