Les structures de données doivent-elles être intégrées dans le langage (comme en Python) ou être fournies dans la bibliothèque standard (comme en Java)?

21

En Python, et très probablement dans de nombreux autres langages de programmation, des structures de données communes peuvent être trouvées comme une partie intégrée du langage de base avec leur propre syntaxe dédiée. Si nous mettons de côté la syntaxe de liste intégrée de LISP, je ne peux pas penser à d'autres langages que je connais qui fournissent une sorte de structure de données au-dessus du tableau comme partie intégrante de leur syntaxe, bien que tous (mais C, je suppose) semblent les fournir dans la bibliothèque standard.

Du point de vue de la conception d'un langage, que pensez-vous de la présence d'une syntaxe spécifique pour les structures de données dans le langage principal? Est-ce une bonne idée et le but de la langue (etc.) change-t-il la qualité de ce choix?

Edit: je suis désolé d'avoir (apparemment) causé une certaine confusion sur les structures de données que je veux dire. Je parle de ceux de base et couramment utilisés, mais toujours pas des plus basiques. Cela exclut les arbres (trop complexes, peu communs), les piles (trop rarement utilisés), les tableaux (trop simples) mais inclut par exemple les ensembles, les listes et les hashmaps.

Anto
la source
1
Sommes-nous en train d'exclure l'objet et la table de hachage?
Orbling
3
@Anto: De nombreux langages ont des hashmaps sous forme de tableaux associatifs, Perl, PHP, JS (techniquement un objet ici), etc.
Orbling
1
Peut-être pourriez-vous être plus précis sur les structures de données auxquelles vous pensez, à part les tableaux, les listes, les hashmaps / tableaux associatifs?
FrustratedWithFormsDesigner
1
Incluez les hashmaps, les listes et tout ce qui est plus avancé que les "structures de données complexes" et jetez les tableaux comme trop simples.
Anto
1
Je pense qu'un titre plus sensé serait quelque chose comme: "Quelles structures de données devraient être incluses dans la langue, et quoi dans la bibliothèque?" Une réponse significative dépend cependant fortement de la langue: plus la bibliothèque est proprement intégrée dans la langue, plus il est raisonnable de déplacer des structures dans la bibliothèque.
Jerry Coffin

Réponses:

13

Cela dépend à quoi sert la langue.

Quelques exemples (quelque peu volés dans d'autres réponses):

  • Perl a une syntaxe spéciale pour les tables de hachage, les tableaux et les chaînes. Perl est souvent utilisé pour les scripts, ceux-ci sont utiles pour les scripts.
  • Matlab a une syntaxe spéciale pour les listes, les matrices et les structures. Matlab est destiné à faire des mathématiques matricielles et vectorielles pour l'ingénierie.
  • Chaîne et tableaux de prise en charge Java / .NET. Ce sont des langages à usage général où les tableaux et les chaînes sont souvent utilisés (de moins en moins avec l'utilisation de nouvelles classes de collection)
  • Tableaux de prise en charge C / C ++. Ce sont des langues qui ne vous cachent pas le matériel. Les chaînes sont partiellement prises en charge (pas de concaténation, utilisez strcpy, etc.)

Je pense que cela dépend du but / de l'esprit / du public de votre langue; dans quelle mesure vous êtes abstrait et éloigné du matériel. Généralement, les langues qui prennent en charge les listes en tant que primitives vous permettent de créer des listes infiniment longues. Tandis qu'un niveau bas comme C / C ++ n'en aurait jamais, car ce n'est pas le but, l'esprit de ces langages.

Pour moi, la collecte des ordures suit la même logique: le public de votre langue se soucie-t-il de savoir exactement quand et si la mémoire est allouée ou libérée? Si oui, malloc / free; sinon, la collecte des ordures.

earlNameless
la source
6
C'est un mauvais endroit pour utiliser le terme «C / C ++», car la présence de types de modèles de haut niveau en C ++ est une différence majeure entre les deux langages.
dan04
La collecte des ordures peut se faire de façon déterministe, vous avez juste besoin de types linéaires (ou du remplacement de leur pauvre homme: RAII).
pyon
@ EduardoLeón, bien que vous puissiez appeler la collecte des ordures à un point déterministe, je ne pense pas que la durée de son exécution soit déterministe (pour la même raison mallocet newnon déterministe en C / C ++).
earlNameless
@earlNameless: Il est déterministe par rapport à l'utilisation de la ressource: les types linéaires (ou types d'unicité, qui sont similaires) en font une erreur de type (et, donc, une erreur de compilation) pour ne pas libérer les ressources (modulo la possibilité, non capturé par le type système, de toute interruption anormale du programme), ou de les utiliser après leur élimination.
pyon
5

Perl a des hashmaps et PL / SQL prend en charge les enregistrements, et j'ai des souvenirs très brumeux de matlab ayant une syntaxe pour prendre en charge des vecteurs et des matrices de toutes les différentes dimensions (bien que je puisse me tromper à propos de celui-ci et on pourrait faire valoir qu'il s'agit de types de données et non de données structures ) ... Je dirais que d' avoir un soutien natif pour des structures très communes est agréable d'avoir. Habituellement, il semble que les tableaux et les hashmaps / tableaux associatifs soient les structures supportées nativement les plus courantes, et elles sont probablement aussi les plus couramment utilisées.

N'oubliez pas que si vous ajoutez le support de la syntaxe native pour d'autres structures telles que les arbres binaires, ces structures ont également été implémentées par les outils de support du langage (compilateur / runtime / etc). Pour combien de structures souhaitez-vous obtenir un support?

Vous devrez inventer une nouvelle notation pour les structures moins nativement supportées ... Keep It Simple !.

FrustratedWithFormsDesigner
la source
Il n'est pas nécessaire d'inventer une syntaxe littérale, par exemple pour les arbres - ils sont plus rares, ils ne sont même pas dans le stdlib de nombreuses langues! Par le même argument, on pourrait s'opposer à l'inclusion d'opérateurs car "il faudrait inventer une nouvelle notation pour les opérations les moins utilisées".
@delnan: La façon dont je l'ai compris était du point de vue de la conception d'un nouveau langage et de la question de savoir si les structures de données en plus des tableaux devraient être prises en charge nativement par (éventuellement) une nouvelle syntaxe, ou si elles devraient être prises en charge en incluant une bibliothèque.
FrustratedWithFormsDesigner
Eh bien, la première phrase parle explicitement de "structures de données communes", donc je suppose que OP n'est pas assez fou pour essayer d'ajouter une syntaxe spéciale pour chaque structure de données obscure jamais inventée.
@delnan: ... puis l'OP continue d'exclure les listes et les tableaux LISP (en général) "... mettez la syntaxe de liste intégrée de LISP de côté, je ne peux penser à aucun autre langage que je connais qui fournit une sorte de structure de données au-dessus du tableau en tant que partie intégrante de leur syntaxe "... alors je pensais qu'ils réfléchissaient à des structures de données plus exotiques que des tableaux / listes ...
FrustratedWithFormsDesigner
Oui (j'ai interprété "au-dessus des tableaux" comme "d'autres structures de données communes"), mais rien dans la question ne fait allusion à "faisons des littéraux pour chaque structure de données que nous avons". C'est bien de dire que cela devrait être limité à ce qui est raisonnable, mais je ne pense pas que nous puissions dire "mauvaise idée" simplement à cause de cette hypothèse .
5

Mon exemple préféré ici est Lua . Lua n'a qu'un seul type de données intégré, la " table ", mais sa flexibilité et sa vitesse signifient que vous les utilisez réellement à la place des tableaux réguliers, des listes liées, des files d'attente, des cartes et ils sont même la base des fonctionnalités orientées objet de Lua (c.-à-d. classes).

Lua est un langage incroyablement simple, mais la flexibilité de la structure des données de la table le rend également assez puissant.

Dean Harding
la source
2
Les objets JavaScript sont vraiment de la même manière - Les tableaux sont simplement des objets avec des propriétés numériques et une longueur, par exemple.
Tikhon Jelvis
1
Les tables Lua sont différentes des objets JavaScript: en JavaScript {}non [], dans Lua vous en avez {}pour les deux. Les tables Lua se comparent mieux aux listes en Lisp.
Jakob
Je suppose qu'en JavaScript, "tout est un objet" - y compris les tableaux - mais tout n'est pas un tableau. À Lua, tout est une table.
Dean Harding
3

Vous n'avez pas besoin d'avoir une syntaxe dédiée pour chaque type de données de haut niveau. Par exemple, il est tolérable d'avoir set([1, 2, 3])(comme Python 2.x) au lieu de {1, 2, 3}.

L'important est d'avoir une façon pratique de construire une structure de données de haut niveau. Ce que vous voulez éviter, c'est du code comme:

s = set()
s.add(1)
s.add(2)
s.add(3)

ce qui me gêne beaucoup quand je l' utilise std::vector, std::setet std::mapen C ++. Heureusement, la nouvelle norme aura std::initializer_list.

dan04
la source
3

À mon avis, c'est un ajout incroyablement simple qui peut être utile étonnamment souvent, du moins s'il est fait avec prudence - c'est-à-dire tout au plus pour les tuples, les listes, les cartes et les ensembles car ceux-ci ont des littéraux bien reconnus.

  • Il est bon marché d'ajouter à une langue. Cela ne vous coûte pas beaucoup de ce précieux budget de complexité:
    • la grammaire est fondamentalement someBracket {expr ','} someBracketou someBracket {expr ':' expr ','} someBracket, avec quelques extras simples morts si vous voulez des choses comme des virgules de fin facultatives. Les littéraux flottants peuvent facilement être plus longs dans la grammaire.
    • Dans de nombreuses langues, aucun des littéraux populaires n'entre en conflit avec la syntaxe existante (une exception à laquelle je peux penser est un langage avec des blocs de type accolade comme expressions, un opérateur virgule et aucun point-virgule, comme dans {1, 2})
    • La sémantique peut être définie en moins de cinq phrases, la version informelle étant "Instancier une nouvelle collection $, puis appeler .add/ .append/ .setItemune fois par expressions données avec cette (ces) expression (s) comme arguments".
  • En raison du troisième point précédent, il est également très facile à mettre en œuvre.
  • Il est incroyablement pratique lorsque vous en avez besoin et n'a pas (besoin) d'impact sur la syntaxe des autres éléments, c'est-à-dire que vous ne le "payez" pas lorsque vous ne l'utilisez pas.
moucheron
la source
3

Clojure est un vif mais prend en charge

Lists: (x1 x2)
Vectors: [x1 x2]
Maps: {k1 v1 k2 v2}
Sets: #{x1 x2}
WuHoUnited
la source
2

Plus vous avez de structures de données dans la langue elle-même, plus la langue sera difficile à apprendre. C'est peut-être une préférence personnelle, mais j'ai tendance à préférer un langage plus simple et tous les extras peuvent être fournis par les bibliothèques.

Les langages conçus pour des domaines spécifiques peuvent parfois bénéficier de la présence de certaines structures de données dans le langage comme Matlab. Mais trop de gens peuvent vous submerger.

ergodicsum
la source
2

Pour qu'une langue soit vraiment utile, elle doit effectuer un certain degré de tâches prêtes à l'emploi. Parce que la programmation quotidienne pratique nécessite des outils qui résolvent leurs problèmes à un certain niveau générique. Le minimalisme a l'air compact et cool, mais lorsque vous souhaitez commencer à utiliser pour résoudre des problèmes importants mais répétés, vous avez besoin d'un niveau d'abstraction sur lequel vous pouvez vous appuyer.

Je pense donc que les langages de programmation devraient intégrer la prise en charge des structures de données les plus couramment utilisées dans la syntaxe des tâches pour lesquelles le langage est conçu.

kamaal
la source
2

En général, je trouve pratique d'avoir des littéraux pour les listes, les ensembles, etc. Mais cela me dérange parfois de ne rien savoir de l'implémentation réelle de - disons - la liste Python ou le tableau Javascript. La seule chose dont je peux être sûr, c'est qu'ils exposent une interface donnée.

Je prends comme référence de l'expressivité d'un langage à quel point il peut écrire ses propres structures de données en tant que bibliothèques et à quel point il est pratique de les utiliser.

Par exemple, Scala propose différentes collections avec différentes garanties de mise en œuvre et de performances. Tous sont implémentés dans Scala lui-même, et la syntaxe pour les utiliser n'est que légèrement plus complexe que s'ils étaient intégrés et avaient un support d'exécution.

La seule structure de base qui a vraiment besoin d'être prise en charge par le runtime lui-même, au moins dans un langage géré, est le tableau: si vous ne gérez pas la mémoire, vous aurez du mal à obtenir un tas d'octets adjacents. Toute autre structure peut être construite à partir de tableaux et de pointeurs (ou références).

Andrea
la source
1

APL (et les variantes modernes connexes, A +, J et K) ont des structures de données scalaires, vectorielles et matricielles de première classe.

Oui, ils peuvent être déconseillés en tant que simples variantes sur le tableau. Mais ils sont également exempts de déclarations complexes et ne proviennent pas d'une bibliothèque distincte, ils se sentent comme des structures de données complexes qui sont une partie de première classe du langage.

S.Lott
la source
APL a également des tableaux imbriqués, et les tableaux n'ont pas besoin d'avoir un type de données homogène, ce qui rend tous les structures de données très puissantes.
RFlack
1

Du point de vue de la conception d'un langage, que pensez-vous de la présence d'une syntaxe spécifique pour les structures de données dans le langage principal? Est-ce une bonne idée et le but de la langue (etc.) change-t-il la qualité de ce choix?

Les littéraux de liste et de carte et une syntaxe de fermeture pratique sont des caractéristiques essentielles des langages de haut niveau.

La différence entre ce code Java:

Thing t = new Thing();
t.setFoo(3);
t.setBar(6.3);
t.setBaz(true);

et ce code Groovy:

t = new Thing(foo: 3, bar: 6.3, baz: true)

est énorme. C'est la différence entre un programme de 40 000 lignes et un programme de 10 000 lignes. La syntaxe est importante.

Kevin Cline
la source
En C # on peut faire: var t = new Thing(foo: 3, bar: 6.3, baz: true);- seulement 4 caractères supplémentaires.
Job
c'est en fait le même nombre; le code Groovy devrait se lire 'def t = ...'
kevin cline
1

Bien sûr, cela dépend de l'application du langage de programmation, mais pour les langages de niveau supérieur, il devrait être aussi pratique que possible de travailler avec n'importe quelle structure de données commune. Jetez un oeil à la liste des types de données abstraits dans Wikipedia pour des exemples. J'ai trouvé les principes de base suivants les plus courants (mais j'aimerais aussi entendre d'autres opinions):

  • séquences ordonnées (1 dimension): tableau, file d'attente, pile, listes ...
  • structures multidimensionnelles ordonnées : tableau, vecteur, matrice ..
  • maps : hashmap, dictionnaire, set, multimap ... (1 dimension)
  • cartes multidimensionnelles : fonctions, cartes de cartes ...
  • types de graphes : arbres, graphes dirigés ...

Vous pouvez émuler n'importe quelle structure avec n'importe quelle autre structure - cela ne dépend que de la facilité et de la clarté du langage de programmation. Par exemple:

  • la file d'attente et la pile sont faciles à émuler avec des tableaux ou des listes, ces derniers fournissent des opérations telles que push, pop, shift, etc.
  • les séquences ordonnées peuvent être émulées avec des cartes dotées de touches numériques
  • les ensembles peuvent être émulés par des cartes qui mappent les valeurs à un booléen
  • la plupart des types de graphiques peuvent être émulés par des séquences ou des cartes d'imbrication
  • les fonctions peuvent être utilisées pour émuler des cartes si vous pouvez facilement modifier leur définition

La plupart des langages fournissent au moins un type pour les séquences ordonnées, un pour les cartes à une dimension et un pour les cartes à plusieurs dimensions, limité aux fonctions. Personnellement, je manque souvent des ensembles et des structures multidimensionnelles ordonnées dans des langages comme Perl, PHP, JavaScript, Lua ... car les émuler n'est pas assez pratique.

Jakob
la source
1

Je pense que c'est une mauvaise idée d'avoir trop de types de données privilégiés qui obtiennent une syntaxe spéciale. Cela complique inutilement la syntaxe du langage, ce qui rend le code plus difficile à lire, le rend plus difficile à apprendre pour les débutants et rend plus difficile le développement d'outils pour le langage.

Il est correct de faire une exception pour un petit nombre de types de structure de données très courants. J'autoriserais probablement au maximum:

  • Tableaux de longueur fixe
  • Ensembles
  • Hashmaps
  • Séquences / listes
  • Enregistrements / structures / classes

Tout ce qui est plus sophistiqué que cela devrait probablement être laissé aux bibliothèques pour gérer, en utilisant la syntaxe normale du langage pour les types de données personnalisés.

En particulier, des choses comme les arbres rouges / noirs, les files d'attente prioritaires, etc. ont beaucoup d'options d'implémentation possibles, il n'est donc pas judicieux de faire une implémentation particulière dans le langage principal. Il vaut mieux laisser les gens choisir la mise en œuvre la plus appropriée à leur situation. Exemples de choix d'implémentation sur lesquels je ne souhaiterais pas qu'un concepteur de langage restreigne mon choix:

  • Mutable ou immuable?
  • Autorise les valeurs nulles ou non?
  • Synchronisé ou non?
  • Soutenu par un stockage persistant ou non?
mikera
la source