En programmation fonctionnelle, la plupart des structures de données immuables nécessitent-elles davantage d’utilisation de la mémoire?

En programmation fonctionnelle, étant donné que presque toutes les structures de données sont immuables, lorsque l’état doit changer, une nouvelle structure est créée. Est-ce que cela signifie beaucoup plus d'utilisation de la mémoire? Je connais bien le paradigme de la programmation orientée objet, maintenant j'essaie de mieux comprendre le paradigme de la programmation fonctionnelle. Le concept de tout être immuable me confond. Il semblerait qu'un programme utilisant des structures immuables nécessite beaucoup plus de mémoire qu'un programme avec des structures mutables. Est-ce que je regarde ça de la bonne façon?

La seule réponse correcte à cette question est "parfois". Les langages fonctionnels peuvent utiliser beaucoup d’astuces pour éviter le gaspillage de mémoire. L'immuabilité facilite le partage des données entre les fonctions, et même entre les structures de données, car le compilateur peut garantir que les données ne seront pas modifiées. Les langages fonctionnels ont tendance à encourager l'utilisation de structures de données pouvant être utilisées efficacement en tant que structures immuables (par exemple, des arbres au lieu de tables de hachage). Si vous ajoutez de la paresse dans le mélange, comme le font de nombreux langages fonctionnels, cela ajoute de nouvelles façons d'économiser de la mémoire (cela ajoute également de nouvelles façons de gaspiller de la mémoire, mais je ne vais pas entrer dans cela).

En programmation fonctionnelle, étant donné que presque toutes les structures de données sont immuables, lorsque l’état doit changer, une nouvelle structure est créée. Est-ce que cela signifie beaucoup plus d'utilisation de la mémoire?

Cela dépend de la structure des données, des modifications exactes effectuées et, dans certains cas, de l'optimiseur. A titre d'exemple, considérons l'ajout au début d'une liste:

list2 = prepend(42, list1) // list2 is now a list that contains 42 followed
                           // by the elements of list1. list1 is unchanged

Ici, les besoins en mémoire supplémentaires sont constants, de même que le coût d’appel à l’exécution prepend. Pourquoi? Parce prependque crée simplement une nouvelle cellule qui a 42pour tête et list1pour queue. Pour ce faire, il n'est pas nécessaire de copier ou d'itérer autrement list2. Autrement dit, à l'exception de la mémoire requise pour le stockage 42, list2réutilise la même mémoire que celle utilisée par list1. Les deux listes étant immuables, ce partage est parfaitement sécurisé.

De même, lorsque vous travaillez avec des structures arborescentes équilibrées, la plupart des opérations ne nécessitent qu'une quantité logarithmique d'espace supplémentaire car tout, à l'exception d'un seul chemin, peut être partagé.

Pour les tableaux, la situation est un peu différente. C'est pourquoi, dans de nombreuses langues de PF, les tableaux ne sont pas utilisés couramment. Cependant, si vous faites quelque chose comme arr2 = map(f, arr1)et que vous arr1ne l'utilisez plus après cette ligne, un optimiseur intelligent peut en réalité créer du code qui mute arr1au lieu de créer un nouveau tableau (sans affecter le comportement du programme). Dans ce cas, la performance sera comme dans une langue impérative bien sûr.

Les implémentations naïves exposeraient effectivement ce problème: lorsque vous créez une nouvelle structure de données au lieu de mettre à jour une structure existante sur place, vous devez supporter un temps système supplémentaire.

Différentes langues ont différentes façons de gérer cela, et la plupart d'entre elles utilisent quelques astuces.

Une stratégie est la collecte des ordures . À partir du moment où la nouvelle structure a été créée ou peu de temps après, les références à l’ancienne structure sortent du domaine, et le ramasse-miettes la détecte instantanément ou assez tôt, en fonction de l’algorithme du GC. Cela signifie que, même s'il y a toujours une surcharge, celle-ci n'est que temporaire et ne croîtra pas de manière linéaire avec la quantité de données.

Un autre choix consiste à sélectionner différents types de structures de données. Lorsque les tableaux constituent la structure de données de liste idéale dans les langages impératifs (généralement enveloppés dans une sorte de conteneur de réallocation dynamique, comme std::vectoren C ++), les langages fonctionnels préfèrent souvent les listes chaînées. Avec une liste chaînée, une opération de préposition ('inconvénients') peut réutiliser la liste existante en tant que fin de la nouvelle liste, de sorte que tout ce qui est réellement alloué est la nouvelle tête de liste. Des stratégies similaires existent pour d'autres types de structures de données - ensembles, arbres, vous l'appelez.

Et puis il y a l'évaluation paresseuse, à la Haskell. L'idée est que les structures de données que vous créez ne sont pas entièrement créées immédiatement. au lieu de cela, ils sont stockés en tant que "thunks" (vous pouvez les considérer comme des recettes permettant de construire la valeur lorsque cela est nécessaire). Ce n'est que lorsque la valeur est nécessaire que le thunk est développé en une valeur réelle. Cela signifie que l’allocation de mémoire peut être différée jusqu’à ce que l’évaluation soit nécessaire. À ce stade, plusieurs thunks peuvent être combinés dans une allocation de mémoire.

Je connais seulement un peu Clojure et ses structures de données immuables .

Clojure fournit un ensemble de listes, de vecteurs, d’ensembles et de cartes immuables. Comme ils ne peuvent pas être modifiés, «ajouter» ou «supprimer» quelque chose d'une collection immuable signifie créer une nouvelle collection, tout comme l'ancienne, mais avec le changement nécessaire. La persistance est un terme utilisé pour décrire la propriété dans laquelle l'ancienne version de la collection est toujours disponible après le «changement» et que la collection conserve ses garanties de performances pour la plupart des opérations. En particulier, cela signifie que la nouvelle version ne peut pas être créée à l'aide d'une copie complète, car cela nécessiterait un temps linéaire. Inévitablement, les collections persistantes sont mises en œuvre à l'aide de structures de données liées, de sorte que les nouvelles versions puissent partager la structure avec la version précédente.

Graphiquement, nous pouvons représenter quelque chose comme ceci:

(def my-list '(1 2 3))

    +---+      +---+      +---+
    | 1 | ---> | 2 | ---> | 3 |
    +---+      +---+      +---+

(def new-list (conj my-list 0))

              +-----------------------------+
    +---+     | +---+      +---+      +---+ |
    | 0 | --->| | 1 | ---> | 2 | ---> | 3 | |
    +---+     | +---+      +---+      +---+ |
              +-----------------------------+

Outre ce qui a été dit dans d’autres réponses, je voudrais mentionner le langage de programmation Clean, qui prend en charge les types dits uniques . Je ne connais pas ce langage, mais je suppose que des types uniques prennent en charge une sorte de "mise à jour destructive".

En d'autres termes, alors que la sémantique de la mise à jour d'un état est que vous créez une nouvelle valeur à partir d'une ancienne en appliquant une fonction, la contrainte d'unicité peut permettre au compilateur de réutiliser des objets de données en interne car il sait que l'ancienne valeur ne sera pas référencée. plus dans le programme après que la nouvelle valeur a été produite.

Pour plus de détails, voir par exemple la page d'accueil de Clean et cet article de Wikipédia.