Est-il possible qu'un langage de programmation basé sur la pile soit simultané?

14

J'ai lu sur les langages de programmation basés sur la pile, tels que FORTH et Cat , et il semble que compte tenu de leur nature, ils ne peuvent exécuter qu'une seule action à la fois quel que soit leur paradigme (FORTH est impératif tandis que Cat est fonctionnel).

Un langage impératif modifierait la pile, et un langage purement fonctionnel, tel que Joy , retournerait une nouvelle pile, mais le fait est qu'une seule pile est utilisée à la fois.

Les langages de programmation basés sur la pile peuvent-ils donc être simultanés? Pourraient-ils atteindre la concurrence en utilisant plusieurs piles en même temps ou quelque chose de similaire?

Est-il possible d'implémenter une évaluation paresseuse dans un langage de programmation basé sur la pile?

Veuillez me corriger si je me méprends sur les langues et les concepts mentionnés ci-dessus

Armando H.
la source
5
Comment un langage impératif peut-il être simultané?
Bergi
Voulez-vous vraiment dire la simultanéité (ce qui n'est pas si difficile à réaliser, utilisez simplement plusieurs threads fonctionnant avec des piles indépendantes plus la mémoire partagée) ou le parallélisme?
Daniel Jour
@DanielJour si je comprends bien, le parallélisme signifie une exécution simultanée tandis que la simultanéité signifie une exécution indépendante, donc, oui, je veux dire la simultanéité. Pourriez-vous nous en dire plus sur les piles indépendantes pour chaque thread?
Armando H.

Réponses:

16

Alors, les langages de programmation basés sur la pile peuvent-ils être simultanés?

Sûr.

Pourraient-ils atteindre la concurrence en utilisant plusieurs piles en même temps ou quelque chose de similaire?

Déjà pour les langues normales, le multi-threading signifie généralement avoir plusieurs piles "d'appel". Il serait tout à fait naturel de donner à chaque thread sa propre pile de données. Il serait simple d'avoir un acteur, disons, dont le corps a été implémenté par du code dans un langage basé sur la pile. Le parallélisme explicite des parannotations du GHC devrait être relativement simple. Le principal problème avec l'exécution de choses en parallèle est que vous ne savez pas quel sera l'effet de pile du code jusqu'à ce que vous l'exécutiez. Cependant, en utilisant une syntaxe de type Joy, on pourrait imaginer [a b c] parque l'exécutiona b csoit contre une pile vide ou une copie de la pile et en ne conservant que l'élément le plus haut de la pile à la fin (ou en poussant une valeur fictive si la pile est vide). Vous pourriez imaginer des variations. Le parallélisme implicite serait plus difficile à faire naïvement par rapport, disons, à un langage purement fonctionnel, mais pourrait certainement l'être aussi. Le code compilé d'un combinateur défini par l'utilisateur n'est souvent pas trop différent du code "normal".

Est-il possible d'implémenter une évaluation paresseuse dans un langage de programmation basé sur la pile?

Les effets de pile inconnus sont à nouveau la partie délicate. Si vous concevez le langage de manière à ce que tous les effets de pile puissent être déterminés statiquement, cela ne semble pas trop difficile. Si vous avez la paresse être explicite, cela semble également relativement simple et ressemblerait à peu près aux citations de Joy et i. Un langage qui se dit un langage concaténatif paresseux semble faire un mélange des deux approches ci-dessus d'après ce que je peux dire. Je ne vois pas vraiment comment un langage concaténatif implicitement paresseux fonctionnerait face à des effets de pile dynamiques, du moins pas de manière vaguement utilisable, mais cela pourrait simplement être un manque d'imagination de ma part.

Soit dit en passant, il n'est pas rare que les langues basées sur une pile aient plusieurs piles, par exemple Forth a une pile de données et une pile de retour sur lesquelles vous pouvez également placer des données arbitraires.

Derek Elkins a quitté SE
la source
8

Je connais un peu FORTH donc je vais me limiter à ça. C'est un langage de bas niveau, vous donnant en tant que programmeur un accès à toutes les ressources matérielles. Vous pouvez donc faire ce que vous voulez.

Accès simultané

Pour avoir des programmes parallèles (edit: utilisé pour dire de vrais programmes concurrents), vous avez besoin d'au moins deux unités d'exécution (CPU-s). Il serait plutôt trivial d'implémenter un mot dans FORTH disant, par exemple, "exécutez ce mot sur le processeur 2 en utilisant ces deux arguments". Le mot allouerait les deux piles nécessaires sur le processeur 2 et commencerait à exécuter le mot. Vous auriez besoin de vous limiter quelque peu exactement dans les constructions que vous pouvez utiliser dans ce programme.

Si le nombre de programmes simultanés est supérieur au nombre d'unités d'exécution, vous opterez pour des programmes "pseudo parallèles". Fondamentalement, il existe deux façons de procéder: les coroutines ou le multitâche préemptif. Dans tous les cas, il est possible (pas facile, mais bien décrit dans la littérature) comment y parvenir et FORTH vous permet d'accéder à toutes les choses de bas niveau dont vous avez besoin.

Évaluation paresseuse

Bien sûr, vous pouvez le faire dans FORTH comme dans n'importe quel langage de programmation. Ce ne sera pas aussi élégant ou "intégré" que dans Haskell. J'utiliserai un exemple très naïf.

L'idée est que vous définissez une "fonction" (utilisée librement ici) qui renvoie un ensemble de choses. Un exemple serait une fonction qui renvoie tous les entiers. Vous effectuez ensuite des opérations sur cet ensemble et lorsque vous avez terminé, donnez le résultat. Par exemple, vous souhaiterez peut-être additionner tous les entiers jusqu'à ce que la somme soit supérieure à 1000. Une évaluation non paresseuse attribuerait d'abord tous les entiers en tant qu'ensemble, ce qui est impossible car il existe un nombre infini d'entiers. Il commencerait alors à travailler sur cet ensemble. Une implémentation paresseuse aurait un moyen de "me donner la valeur suivante dans l'ensemble". Faire cela n'a vraiment besoin que d'une variable dans la fonction "last value give".

Haskell fait les choses de cette façon. Bien sûr, il gère des situations plus compliquées, mais l'idée est la même. Il recouvre l'évaluation d'une manière qui vous permet en tant que programmeur de vous concentrer sur le problème, pas sur la façon de le résoudre.

ghellquist
la source
4
"Pour avoir de vrais programmes concurrents, vous avez besoin d'au moins deux unités d'exécution". Il s'agit simplement d'un problème de mise en œuvre. Du point de vue du langage de programmation, il n'y a presque aucune différence entre deux threads s'exécutant sur un seul processeur ou sur deux. Dans un sens, chaque thread peut être considéré comme une «unité d'exécution» à part entière.
Lézard discret
1
Parfois, les détails de mise en œuvre doivent être pris en considération. Un exemple est lors de l'interfaçage avec le monde réel en dehors d'un véritable ordinateur. En temps réel difficile, selon «la bonne réponse trop tard est faux», le timing peut être différent lorsque vous comparez l'exécution sur deux unités d'exécution à l'exécution mélangée sur une unité.
ghellquist
Parfois nous le faisons. Cependant, je doute que ce soit un tel cas. Par exemple, la question ne mentionne pas les exigences de planification en temps réel.
Lézard discret
3
"Concurrence"! = "Parallélisme". On peut dire que plusieurs threads s'exécutant sur une machine à processeur unique s'exécutent simultanément, même si aucun traitement parallèle ne se produit.
Solomon Slow
Point pris sur la concurrence par rapport aux parallèles. Je vais changer le texte.
ghellquist