L'immuabilité dans la programmation fonctionnelle existe-t-elle vraiment?

Bien que je travaille en tant que programmeur dans ma vie quotidienne et que j'utilise tous les langages à la mode (Python, Java, C, etc.), je n'ai toujours pas de vision claire de ce qu'est la programmation fonctionnelle. D'après ce que j'ai lu, une propriété des langages fonctionnels est que les structures de données sont immuables . Pour moi, cela soulève à lui seul beaucoup de questions. Mais d'abord, j'écrirai un peu ce que je comprends de l'immuabilité et si je me trompe, n'hésitez pas à me corriger.

Ma compréhension de l'immuabilité:

• Lorsqu'un programme démarre, il a des structures de données fixes avec des données fixes
• On ne peut pas ajouter de nouvelles données à ces structures
• Il n'y a pas de variables dans le code
• Vous pouvez simplement "copier" à partir des données déjà ou des données actuellement calculées
• En raison de tout ce qui précède, l'immuabilité ajoute une énorme complexité d'espace à un programme

Mes questions:

1. Si les structures de données sont censées rester telles quelles (immuables), comment diable peut-on ajouter un nouvel élément dans une liste?
2. Quel est l'intérêt d'avoir un programme qui ne peut pas obtenir de nouvelles données? Supposons que vous disposez d'un capteur connecté à votre ordinateur qui souhaite alimenter le programme en données. Cela signifierait-il que nous ne pouvons stocker les données entrantes nulle part?
3. En quoi la programmation fonctionnelle est-elle bonne pour l'apprentissage automatique dans ce cas? Étant donné que l'apprentissage automatique repose sur l'hypothèse d'une mise à jour de la "perception" des choses par le programme - stockant ainsi de nouvelles données.

Lorsqu'un programme démarre, il a des structures de données fixes avec des données fixes

C'est un peu une idée fausse. Il a une forme fixe et un ensemble fixe de règles de réécriture, mais ces règles de réécriture peuvent exploser en quelque chose de beaucoup plus grand. Par exemple, l'expression [1..100000000] dans Haskell est représentée par une très petite quantité de code mais sa forme normale est massive.

On ne peut pas ajouter de nouvelles données à ces structures

Oui et non. Le sous-ensemble purement fonctionnel d'un langage comme Haskell ou ML ne peut pas obtenir de données du monde extérieur, mais tout langage de programmation pratique dispose d'un mécanisme pour insérer des données du monde extérieur dans le sous-ensemble purement fonctionnel. À Haskell, cela se fait très soigneusement, mais en ML, vous pouvez le faire quand vous le souhaitez.

Il n'y a pas de variables dans le code

C'est à peu près vrai, mais ne confondez pas cela avec l'idée que rien ne peut être nommé. Vous nommez constamment des expressions utiles et les réutilisez constamment. Aussi bien ML que Haskell, tous les Lisp que j'ai essayés, et les hybrides comme Scala, ont tous un moyen de créer des variables. Ils ne sont tout simplement pas couramment utilisés. Et encore une fois, les sous-ensembles purement fonctionnels de ces langages n'en ont pas.

Vous pouvez simplement "copier" à partir des données déjà ou des données actuellement calculées

Vous pouvez effectuer le calcul par réduction à la forme normale. La meilleure chose à faire est probablement d'aller écrire des programmes dans un langage fonctionnel pour voir comment ils effectuent en fait les calculs.

Par exemple, "sum [1..1000]" n'est pas un calcul que je veux effectuer, mais il est assez facilement réalisé par Haskell. Nous lui avons donné une petite expression qui avait du sens pour nous et Haskell nous a donné le numéro correspondant. Il effectue donc définitivement le calcul.

Si les structures de données sont censées rester telles quelles (immuables), comment diable peut-on ajouter un nouvel élément dans une liste?

Vous n'ajoutez pas un nouvel élément à une liste, vous créez une nouvelle liste à partir de l'ancien. Parce que l'ancien ne peut pas être muté, il est parfaitement sûr de l'utiliser dans la nouvelle liste, ou partout où vous le souhaitez. Beaucoup plus de données peuvent être partagées en toute sécurité dans ce schéma.

Quel est l'intérêt d'avoir un programme qui ne peut pas obtenir de nouvelles données? Supposons que vous disposez d'un capteur connecté à votre ordinateur qui souhaite alimenter le programme en données. Cela signifierait-il que nous ne pouvons stocker les données entrantes nulle part?

En ce qui concerne l'entrée utilisateur, tout langage de programmation pratique a un moyen d'obtenir une entrée utilisateur. Ça arrive. Cependant, il existe un sous-ensemble entièrement fonctionnel de ces langages dans lequel vous écrivez la plupart de votre code et vous en récoltez les avantages de cette manière.

En quoi la programmation fonctionnelle est-elle bonne pour l'apprentissage automatique dans ce cas? Étant donné que l'apprentissage automatique repose sur l'hypothèse d'une mise à jour de la "perception" des choses par le programme - stockant ainsi de nouvelles données.

Ce serait le cas pour l'apprentissage actif, mais la plupart des apprentissages automatiques avec lesquels j'ai travaillé (je travaille en tant que singe code dans un groupe d'apprentissage automatique et le fais depuis quelques années) ont un processus d'apprentissage unique où toutes les données de formation sont chargées. à la fois. Mais pour un apprentissage actif, vous ne pouvez pas faire les choses à 100% de manière purement fonctionnelle. Vous allez devoir lire certaines données du monde extérieur.

L'immuabilité ou la mutabilité ne sont pas des concepts qui ont du sens dans la programmation fonctionnelle.

Le contexte informatique

C'est une très bonne question qui est une suite intéressante (pas un doublon) à une autre récente: quelle est la différence entre l'affectation, l'évaluation et la liaison de nom?

Plutôt que de répondre à vos déclarations une par une, j'essaie ici de vous donner un aperçu structuré de ce qui est en jeu.

Il y a plusieurs questions à considérer pour vous répondre, notamment:

• Qu'est-ce qu'un modèle de calcul et quels concepts ont du sens pour un modèle donné

• Quelle est la signification des mots que vous utilisez et comment cela dépend-il du contexte

Le style de programmation fonctionnel semble idiot parce que vous le voyez avec un œil de programmeur impératif. Mais c'est un paradigme différent, et vos concepts impératifs et votre perception sont étrangers, hors de propos. Les compilateurs n'ont pas de tels préjugés.

Mais la conclusion finale est qu'il est possible d'écrire des programmes de manière purement fonctionnelle, y compris pour l'apprentissage automatique, la programmation fonctionnelle pensée n'ayant pas le concept de stockage de données. Je semble être en désaccord sur ce point avec d'autres réponses.

Dans l'espoir que certains seront intéressés malgré la longueur de cette réponse.

Paradigmes informatiques

La question porte sur la programmation fonctionnelle (aka programmation applicative), un modèle de calcul spécifique, dont le représentant théorique et le plus simple est le calcul lambda.

Si vous restez à un niveau théorique, il existe de nombreux modèles de calcul: la machine de Turing (TM), la machine RAM et autres , le calcul lambda, la logique combinatoire, la théorie des fonctions récursives, les systèmes semi-Thue, etc. Le calcul le plus puissant les modèles se sont révélés équivalents en termes de ce qu'ils peuvent aborder, et c'est l'essentiel de la thèse Church-Turing .

Un concept important consiste à réduire les modèles les uns aux autres, ce qui est la base pour établir les équivalences qui conduisent à la thèse de Church-Turing. Du point de vue des programmeurs, la réduction d'un modèle à un autre est à peu près ce qu'on appelle généralement un compilateur. Si vous prenez la programmation logique comme modèle de calcul, il est assez différent du modèle fourni par le PC que vous avez acheté dans un magasin, et le compilateur traduit les programmes écrits en langage de programmation logique dans le modèle de calcul représenté par votre PC (à peu près l'ordinateur RAM).

$\beta$

Dans la pratique, les langages de programmation que nous utilisons ont tendance à mélanger des concepts d'origines théoriques différentes, essayant de le faire afin que des parties sélectionnées d'un programme puissent bénéficier des propriétés de certains modèles, le cas échéant. De même, les personnes qui construisent des systèmes peuvent choisir différentes langues pour différents composants, afin de les adapter au mieux à la tâche à accomplir.

Par conséquent, vous voyez rarement un paradigme de programmation à l'état pur dans un langage de programmation. Les langages de programmation sont toujours classés selon le paradigme dominant, mais les propriétés du langage peuvent être affectées lorsque des concepts d'autres paradigmes sont impliqués, brouillant souvent les distinctions et les problèmes conceptuels.

Typiquement, les langages comme Haskell et ML ou CAML sont considérés comme fonctionnels, mais ils peuvent permettre un comportement impératif ... Sinon pourquoi parlerait-on du " sous-ensemble purement fonctionnel "?

On peut alors prétendre que, vous pouvez faire ceci ou cela dans mon langage de programmation fonctionnelle, mais cela ne répond pas vraiment à une question sur la programmation fonctionnelle quand elle s'appuie sur ce qui peut être considéré comme extra-fonctionnel.

Les réponses devraient être plus précisément liées à un paradigme spécifique, sans les extras.

Qu'est-ce qu'une variable?

Un autre problème est l'utilisation de la terminologie. En mathématiques, une variable est une entité qui représente une valeur indéterminée dans un domaine. Il est utilisé à diverses fins. Utilisé dans une équation, il peut représenter n'importe quelle valeur telle que l'équation soit vérifiée. Cette vision est utilisée dans la programmation logique sous le nom de " variable logique ", probablement parce que la variable de nom avait déjà une autre signification lors du développement de la programmation logique.

Dans la programmation impérative traditionnelle, une variable est comprise comme une sorte de conteneur (ou emplacement de mémoire) qui peut mémoriser la représentation d'une valeur, et éventuellement obtenir sa valeur actuelle remplacée par une autre).

En programmation fonctionnelle, une variable a le même objectif en mathématiques qu'un espace réservé pour une certaine valeur, à fournir. Dans la programmation impérative traditionnelle, ce rôle est en fait joué par la constante (à ne pas confondre avec les littéraux qui sont des valeurs déterminées exprimées avec une notation spécifique à ce domaine de valeurs, comme 123, true, ["abdcz", 3.14]).

Les variables de toute nature, ainsi que constantes, peuvent être représentées par des identifiants.

La variable impérative peut voir sa valeur modifiée et c'est la base de la mutabilité. La variable fonctionnelle ne peut pas.

Les langages de programmation permettent généralement de créer des entités plus grandes à partir des plus petites du langage.

Les langages impératifs permettent à ces constructions d'inclure des variables et c'est ce qui vous donne des données mutables.

Comment lire un programme

Un programme est fondamentalement une description abstraite de votre algorithme. Il s'agit d'un langage, qu'il s'agisse d'une conception pragmatique ou d'un langage paradigmatiquement pur.

En principe, vous pouvez prendre chaque déclaration pour ce qu'elle est censée signifier de manière abstraite. Ensuite, le compilateur traduira cela sous une forme appropriée pour que l'ordinateur l'exécute, mais ce n'est pas votre problème en première approximation.

Bien sûr, la réalité est un peu plus dure, et il est souvent bon d'avoir une idée de ce qui se passe afin d'éviter les structures que le compilateur ne saura pas gérer pour une exécution efficace. Mais c'est déjà de l'optimisation ... pour laquelle les compilateurs peuvent être très bons, souvent meilleurs que les programmeurs.

Programmation fonctionnelle et mutabilité

La mutabilité est basée sur l'existence de variables impératives pouvant contenir des valeurs, à modifier par affectation. Comme ceux-ci n'existent pas dans la programmation fonctionnelle, tout peut être considéré comme immuable.

La programmation fonctionnelle porte exclusivement sur les valeurs.

Vos quatre premières déclarations sur l'immuabilité sont pour la plupart correctes, mais décrivent avec une vue impérative quelque chose qui n'est pas impératif. C'est un peu comme décrire avec des couleurs dans un monde où tout le monde est aveugle. Vous utilisez des concepts étrangers à la programmation fonctionnelle.

Vous n'avez que des valeurs pures et un tableau d'entiers est une valeur pure. Pour obtenir un autre tableau qui ne diffère que par un élément, vous devez utiliser une valeur de tableau différente. Changer un élément n'est qu'un concept qui n'existe pas dans ce contexte. Vous pouvez avoir une fonction qui a un tableau et certains indices comme argument, et renvoie un résultat qui est un tableau presque identique qui ne diffère que là où indiqué par les indices. Mais c'est toujours une valeur de tableau indépendante. Comment ces valeurs sont-elles représentées n'est pas votre problème. Peut-être qu'ils "partagent" beaucoup la traduction impérative pour l'ordinateur ... mais c'est le travail du compilateur ... et vous ne voulez même pas savoir pour quel type d'architecture de machine il compile.

Vous ne copiez pas de valeurs (cela n'a aucun sens, c'est un concept étranger). Vous utilisez simplement des valeurs qui existent dans les domaines que vous avez définis dans votre programme. Soit vous les décrivez (comme des littéraux), soit ils sont le résultat de l'application d'une fonction à d'autres valeurs. Vous pouvez leur donner un nom (définissant ainsi une constante) pour vous assurer que la même valeur est utilisée à différents endroits du programme. Notez que l'application de fonction ne doit pas être perçue comme un calcul mais comme le résultat de l'application aux arguments donnés. Écrire 5+2ou écrire 7revient au même. Ce qui est conforme au paragraphe précédent.

Il n'y a pas de variables impératives. Aucune affectation n'est possible. Vous ne pouvez lier des noms qu'à des valeurs (pour former des constantes), contrairement aux langages impératifs où vous pouvez lier des noms à des variables assignables.

Il est difficile de savoir si cela a un coût en complexité. D'une part, vous faites référence à la complexité concerne les paradigmes impératifs. Il n'est pas défini comme tel pour la programmation fonctionnelle, sauf si vous choisissez de lire votre programme fonctionnel comme un impératif, ce qui n'est pas l'intention du concepteur. En effet, la vue fonctionnelle est conçue pour vous permettre de ne pas vous soucier de ces problèmes et de vous concentrer sur ce qui est calculé. C'est un peu comme la spécification par rapport à l'implémentation.

Le compilateur doit prendre en charge l'implémentation et être suffisamment intelligent pour adapter au mieux ce qui doit être fait au matériel qui le fera, quel qu'il soit.

Je ne dis pas que les programmeurs ne s'en soucient jamais. Je ne dis pas non plus que les langages de programmation et la technologie des compilateurs sont aussi matures que nous le souhaiterions.

Répondre aux questions

1. Vous ne modifiez pas la valeur existante (concept extraterrestre), mais calculez de nouvelles valeurs qui diffèrent où vous le souhaitez, éventuellement en ayant un élément supplémentaire, il s'agit d'une liste.

2. Le programme peut obtenir de nouvelles données. L'essentiel est de savoir comment vous exprimez cela dans la langue. Vous pouvez par exemple considérer que le programme fonctionne avec une valeur spécifique, éventuellement sans limite de taille, qui est appelée le flux d'entrée. C'est une valeur qui est censée être là (si elle est déjà pleinement connue ou non n'est pas votre problème). Ensuite, vous avez une fonction qui renvoie une paire composée du premier élément du flux et du reste du flux.

   Vous pouvez l'utiliser pour construire des réseaux de composants communicants de manière purement applicative (coroutines)

3. L'apprentissage automatique n'est qu'un autre problème lorsque vous devez augmenter les données et modifier les valeurs. En programmation fonctionnelle, vous ne le faites pas: vous calculez simplement de nouvelles valeurs qui diffèrent de manière appropriée en fonction des données d'entraînement. La machine résultante fonctionnera également. Ce qui vous préoccupe, c'est le temps de calcul et l'efficacité de l'espace. Mais, encore une fois, c'est un problème différent, qui devrait idéalement être traité par le compilateur.

Remarques finales

Il est assez clair, d'après les commentaires ou les autres réponses, que les langages de programmation fonctionnels pratiques ne sont pas purement fonctionnels. C'est une réflexion sur le fait que notre technologie doit encore être améliorée, surtout en ce qui concerne la compilation.

Est-il possible d'écrire dans un style purement applicatif? La réponse est connue depuis environ 40 ans et c'est "oui". Le but même de la sémantique dénotationnelle telle qu'elle est apparue dans les années 1970 était précisément de traduire (compiler) les langues dans un style purement fonctionnel, jugé mieux compris mathématiquement et donc considéré comme une meilleure fondation pour définir la sémantique des programmes.

L'aspect intéressant est que la structure de programmation impérative, y compris les variables, peut être traduite en un style fonctionnel en introduisant des domaines de valeurs appropriés, comme un magasin de données. Et malgré le style fonctionnel, il reste étonnamment similaire au code des compilateurs réels écrits dans un style impératif.

C'est une idée fausse que les programmes fonctionnels ne peuvent pas stocker de données, et je ne pense pas que la réponse de Jakes ait vraiment expliqué cela très bien.

Les programmes fonctionnels sont, comme tous les programmes, des fonctions vraiment mappant des entiers à des entiers. Tout programme impératif fonctionnant sur des structures de données mutables a un équivalent fonctionnel. C'est juste un autre moyen d'atteindre le même but.

La façon fonctionnelle de stocker des données d'expérience à partir d'une source serait d'appeler la fonction de stockage avec la structure de données comme argument et de produire une concaténation de la structure de données existante et des nouvelles données et donc les données sont stockées sans la notion de structures de données mutables.

D'après ma propre expérience , je pense que le concept de structures de données immuables conduit les développeurs conventionnels à penser qu'il y a certaines choses qui sont peu pratiques ou même impossibles à faire dans un cadre fonctionnel. Ce n'est pas le cas.