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

22

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?

gpuguy
la source
il y a une assez bonne discussion approfondie à ce sujet dans abelson & sussman, structure et interprétation des programmes informatiques
vzn

Réponses:

19

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 .

Uday Reddy
la source
Cela a beaucoup de sens pour moi. Merci de partager vos PPT. Partagez-vous également des enregistrements vidéo de la même chose?
gpuguy
@gpuguy. Je n'utilise pas beaucoup PowerPoint. Le tableau blanc est mon support préféré. Mais les documents devraient être tout à fait lisibles par eux-mêmes.
Uday Reddy
+1 Les mathématiques n'ont jamais fonctionné avec des objets de données mutables. Aussi le lien vers vos notes de cours.
Guy Coder
15

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.

Andrej Bauer
la source
alors qu'il a tant d'avantages, pourquoi ne pas utiliser également une structure de données persistante dans les langages impératifs?
gpuguy
4
Peut-être vous demanderez-vous bientôt "Pourquoi utiliser des langues impératives?"
Andrej Bauer
4
Mais sérieusement, il existe des infrastructures de données difficiles à remplacer par des infrastructures persistantes, par exemple les programmes de calcul de nombres qui utilisent des tableaux et des matrices sont beaucoup plus rapides avec les structures de données traditionnelles car le matériel est optimisé pour ce genre de chose.
Andrej Bauer
1
@gpuguy. Les structures de données persistantes peuvent et doivent également être utilisées dans les langages impératifs, chaque fois qu'elles sont applicables et appropriées. Pour pouvoir les utiliser, le langage doit prendre en charge la gestion de la mémoire basée sur le garbage collection. De nombreux langages modernes ont cela: Java, C #, Scala, Python, Ruby, Javascript etc.
Uday Reddy
Sans doute, un gros avantage est l'interface plus abstraite par rapport aux infrastructures de données mutables. Vous pouvez changer des choses sous le capot (cf immuabilité vs intégrité référentielle) mais pas besoin.
Raphael
2

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]ϕpϕq[P]

  • [P]P
  • ϕpϕq)pq

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.

afsantos
la source
2

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"

Thomas Klimpel
la source
@DW Vous avez probablement raison de dire que cette réponse n'est pas une réponse autonome. Elle ne s'étend actuellement que sur certains points soulevés dans les réponses d'Uday Reddy et Andrej Bauer. Je pense que je peux le modifier pour être autonome et répondre directement au "Je veux comprendre à un bas niveau ce qui se passerait si la structure des données n'est pas persistante?" partie de la question. Je regarderais 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 une structure de données, et expliquerais les choses qui peuvent mal tourner.
Thomas Klimpel
@DW Je pense qu'aucune des réponses à cette question ne répond vraiment à la question. En particulier, il n'y a pas grand-chose sur ce que sont réellement les structures de données persistantes (autres qu'immuables) et comment elles sont mises en œuvre.
Guildenstern