Mengapa array C tidak melacak panjangnya?

Apa alasan di balik tidak secara eksplisit menyimpan panjang array dengan array C?

Cara saya melihatnya, ada banyak alasan untuk melakukannya tetapi tidak terlalu banyak mendukung standar (C89). Misalnya:

1. Memiliki panjang yang tersedia di buffer dapat mencegah buffer overrun.
2. Gaya Java arr.lengthjelas dan menghindari programer dari harus mempertahankan banyak ints di stack jika berhadapan dengan beberapa array
3. Parameter fungsi menjadi lebih meyakinkan.

Tapi mungkin alasan yang paling memotivasi, menurut pendapat saya, adalah bahwa biasanya, tidak ada ruang yang disimpan tanpa mempertahankan panjangnya. Saya berani mengatakan bahwa sebagian besar penggunaan array melibatkan alokasi dinamis. Benar, mungkin ada beberapa kasus di mana orang menggunakan array yang dialokasikan pada stack, tapi itu hanya satu panggilan fungsi * - stack dapat menangani tambahan 4 atau 8 byte.

Karena manajer tumpukan harus melacak ukuran blok bebas yang digunakan oleh array yang dialokasikan secara dinamis, mengapa tidak membuat informasi tersebut dapat digunakan (dan menambahkan aturan tambahan, diperiksa pada waktu kompilasi, bahwa seseorang tidak dapat memanipulasi panjang secara eksplisit kecuali jika mau suka menembak diri sendiri di kaki).

Satu-satunya hal yang dapat saya pikirkan di sisi lain adalah bahwa tidak ada pelacakan panjang mungkin telah membuat kompiler sederhana, tapi tidak yang jauh lebih sederhana.

* Secara teknis, seseorang dapat menulis semacam fungsi rekursif dengan array dengan penyimpanan otomatis, dan dalam hal ini (sangat rumit) menyimpan panjang mungkin memang menghasilkan lebih banyak penggunaan ruang secara efektif.

Array C melacak panjangnya, karena panjang array adalah properti statis:

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

Anda biasanya tidak dapat menanyakan panjang ini, tetapi Anda tidak perlu karena itu statis - cukup deklarasikan makro XS_LENGTHuntuk panjangnya, dan Anda selesai.

Masalah yang lebih penting adalah bahwa array C secara implisit terdegradasi menjadi pointer, misalnya ketika diteruskan ke suatu fungsi. Ini memang masuk akal, dan memungkinkan untuk beberapa trik tingkat rendah yang bagus, tetapi kehilangan informasi tentang panjang array. Jadi pertanyaan yang lebih baik adalah mengapa C dirancang dengan degradasi implisit ke pointer.

Masalah lain adalah bahwa pointer tidak memerlukan penyimpanan kecuali alamat memori itu sendiri. C memungkinkan kita untuk melemparkan bilangan bulat ke pointer, pointer ke pointer lainnya, dan memperlakukan pointer seolah-olah mereka array. Saat melakukan ini, C tidak cukup gila untuk membuat beberapa panjang array menjadi ada, tetapi tampaknya percaya pada moto Spiderman: dengan kekuatan besar programmer diharapkan akan memenuhi tanggung jawab besar untuk melacak panjang dan meluap.

Banyak dari ini berkaitan dengan komputer yang tersedia pada saat itu. Tidak hanya program yang dikompilasi harus dijalankan pada komputer sumber daya yang terbatas, tetapi, mungkin yang lebih penting, kompiler itu sendiri harus dijalankan pada mesin ini. Pada saat Thompson mengembangkan C, ia menggunakan PDP-7, dengan 8k RAM. Fitur bahasa yang kompleks yang tidak memiliki analog langsung pada kode mesin yang sebenarnya sama sekali tidak termasuk dalam bahasa.

Pembacaan yang cermat melalui sejarah C menghasilkan lebih banyak pemahaman di atas, tetapi itu tidak sepenuhnya akibat dari keterbatasan mesin yang mereka miliki:

Selain itu, bahasa (C) menunjukkan kekuatan yang cukup besar untuk menggambarkan konsep-konsep penting, misalnya, vektor yang panjangnya bervariasi pada waktu berjalan, dengan hanya beberapa aturan dasar dan konvensi. ... Sangat menarik untuk membandingkan pendekatan C dengan dua bahasa yang hampir bersamaan, Algol 68 dan Pascal [Jensen 74]. Array dalam Algol 68 memiliki batas tetap, atau `fleksibel: 'diperlukan mekanisme yang cukup baik dalam definisi bahasa, dan dalam kompiler, untuk mengakomodasi array fleksibel (dan tidak semua kompiler sepenuhnya mengimplementasikannya.) Pascal asli hanya memiliki ukuran tetap array dan string, dan ini terbukti mengurung [Kernighan 81].

Array C secara inheren lebih kuat. Menambahkan batasan pada mereka membatasi apa yang bisa digunakan oleh programmer. Pembatasan seperti itu mungkin berguna untuk programmer, tetapi tentu juga membatasi.

Kembali pada hari ketika C dibuat, dan tambahan 4 byte ruang untuk setiap string tidak peduli seberapa pendek akan sangat sia-sia!

Ada masalah lain - ingat bahwa C tidak berorientasi objek, jadi jika Anda melakukan awalan panjang semua string, itu harus didefinisikan sebagai tipe intrinsik kompiler, bukan a char*. Jika itu adalah tipe khusus, maka Anda tidak akan dapat membandingkan string dengan string konstan, yaitu:

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

harus memiliki detail kompiler khusus untuk mengonversi string statis menjadi String, atau memiliki fungsi string yang berbeda untuk memperhitungkan awalan panjang.

Saya pikir pada akhirnya, mereka tidak memilih cara awalan panjang seperti Pascal.

Dalam C, setiap himpunan bagian yang berdekatan dari array juga merupakan array dan dapat dioperasikan seperti itu. Ini berlaku untuk operasi baca dan tulis. Properti ini tidak akan tahan jika ukurannya disimpan secara eksplisit.

Masalah terbesar dengan memiliki array yang ditandai dengan panjangnya tidak begitu banyak ruang yang dibutuhkan untuk menyimpan panjang itu, atau pertanyaan tentang bagaimana harus disimpan (menggunakan satu byte tambahan untuk array pendek umumnya tidak akan keberatan, juga tidak akan menggunakan empat byte tambahan untuk array panjang, tetapi menggunakan empat byte bahkan untuk array pendek mungkin). Masalah yang jauh lebih besar adalah kode yang diberikan seperti:

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

satu-satunya cara agar kode dapat menerima panggilan pertama, ClearTwoElementstetapi menolak panggilan kedua adalah ClearTwoElementsmetode menerima informasi yang cukup untuk mengetahui bahwa dalam setiap kasus kode menerima referensi ke bagian array fooselain mengetahui bagian mana. Itu biasanya akan menggandakan biaya melewati parameter pointer. Lebih lanjut, jika setiap array didahului oleh pointer ke alamat yang baru saja melewati akhir (format yang paling efisien untuk validasi), kode yang dioptimalkan untuk ClearTwoElementskemungkinan akan menjadi sesuatu seperti:

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

Perhatikan bahwa pemanggil metode dapat, secara umum, secara sempurna secara sah mengirimkan pointer ke awal array atau elemen terakhir ke suatu metode; hanya jika metode ini mencoba untuk mengakses elemen-elemen yang keluar di luar array yang lewat akan pointer tersebut menyebabkan masalah. Akibatnya, metode yang dipanggil harus terlebih dahulu memastikan array cukup besar sehingga aritmatika pointer untuk memvalidasi argumennya tidak akan keluar dari batas, dan kemudian melakukan beberapa perhitungan pointer untuk memvalidasi argumen. Waktu yang dihabiskan dalam validasi tersebut kemungkinan akan melebihi biaya yang dihabiskan untuk melakukan pekerjaan nyata. Lebih lanjut, metode ini mungkin bisa lebih efisien jika ditulis dan dipanggil:

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

Konsep tipe yang menggabungkan sesuatu untuk mengidentifikasi objek dengan sesuatu untuk mengidentifikasi bagiannya adalah bagus. Akan tetapi, penunjuk gaya-C lebih cepat jika tidak perlu melakukan validasi.

Salah satu perbedaan mendasar antara C dan sebagian besar bahasa generasi ke-3 lainnya, dan semua bahasa yang lebih baru yang saya ketahui, adalah bahwa C tidak dirancang untuk membuat hidup lebih mudah atau lebih aman bagi programmer. Itu dirancang dengan harapan bahwa programmer tahu apa yang mereka lakukan dan ingin melakukan dengan tepat dan hanya itu. Itu tidak melakukan apa pun 'di balik layar' sehingga Anda tidak mendapatkan kejutan. Bahkan optimasi tingkat kompiler adalah opsional (kecuali jika Anda menggunakan kompiler Microsoft).

Jika seorang programmer ingin menulis batasan memeriksa kode mereka, C membuatnya cukup sederhana untuk melakukannya, tetapi programmer harus memilih untuk membayar harga yang sesuai dalam hal ruang, kompleksitas dan kinerja. Meskipun saya belum menggunakannya dalam kemarahan selama bertahun-tahun, saya masih menggunakannya ketika mengajar pemrograman untuk melintasi konsep pengambilan keputusan berdasarkan kendala. Pada dasarnya, itu berarti Anda dapat memilih untuk melakukan apa pun yang Anda inginkan, tetapi setiap keputusan yang Anda buat memiliki harga yang harus Anda waspadai. Ini menjadi lebih penting ketika Anda mulai memberi tahu orang lain apa yang Anda ingin program mereka lakukan.

Jawaban singkat:

Karena C adalah bahasa pemrograman tingkat rendah, bahasa C mengharapkan Anda untuk mengurus sendiri masalah ini, tetapi ini menambah fleksibilitas yang lebih besar dalam cara Anda menerapkannya.

C memiliki konsep waktu kompilasi array yang diinisialisasi dengan panjang tetapi pada saat runtime semuanya disimpan sebagai pointer tunggal ke awal data. Jika Anda ingin meneruskan panjang array ke suatu fungsi bersama dengan array, Anda melakukannya sendiri:

retval = my_func(my_array, my_array_length);

Atau Anda bisa menggunakan struct dengan pointer dan panjang, atau solusi lain.

Bahasa tingkat yang lebih tinggi akan melakukan ini untuk Anda sebagai bagian dari jenis arraynya. Dalam C Anda diberi tanggung jawab untuk melakukan ini sendiri, tetapi juga fleksibilitas untuk memilih bagaimana melakukannya. Dan jika semua kode yang Anda tulis sudah tahu panjang array, Anda tidak perlu melewatkan panjang sebagai variabel sama sekali.

Kelemahan yang jelas adalah bahwa tanpa batas yang melekat memeriksa array yang dilewati sebagai pointer Anda dapat membuat beberapa kode berbahaya tapi itu adalah sifat bahasa tingkat rendah / sistem dan pertukaran yang mereka berikan.

Masalah penyimpanan tambahan adalah masalah, tetapi menurut saya kecil. Lagi pula, sebagian besar waktu Anda akan perlu untuk melacak panjangnya, meskipun amon membuat poin yang baik bahwa sering dapat dilacak secara statis.

Masalah yang lebih besar adalah di mana menyimpan panjang dan berapa lama membuatnya. Tidak ada satu tempat yang berfungsi dalam semua situasi. Anda mungkin mengatakan hanya menyimpan panjang dalam memori sebelum data. Bagaimana jika array tidak menunjuk ke memori, tetapi sesuatu seperti buffer UART?

Meninggalkan panjang memungkinkan programmer untuk membuat abstraksi sendiri untuk situasi yang sesuai, dan ada banyak perpustakaan siap pakai yang tersedia untuk kasus tujuan umum. Pertanyaan sebenarnya adalah mengapa abstraksi itu tidak digunakan dalam aplikasi yang sensitif terhadap keamanan?

Dari Perkembangan Bahasa C :

Struktur, tampaknya, harus memetakan dengan cara yang intuitif ke memori di dalam mesin, tetapi dalam struktur yang mengandung array, tidak ada tempat yang baik untuk menyimpan pointer yang berisi basis array, maupun cara mudah untuk mengaturnya. diinisialisasi. Sebagai contoh, entri direktori sistem Unix awal dapat dijelaskan dalam C as

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

Saya ingin struktur tidak hanya untuk mencirikan objek abstrak tetapi juga untuk menggambarkan kumpulan bit yang dapat dibaca dari direktori. Di mana kompiler dapat menyembunyikan pointer ke namesemantik yang diminta? Bahkan jika struktur dianggap lebih abstrak, dan ruang untuk pointer bisa disembunyikan entah bagaimana, bagaimana saya bisa menangani masalah teknis menginisialisasi pointer ini dengan benar ketika mengalokasikan objek yang rumit, mungkin salah satu yang menetapkan struktur berisi array berisi struktur hingga kedalaman sewenang-wenang?

Solusinya merupakan lompatan penting dalam rantai evolusi antara BCPL tanpa tipe dan mengetik C. Ini menghilangkan materialisasi dari pointer di penyimpanan, dan bukannya menyebabkan penciptaan pointer ketika nama array disebutkan dalam ekspresi. Aturan, yang bertahan dalam C hari ini, adalah bahwa nilai-nilai tipe array dikonversi, ketika mereka muncul dalam ekspresi, menjadi pointer ke yang pertama dari objek yang membentuk array.

Bagian itu membahas mengapa ekspresi array membusuk ke pointer di sebagian besar keadaan, tetapi alasan yang sama berlaku untuk mengapa panjang array tidak disimpan dengan array itu sendiri; jika Anda ingin pemetaan satu-ke-satu antara definisi tipe dan perwakilannya dalam memori (seperti yang dilakukan Ritchie), maka tidak ada tempat yang baik untuk menyimpan metadata itu.

Juga, pikirkan tentang array multidimensi; di mana Anda menyimpan metadata panjang untuk setiap dimensi sehingga Anda masih bisa berjalan melalui array dengan sesuatu seperti

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

Pertanyaannya mengasumsikan bahwa ada array dalam C. Tidak ada. Hal-hal yang disebut array hanyalah gula sintaksis untuk operasi pada urutan data dan aritmatika pointer terus menerus.

Kode berikut menyalin beberapa data dari src ke dst dalam potongan berukuran int tidak mengetahui bahwa itu sebenarnya string karakter.

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

Mengapa C sangat sederhana sehingga tidak memiliki array yang tepat? Saya tidak tahu jawaban yang benar untuk pertanyaan baru ini. Tetapi beberapa orang sering mengatakan bahwa C hanya (agak) assembler lebih mudah dibaca dan portabel.