Dlaczego tablice C nie śledzą ich długości?

Jakie było uzasadnienie braku wyraźnego przechowywania długości tablicy z tablicą w C?

Moim zdaniem istnieje wiele powodów, aby to zrobić, ale niewiele z tego powodu (C89). Na przykład:

1. Dostępna długość bufora może zapobiec jego przepełnieniu.
2. Styl Java arr.lengthjest zarówno przejrzysty, jak i pozwala programistom uniknąć konieczności utrzymywania wielu ints na stosie, jeśli ma się do czynienia z kilkoma tablicami
3. Parametry funkcji stają się bardziej przekonujące.

Moim zdaniem jednak najbardziej motywującym powodem jest to, że zwykle nie oszczędza się miejsca bez zachowania długości. Zaryzykowałbym stwierdzenie, że większość zastosowań tablic wymaga dynamicznej alokacji. To prawda, że ​​mogą być przypadki, w których ludzie używają tablicy przydzielonej na stosie, ale to tylko jedno wywołanie funkcji * - stos może obsłużyć dodatkowe 4 lub 8 bajtów.

Ponieważ menedżer sterty i tak musi śledzić rozmiar wolnego bloku zużywanego przez dynamicznie przydzielaną tablicę, dlaczego nie uczynić tej informacji użyteczną (i dodać dodatkową regułę, sprawdzaną podczas kompilacji, że nie można jawnie manipulować długością, chyba że lubię strzelać sobie w stopę).

Jedyną rzeczą, o której mogę myśleć po drugiej stronie, jest to, że żadne śledzenie długości nie mogło uprościć kompilatorów, ale nie było o wiele prostsze.

* Technicznie można napisać jakąś funkcję rekurencyjną z tablicą z automatycznym przechowywaniem, aw tym (bardzo skomplikowanym) przypadku przechowywania długości może faktycznie skutkować efektywnie większym wykorzystaniem miejsca.

Tablice C śledzą ich długość, ponieważ długość tablicy jest właściwością statyczną:

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

Zwykle nie możesz zapytać o tę długość, ale nie musisz, ponieważ jest ona statyczna - po prostu zadeklaruj makro XS_LENGTHdla długości i gotowe.

Ważniejszą kwestią jest to, że tablice C domyślnie rozkładają się na wskaźniki, np. Po przekazaniu do funkcji. Ma to pewien sens i pozwala na kilka ciekawych sztuczek na niskim poziomie, ale traci informacje o długości tablicy. Lepszym pytaniem byłoby więc, dlaczego C zaprojektowano z tą ukrytą degradacją wskaźników.

Inną kwestią jest to, że wskaźniki nie potrzebują pamięci poza samym adresem pamięci. C pozwala nam rzutować liczby całkowite na wskaźniki, wskaźniki na inne wskaźniki i traktować wskaźniki tak, jakby były tablicami. Czyniąc to, C nie jest wystarczająco szalony, aby wytworzyć pewną długość tablicy, ale wydaje się ufać motto Spidermana: z wielką mocą programista ma nadzieję spełnić wielką odpowiedzialność za śledzenie długości i przelewów.

Wiele miało to związek z dostępnymi wówczas komputerami. Skompilowany program musiał nie tylko działać na komputerze o ograniczonych zasobach, ale, co ważniejsze, sam kompilator musiał działać na tych komputerach. W czasie, gdy Thompson opracował C, korzystał z PDP-7 z 8k RAM. Skomplikowane funkcje językowe, które nie miały bezpośredniego odpowiednika w rzeczywistym kodzie maszynowym, po prostu nie zostały uwzględnione w tym języku.

Uważne przeczytanie historii języka C pozwala lepiej zrozumieć powyższe, ale nie było to całkowicie wynikiem ograniczeń maszynowych, które mieli:

Co więcej, język (C) wykazuje znaczną moc opisywania ważnych pojęć, na przykład wektorów, których długość zmienia się w czasie wykonywania, z kilkoma tylko podstawowymi zasadami i konwencjami. ... Interesujące jest porównanie podejścia C z podejściem dwóch prawie współczesnych języków, Algola 68 i Pascala [Jensen 74]. Tablice w Algolu 68 albo mają stałe granice, albo są „elastyczne:” zarówno w definicji języka, jak iw kompilatorach wymagany jest znaczny mechanizm, aby dostosować się do elastycznych tablic (i nie wszystkie kompilatory je w pełni implementują). Oryginalny Pascal miał tylko stały rozmiar tablice i łańcuchy, a to okazało się ograniczające [Kernighan 81].

Macierze C są z natury silniejsze. Dodanie do nich granic ogranicza to, do czego programista może ich użyć. Takie ograniczenia mogą być przydatne dla programistów, ale z konieczności są również ograniczające.

Wracając do czasów, gdy C został utworzony, i dodatkowe 4 bajty miejsca na każdy ciąg, bez względu na to, jak krótkie byłoby marnotrawstwem!

Jest jeszcze jeden problem - pamiętaj, że C nie jest zorientowane obiektowo, więc jeśli wykonasz przedrostek długości wszystkich łańcuchów, musiałby zostać zdefiniowany jako wewnętrzny typ kompilatora, a nie a char*. Jeśli byłby to specjalny typ, to nie byłbyś w stanie porównać łańcucha z ciągiem stałym, tj .:

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

musiałby mieć specjalne szczegóły kompilatora, aby albo przekonwertować ten ciąg statyczny na Ciąg, albo mieć różne funkcje ciągów, aby uwzględnić prefiks długości.

Myślę jednak, że ostatecznie nie wybrali przedrostka długości w przeciwieństwie do Pascala.

W C dowolny ciągły podzbiór tablicy jest również tablicą i może być obsługiwany jako taki. Dotyczy to zarówno operacji odczytu, jak i zapisu. Ta właściwość nie zachowałaby się, gdyby rozmiar był przechowywany jawnie.

Największym problemem związanym z oznaczaniem tablic ich długością jest nie tyle przestrzeń wymagana do przechowywania tej długości, ani pytanie, w jaki sposób powinna być przechowywana (użycie jednego dodatkowego bajtu dla krótkich tablic na ogół nie byłoby niekorzystne, ani użycie czterech dodatkowe bajty dla długich tablic, ale użycie czterech bajtów może być nawet dla krótkich tablic). Dużo większym problemem jest to, że dany kod, taki jak:

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

jedynym sposobem, w jaki kod byłby w stanie zaakceptować pierwsze wywołanie, ClearTwoElementsale odrzucić drugie, byłoby otrzymanie przez ClearTwoElementsmetodę informacji wystarczających do tego, aby wiedzieć, że w każdym przypadku otrzymywał odwołanie do części tablicy foooprócz znajomości, która część. To zwykle podwaja koszt przekazywania parametrów wskaźnika. Ponadto, jeśli każda tablica była poprzedzona wskaźnikiem do adresu tuż za końcem (najbardziej wydajny format sprawdzania poprawności), zoptymalizowany kod dla ClearTwoElementsprawdopodobnie stałby się mniej więcej taki:

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

Zauważ, że program wywołujący metodę może, ogólnie rzecz biorąc, całkowicie słusznie przekazać wskaźnik na początek tablicy lub ostatni element metody; tylko jeśli metoda próbuje uzyskać dostęp do elementów, które wychodzą poza tablicę przekazaną, takie wskaźniki spowodowałyby problemy. W związku z tym wywoływana metoda musi najpierw upewnić się, że tablica jest wystarczająco duża, aby arytmetyka wskaźnika w celu sprawdzenia poprawności jej argumentów nie wykroczyła poza granice, a następnie wykonała obliczenia wskaźnika w celu sprawdzenia poprawności argumentów. Czas poświęcony na taką weryfikację prawdopodobnie przekroczyłby koszt poświęcony na jakąkolwiek prawdziwą pracę. Ponadto metoda może być bardziej wydajna, gdyby została napisana i wywołana:

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

Koncepcja typu, który łączy coś w celu identyfikacji przedmiotu z czymś w celu zidentyfikowania jego części, jest dobra. Wskaźnik w stylu C jest jednak szybszy, jeśli nie jest konieczne przeprowadzenie sprawdzania poprawności.

Jedną z fundamentalnych różnic między C i większością innych języków 3. generacji oraz wszystkimi nowszymi językami, o których wiem, jest to, że C nie zostało zaprojektowane tak, aby ułatwić życie programistom. Został zaprojektowany z oczekiwaniem, że programista wie, co robi i chce robić dokładnie i tylko to. Nie robi nic „za kulisami”, więc nie dostajesz żadnych niespodzianek. Nawet optymalizacja poziomu kompilatora jest opcjonalna (chyba że używasz kompilatora Microsoft).

Jeśli programista chce napisać granice sprawdzając w swoim kodzie, C sprawia, że ​​jest to wystarczająco proste, ale programiści muszą zapłacić odpowiednią cenę pod względem miejsca, złożoności i wydajności. Chociaż od wielu lat nie używałem go w gniewie, nadal go używam, ucząc programowania, aby przejść przez koncepcję podejmowania decyzji opartych na ograniczeniach. Zasadniczo oznacza to, że możesz zrobić wszystko, co chcesz, ale każda podejmowana decyzja ma swoją cenę, o której musisz wiedzieć. Staje się to jeszcze ważniejsze, gdy zaczynasz mówić innym, co chcesz robić w ich programach.

Krótka odpowiedź:

Ponieważ C jest językiem programowania niskiego poziomu , oczekuje się, że sam zajmiesz się tymi problemami, ale daje to większą elastyczność w sposobie jego implementacji.

C ma koncepcję czasu kompilacji tablicy, która jest inicjowana długością, ale w czasie wykonywania całość jest po prostu przechowywana jako pojedynczy wskaźnik na początku danych. Jeśli chcesz przekazać długość tablicy do funkcji wraz z tablicą, zrób to sam:

retval = my_func(my_array, my_array_length);

Lub możesz użyć struktury ze wskaźnikiem i długością lub dowolnego innego rozwiązania.

Język wyższego poziomu zrobiłby to za ciebie jako część swojego typu tablicy. W C masz obowiązek zrobienia tego sam, ale także elastyczność wyboru sposobu, w jaki to zrobić. A jeśli cały kod, który piszesz, zna już długość tablicy, nie musisz w ogóle podawać długości jako zmiennej.

Oczywistą wadą jest to, że bez nieodłącznych ograniczeń sprawdzania tablic przekazywanych jako wskaźniki można stworzyć niebezpieczny kod, ale taka jest natura języków niskiego poziomu / języków systemowych i kompromis, jaki dają.

Problem dodatkowej przestrzeni dyskowej jest problemem, ale moim zdaniem niewielki. W końcu przez większość czasu i tak będziesz musiał śledzić długość, chociaż amon miał dobrą opinię, że często można ją śledzić statycznie.

Większy problem polega na tym, gdzie przechowywać długość i jak długo ją robić. Nie ma jednego miejsca, które działałoby we wszystkich sytuacjach. Można powiedzieć, że wystarczy zapisać długość w pamięci tuż przed danymi. Co jeśli tablica nie wskazuje na pamięć, ale coś w rodzaju bufora UART?

Pozostawienie tej długości pozwala programiście tworzyć własne abstrakty dla odpowiedniej sytuacji, a istnieje wiele gotowych bibliotek dostępnych dla ogólnego zastosowania. Prawdziwe pytanie brzmi: dlaczego te abstrakcje nie są używane w aplikacjach wrażliwych na bezpieczeństwo?

Z opracowania języka C :

Wyglądało na to, że struktury powinny intuicyjnie mapować się na pamięć w maszynie, ale w strukturze zawierającej tablicę nie było dobrego miejsca na schowanie wskaźnika zawierającego podstawę tablicy ani żadnego wygodnego sposobu na ustawienie go zainicjowano. Na przykład wpisy katalogu wczesnych systemów uniksowych można opisać w C jako

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

Chciałem, aby struktura nie tylko charakteryzowała obiekt abstrakcyjny, ale także opisywała kolekcję bitów, które można odczytać z katalogu. Gdzie kompilator mógłby ukryć wskaźnik name, którego wymagała semantyka? Nawet jeśli konstrukcje byłyby rozważane bardziej abstrakcyjnie, a przestrzeń wskaźników mogła być jakoś ukryta, jak mogłem poradzić sobie z problemem technicznym związanym z prawidłową inicjalizacją wskaźników podczas przydzielania skomplikowanego obiektu, być może takiego, który określał struktury zawierające tablice zawierające struktury na dowolną głębokość?

Rozwiązanie stanowiło kluczowy skok w ewolucyjnym łańcuchu między typem BCPL a typem C. Wyeliminowało ono materializację wskaźnika w pamięci, a zamiast tego spowodowało utworzenie wskaźnika, gdy nazwa tablicy jest wymieniona w wyrażeniu. Reguła, która obowiązuje w dzisiejszym C, polega na tym, że wartości typu tablicy są konwertowane, gdy pojawiają się w wyrażeniach, na wskaźniki do pierwszego z obiektów tworzących tablicę.

Ten fragment wyjaśnia, dlaczego wyrażenia tablicowe rozpadają się na wskaźniki w większości przypadków, ale to samo rozumowanie dotyczy tego, dlaczego długość tablicy nie jest przechowywana z samą tablicą; jeśli chcesz mapowania typu jeden do jednego między definicją typu a jej reprezentacją w pamięci (tak jak zrobiła to Ritchie), to nie ma dobrego miejsca do przechowywania tych metadanych.

Pomyśl także o tablicach wielowymiarowych; gdzie miałbyś przechowywać metadane długości dla każdego wymiaru, tak abyś nadal mógł przechodzić przez tablicę czymś podobnym

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

Pytanie zakłada, że ​​w C. są tablice. Nie ma. Rzeczy, które są nazywane tablicami, to po prostu cukier składniowy do operacji na ciągłych sekwencjach danych i arytmetyki wskaźników.

Poniższy kod kopiuje niektóre dane z src do dst w kawałkach o dużych rozmiarach, nie wiedząc, że jest to właściwie ciąg znaków.

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

Dlaczego C jest tak uproszczony, że nie ma odpowiednich tablic? Nie znam poprawnej odpowiedzi na to nowe pytanie. Ale niektórzy ludzie często mówią, że C jest (nieco) bardziej czytelnym i przenośnym asemblerem.