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

Los arrays C hacen un seguimiento de su longitud, ya que la longitud del array 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_LENGTH para la longitud y listo.

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

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

Mucho de esto tuvo que ver con las computadoras disponibles en ese momento. El programa compilado no solo tenía que ejecutarse en una computadora de recursos limitados, sino que, quizás lo más importante, el compilador tenía que ejecutarse en estas máquinas. Cuando 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 a través del historial de C permite comprender mejor lo anterior, pero no fue totalmente 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 idiomas casi contemporáneos, Algol 68 y Pascal [Jensen 74]. Los arreglos en Algol 68 tienen límites fijos o son 'flexibles:' se requiere un mecanismo considerable tanto en la definición del idioma como en los compiladores, para acomodar arreglos flexibles (y no todos los compiladores los implementan completamente). El Pascal original solo tenía un tamaño fijo. arrays y cadenas, y esto resultó ser limitante [Kernighan 81].

Las matrices C son inherentemente más potentes. Agregar límites a ellos restringe lo que el programador puede usarlos. Tales restricciones pueden ser útiles para los programadores, pero necesariamente también son limitantes.

¡Atrás en el día en que se creó C, y extra 4 bytes de espacio para cada cadena, sin importar lo corta que haya sido !

Hay otro problema: recuerde que C no está orientado a objetos, por lo que si hace un prefijo de longitud para todas las cadenas, debería definirse como un tipo intrínseco del compilador, no como char* . Si fuera un tipo especial, entonces no podría 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.

Creo que en última instancia, sin embargo, simplemente no eligieron la forma de prefijo de longitud, a diferencia de Pascal.

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

El mayor problema de tener matrices etiquetadas con su longitud no es tanto el espacio requerido para almacenar esa longitud, ni la cuestión de cómo se debe almacenar (usar un byte adicional para las matrices cortas generalmente no sería objetable, ni sería usar cuatro bytes adicionales para arreglos largos, pero usar cuatro bytes incluso para arreglos cortos podría ser). Un problema mucho mayor es el 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 el código podría aceptar la primera llamada a ClearTwoElements pero rechazar la segunda sería que el método ClearTwoElements reciba información suficiente para saber que en cada caso estaba recibiendo una referencia a parte de la matriz foo además de saber qué parte. Eso normalmente duplicaría el costo de pasar parámetros de puntero. Además, si cada matriz estuviera precedida por un puntero a una dirección justo después del final (el formato más eficaz para la validación), el código optimizado para ClearTwoElements probablemente 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 un invocador de método podría, en general, pasar perfectamente un puntero al inicio de la matriz o el último elemento a un método; solo si el método intenta acceder a elementos que van fuera de la matriz pasada, tales punteros causarán 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 realizar algunos cálculos de punteros para validar los argumentos. El tiempo empleado en dicha validación probablemente excedería el costo invertido en realizar un trabajo real. Además, el método podría ser más eficiente si se escribiera y 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 de 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 la escena", por lo que no recibe ninguna sorpresa. Incluso la optimización del nivel del compilador es opcional (a menos que use un compilador de Microsoft).

Si un programador desea escribir los límites de verificación en su código, C hace que sea lo suficientemente simple para hacerlo, pero el programador debe elegir pagar el precio correspondiente en términos de espacio, complejidad y rendimiento. A pesar de que no lo he usado enojada durante muchos años, todavía lo uso cuando enseño programación para entender 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 comienza a decirle a los demás lo que quiere que hagan sus programas.

Respuesta corta:

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

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 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 puedes usar una estructura con un puntero y una longitud, o cualquier otra solución.

Un lenguaje de nivel superior lo haría por usted como parte de su tipo de matriz. En C se le otorga 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 en absoluto.

El inconveniente obvio es que, sin pases inherentes, la verificación de las matrices se pasa como indicadores para 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 extra es un problema, pero en mi opinión uno menor. Después de todo, la mayor parte del tiempo tendrá que realizar un seguimiento de la longitud de todos modos, aunque amon señaló que a menudo se puede realizar un seguimiento estático.

Un problema mayor es donde almacenar la longitud y el 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 como un búfer UART?

Abandonar el espacio permite al programador crear sus propias abstracciones para la situación apropiada, y hay muchas bibliotecas listas para usar 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?

De El desarrollo del lenguaje C :

Al parecer, las estructuras deberían asignarse de manera intuitiva a la memoria de la máquina, pero en una estructura que contenga una matriz, no había un buen lugar para guardar el puntero que contiene la base de la matriz, ni ninguna forma conveniente de organizar que sea inicializado Por ejemplo, las entradas de directorio de los primeros sistemas Unix pueden describirse en C como

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

Quería que la estructura no se limitara a caracterizar un objeto abstracto sino también a describir una colección de bits que podrían leerse desde un directorio. ¿Dónde podría el compilador ocultar el puntero a name que exigía la semántica? Incluso si las estructuras se pensaran de manera más abstracta y el espacio para los punteros se pudiera ocultar de alguna manera, ¿cómo podría manejar el problema técnico de inicializar correctamente estos punteros al asignar un objeto complicado, tal vez uno que especificara estructuras que contenían arrays que contienen estructuras a una profundidad arbitraria?

La solución constituyó el salto crucial en la cadena evolutiva entre BCPL sin tipo y C. mecanografiada. Eliminó la materialización del puntero en el almacenamiento, y en su lugar 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 se descomponen en 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 propia matriz; Si desea una asignación 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.

También, piensa en matrices multidimensionales; ¿dónde almacenaría los metadatos de longitud para cada dimensión de manera tal que aún pueda 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 asume que hay matrices en C. No 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 trozos 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 es 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 un ensamblador portátil (más o menos) más legible.