Pourquoi les tableaux C ne suivent-ils pas leur longueur?

Quel était le raisonnement derrière ne pas stocker explicitement la longueur d'un tableau avec un tableau C?

À mon avis, les raisons sont très nombreuses mais peu favorables à la norme (C89). Par exemple:

1. Avoir la longueur disponible dans un tampon peut empêcher un dépassement de tampon.
2. Un style Java arr.lengthest à la fois clair et évite au programmeur de devoir garder plusieurs ints sur la pile s’il utilise plusieurs tableaux
3. Les paramètres de fonction deviennent plus convaincants.

Mais peut-être la raison la plus motivante, à mon avis, est-elle que généralement, aucun espace n'est économisé sans conserver la longueur. J'oserais dire que la plupart des utilisations de tableaux impliquent une allocation dynamique. Certes, il peut arriver que des personnes utilisent un tableau alloué sur la pile, mais il ne s’agit que d’un seul appel de fonction *: la pile peut gérer 4 ou 8 octets supplémentaires.

Puisque le gestionnaire de tas doit suivre la taille de bloc libre utilisée par le tableau alloué dynamiquement, pourquoi ne pas rendre cette information utilisable (et ajouter la règle supplémentaire, vérifiée au moment de la compilation, qui interdit de manipuler explicitement la longueur à moins de le faire aimer se tirer une balle dans le pied).

La seule chose que je peux penser de l'autre côté est qu'aucun suivi de longueur peut avoir fait des compilateurs plus simple, mais pas que beaucoup plus simple.

* Techniquement, on pourrait écrire une sorte de fonction récursive avec un tableau avec stockage automatique, et dans ce cas (très complexe) le stockage de la longueur peut effectivement entraîner une utilisation réellement plus importante de l'espace.

Les tableaux C gardent une trace de leur longueur, car la longueur du tableau est une propriété statique:

int xs[42];  /* a 42-element array */

En règle générale, vous ne pouvez pas interroger cette longueur, mais vous n'en avez pas besoin, car elle est statique. Déclarez simplement une macro XS_LENGTHpour la longueur et vous avez terminé.

Le problème le plus important est que les tableaux C se dégradent implicitement en pointeurs, par exemple lorsqu'ils sont transmis à une fonction. Cela a du sens, et permet quelques belles astuces de bas niveau, mais il perd les informations sur la longueur du tableau. Une meilleure question serait donc de savoir pourquoi C a été conçu avec cette dégradation implicite des pointeurs.

Un autre problème est que les pointeurs n'ont besoin d'aucun stockage, à l'exception de l'adresse de la mémoire elle-même. C nous permet de convertir des entiers en pointeurs, des pointeurs vers d’autres pointeurs, et de traiter les pointeurs comme s’ils étaient des tableaux. Ce faisant, C n’est pas assez fou pour fabriquer une longueur de tableau, mais semble croire en la devise de Spiderman: avec un grand pouvoir, le programmeur assumera la grande responsabilité de garder une trace des longueurs et des débordements.

Cela tenait en grande partie aux ordinateurs disponibles à l’époque. Non seulement le programme compilé devait-il s'exécuter sur un ordinateur disposant de peu de ressources, mais, chose plus importante peut-être, le compilateur lui-même devait s'exécuter sur ces machines. Au moment où Thompson a développé le C, il utilisait un PDP-7, avec 8 ko de RAM. Les fonctionnalités de langage complexes qui n'avaient pas d'analogue immédiat sur le code machine réel n'étaient tout simplement pas incluses dans le langage.

Une lecture attentive de l’ histoire du C permet de mieux comprendre ce qui précède, mais cela n’a pas été entièrement imputable aux limitations de la machine qu’ils avaient:

De plus, le langage (C) montre un pouvoir considérable pour décrire des concepts importants, par exemple des vecteurs dont la longueur varie au moment de l'exécution, avec seulement quelques règles et conventions de base. ... Il est intéressant de comparer l'approche de C avec celle de deux langues presque contemporaines, Algol 68 et Pascal [Jensen 74]. Les tableaux dans Algol 68 ont soit des limites fixes, soit sont "flexibles:" Un mécanisme considérable est nécessaire, à la fois dans la définition du langage et dans les compilateurs, pour prendre en charge les tableaux flexibles (tous les compilateurs ne les implémentent pas complètement.) tableaux et des chaînes, et cela s'est avéré confiner [Kernighan 81].

Les tableaux sont intrinsèquement plus puissants. Leur ajouter des limites limite les possibilités d'utilisation par le programmeur. De telles restrictions peuvent être utiles aux programmeurs, mais sont nécessairement aussi limitantes.

À l'époque de la création de C, il restait 4 octets d'espace supplémentaire pour chaque chaîne, peu importe la longueur de sa longueur, ce qui aurait été une perte de temps!

Il y a un autre problème - rappelez-vous que C n'est pas orienté objet, donc si vous préférez le préfixe de longueur pour toutes les chaînes, il devrait être défini comme un type intrinsèque du compilateur, pas un char*. S'il s'agissait d'un type spécial, vous ne pourriez pas comparer une chaîne à une chaîne constante, c'est-à-dire:

String x = "hello";
if (strcmp(x, "hello") == 0) 
  exit;

aurait besoin d'avoir des détails spéciaux du compilateur pour convertir cette chaîne statique en chaîne, ou avoir différentes fonctions de chaîne pour prendre en compte le préfixe de longueur.

Je pense que finalement, ils n’ont tout simplement pas choisi le préfixe de longueur contrairement à Pascal.

En C, tout sous-ensemble contigu d’un tableau est également un tableau et peut être utilisé comme tel. Ceci s’applique à la fois aux opérations de lecture et d’écriture. Cette propriété ne serait pas valable si la taille était explicitement stockée.

Le plus gros problème d'avoir des tableaux étiquetés avec leur longueur n'est pas tant l'espace requis pour stocker cette longueur, ni la question de savoir comment le stocker. Utiliser un octet supplémentaire pour les tableaux courts ne serait généralement pas inacceptable, ni quatre. des octets supplémentaires pour les tableaux longs, mais l’utilisation de quatre octets, même pour des tableaux courts, peut être). Un problème beaucoup plus important est celui du code suivant:

void ClearTwoElements(int *ptr)
{
  ptr[-2] = 0;
  ptr[2] = 0;
}
void blah(void)
{
  static int foo[10] = {1,2,3,4,5,6,7,8,9,10};
  ClearTwoElements(foo+2);
  ClearTwoElements(foo+7);
  ClearTwoElements(foo+1);
  ClearTwoElements(foo+8);
}

la seule façon pour ce code d'accepter le premier appel ClearTwoElementsmais de rejeter le second serait que le ClearTwoElementsprocédé reçoive une information suffisante pour savoir qu'il recevait dans chaque cas une référence à une partie du tableau, fooen plus de savoir quelle partie. Cela doublerait généralement le coût de passage des paramètres de pointeur. En outre, si chaque tableau était précédé d'un pointeur sur une adresse située juste après la fin (le format le plus efficace pour la validation), un code optimisé ClearTwoElementsdeviendrait probablement le suivant:

void ClearTwoElements(int *ptr)
{
  int* array_end = ARRAY_END(ptr);
  if ((array_end - ARRAY_BASE(ptr)) < 10 ||
      (ARRAY_BASE(ptr)+4) <= ADDRESS(ptr) ||          
      (array_end - 4) < ADDRESS(ptr)))
    trap();
  *(ADDRESS(ptr) - 4) = 0;
  *(ADDRESS(ptr) + 4) = 0;
}

Notez qu'un appelant de méthode peut, en général, parfaitement légitimement passer un pointeur au début du tableau ou au dernier élément d'une méthode; si la méthode tente d'accéder à des éléments qui sortent du tableau passé, de tels pointeurs pourraient causer des problèmes. Par conséquent, une méthode appelée devrait d’abord s’assurer que le tableau était suffisamment grand pour que l’arithmétique du pointeur permettant de valider ses arguments ne soit pas elle-même hors limites, puis effectuer quelques calculs de pointeur pour valider les arguments. Le temps consacré à cette validation dépasserait probablement le coût consacré à un travail réel. En outre, la méthode pourrait probablement être plus efficace si elle était écrite et appelée:

void ClearTwoElements(int arr[], int index)
{
  arr[index-2] = 0;
  arr[index+2] = 0;
}
void blah(void)
{
  static int foo[10] = {1,2,3,4,5,6,7,8,9,10};
  ClearTwoElements(foo,2);
  ClearTwoElements(foo,7);
  ClearTwoElements(foo,1);
  ClearTwoElements(foo,8);
}

Le concept d'un type qui combine quelque chose qui identifie un objet avec quelque chose qui identifie un morceau de celui-ci est bon. Un pointeur de style C est cependant plus rapide s'il n'est pas nécessaire d'effectuer une validation.

L'une des différences fondamentales entre C et la plupart des langages de 3ème génération, et tous les langages plus récents dont je suis conscient, est que C n'a pas été conçu pour simplifier la vie du programmeur, ni pour la rendre plus sûre. Il a été conçu dans l’espoir que le programmeur sache ce qu’il fait et veut faire exactement et seulement cela. Il ne fait rien "en coulisse", vous n'avez donc aucune surprise. Même l'optimisation au niveau du compilateur est facultative (sauf si vous utilisez un compilateur Microsoft).

Si un programmeur veut écrire des limites en vérifiant son code, C le simplifie, mais le programmeur doit choisir de payer le prix correspondant en termes d'espace, de complexité et de performances. Même si je ne l'utilisais pas dans la colère depuis de nombreuses années, je l'utilise quand même pour enseigner la programmation afin de faire comprendre le concept de prise de décision basée sur des contraintes. En gros, cela signifie que vous pouvez choisir de faire tout ce que vous voulez, mais chaque décision que vous prenez a un prix que vous devez connaître. Cela devient encore plus important lorsque vous commencez à dire aux autres ce que vous voulez que leurs programmes fassent.

Réponse courte:

C étant un langage de programmation de bas niveau , il s’attend à ce que vous vous occupiez de ces problèmes vous-même, mais cela ajoute une plus grande souplesse dans la façon dont vous l’implémentez.

C a le concept de compilation d’un tableau qui est initialisé avec une longueur, mais au moment de l’exécution, le tout est simplement stocké sous la forme d’un pointeur unique indiquant le début des données. Si vous voulez transmettre la longueur du tableau à une fonction avec le tableau, vous le faites vous-même:

retval = my_func(my_array, my_array_length);

Ou vous pouvez utiliser une structure avec un pointeur et une longueur, ou toute autre solution.

Un langage de niveau supérieur le ferait pour vous dans le cadre de son type de tableau. En C, on vous confie la responsabilité de le faire vous-même, mais vous avez également la possibilité de choisir comment le faire. Et si tout le code que vous écrivez connaît déjà la longueur du tableau, vous n'avez pas besoin de la transmettre comme variable.

L’inconvénient évident est qu’en l’absence de limites inhérentes à la vérification des tableaux transmis en tant que pointeurs, vous pouvez créer un code dangereux, mais c’est la nature des langages de bas niveau / systèmes et le compromis qu’ils donnent.

Le problème du stockage supplémentaire est un problème, mais à mon avis un problème mineur. Après tout, la plupart du temps, vous aurez besoin de suivre la longueur de toute façon, même si un argument précis a été avancé: elle peut souvent être suivie de manière statique.

Un problème plus important est de savoir où stocker la longueur et combien de temps pour la fabriquer. Il n'y a pas un seul endroit qui fonctionne dans toutes les situations. Vous pourriez dire simplement stocker la longueur dans la mémoire juste avant les données. Que se passe-t-il si le tableau ne pointe pas vers la mémoire, mais quelque chose comme un tampon UART?

Le fait de ne pas laisser de longueur permet au programmeur de créer ses propres abstractions pour la situation appropriée et de nombreuses bibliothèques prêtes à l'emploi sont disponibles pour le cas d'utilisation générale. La vraie question est de savoir pourquoi ces abstractions ne sont pas utilisées dans des applications sensibles à la sécurité.

Du développement du langage C :

Les structures, semble-t-il, devaient correspondre de manière intuitive à la mémoire de la machine, mais dans une structure contenant un tableau, il n'y avait pas de bonne place pour cacher le pointeur contenant la base du tableau, ni aucun moyen pratique de l'arranger. initialisé. Par exemple, les entrées de répertoire des anciens systèmes Unix peuvent être décrites en C comme suit:

struct {
    int inumber;
    char    name[14];
};

Je voulais que la structure ne caractérise pas simplement un objet abstrait, mais décrive également une collection de bits pouvant être lus dans un répertoire. Où le compilateur pourrait-il cacher le pointeur sur namecelui demandé par la sémantique? Même si on pensait de manière plus abstraite aux structures et si l’espace pour les pointeurs pouvait être caché, comment puis-je régler le problème technique de l’initialisation correcte de ces pointeurs lors de l’allocation d’un objet compliqué, par exemple des structures contenant des tableaux contenant des structures à une profondeur arbitraire?

La solution a constitué le saut crucial dans la chaîne évolutive entre BCPL sans typage et C typé. Elle a éliminé la matérialisation du pointeur dans le stockage et a plutôt provoqué la création du pointeur lorsque le nom du tableau est mentionné dans une expression. La règle, qui subsiste dans le C actuel, est que les valeurs de type tableau sont converties, lorsqu'elles apparaissent dans des expressions, en pointeurs sur le premier des objets constituant le tableau.

Ce passage explique pourquoi les expressions de tableau décroissent en pointeurs dans la plupart des cas, mais le même raisonnement s'applique à la raison pour laquelle la longueur du tableau n'est pas stockée avec le tableau lui-même; si vous voulez un mappage un-à-un entre la définition de type et sa représentation en mémoire (comme Ritchie l'a fait), il n'y a pas de bon endroit pour stocker ces métadonnées.

Pensez également aux tableaux multidimensionnels. où stockeriez-vous les métadonnées de longueur pour chaque dimension de sorte que vous puissiez toujours parcourir le tableau avec quelque chose comme

T *p = &a[0][0];

for ( size_t i = 0; i < rows; i++ )
  for ( size_t j = 0; j < cols; j++ )
    do_something_with( *p++ );

La question suppose qu'il y a des tableaux en C. Il n'y en a pas. Les choses appelées tableaux ne sont qu'un sucre syntaxique pour les opérations sur des séquences continues de données et l'arithmétique de pointeur.

Le code suivant copie certaines données de src vers dst sous forme de fragments de taille int ne sachant pas qu'il s'agit en fait d'une chaîne de caractères.

char src[] = "Hello, world";
char dst[1024];
int *my_array = src; /* What? Compiler warning, but the code is valid. */
int *other_array = dst;
int i;
for (i = 0; i <= sizeof(src)/sizeof(int); i++)
    other_array[i] = my_array[i]; /* Oh well, we've copied some extra bytes */
printf("%s\n", dst);

Pourquoi C est tellement simplifié qu'il n'a pas de tableaux appropriés? Je ne sais pas réponse correcte à cette nouvelle question. Mais certaines personnes disent souvent que C est juste un assembleur (un peu) plus lisible et portable.