Perché i C array non tengono traccia della loro lunghezza?

Gli array C tengono traccia della loro lunghezza, in quanto la lunghezza dell'array è una proprietà statica:

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

Di solito non puoi interrogare questa lunghezza, ma non è necessario perché è statica in ogni caso - basta dichiarare una macro XS_LENGTH per la lunghezza, e il gioco è fatto.

Il problema più importante è che gli array C si degradano implicitamente in puntatori, ad es. quando passato a una funzione. Questo ha un senso e consente alcuni trucchi di basso livello, ma perde le informazioni sulla lunghezza dell'array. Quindi una domanda migliore sarebbe il motivo per cui C è stato progettato con questo degrado implicito ai puntatori.

Un'altra questione è che i puntatori non hanno bisogno di spazio di archiviazione tranne l'indirizzo di memoria stesso. C ci permette di trasmettere numeri interi a puntatori, puntatori ad altri puntatori e di trattare i puntatori come se fossero matrici. Mentre fa questo, C non è abbastanza folle da fabbricare la lunghezza dell'array nell'esistenza, ma sembra fidarsi del motto di Spiderman: con grande potenza il programmatore spera di soddisfare la grande responsabilità di tenere traccia delle lunghezze e degli straripamenti.

Molto di questo ha a che fare con i computer disponibili in quel momento. Non solo il programma compilato deve essere eseguito su un computer con risorse limitate, ma, forse ancora più importante, il compilatore stesso deve essere eseguito su queste macchine. All'epoca in cui Thompson sviluppò C, stava usando un PDP-7, con 8k di RAM. Funzionalità linguistiche complesse che non avevano un analogico immediato sul codice macchina reale non erano semplicemente incluse nella lingua.

Un'attenta lettura della cronologia di C offre maggiore comprensione in quanto sopra, ma non era interamente un risultato delle limitazioni della macchina che avevano:

Moreover, the language (C) shows considerable power to describe important concepts, for example, vectors whose length varies at run time, with only a few basic rules and conventions. ... It is interesting to compare C's approach with that of two nearly contemporaneous languages, Algol 68 and Pascal [Jensen 74]. Arrays in Algol 68 either have fixed bounds, or are 'flexible:' considerable mechanism is required both in the language definition, and in compilers, to accommodate flexible arrays (and not all compilers fully implement them.) Original Pascal had only fixed-sized arrays and strings, and this proved confining [Kernighan 81].

Gli array C sono intrinsecamente più potenti. L'aggiunta di limiti ad essi limita ciò che il programmatore può usarli. Tali restrizioni possono essere utili per i programmatori, ma necessariamente sono anche limitanti.

Indietro nel giorno in cui C è stato creato, e 4 byte extra di spazio per ogni stringa, non importa quanto breve sarebbe stato uno spreco!

C'è un altro problema - ricorda che C non è orientato agli oggetti, quindi se fai il prefisso di lunghezza di tutte le stringhe, dovrebbe essere definito come un tipo intrinseco del compilatore, non un char* . Se fosse un tipo speciale, non sarebbe possibile confrontare una stringa con una stringa costante, cioè:

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

dovrebbe avere dettagli speciali del compilatore per convertire quella stringa statica in una stringa o avere funzioni di stringa diverse per tenere conto del prefisso della lunghezza.

Penso che alla fine, però, non hanno scelto il modo di prefisso della lunghezza a differenza di Pascal.

In C, qualsiasi sottogruppo contiguo di un array è anche un array e può essere utilizzato come tale. Questo vale sia per le operazioni di lettura e scrittura. Questa proprietà non sarebbe valida se la dimensione fosse stata memorizzata in modo esplicito.

Il problema più grande con gli array etichettati con la loro lunghezza non è tanto lo spazio richiesto per archiviare quella lunghezza, né la questione di come dovrebbe essere memorizzato (usare un byte in più per i cortocircuiti in genere non sarebbe discutibile, né userebbe quattro byte extra per array lunghi, ma potrebbe essere l'utilizzo di quattro byte anche per array corti). Un problema molto più grande è dato dal codice come:

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);
}

l'unico modo in cui il codice sarebbe in grado di accettare la prima chiamata a ClearTwoElements ma rifiutare il secondo sarebbe il metodo ClearTwoElements per ricevere informazioni sufficienti a sapere che in ogni caso stava ricevendo un riferimento a parte di l'array foo oltre a sapere quale parte. Questo in genere raddoppierà il costo del passaggio dei parametri del puntatore. Inoltre, se ogni array era preceduto da un puntatore a un indirizzo appena passato (il formato più efficiente per la convalida), il codice ottimizzato per ClearTwoElements sarebbe probabilmente diventato qualcosa del tipo:

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;
}

Si noti che un chiamante del metodo potrebbe, in generale, legittimamente passare un puntatore all'inizio della matrice o l'ultimo elemento a un metodo; solo se il metodo tenta di accedere a elementi che escono dall'array passato, tali indicatori causano problemi. Di conseguenza, un metodo chiamato dovrebbe prima assicurarsi che l'array sia abbastanza grande che l'aritmetica del puntatore per convalidare i suoi argomenti non andrà di per sé fuori dai limiti, e quindi eseguire alcuni calcoli con puntatori per convalidare gli argomenti. Il tempo speso in tale convalida probabilmente supererebbe il costo speso facendo qualsiasi lavoro reale. Inoltre, il metodo potrebbe essere più efficiente se fosse stato scritto e chiamato:

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);
}

Il concetto di un tipo che combina qualcosa per identificare un oggetto con qualcosa per identificare un suo pezzo è buono. Un puntatore in stile C è più veloce, tuttavia, se non è necessario eseguire la convalida.

Una delle differenze fondamentali tra C e la maggior parte delle altre lingue di terza generazione, e tutte le lingue più recenti di cui sono a conoscenza, è che C non è stato progettato per rendere la vita più facile o più sicura per il programmatore. È stato progettato con l'aspettativa che il programmatore sapeva cosa stavano facendo e voleva fare esattamente e solo quello. Non fa nulla di "dietro le quinte" in modo da non avere sorprese. Anche l'ottimizzazione del livello del compilatore è facoltativa (a meno che non si utilizzi un compilatore Microsoft).

Se un programmatore desidera scrivere limiti controllando nel proprio codice, C lo rende abbastanza semplice da eseguire, ma il programmatore deve scegliere di pagare il prezzo corrispondente in termini di spazio, complessità e prestazioni. Anche se non l'ho usato per molti anni nella rabbia, lo uso ancora quando insegno alla programmazione per superare il concetto di decisione basata sui vincoli. Fondamentalmente, ciò significa che puoi scegliere di fare tutto ciò che vuoi, ma ogni decisione che prendi ha un prezzo di cui devi essere consapevole. Questo diventa ancora più importante quando inizi a dire agli altri cosa vuoi che facciano i loro programmi.

Risposta breve:

Poiché C è un linguaggio di programmazione di basso livello , si aspetta che tu ti prenda cura di questi problemi da solo, ma ciò aggiunge una maggiore flessibilità esattamente nel come tu implementalo.

C ha un concetto in fase di compilazione di un array che viene inizializzato con una lunghezza ma in fase di esecuzione l'intera operazione viene semplicemente memorizzata come un singolo puntatore all'inizio dei dati. Se si desidera passare la lunghezza dell'array a una funzione insieme all'array, lo si fa da soli:

retval = my_func(my_array, my_array_length);

Oppure potresti usare una struct con un puntatore e una lunghezza, o qualsiasi altra soluzione.

Un linguaggio di livello superiore farebbe questo per te come parte del suo tipo di array. In C ti viene data la responsabilità di farlo da solo, ma anche la flessibilità di scegliere come farlo. E se tutto il codice che stai scrivendo conosce già la lunghezza dell'array, non devi affatto passare la lunghezza come variabile.

L'ovvio inconveniente è che senza limiti inerenti il controllo degli array passati come indicatori è possibile creare codice pericoloso, ma questa è la natura dei linguaggi di basso livello / sistema e del trade-off che danno.

Il problema dell'archiviazione extra è un problema, ma a mio parere è un problema minore. Dopotutto, per la maggior parte del tempo dovrai comunque tenere traccia della lunghezza, sebbene Amon abbia fatto un buon punto sul fatto che spesso può essere monitorato staticamente.

Un problema più grande è dove per memorizzare la lunghezza e quanto a lungo per farlo. Non c'è un posto che funzioni in tutte le situazioni. Si potrebbe dire che è sufficiente memorizzare la lunghezza nella memoria appena prima dei dati. Cosa succede se l'array non punta alla memoria, ma qualcosa come un buffer UART?

Lasciando la lunghezza fuori permette al programmatore di creare le proprie astrazioni per la situazione appropriata, e ci sono un sacco di librerie già pronte disponibili per il caso generale. La vera domanda è: perché queste astrazioni non sono usate in applicazioni sensibili alla sicurezza?

Da Sviluppo della lingua C :

Structures, it seemed, should map in an intuitive way onto memory in the machine, but in a structure containing an array, there was no good place to stash the pointer containing the base of the array, nor any convenient way to arrange that it be initialized. For example, the directory entries of early Unix systems might be described in C as

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

I wanted the structure not merely to characterize an abstract object but also to describe a collection of bits that might be read from a directory. Where could the compiler hide the pointer to name that the semantics demanded? Even if structures were thought of more abstractly, and the space for pointers could be hidden somehow, how could I handle the technical problem of properly initializing these pointers when allocating a complicated object, perhaps one that specified structures containing arrays containing structures to arbitrary depth?

The solution constituted the crucial jump in the evolutionary chain between typeless BCPL and typed C. It eliminated the materialization of the pointer in storage, and instead caused the creation of the pointer when the array name is mentioned in an expression. The rule, which survives in today's C, is that values of array type are converted, when they appear in expressions, into pointers to the first of the objects making up the array.

Questo passaggio affronta il motivo per cui le espressioni dell'array decadono ai puntatori nella maggior parte dei casi, ma lo stesso ragionamento si applica al motivo per cui la lunghezza dell'array non è memorizzata con l'array stesso; se si desidera un mapping uno-a-uno tra la definizione del tipo e la sua rappresentazione in memoria (come ha fatto Ritchie), quindi non c'è un buon posto per archiviare i metadati.

Inoltre, pensa agli array multidimensionali; dove memorizzeresti i metadati di lunghezza per ogni dimensione in modo tale da poter ancora attraversare l'array con qualcosa come

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 domanda presuppone che ci siano matrici in C. Non ce ne sono. Le cose che sono chiamate array sono solo uno zucchero sintattico per operazioni su sequenze continue di dati e aritmetica puntatore.

Il seguente codice copia alcuni dati da src a dst in blocchi int-sized senza sapere che è effettivamente una stringa di caratteri.

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);

Perché C è così semplificato da non avere array adeguati? Non conosco la risposta corretta a questa nuova domanda. Ma alcune persone dicono spesso che C è solo (un po ') assemblatore più leggibile e portatile.