¿Por qué las matrices C no realizan un seguimiento de su longitud?

¿Cuál fue el razonamiento detrás de no almacenar explícitamente la longitud de una matriz con una matriz en C?

A mi modo de ver, hay razones abrumadoras para hacerlo, pero no muchas en apoyo del estándar (C89). Por ejemplo:

1. Tener longitud disponible en un búfer puede evitar el desbordamiento del búfer.
2. Un estilo Java arr.lengthes claro y evita que el programador tenga que mantener muchos ints en la pila si se trata de varias matrices.
3. Los parámetros de la función se vuelven más convincentes.

Pero quizás la razón más motivadora, en mi opinión, es que generalmente no se ahorra espacio sin mantener la longitud. Me aventuraría a decir que la mayoría de los usos de las matrices implican una asignación dinámica. Es cierto que puede haber algunos casos en los que las personas usan una matriz asignada en la pila, pero esa es solo una llamada de función *: la pila puede manejar 4 u 8 bytes adicionales.

Dado que el administrador de almacenamiento dinámico tiene que rastrear el tamaño de bloque libre utilizado por la matriz asignada dinámicamente de todos modos, ¿por qué no hacer que esa información sea utilizable (y agregar la regla adicional, verificada en el momento de la compilación, que uno no puede manipular la longitud explícitamente a menos que uno lo haga)? gusta dispararse en el pie).

La única cosa que puedo pensar en el otro lado es que no hay seguimiento longitud puede haber hecho compiladores más simple, pero no que mucho más simple.

* Técnicamente, se podría escribir algún tipo de función recursiva con una matriz con almacenamiento automático, y en este caso (muy elaborado) el almacenamiento de la longitud puede resultar en un mayor uso del espacio.

Las matrices C hacen un seguimiento de su longitud, ya que la longitud de la matriz es una propiedad estática:

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

Por lo general, no puede consultar esta longitud, pero no es necesario porque es estática de todos modos: simplemente declare una macro XS_LENGTHpara la longitud y listo.

El problema más importante es que las matrices C se degradan implícitamente en punteros, por ejemplo, cuando se pasan a una función. Esto tiene sentido y permite algunos buenos trucos de bajo nivel, pero pierde la información sobre la longitud de la matriz. Entonces, una mejor pregunta sería por qué C fue diseñado con esta degradación implícita a los punteros.

Otra cuestión es que los punteros no necesitan almacenamiento, excepto la dirección de memoria en sí. C nos permite convertir enteros en punteros, punteros a otros punteros y tratar punteros como si fueran matrices. Al hacer esto, C no es lo suficientemente loco como para fabricar algo de longitud de matriz, pero parece confiar en el lema de Spiderman: con gran poder, el programador cumplirá con la gran responsabilidad de realizar un seguimiento de las longitudes y desbordamientos.

Mucho de esto tuvo que ver con las computadoras disponibles en ese momento. El programa compilado no solo tuvo que ejecutarse en una computadora de recursos limitados, sino que, quizás lo más importante, el compilador mismo tuvo que ejecutarse en estas máquinas. En el momento en que Thompson desarrolló C, estaba usando un PDP-7, con 8k de RAM. Las funciones de lenguaje complejas que no tenían un análogo inmediato en el código de máquina real simplemente no se incluyeron en el idioma.

Una lectura cuidadosa de la historia de C arroja más información sobre lo anterior, pero no fue completamente el resultado de las limitaciones de la máquina que tenían:

Además, el lenguaje (C) muestra un poder considerable para describir conceptos importantes, por ejemplo, vectores cuya longitud varía en el tiempo de ejecución, con solo unas pocas reglas y convenciones básicas. ... Es interesante comparar el enfoque de C con el de dos lenguajes casi contemporáneos, Algol 68 y Pascal [Jensen 74]. Las matrices en Algol 68 tienen límites fijos o son 'flexibles:' se requiere un mecanismo considerable tanto en la definición del lenguaje como en los compiladores, para acomodar matrices flexibles (y no todos los compiladores los implementan completamente). Pascal original solo tenía un tamaño fijo matrices y cadenas, y esto resultó confinado [Kernighan 81].

Las matrices C son inherentemente más potentes. Agregarles límites restringe para qué los puede usar el programador. Dichas restricciones pueden ser útiles para los programadores, pero necesariamente también son limitantes.

En el día en que se creó C, ¡y 4 bytes adicionales de espacio para cada cadena, sin importar cuán corto hubiera sido un desperdicio!

Hay otro problema: recuerde que C no está orientado a objetos, por lo que si realiza el prefijo de longitud de todas las cadenas, debería definirse como un tipo intrínseco del compilador, no a char*. Si fuera un tipo especial, entonces no sería capaz de comparar una cadena con una cadena constante, es decir:

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

tendría que tener detalles especiales del compilador para convertir esa cadena estática en una cadena, o tener diferentes funciones de cadena para tener en cuenta el prefijo de longitud.

Sin embargo, creo que, en última instancia, simplemente no eligieron el prefijo de longitud a diferencia de decir Pascal.

En C, cualquier subconjunto contiguo de una matriz también es una matriz y se puede operar como tal. Esto se aplica tanto a las operaciones de lectura como de escritura. Esta propiedad no se mantendría si el tamaño se almacenara explícitamente.

El mayor problema con tener matrices etiquetadas con su longitud no es tanto el espacio requerido para almacenar esa longitud, ni la cuestión de cómo debe almacenarse (usar un byte adicional para matrices cortas generalmente no sería objetable, ni tampoco usar cuatro bytes adicionales para matrices largas, pero puede ser el uso de cuatro bytes incluso para matrices cortas). Un problema mucho mayor es ese código dado como:

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 única forma en que ese código podría aceptar la primera llamada ClearTwoElementspero rechazar la segunda sería que el ClearTwoElementsmétodo recibiera información suficiente para saber que en cada caso estaba recibiendo una referencia a parte de la matriz fooademás de saber qué parte. Eso normalmente duplicaría el costo de pasar los parámetros del puntero. Además, si cada matriz fue precedida por un puntero a una dirección justo después del final (el formato más eficiente para la validación), el código optimizado para ClearTwoElementsprobablemente se convertiría en algo como:

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

Tenga en cuenta que una persona que llama al método podría, en general, pasar un puntero al inicio de la matriz o el último elemento a un método de forma legítima; solo si el método intenta acceder a elementos que van fuera de la matriz pasada, tales punteros causarían algún problema. En consecuencia, un método llamado tendría que asegurarse primero de que la matriz fuera lo suficientemente grande como para que la aritmética del puntero para validar sus argumentos no se salga de los límites, y luego haga algunos cálculos de puntero para validar los argumentos. El tiempo empleado en dicha validación probablemente excedería el costo dedicado a realizar cualquier trabajo real. Además, el método podría ser más eficiente si se escribiera y se llamara:

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

El concepto de un tipo que combina algo para identificar un objeto con algo para identificar una pieza del mismo es bueno. Sin embargo, un puntero estilo C es más rápido si no es necesario realizar la validación.

Una de las diferencias fundamentales entre C y la mayoría de los otros lenguajes de tercera generación, y todos los lenguajes más recientes que conozco, es que C no fue diseñado para hacer la vida más fácil o segura para el programador. Fue diseñado con la expectativa de que el programador sabía lo que estaban haciendo y quería hacer exactamente y solo eso. No hace nada "detrás de escena" para que no te sorprendas. Incluso la optimización de nivel de compilador es opcional (a menos que use un compilador de Microsoft).

Si un programador quiere escribir límites comprobando su código, C hace que sea lo suficientemente simple como para hacerlo, pero el programador debe elegir pagar el precio correspondiente en términos de espacio, complejidad y rendimiento. Aunque no lo he usado con ira en muchos años, todavía lo uso al enseñar programación para transmitir el concepto de toma de decisiones basada en restricciones. Básicamente, eso significa que puede elegir hacer lo que quiera, pero cada decisión que tome tiene un precio que debe tener en cuenta. Esto se vuelve aún más importante cuando comienzas a decirles a los demás lo que quieres que hagan sus programas.

Respuesta corta:

Debido a que C es un lenguaje de programación de bajo nivel , espera que usted se encargue de estos problemas usted mismo, pero esto agrega una mayor flexibilidad en cómo exactamente lo implementa.

C tiene un concepto de tiempo de compilación de una matriz que se inicializa con una longitud, pero en tiempo de ejecución todo se almacena simplemente como un puntero único al inicio de los datos. Si desea pasar la longitud de la matriz a una función junto con la matriz, hágalo usted mismo:

retval = my_func(my_array, my_array_length);

O podría usar una estructura con puntero y longitud, o cualquier otra solución.

Un lenguaje de nivel superior haría esto por usted como parte de su tipo de matriz. En C se le da la responsabilidad de hacerlo usted mismo, pero también la flexibilidad de elegir cómo hacerlo. Y si todo el código que está escribiendo ya conoce la longitud de la matriz, no necesita pasar la longitud como una variable.

El inconveniente obvio es que sin verificar los límites inherentes en las matrices que se pasan como punteros, puede crear un código peligroso, pero esa es la naturaleza de los lenguajes de bajo nivel / sistemas y la compensación que ofrecen.

El problema del almacenamiento adicional es un problema, pero en mi opinión, uno menor. Después de todo, la mayoría de las veces tendrá que rastrear la longitud de todos modos, aunque amon hizo un buen punto de que a menudo se puede rastrear estáticamente.

Un problema mayor es dónde almacenar la longitud y cuánto tiempo para hacerlo. No hay un solo lugar que funcione en todas las situaciones. Podría decir que simplemente almacene la longitud en la memoria justo antes de los datos. ¿Qué pasa si la matriz no apunta a la memoria, sino algo así como un búfer UART?

Dejar el espacio extendido le permite al programador crear sus propias abstracciones para la situación apropiada, y hay muchas bibliotecas preparadas disponibles para el caso de propósito general. La verdadera pregunta es ¿por qué no se utilizan esas abstracciones en aplicaciones sensibles a la seguridad?

Del desarrollo del lenguaje C :

Al parecer, las estructuras deberían mapearse de forma intuitiva en la memoria de la máquina, pero en una estructura que contiene una matriz, no había un buen lugar para esconder el puntero que contenía la base de la matriz, ni ninguna forma conveniente de organizarlo. inicializado Por ejemplo, las entradas de directorio de los primeros sistemas Unix podrían describirse en C como

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

Quería que la estructura no solo caracterizara un objeto abstracto, sino que también describiera una colección de bits que pudieran leerse desde un directorio. ¿Dónde podría el compilador ocultar el puntero al nameque exigía la semántica? Incluso si las estructuras se pensaran de manera más abstracta, y el espacio para los punteros pudiera ocultarse de alguna manera, ¿cómo podría manejar el problema técnico de inicializar adecuadamente estos punteros al asignar un objeto complicado, tal vez uno que especifica estructuras que contienen matrices que contienen estructuras a una profundidad arbitraria?

La solución constituyó el salto crucial en la cadena evolutiva entre BCPL sin tipo y tipo C. Eliminó la materialización del puntero almacenado y, en cambio, causó la creación del puntero cuando el nombre de la matriz se menciona en una expresión. La regla, que sobrevive en la C de hoy, es que los valores del tipo de matriz se convierten, cuando aparecen en expresiones, en punteros al primero de los objetos que forman la matriz.

Ese pasaje aborda por qué las expresiones de matriz decaen a punteros en la mayoría de las circunstancias, pero el mismo razonamiento se aplica a por qué la longitud de la matriz no se almacena con la matriz misma; Si desea un mapeo uno a uno entre la definición de tipo y su representación en la memoria (como lo hizo Ritchie), entonces no hay un buen lugar para almacenar esos metadatos.

Además, piense en matrices multidimensionales; ¿Dónde almacenaría los metadatos de longitud para cada dimensión de modo que aún pudiera recorrer la matriz con algo como

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 pregunta supone que hay matrices en C. No las hay. Las cosas que se llaman matrices son solo un azúcar sintáctico para operaciones en secuencias continuas de datos y aritmética de punteros.

El siguiente código copia algunos datos de src a dst en fragmentos de tamaño int sin saber que en realidad es una cadena de caracteres.

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

¿Por qué C está tan simplificado que no tiene matrices adecuadas? No sé la respuesta correcta a esta nueva pregunta. Pero algunas personas a menudo dicen que C es simplemente (algo) un ensamblador más legible y portátil.