Por que as matrizes C não controlam seu comprimento?

Qual foi o motivo por trás de não armazenar explicitamente o comprimento de uma matriz com uma matriz em C?

Do meu ponto de vista, há razões esmagadoras para fazê-lo, mas não muitas em apoio ao padrão (C89). Por exemplo:

1. Ter o comprimento disponível em um buffer pode impedir a saturação do buffer.
2. Um estilo Java arr.lengthé claro e evita que o programador precise manter muitos ints na pilha se estiver lidando com várias matrizes
3. Os parâmetros de função se tornam mais convincentes.

Mas talvez a razão mais motivadora, na minha opinião, seja que, geralmente, nenhum espaço é economizado sem manter o comprimento. Atrevo-me a dizer que a maioria dos usos de matrizes envolve alocação dinâmica. É verdade que pode haver alguns casos em que as pessoas usam uma matriz alocada na pilha, mas essa é apenas uma chamada de função * - a pilha pode lidar com 4 ou 8 bytes extras.

Como o gerenciador de heap precisa rastrear o tamanho do bloco livre usado pela matriz alocada dinamicamente de qualquer maneira, por que não tornar essas informações utilizáveis ​​(e adicionar a regra adicional, verificada no tempo de compilação, que não é possível manipular o comprimento explicitamente, a menos que seja necessário? gosta de dar um tiro no próprio pé).

A única coisa que posso pensar no outro lado é que nenhum seguimento comprimento pode ter feito compiladores mais simples, mas não que muito mais simples.

* Tecnicamente, pode-se escrever algum tipo de função recursiva com uma matriz com armazenamento automático e, nesse caso (muito elaborado), armazenar o comprimento pode realmente resultar em um uso de espaço efetivamente maior.

As matrizes C controlam seu comprimento, pois o comprimento da matriz é uma propriedade estática:

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

Normalmente, você não pode consultar esse comprimento, mas não precisa, porque é estático de qualquer maneira - basta declarar uma macro XS_LENGTHpara o comprimento e pronto.

A questão mais importante é que as matrizes C se degradam implicitamente em ponteiros, por exemplo, quando passadas para uma função. Isso faz algum sentido e permite alguns bons truques de baixo nível, mas perde as informações sobre o comprimento da matriz. Portanto, uma pergunta melhor seria por que C foi projetado com essa degradação implícita em ponteiros.

Outra questão é que os ponteiros não precisam de armazenamento, exceto o próprio endereço de memória. C nos permite converter números inteiros para ponteiros, ponteiros para outros ponteiros e tratar ponteiros como se fossem matrizes. Enquanto isso, C não é insano o suficiente para fabricar um certo comprimento de matriz, mas parece confiar no lema do Homem-Aranha: com grande poder, o programador cumprirá a grande responsabilidade de acompanhar os comprimentos e transbordamentos.

Muito disso tinha a ver com os computadores disponíveis no momento. Não apenas o programa compilado teve que ser executado em um computador com recursos limitados, mas, talvez mais importante, o próprio compilador teve que ser executado nessas máquinas. Na época, Thompson desenvolveu o C, ele estava usando um PDP-7, com 8k de RAM. Recursos complexos de linguagem que não tinham um analógico imediato no código de máquina real simplesmente não foram incluídos no idioma.

Uma leitura cuidadosa do histórico de C gera mais entendimento do que foi dito acima, mas não foi inteiramente o resultado das limitações da máquina que eles tinham:

Além disso, a linguagem (C) mostra um poder considerável para descrever conceitos importantes, por exemplo, vetores cuja duração varia em tempo de execução, com apenas algumas regras e convenções básicas. ... É interessante comparar a abordagem de C com a de duas línguas quase contemporâneas, Algol 68 e Pascal [Jensen 74]. As matrizes no Algol 68 têm limites fixos ou são `flexíveis: 'é necessário um mecanismo considerável tanto na definição da linguagem quanto nos compiladores, para acomodar as matrizes flexíveis (e nem todos os compiladores as implementam totalmente.) O original Pascal tinha apenas tamanho fixo matrizes e strings, e isso se mostrou confinante [Kernighan 81].

Matrizes C são inerentemente mais poderosas. Adicionar limites a eles restringe o que o programador pode usá-los. Tais restrições podem ser úteis para programadores, mas necessariamente também são limitativas.

No dia em que C foi criado, e 4 bytes de espaço extra para cada string, por mais curto que tenha sido um desperdício!

Há outro problema - lembre-se de que C não é orientado a objetos; portanto, se você usar o prefixo do comprimento de todas as strings, ele deverá ser definido como um tipo intrínseco do compilador, não a char*. Se fosse um tipo especial, não seria possível comparar uma sequência com uma constante, ou seja:

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

teria que ter detalhes especiais do compilador para converter essa string estática em uma String ou ter funções diferentes de string para levar em consideração o prefixo do comprimento.

Acho que, no final das contas, eles simplesmente não escolheram o prefixo de comprimento, diferentemente do que diz Pascal.

Em C, qualquer subconjunto contíguo de uma matriz também é uma matriz e pode ser operado como tal. Isso se aplica às operações de leitura e gravação. Esta propriedade não se manteria se o tamanho fosse armazenado explicitamente.

O maior problema em ter matrizes marcadas com seu comprimento não é tanto o espaço necessário para armazenar esse comprimento, nem a questão de como ele deve ser armazenado (o uso de um byte extra para matrizes curtas geralmente não seria questionável, nem o uso de quatro bytes extras para matrizes longas, mas usar quatro bytes mesmo para matrizes curtas pode ser). Um problema muito maior é esse código, 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);
}

a única maneira pela qual o código seria capaz de aceitar a primeira chamada, ClearTwoElementsmas rejeitar a segunda, seria o ClearTwoElementsmétodo receber informações suficientes para saber que, em cada caso, estava recebendo uma referência a parte da matriz foo, além de saber qual parte. Isso normalmente dobraria o custo de passar os parâmetros do ponteiro. Além disso, se cada matriz fosse precedida por um ponteiro para um endereço logo após o final (o formato mais eficiente para validação), o código otimizado para ClearTwoElementsprovavelmente se tornaria 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;
}

Observe que um responsável pela chamada de método pode, em geral, perfeitamente legitimamente transmitir um ponteiro para o início da matriz ou o último elemento para um método; somente se o método tentar acessar elementos que vão para fora da matriz passada, esses ponteiros causarão algum problema. Conseqüentemente, um método chamado precisaria primeiro garantir que a matriz fosse grande o suficiente para que o aritmético do ponteiro para validar seus argumentos não saia dos limites e faça alguns cálculos de ponteiro para validar os argumentos. O tempo gasto em tal validação provavelmente excederia o custo gasto com qualquer trabalho real. Além disso, o método provavelmente poderia ser mais eficiente se fosse escrito e chamado:

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

O conceito de um tipo que combina algo para identificar um objeto com algo para identificar uma parte dele é bom. Um ponteiro no estilo C é mais rápido, no entanto, se não for necessário executar a validação.

Uma das diferenças fundamentais entre C e a maioria das outras linguagens de terceira geração, e todas as linguagens mais recentes que conheço, é que C não foi projetado para tornar a vida mais fácil ou segura para o programador. Foi projetado com a expectativa de que o programador soubesse o que estava fazendo e desejasse fazer exatamente e somente isso. Ele não faz nada nos bastidores, para que você não tenha surpresas. Até a otimização no nível do compilador é opcional (a menos que você use um compilador da Microsoft).

Se um programador deseja escrever limites de verificação em seu código, C torna mais simples, mas o programador deve optar por pagar o preço correspondente em termos de espaço, complexidade e desempenho. Embora eu não o use com raiva por muitos anos, ainda o uso quando ensino programação para entender o conceito de tomada de decisão baseada em restrições. Basicamente, isso significa que você pode optar por fazer o que quiser, mas todas as decisões tomadas têm um preço que você precisa estar ciente. Isso se torna ainda mais importante quando você começa a dizer aos outros o que deseja que os programas deles façam.

Resposta curta:

Como C é uma linguagem de programação de baixo nível , ele espera que você cuide desses problemas, mas isso adiciona maior flexibilidade exatamente à maneira como você o implementa.

C tem um conceito em tempo de compilação de uma matriz que é inicializada com um comprimento, mas em tempo de execução a coisa toda é simplesmente armazenada como um ponteiro único para o início dos dados. Se você deseja passar o comprimento da matriz para uma função junto com a matriz, faça você mesmo:

retval = my_func(my_array, my_array_length);

Ou você pode usar uma estrutura com um ponteiro e comprimento, ou qualquer outra solução.

Uma linguagem de nível superior faria isso por você como parte de seu tipo de matriz. Em C, você tem a responsabilidade de fazer isso sozinho, mas também a flexibilidade de escolher como fazê-lo. E se todo o código que você está escrevendo já sabe o comprimento da matriz, você não precisa passar o comprimento como uma variável.

A desvantagem óbvia é que, sem a verificação de limites inerentes às matrizes passadas como ponteiros, você pode criar um código perigoso, mas essa é a natureza das linguagens de baixo nível / sistemas e o trade-off que elas oferecem.

O problema do armazenamento extra é um problema, mas, na minha opinião, um problema menor. Afinal, na maioria das vezes você precisará rastrear o comprimento de qualquer maneira, embora amon tenha enfatizado que muitas vezes pode ser rastreado estaticamente.

Um problema maior é onde armazenar o comprimento e quanto tempo durar. Não há um lugar que funcione em todas as situações. Você pode dizer apenas armazene o comprimento na memória antes dos dados. E se a matriz não estiver apontando para a memória, mas algo como um buffer UART?

Deixar de lado o comprimento permite que o programador crie suas próprias abstrações para a situação apropriada, e há muitas bibliotecas prontas disponíveis para o caso de uso geral. A verdadeira questão é por que essas abstrações não estão sendo usadas em aplicativos sensíveis à segurança?

Do desenvolvimento da linguagem C :

As estruturas, ao que parece, deveriam mapear de maneira intuitiva a memória da máquina, mas em uma estrutura que contenha uma matriz, não havia um bom lugar para esconder o ponteiro que continha a base da matriz, nem qualquer maneira conveniente de organizá-la. inicializado. Por exemplo, as entradas de diretório dos primeiros sistemas Unix podem ser descritas em C como

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

Queria que a estrutura não apenas caracterizasse um objeto abstrato, mas também descrevesse uma coleção de bits que podem ser lidos em um diretório. Onde o compilador poderia ocultar o ponteiro para o nameque a semântica exigia? Mesmo se as estruturas fossem pensadas de maneira mais abstrata e o espaço para ponteiros pudesse ser oculto de alguma forma, como eu poderia lidar com o problema técnico de inicializar adequadamente esses ponteiros ao alocar um objeto complicado, talvez um que especificasse estruturas contendo matrizes contendo estruturas com profundidade arbitrária?

A solução constituiu o salto crucial na cadeia evolutiva entre o BCPL sem tipo e o tipo C. Ele eliminou a materialização do ponteiro no armazenamento e, em vez disso, causou a criação do ponteiro quando o nome do array é mencionado em uma expressão. A regra, que sobrevive no C de hoje, é que os valores do tipo de matriz são convertidos, quando aparecem em expressões, em ponteiros para o primeiro dos objetos que compõem a matriz.

Essa passagem aborda por que as expressões de matriz decaem para ponteiros na maioria das circunstâncias, mas o mesmo raciocínio se aplica ao motivo pelo qual o comprimento da matriz não é armazenado na própria matriz; se você deseja um mapeamento individual entre a definição de tipo e sua representação na memória (como Ritchie fez), não há um bom lugar para armazenar esses metadados.

Além disso, pense em matrizes multidimensionais; onde você armazenaria os metadados de comprimento para cada dimensão, para poder percorrer a matriz com 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++ );

A questão assume que existem matrizes em C. Não há. As coisas que são chamadas de matrizes são apenas um açúcar sintático para operações em seqüências contínuas de dados e aritmética de ponteiros.

O código a seguir copia alguns dados do src para o dst em partes com tamanho int sem saber que na verdade é uma sequência 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 que C é tão simplificado que não possui matrizes apropriadas? Não sei a resposta correta para esta nova pergunta. Mas algumas pessoas costumam dizer que C é apenas (um pouco) montador mais legível e portátil.