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

32

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?

user467799
la source
La destruction déterministe n'est vraiment utile qu'avec des effets secondaires. Dans le contexte de la programmation fonctionnelle pure , cela signifie simplement s'assurer que certaines actions (monadiques) s'exécutent toujours à la fin d'une séquence. En passant, il est facile d'écrire un langage concaténatif fonctionnel qui n'a pas besoin de ramasser les ordures.
Jon Purdy
Je m'intéresse au contenu de la question, qu'est-ce qu'on a à voir avec l'otehr?
mattnz
1
Dans un langage fonctionnel sans garbage collection, je ne vois pas comment le partage structurel de structures de données immuables est possible. Il peut être possible de créer un tel langage, mais ce n'est pas celui que j'utiliserais.
dan_waterworth
Rust a beaucoup de fonctionnalités communément identifiées comme `` fonctionnelles '' (au moins, elles sont généralement recherchées dans les langages non func comme fonctionnalités). Je suis curieux de savoir ce qu'il manque. Immut par défaut, fermetures, dépassement de fonction, surcharge de principe, ADT (pas encore de GADT), correspondance de modèle, le tout sans GC. Quoi d'autre?
Noein

Réponses:

10

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.

Steve314
la source
Je ne vois pas pourquoi un GC est nécessaire dans tous les langages fonctionnels. si vous disposez d'un framework RAII de style C ++, le compilateur peut également utiliser ce mécanisme. Les valeurs partagées ne sont pas un problème pour les frameworks RAII (voir C ++ shared_ptr<>), vous gardez toujours la destruction déterministe. La seule chose délicate pour RAII sont les références cycliques; RAII fonctionne correctement si le graphique de propriété est un graphique acyclique dirigé.
MSalters
Le fait est que le style de programmation fonctionnel est pratiquement construit autour de fermetures / lambdas / fonctions anonymes. Sans GC, vous n'avez pas la même liberté d'utiliser vos fermetures, donc votre langage devient nettement moins fonctionnel.
comingstorm
@comingstorm - C ++ a des lambdas (à partir de C ++ 11) mais pas de garbage collector standard. Les lambdas transportent également leur environnement dans une fermeture - et les éléments de cet environnement peuvent être passés par référence, ainsi que la possibilité de passer des pointeurs par valeur. Mais comme je l'ai écrit dans mon deuxième paragraphe, C ++ permet la possibilité de balancer les pointeurs - c'est la responsabilité des programmeurs (plutôt que des compilateurs ou des environnements d'exécution) de s'assurer que cela ne se produise jamais.
Steve314
@MSalters - il y a des coûts pour garantir qu'aucun cycle de référence ne puisse jamais être créé. Il est donc au moins non trivial de rendre le langage responsable de cette restriction. L'affectation à un pointeur devient probablement une opération à temps non constant. Bien que ce soit toujours la meilleure option dans certains cas. La collecte des ordures évite ce problème, avec des coûts différents. Rendre le programmeur responsable en est une autre. Il n'y a aucune raison pour laquelle les pointeurs pendants devraient être OK dans les langages impératifs mais pas fonctionnels, mais je ne recommande toujours pas d'écrire pointer-dangling-Haskell.
Steve314
Je dirais que la gestion manuelle de la mémoire signifie que vous n'avez pas tout à fait la même liberté d'utiliser les fermetures C ++ 11 que les fermetures Lisp ou Haskell. (Je suis en fait très intéressé à comprendre les détails de ce compromis, car je voudrais écrire un langage de programmation de systèmes fonctionnels ...)
comingstorm
3

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.

BЈовић
la source
8
Et si vous ne considérez pas le C ++ comme un langage fonctionnel (à mon humble avis, même si vous pouvez écrire un programme fonctionnel avec lui, vous pouvez également écrire avec lui des programmes extrêmement non fonctionnels (fonctionnant ...))
mattnz
@mattnz Alors je suppose que la réponse ne s'applique pas. Je ne sais pas ce qui se passe dans d'autres langues (comme par exemple haskel)
BЈовић
9
Dire que C ++ est fonctionnel, c'est comme dire que Perl est orienté objet ...
Dynamic
Au moins les compilateurs c ++ peuvent vérifier les effets secondaires. (via const)
tp1
@ tp1 - (1) J'espère que cela ne va pas régresser pour savoir qui est le meilleur langage, et (2) ce n'est pas vraiment vrai. Premièrement, les effets vraiment importants sont principalement des E / S. Deuxièmement, même pour les effets sur la mémoire mutable, const ne les bloque pas. Même si vous supposez qu'il n'y a aucune possibilité de renverser le système de types (généralement raisonnable en C ++), il y a le problème de la constance logique et du mot clé C ++ "mutable". Fondamentalement, vous pouvez toujours avoir des mutations malgré const. Vous devez vous assurer que le résultat est toujours "logiquement" le même, mais pas nécessairement la même représentation.
Steve314
2

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".

Uday Reddy
la source
1
Le comptage de références IMO est un garbage collection, et avoir un tas n'implique pas que ce soient de toute façon les seules options. C mallocs et mfrees utilisent un tas, mais n'ont pas de ramasse-miettes (standard) et ne comptent que les références si vous écrivez le code pour le faire. C ++ est presque le même - il a (en standard, en C ++ 11) des pointeurs intelligents avec un comptage de référence intégré, mais vous pouvez toujours faire de nouveaux manuels et supprimer si vous en avez vraiment besoin.
Steve314
Une raison courante pour affirmer que le comptage de références n'est pas un garbage collection est qu'il ne parvient pas à collecter des cycles de référence. Cela s'applique certainement aux implémentations simples (y compris probablement les pointeurs intelligents C ++ - je n'ai pas vérifié) mais ce n'est pas toujours le cas. Au moins une machine virtuelle Java (par IBM, IIRC) a utilisé le comptage de références comme base pour sa collecte des ordures.
Steve314