Tous les langages fonctionnels utilisent-ils la récupération de place?

Existe-t-il un langage fonctionnel qui permet d'utiliser la sémantique de pile - destruction déterministe automatique à la fin de la portée?

Pas que je sache, bien que je ne sois pas un expert en programmation fonctionnelle.

Cela semble assez difficile en principe, car les valeurs renvoyées par les fonctions peuvent contenir des références à d'autres valeurs qui ont été créées (sur la pile) dans la même fonction, ou pourraient tout aussi bien être passées en tant que paramètre, ou référencées par quelque chose passé comme paramètre. En C, ce problème est résolu en permettant que des pointeurs pendants (ou plus précisément, un comportement non défini) puissent se produire si le programmeur ne réussit pas. Ce n'est pas le genre de solution que les concepteurs de langages fonctionnels approuvent.

Il existe cependant des solutions potentielles. Une idée est de faire de la durée de vie de la valeur une partie du type de la valeur, ainsi que des références à celle-ci, et de définir des règles basées sur le type qui empêchent les valeurs allouées par pile d'être renvoyées par, ou référencées par quelque chose renvoyé par, un une fonction. Je n'ai pas travaillé sur les implications, mais je pense que ce serait horrible.

Pour le code monadique, il existe une autre solution qui est (en fait ou presque) monadique aussi, et pourrait donner une sorte d'IORef détruit de manière déterministe automatiquement. Le principe est de définir des actions "d'emboîtement". Lorsqu'ils sont combinés (à l'aide d'un opérateur associatif), ceux-ci définissent un flux de contrôle d'imbrication - je pense que "l'élément XML", la plus à gauche des valeurs fournissant la paire de balises de début et de fin externes. Ces «balises XML» ne font que définir l'ordre des actions monadiques à un autre niveau d'abstraction.

À un moment donné (sur le côté droit de la chaîne de composition associative), vous avez besoin d'une sorte de terminateur pour terminer l'imbrication - quelque chose pour remplir le trou au milieu. La nécessité d'un terminateur est ce qui signifie probablement que l'opérateur de composition d'imbrication n'est pas monadique, mais encore une fois, je ne suis pas entièrement sûr car je n'ai pas travaillé sur les détails. Comme l'application du terminateur ne fait que convertir une action d'imbrication en une action monadique normale composée, peut-être pas - cela n'affecte pas nécessairement l'opérateur de composition d'imbrication.

Beaucoup de ces actions spéciales auraient une étape "end-tag" nulle et associeraient l'étape "begin-tag" à une action monadique simple. Mais certains représenteraient des déclarations de variables. Ceux-ci représenteraient le constructeur avec la balise de début et le destructeur avec la balise de fin. Vous obtenez donc quelque chose comme ...

act = terminate ((def-var "hello" ) >>>= \h ->
                 (def-var " world") >>>= \w ->
                 (use-val ((get h) ++ (get w)))
                )

Traduction en une composition monadique avec l'ordre d'exécution suivant, chaque balise (et non élément) devenant une action monadique normale ...

<def-var val="hello">  --  construction
  <def-var val=" world>  --  construction
    <use-val ...>
      <terminator/>
    </use-val>  --  do nothing
  </def-val>  --  destruction
</def-val>  --  destruction

De telles règles pourraient permettre l'implémentation de RAII de style C ++. Les références de type IORef ne peuvent pas échapper à leur portée, pour des raisons similaires à celles pour lesquelles les IORefs normaux ne peuvent pas échapper à la monade - les règles de la composition associative ne permettent pas à la référence de s'échapper.

EDIT - j'ai presque oublié de dire - il y a un domaine précis dont je ne suis pas sûr ici. Il est important de s'assurer qu'une variable externe ne peut pas référencer une variable interne, donc il doit y avoir des restrictions sur ce que vous pouvez faire avec ces références de type IORef. Encore une fois, je n'ai pas travaillé sur tous les détails.

Par conséquent, la construction pourrait par exemple ouvrir un fichier dont la destruction se ferme. La construction pourrait ouvrir une douille que la destruction ferme. Fondamentalement, comme en C ++, les variables deviennent des gestionnaires de ressources. Mais contrairement à C ++, il n'y a pas d'objets alloués en tas qui ne peuvent pas être détruits automatiquement.

Bien que cette structure prenne en charge RAII, vous avez toujours besoin d'un garbage collector. Bien qu'une action d'imbrication puisse allouer et libérer de la mémoire, la traitant comme une ressource, il y a toujours toutes les références aux valeurs fonctionnelles (potentiellement partagées) dans ce morceau de mémoire et ailleurs. Étant donné que la mémoire peut être simplement allouée sur la pile, évitant ainsi d'avoir besoin d'un tas libre, la véritable signification (s'il y en a) concerne d'autres types de gestion des ressources.

Donc, cela permet de séparer la gestion des ressources de style RAII de la gestion de la mémoire, au moins dans le cas où RAII est basé sur une portée d'imbrication simple. Vous avez toujours besoin d'un garbage collector pour la gestion de la mémoire, mais vous obtenez un nettoyage déterministe automatique sûr et rapide des autres ressources.

Si vous considérez le C ++ comme un langage fonctionnel (il a des lambdas), alors c'est un exemple de langage qui n'utilise pas de garbage collection.

Je dois dire que la question est un peu mal définie car elle suppose qu'il existe une collection standard de "langages fonctionnels". Presque tous les langages de programmation prennent en charge une certaine quantité de programmation fonctionnelle. Et, presque tous les langages de programmation prennent en charge une certaine quantité de programmation impérative. Où tracer la ligne pour dire quel est un langage fonctionnel et quel est un langage impératif, autre que guidé par les préjugés culturels et le dogme populaire?

Une meilleure façon de formuler la question serait «est-il possible de prendre en charge la programmation fonctionnelle dans une mémoire allouée par pile». Comme déjà mentionné, la réponse est très difficile. Le style de programmation fonctionnel favorise l'allocation de structures de données récursives à volonté, ce qui nécessite une mémoire de tas (qu'elle soit récupérée ou comptée par référence). Cependant, il existe une technique d'analyse du compilateur assez sophistiquée appelée analyse de la mémoire basée sur la région, qui permet au compilateur de diviser le tas en grands blocs qui peuvent être alloués et désalloués automatiquement, d'une manière similaire à l'allocation de pile. La page Wikipedia répertorie diverses implémentations de la technique, pour les langages "fonctionnels" et "impératifs".