Programmation fonctionnelle: immuabilité etc.

Question

J'ai récemment posé une question sur la programmation fonctionnelle, et reçu (bon!) réponses qui ont suscité plus de questions (comme cela semble être le cas avec l'apprentissage, parfois). Voici des exemples de couple:

1. Une réponse fait référence à un avantage de structures de données immuables: chaque thread peut avoir sa propre copie. Maintenant, pour moi, cela ressemble plutôt à un système de contrôle de version (pour utiliser une analogie), où au lieu du code de verrouillage que quelqu'un a vérifié de sorte qu'il ne peut être modifié par quelqu'un d'autre, tout le monde peut vérifier leurs propres copies. Ça m'a l'air bien. Cependant, dans VCS vous avez le concept de changements « fusion », dans le cas où deux personnes ont changé de la même chose. Il semble que cette question pourrait certainement arriver dans un scénario multithread ... alors comment est « fusion » fait quand il est important que les discussions voir les données les plus récentes?

2. Cette réponse a parlé de cas où des opérations étaient réalisée dans une boucle sur un objet, et comment vous pouvez utiliser un nouvel objet à chaque fois par la mise à jour au lieu d'un ancien. Cependant, disons que la mise à jour est bankAccount dans un scénario non-boucle - par exemple un système bancaire GUI. L'opérateur clique sur le bouton « Modifier taux d'intérêt », ce qui déclenche un événement qui (en C # par exemple) faire quelque chose comme bankAccount.InterestRate = newRateFromUser. Je sens que je suis être dense ici, mais nous espérons que mon exemple est logique: il doit y avoir une certaine façon que l'objet est mis à jour, non? Plusieurs autres peuvent dépendre des nouvelles données.

Quoi qu'il en soit, si vous pouvez me aider à tête autour du changement de paradigme, je serais reconnaissant. Je me souviens que mon cerveau en passant par « phases stupides » similaires lors de l'apprentissage POO après un arrière-plan de l'approche simple impératif procédurale de codage.

Answer 1

Réponse à la partie 1: Les objets non modifiables ne le font pas par eux-mêmes soutenir quelque chose comme « fusion » pour permettre aux résultats des mises à jour de deux fils à combiner. Il existe deux grandes stratégies pour que: le pessimiste et l'optimiste. Si vous êtes pessimiste, vous assumez il est fort probable que deux threads veulent mettre à jour le même morceau de données en même temps. Donc, vous employez de verrouillage, de sorte que le second thread geler jusqu'à ce que le premier fil dit qu'il a terminé. Si vous êtes optimiste que cela se produira que rarement, vous laissez les deux fils travaillent sur leur propre copie logique des données. Celui qui termine première fournit la nouvelle version, et l'autre doit recommencer depuis le début - que maintenant il commence à partir des résultats des changements du premier fil. Cette remise en route cher ne se produit que de temps en temps, donc sur tout ce qu'il fonctionne mieux en raison de l'absence de verrouillage (bien que cela soit vrai que si votre optimisme était bien placé sur la façon rarement un choc se produit).

Partie 2: langues sans état fonctionnel pur n'éliminent pas vraiment ce problème. Même un programme pur Haskell peut avoir l'état associé. La différence est que le code stateful a un type de retour différent. Une fonction qui manipule l'état est exprimé comme une séquence d'opérations qui fonctionnent sur un objet représentant cet état. Dans un exemple absurde, considérez le système de fichiers de l'ordinateur. Chaque fois qu'un programme modifie le contenu d'un fichier (même par un seul octet), il a créé une nouvelle « version » de l'ensemble du système de fichiers. Et par extension, une nouvelle version de l'univers entier. Mais concentrons-nous sur le système de fichiers pour l'instant. Toute autre partie du programme qui examine le système de fichiers peut maintenant être affecté par cet octet modifié. Ainsi, Haskell dit que les fonctions d'exploitation sur le système de fichiers doit passer efficacement autour d'un objet représentant une version du système de fichiers. Ensuite, parce que ce serait fastidieux de traiter manuellement, il se l'exigence intérieur et dit que si une fonction veut être en mesure de faire IO, il doit retourner une sorte d'objet conteneur. A l'intérieur du conteneur est la valeur la fonction veut revenir. Mais le récipient sert de preuve que la fonction soit aussi a des effets secondaires ou peut voir les effets secondaires. Cela signifie que le système de type de Haskell est capable de faire la distinction entre les fonctions-avec-effets secondaires et les fonctions « pures ». Ainsi, il aide à contenir et à gérer le statefulness de code, sans vraiment l'éliminer.

Answer 2

Pensez à la classe String dans Net (qui est un objet immuable). Si vous appelez une méthode sur une chaîne, vous obtenez une nouvelle copie:

String s1 = "there";
String s2 = s1.Insert(0, "hello ");

Console.Writeline("string 1: " + s1);
Console.Writeline("string 2: " + s2);

Affichera:

string 1: il y a

string 2: bonjour il y a

Comparer ce comportement à StringBuilder, qui a essentiellement la même signature:

StringBuilder sb  = new StringBuilder("there");
StringBuilder sb2 = sb.Insert(0, "hi ");

Console.WriteLine("sb 1: " + sb.ToString());
Console.WriteLine("sb 2: " + sb2.ToString());

Parce que StringBuilder est mutable, les deux variables pointent vers le même objet. La sortie sera:

sb 1: Salut à

sb 2: Salut à

Donc, vous ne pouvez absolument pas changer une chaîne une fois que vous avez créé. s1 sera toujours « là » jusqu'à la fin du temps (ou jusqu'à ce que ses déchets collectés). Ce qui est important dans le filetage parce que vous pouvez toujours parcourir chaque caractère et imprimer sa valeur en sachant que ce sera toujours imprimer « là ». Si vous avez commencé l'impression StringBuilder après sa création, vous pouvez imprimer les deux premiers caractères de là et get'th. Maintenant, imaginez un autre thread vient insertion d'encarts publicitaires de la salut. La valeur est maintenant différente! Lorsque vous imprimez le troisième caractère, il est l'espace de « salut ». Donc, vous imprimez:. 'E il'

Answer 3

En ce qui concerne # 2 ...

  

Plusieurs autres peuvent dépendre de la   les nouvelles données.

est ce que les puristes appellent un « effet ». La notion de multiples références d'objet au même objet mutable est l'essence même de l'Etat mutable et le nœud de la question. En POO, vous pouvez avoir un objet « un » de type BankAccount, et si vous lisez a.Balance ou autres joyeusetés à différents fois vous pouvez voir des valeurs différentes. En revanche, dans FP pur, si « a » est de type BankAccount, il est immuable et a la même valeur quel que soit le temps.

Depuis cependant un BankAccount est sans doute un objet que nous voulons modéliser dont l'état ne varie avec le temps, nous en FP encode cette information dans le type. Donc, « a » peut-être de type « IO BankAccount », ou un autre type monadique qui se résume essentiellement à faire « un » être en fait une fonction qui prend en entrée « l'état précédent du monde » (ou état précédent des taux d'intérêt bancaires , ou autre), et retourne un nouvel état du monde. Mise à jour du taux d'intérêt serait une autre opération avec un type qui représente l'effet (par exemple, une autre opération IO), et serait donc revenir un nouveau « monde », et tout ce qui peut dépendre du taux d'intérêt (Etat mondial) serait données avec type qui sait qu'il doit prendre ce monde comme entrée.

Par conséquent, la seule façon possible d'appeler « a.Balance » ou tout le reste est d'utiliser le code qui, grâce aux types statiques, impose que certains « l'histoire du monde qui nous a jusqu'à présent » a été correctement sondé à le point de l'appel, et quel que soit l'histoire du monde est l'entrée affecte ce résultat que nous obtiendrons de a.Balance.

Lecture sur le Etat Monad peut être utile d'avoir une idée de la façon dont vous le modèle « partagé état mutable » purement.

Answer 4

1. structures de données Immuable ne sont pas comme VCS. Pensez à une structure de données Immuable en tant que fichier en lecture seule. Si sa lecture seule, peu importe qui est en train de lire la partie du fichier à un moment donné, tout le monde va lire les informations correctes.

2. Cette réponse parle http://en.wikipedia.org/ wiki / Monad_ (functional_programming)

Answer 5

MVCC ( multiversion Contrôle d'accès simultané )

La solution pour le problème que vous faites référence est décrit par Rich Hickey dans son présentations vidéo .

En bref : au lieu de transmettre les données par référence directement aux clients, vous ajoutez un niveau plus sur indirection et passez la référence à la référence aux données. ( Eh bien, vous voulez réellement avoir au moins un niveau plus de indirection. Mais supposons que la structure de données est très simple, comme le « tableau ». )
Étant donné que les données sont immuables, chaque fois que les données doivent être modifiées, vous créez la copie de la partie modifiée ( dans le cas du tableau, vous devez créer un autre tableau! ) plus vous créez une autre référence à tous les « changé » les données.
Donc, pour tous les clients qui ont utilisé la 1ère version du tableau, ils utilisent la référence à la première version. Chaque client tente d'accéder à la version 2 utilise la deuxième référence.
La structure de données « tableau » est pas très intéressant pour cette méthode, parce que vous ne pouvez pas partager les données et vous êtes obligé de tout copier. Mais pour les structures de données plus sophistiquées comme les arbres, certaines parties de la structure de données peuvent être « partagées », de sorte que vous n'êtes pas obligé de copier tout à chaque fois.

Pour plus de détails s'il vous plaît jeter un oeil à cet article: » purement Structures de données fonctionnelles " par Chris Okasaki.

Answer 6

"Immuable" signifie exactement cela:. Il ne change pas

La façon dont les programmes fonctionnels font des mises à jour est en passant autour de nouvelles choses. Une valeur existante ne change jamais: vous venez de construire une nouvelle valeur et passer au lieu. Très souvent, les actions nouvelles de valeur Etat avec l'ancien; de bons exemples de la technique sont des listes composées de cellules contre, et le fermeture éclair .