Apa yang begitu sulit tentang pointer / rekursi? [Tutup]

Dalam bahaya sekolah-sekolah java Joel membahas pengalamannya di Penn dan kesulitan "kesalahan segmentasi". Dia berkata

[segfault sulit sampai Anda] "ambil napas dalam-dalam dan benar-benar mencoba memaksa pikiran Anda untuk bekerja pada dua tingkat abstraksi yang berbeda secara bersamaan."

Diberikan daftar penyebab umum untuk segfault, saya tidak mengerti bagaimana kita harus bekerja pada 2 level abstraksi.

Untuk beberapa alasan, Joel menganggap konsep-konsep ini inti untuk kemampuan programmer untuk abstrak. Saya tidak ingin berasumsi terlalu banyak. Jadi, apa yang sulit dari pointer / rekursi? Contohnya akan menyenangkan.

Saya pertama kali memperhatikan bahwa petunjuk dan rekursi sulit di perguruan tinggi. Saya telah mengikuti beberapa kursus tahun pertama yang tipikal (satu adalah C dan Assembler, yang lain dalam Skema). Kedua kursus dimulai dengan ratusan siswa, banyak di antaranya memiliki pengalaman pemrograman tingkat sekolah menengah (biasanya BASIC dan Pascal, pada masa itu). Tetapi segera setelah petunjuk diperkenalkan dalam kursus C, dan rekursi diperkenalkan dalam kursus Skema, sejumlah besar siswa - bahkan mungkin mayoritas - benar-benar bingung. Ini adalah anak-anak yang telah menulis BANYAK kode sebelumnya dan tidak memiliki masalah sama sekali, tetapi ketika mereka mencapai pointer dan rekursi, mereka juga menabrak dinding dalam hal kemampuan kognitif mereka.

Hipotesis saya adalah bahwa petunjuk dan rekursi adalah sama karena mereka mengharuskan Anda menyimpan dua tingkat abstraksi di kepala Anda pada saat yang sama. Ada sesuatu tentang multi-level-abstraksi yang membutuhkan jenis kecerdasan mental yang sangat mungkin sebagian orang tidak akan pernah miliki.

• Dengan pointer, "dua tingkat abstraksi" adalah "data, alamat data, alamat alamat data, dll.," Atau apa yang secara tradisional kita sebut "nilai vs referensi." Bagi siswa yang tidak terlatih, sangat sulit untuk melihat perbedaan antara alamat x dan x itu sendiri .
• Dengan rekursi, "dua tingkat abstraksi" memahami bagaimana mungkin suatu fungsi memanggil dirinya sendiri. Algoritma rekursif kadang-kadang disebut "pemrograman oleh angan-angan" dan sangat, sangat tidak wajar untuk memikirkan suatu algoritma dalam hal "kasus dasar + kasus induktif" daripada daftar langkah-langkah yang Anda ikuti untuk menyelesaikan masalah yang lebih alami. . " Untuk siswa yang tidak terlatih melihat algoritma rekursif, algoritma tersebut muncul untuk mengajukan pertanyaan .

Saya juga akan sangat bersedia untuk menerima bahwa mungkin untuk mengajarkan petunjuk dan / atau rekursi kepada siapa pun ... Saya tidak memiliki bukti dengan satu atau lain cara. Saya tahu bahwa secara empiris, dapat benar-benar memahami kedua konsep ini adalah prediktor yang sangat, sangat baik dari kemampuan pemrograman umum dan bahwa dalam kursus normal pelatihan CS sarjana, kedua konsep ini berdiri sebagai beberapa hambatan terbesar.

Rekursi bukan hanya "fungsi yang memanggil dirinya sendiri". Anda tidak akan benar-benar menghargai mengapa rekursi sulit sampai Anda menemukan diri Anda menyusun stack-frame untuk mencari tahu apa yang salah dengan parser keturunan rekursif Anda. Seringkali Anda memiliki fungsi yang saling rekursif (fungsi A memanggil fungsi B, yang memanggil fungsi C, yang dapat memanggil fungsi A). Ini bisa sangat sulit untuk mencari tahu apa yang salah ketika Anda N stackframes jauh di dalam serangkaian fungsi yang saling rekursif.

Adapun pointer, sekali lagi, konsep pointer cukup sederhana: variabel yang menyimpan alamat memori. Tetapi sekali lagi, ketika terjadi kesalahan dengan struktur data rumit void**pointer yang menunjuk ke node yang berbeda, Anda akan melihat mengapa hal itu bisa menjadi rumit ketika Anda berjuang untuk mencari tahu mengapa salah satu pointer Anda menunjuk ke alamat sampah.

Java mendukung pointer (disebut referensi) dan mendukung rekursi. Jadi di permukaan, argumennya tampak sia-sia.

Apa yang sebenarnya dia bicarakan adalah kemampuan untuk debug. Pointer Java (err, referensi) dijamin untuk menunjuk ke objek yang valid. Pointer AC tidak. Dan trik dalam pemrograman C, dengan asumsi bahwa Anda tidak menggunakan alat seperti valgrind , adalah untuk mencari tahu di mana Anda mengacaukan pointer (jarang pada titik yang ditemukan di stacktrace).

Masalah dengan pointer dan rekursi bukanlah bahwa mereka selalu sulit untuk dipahami, tetapi bahwa mereka diajarkan dengan buruk, terutama sehubungan dengan bahasa seperti C atau C ++ (terutama karena bahasa itu sendiri sedang diajarkan dengan buruk). Setiap kali saya mendengar (atau membaca) seseorang berkata "sebuah array hanyalah sebuah pointer" Saya mati sedikit di dalam.

Demikian pula, setiap kali seseorang menggunakan fungsi Fibonacci untuk menggambarkan rekursi saya ingin berteriak. Ini adalah contoh buruk karena versi berulang tidak lebih sulit untuk ditulis dan berkinerja setidaknya sama baiknya atau lebih baik daripada yang rekursif, dan itu tidak memberi Anda wawasan nyata mengapa solusi rekursif akan berguna atau diinginkan. Quicksort, traversal pohon, dll., Adalah contoh yang jauh lebih baik untuk mengapa dan bagaimana rekursi.

Harus bercanda dengan pointer adalah artefak bekerja dalam bahasa pemrograman yang memaparkan mereka. Generasi programmer Fortran membuat daftar dan pohon, tumpukan, dan antrian tanpa perlu tipe pointer khusus (atau alokasi memori dinamis), dan saya belum pernah mendengar ada yang menuduh Fortran sebagai bahasa mainan.

Ada beberapa kesulitan dengan pointer:

1. Mengasingkan Kemungkinan mengubah nilai suatu objek menggunakan berbagai nama / variabel.
2. Non-lokalitas Kemungkinan mengubah nilai objek dalam konteks yang berbeda dari yang dinyatakannya (ini juga terjadi dengan argumen yang dilewatkan oleh referensi).
3. Ketidakcocokan seumur hidup Masa pakai penunjuk mungkin berbeda dari masa objek yang ditunjuknya, dan itu dapat menyebabkan referensi yang tidak valid (SEGFAULTS) atau sampah.
4. Aritmatika Pointer . Beberapa bahasa pemrograman memungkinkan manipulasi pointer sebagai integer, dan itu berarti bahwa pointer dapat menunjuk ke mana saja (termasuk tempat-tempat yang paling tidak terduga ketika ada bug). Untuk menggunakan aritmatika pointer dengan benar, seorang programmer harus menyadari ukuran memori dari objek yang ditunjuk, dan itu sesuatu yang lebih untuk dipikirkan.
5. Type Casts Kemampuan untuk melemparkan pointer dari satu jenis ke yang lain memungkinkan penimpaan memori dari suatu objek yang berbeda dari yang dimaksud.

Itu sebabnya seorang programmer harus berpikir lebih teliti ketika menggunakan pointer (saya tidak tahu tentang dua level abstraksi ). Ini adalah contoh kesalahan khas yang dilakukan oleh seorang pemula:

Pair* make_pair(int a, int b)
{
    Pair p;
    p.a = a;
    p.b = b;
    return &p;
}

Perhatikan bahwa kode seperti di atas sangat masuk akal dalam bahasa yang tidak memiliki konsep pointer tetapi salah satu nama (referensi), objek, dan nilai, sebagai bahasa pemrograman fungsional, dan bahasa dengan pengumpulan sampah (Java, Python) tidak .

Kesulitan dengan fungsi rekursif terjadi ketika orang-orang tanpa latar belakang matematika yang cukup (di mana sifat rekursif adalah umum dan diperlukan) mencoba untuk mendekati mereka dengan berpikir bahwa fungsi tersebut akan berperilaku berbeda tergantung pada berapa kali telah dipanggil sebelumnya . Masalah itu diperparah karena fungsi rekursif memang dapat dibuat dengan cara di mana Anda harus berpikir seperti itu untuk memahaminya.

Pikirkan fungsi rekursif dengan pointer yang dibagikan, seperti dalam implementasi prosedural dari Pohon Merah-Hitam di mana struktur data dimodifikasi di tempat; itu adalah sesuatu yang lebih sulit untuk dipikirkan daripada rekan fungsional .

Tidak disebutkan dalam pertanyaan, tetapi masalah penting lainnya yang membuat siswa kesulitan adalah konkurensi .

Seperti yang telah disebutkan orang lain, ada masalah tambahan, non-konseptual dengan beberapa konstruksi bahasa pemrograman: itu adalah bahwa bahkan jika kita mengerti, kesalahan sederhana dan jujur ​​dengan konstruksi itu bisa sangat sulit untuk di-debug.

Pointer dan rekursi adalah dua binatang yang terpisah dan ada alasan berbeda yang masing-masing memenuhi syarat sebagai "sulit".

Secara umum, pointer memerlukan model mental yang berbeda dari tugas variabel murni. Ketika saya memiliki variabel pointer, hanya saja: pointer ke objek lain, satu-satunya data yang dikandungnya adalah alamat memori yang ditunjuknya. Jadi misalnya jika saya memiliki pointer int32 dan memberikan nilai secara langsung, saya tidak mengubah nilai int, saya menunjuk ke alamat memori baru (ada banyak trik rapi yang dapat Anda lakukan dengan ini ). Yang lebih menarik adalah memiliki pointer ke pointer (ini adalah apa yang terjadi ketika Anda melewatkan variabel Ref sebagai Parameter fungsi dalam C #, fungsi tersebut dapat menetapkan objek yang sama sekali berbeda untuk Parameter dan nilai itu masih akan berada dalam ruang lingkup ketika fungsi tersebut keluar.

Rekursi membutuhkan sedikit lompatan mental ketika pertama kali belajar karena Anda mendefinisikan suatu fungsi dalam hal itu sendiri. Ini adalah konsep liar ketika Anda pertama kali menemukannya, tetapi begitu Anda memahami gagasan itu, itu menjadi sifat kedua.

Tapi kembali ke pokok pembicaraan. Argumen Joel bukan tentang petunjuk atau rekursi di dalam dan tentang diri mereka sendiri, tetapi lebih pada kenyataan bahwa siswa dikeluarkan lebih jauh dari bagaimana komputer benar-benar bekerja. Ini adalah Ilmu dalam Ilmu Komputer. Ada perbedaan nyata antara belajar ke program dan belajar bagaimana program bekerja. Saya tidak berpikir itu masalah tentang "Saya mempelajarinya dengan cara ini sehingga setiap orang harus mempelajarinya dengan cara ini" karena dia berpendapat bahwa banyak program CS menjadi sekolah perdagangan yang dimuliakan.

Saya memberi P. Brian +1, karena saya merasa seperti itu: rekursi adalah konsep mendasar sehingga dia yang memiliki sedikit kesulitan dengannya sebaiknya mempertimbangkan mencari pekerjaan di mac donalds, tetapi kemudian, bahkan ada rekursi:

make a burger:
   put a cold burger on the grill
   wait
   flip
   wait
   hand the fried burger over to the service personel
   unless its end of shift: make a burger

Tentunya, kurangnya pemahaman juga ada hubungannya dengan sekolah kami. Di sini orang harus memperkenalkan bilangan asli seperti Peano, Dedekind dan Frege, jadi kita tidak akan mengalami banyak kesulitan di kemudian hari.

Saya tidak setuju dengan Joel bahwa masalahnya adalah salah satu dari berpikir pada berbagai tingkat abstraksi per-se, saya pikir lebih dari itu petunjuk dan rekursi adalah dua contoh masalah yang baik yang memerlukan perubahan dalam model mental yang dimiliki orang tentang bagaimana program bekerja.

Pointer, saya pikir, adalah kasus yang lebih sederhana untuk diilustrasikan. Berurusan dengan pointer memerlukan model mental pelaksanaan program yang menjelaskan cara program bekerja dengan alamat dan data memori. Pengalaman saya adalah sering kali programmer bahkan tidak memikirkan hal ini sebelum mereka belajar tentang pointer. Bahkan jika mereka mengetahuinya dalam pengertian abstrak, mereka belum mengadopsinya ke dalam model kognitif mereka tentang bagaimana suatu program bekerja. Ketika pointer diperkenalkan itu membutuhkan perubahan mendasar dalam cara mereka berpikir tentang cara kerja kode.

Rekursi bermasalah karena ada dua blok konseptual untuk pemahaman. Yang pertama adalah pada level mesin, dan seperti halnya pointer dapat diatasi dengan mengembangkan pemahaman yang baik tentang bagaimana sebenarnya program disimpan dan dieksekusi. Masalah lain dengan rekursi adalah, saya pikir, bahwa orang memiliki kecenderungan alami untuk mencoba mendekonstruksi masalah rekursif menjadi masalah non-rekursif, yang membingungkan pemahaman tentang fungsi rekursif sebagai gestalt. Ini bisa menjadi masalah dengan orang-orang yang memiliki latar belakang matematika yang tidak memadai, atau model mental yang tidak mengikat teori matematika dengan pengembangan program.

Masalahnya adalah, saya tidak berpikir bahwa pointer dan rekursi adalah satu-satunya dua area yang bermasalah bagi orang yang terjebak dalam model mental yang tidak memadai. Paralelisme tampaknya menjadi bidang lain yang membuat sebagian orang terjebak dan mengalami kesulitan mengadaptasi model mental mereka untuk dipertanggungjawabkan, hanya saja sering kali petunjuk dan rekursi mudah diuji dalam sebuah wawancara.

  DATA    |     CODE
          |
 pointer  |   recursion    SELF REFERENTIAL
----------+---------------------------------
 objects  |   macro        SELF MODIFYING
          |
          |

Konsep data referensi diri dan kode masing-masing mendasari definisi pointer dan rekursi. Sayangnya, paparan luas ke bahasa pemrograman imperatif telah menyebabkan siswa ilmu komputer untuk percaya bahwa mereka harus memahami implementasi melalui perilaku operasional runtime mereka ketika mereka harus mempercayai misteri ini dengan aspek fungsional bahasa. Menjumlahkan semua angka hingga seratus tampaknya masalah sederhana mulai dengan satu dan menambahkannya ke yang berikutnya dalam urutan dan melakukannya mundur dengan bantuan fungsi referensial diri melingkar tampaknya jahat dan bahkan berbahaya bagi banyak orang yang tidak terbiasa dengan keselamatan fungsi murni.

Konsep data dan kode modifikasi sendiri mendasari definisi objek (yaitu data pintar) dan makro masing-masing. Saya menyebutkan ini karena mereka bahkan lebih sulit untuk dipahami terutama ketika pemahaman operasional runtime diharapkan dari kombinasi keempat konsep - misalnya makro menghasilkan seperangkat objek yang mengimplementasikan pengurai yang layak secara rekursif dengan bantuan pohon pointer. . Daripada menelusuri seluruh operasi keadaan program langkah demi langkah melalui setiap lapisan abstraksi sekaligus, programmer imperatif perlu belajar untuk percaya bahwa variabel mereka hanya ditugaskan sekali dalam fungsi murni dan bahwa pemanggilan berulang dari fungsi murni yang sama dengan argumen yang sama selalu menghasilkan hasil yang sama (yaitu transparansi referensial), bahkan dalam bahasa yang mendukung fungsi yang tidak murni juga, seperti Java. Berlari dalam lingkaran setelah runtime adalah usaha yang sia-sia. Abstraksi harus disederhanakan.

Sangat mirip dengan jawaban Anon.
Selain kesulitan kognitif untuk pemula, baik petunjuk dan rekursi sangat kuat, dan dapat digunakan dengan cara yang samar.

Kelemahan dari kekuatan besar, adalah mereka memberi Anda kekuatan besar untuk mengacaukan program Anda dengan cara yang halus.
Menyimpan nilai palsu ke dalam variabel normal sudah cukup buruk, tetapi menyimpan sesuatu yang palsu ke dalam pointer dapat menyebabkan segala macam hal bencana yang tertunda terjadi.
Dan lebih buruk lagi, efek tersebut dapat berubah ketika Anda mencoba mendiagnosis / men-debug apa penyebab perilaku program aneh. Tetapi, jika sesuatu dilakukan secara salah secara salah, mungkin sulit untuk mengetahui apa yang sedang terjadi.

Begitu pula dengan rekursi. Ini bisa menjadi cara yang sangat ampuh untuk mengatur hal-hal rumit - dengan memasukkan trickiness ke dalam struktur data tersembunyi (stack).