Co jest takiego trudnego w przypadku wskaźników / rekurencji? [Zamknięte]

W opałach szkół java Joel omawia swoje doświadczenia w Penn i trudność „błędów segmentacji”. On mówi

[błędy są trudne, dopóki nie] „weź głęboki oddech i naprawdę spróbuj zmusić swój umysł do pracy na dwóch różnych poziomach abstrakcji jednocześnie”.

Biorąc pod uwagę listę typowych przyczyn segfaultów, nie rozumiem, jak musimy pracować na 2 poziomach abstrakcji.

Z jakiegoś powodu Joel uważa te koncepcje za kluczowe dla zdolności programistów do abstrakcji. Nie chcę zakładać zbyt wiele. Więc co jest takiego trudnego w przypadku wskaźników / rekurencji? Przykłady byłyby fajne.

Po raz pierwszy zauważyłem, że wskaźniki i rekurencja były trudne na studiach. Wziąłem kilka typowych kursów pierwszego roku (jeden to C i Asembler, drugi był w Schemacie). Oba kursy rozpoczęły się od setek studentów, z których wielu miało wieloletnie doświadczenie w programowaniu na poziomie szkoły średniej (zwykle w tamtych czasach BASIC i Pascal). Ale jak tylko wskaźniki zostały wprowadzone na kursie C, a rekursja została wprowadzona na kursie Scheme, ogromna liczba studentów - być może nawet większość - została całkowicie zmarnowana. Były to dzieci, które wcześniej napisały DUŻO kodu i nie miały żadnych problemów, ale kiedy trafiły we wskaźniki i rekurencję, uderzyły także w ścianę pod względem zdolności poznawczych.

Moja hipoteza jest taka, że ​​wskaźniki i rekurencja są takie same, ponieważ wymagają utrzymania dwóch poziomów abstrakcji w głowie jednocześnie. Jest coś w wielopoziomowej abstrakcji, która wymaga pewnego rodzaju zdolności umysłowych, których jest bardzo możliwe, że niektórzy nigdy nie będą mieli.

• W przypadku wskaźników „dwa poziomy abstrakcji” to „dane, adres danych, adres adresu danych itp.” Lub to, co tradycyjnie nazywamy „wartością vs. referencją”. Dla nieprzeszkolonego studenta bardzo trudno jest dostrzec różnicę między adresem x a samym x .
• W przypadku rekurencji „dwa poziomy abstrakcji” rozumieją, w jaki sposób funkcja może się nazywać sama. Algorytm rekurencyjny jest czasem tym, co ludzie nazywają „programowaniem przez pobożne życzenia” i bardzo, bardzo nienaturalnie jest myśleć o algorytmie w kategoriach „przypadek podstawowy + przypadek indukcyjny” zamiast bardziej naturalnej „listy kroków, które należy wykonać, aby rozwiązać problem . ” Dla nieprzeszkolonego studenta przyglądającego się algorytmowi rekurencyjnemu algorytm wydaje się prosić o pytanie .

Byłbym również całkowicie skłonny zaakceptować fakt, że można uczyć wskazówek i / lub rekurencji dla kogokolwiek ... Nie mam dowodów w ten czy inny sposób. Wiem, że empirycznie, faktyczne zrozumienie tych dwóch pojęć jest bardzo, bardzo dobrym predyktorem ogólnych umiejętności programowania i że w normalnym toku licencjackim treningu CS te dwie koncepcje są jednymi z największych przeszkód.

Rekurencja to nie tylko „funkcja, która sama się nazywa”. Naprawdę nie docenisz, dlaczego rekurencja jest trudna, dopóki nie wyciągniesz ramek stosu, aby dowiedzieć się, co poszło nie tak z parserem rekurencyjnego zejścia. Często będziesz mieć funkcje wzajemnie rekurencyjne (funkcja A wywołuje funkcję B, która wywołuje funkcję C, która może wywoływać funkcję A). Może być bardzo trudno zorientować się, co poszło nie tak, gdy masz głębokie ramki na stosy w rekurencyjnej serii funkcji.

Jeśli chodzi o wskaźniki, znowu koncepcja wskaźników jest dość prosta: zmienna przechowująca adres pamięci. Ale znowu, gdy coś pójdzie nie tak ze skomplikowaną strukturą danych void**wskaźników, które wskazują na różne węzły, zobaczysz, dlaczego może to być trudne, gdy próbujesz dowiedzieć się, dlaczego jeden z twoich wskaźników wskazuje na śmieciowy adres.

Java obsługuje wskaźniki (nazywane są referencjami) i obsługuje rekurencję. Na pierwszy rzut oka jego argument wydaje się bezcelowy.

To, o czym tak naprawdę mówi, to zdolność do debugowania. Wskaźnik Java (err, referencja) z pewnością wskazuje prawidłowy obiekt. Wskaźnik AC nie jest. A sztuczka w programowaniu C, zakładając, że nie używasz narzędzi takich jak valgrind , polega na tym, aby dowiedzieć się dokładnie, gdzie spieprzyłeś wskaźnik (rzadko w punkcie znajdującym się w stosie).

Problem ze wskaźnikami i rekurencją nie polega na tym, że niekoniecznie są trudne do zrozumienia, ale na tym, że są źle nauczane, szczególnie w odniesieniu do języków takich jak C lub C ++ (głównie dlatego, że same języki są źle nauczane). Za każdym razem, gdy słyszę (lub czytam), ktoś mówi „tablica jest tylko wskaźnikiem”, umieram trochę w środku.

Podobnie, za każdym razem, gdy ktoś używa funkcji Fibonacciego do zilustrowania rekurencji, chcę krzyczeć. Jest to zły przykład, ponieważ wersja iteracyjna nie jest trudniejsza do napisania i działa co najmniej tak dobrze lub lepiej niż wersja rekurencyjna i nie daje rzeczywistego zrozumienia, dlaczego rozwiązanie rekurencyjne byłoby przydatne lub pożądane. Quicksort, przechodzenie przez drzewa itp. Są znacznie lepszymi przykładami przyczyny i sposobu rekurencji.

Konieczność zmarnowania wskaźników jest artefaktem pracy w języku programowania, który je ujawnia. Pokolenia programistów Fortran budowały listy, drzewa, stosy i kolejki bez potrzeby używania specjalnego typu wskaźnika (lub dynamicznej alokacji pamięci) i nigdy nie słyszałem, aby ktokolwiek oskarżał Fortran o bycie zabawkowym językiem.

Istnieje kilka trudności ze wskaźnikami:

1. Aliasing Możliwość zmiany wartości obiektu przy użyciu różnych nazw / zmiennych.
2. Brak lokalizacji Możliwość zmiany wartości obiektu w kontekście innym niż ten, w którym jest deklarowana (dzieje się tak również w przypadku argumentów przekazywanych przez referencję).
3. Niezgodność czasu życia Czas życia wskaźnika może różnić się od czasu życia obiektu, na który wskazuje, co może prowadzić do nieprawidłowych odwołań (SEGFAULTS) lub śmieci.
4. Wskaźnik arytmetyczny . Niektóre języki programowania pozwalają na manipulowanie wskaźnikami jako liczbami całkowitymi, co oznacza, że ​​wskaźniki mogą wskazywać w dowolnym miejscu (w tym w najbardziej nieoczekiwanych miejscach, w których występuje błąd). Aby poprawnie używać arytmetyki wskaźników, programista musi być świadomy wielkości pamięci wskazywanych obiektów, i to jest coś więcej do przemyślenia.
5. Rzutowanie typu Zdolność rzutowania wskaźnika z jednego typu na inny pozwala na zastąpienie pamięci obiektu innego niż zamierzony.

Właśnie dlatego programista musi dokładniej przemyśleć, kiedy używa wskaźników (nie wiem o dwóch poziomach abstrakcji ). Oto przykład typowych błędów popełnianych przez nowicjusza:

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

Zauważ, że kod podobny do powyższego jest całkowicie rozsądny w językach, które nie mają pojęcia wskaźników, ale raczej jedną z nazw (referencji), obiektów i wartości, jako funkcjonalne języki programowania i języki z odśmiecaniem (Java, Python). .

Trudność z funkcjami rekurencyjnymi występuje, gdy ludzie bez wystarczającego zaplecza matematycznego (gdzie rekurencyjność jest powszechna i wymagana wiedza) próbują do nich podejść, myśląc, że funkcja będzie zachowywać się inaczej w zależności od tego, ile razy była wcześniej wywoływana . Problem ten nasila się, ponieważ funkcje rekurencyjne mogą być rzeczywiście tworzone w sposób, w jaki trzeba myśleć w ten sposób, aby je zrozumieć.

Pomyśl o funkcjach rekurencyjnych z przekazywanymi wskaźnikami, jak w proceduralnej implementacji drzewa czerwono-czarnego, w którym struktura danych jest modyfikowana na miejscu; jest to coś trudniejszego do myślenia niż funkcjonalny odpowiednik .

Nie jest to wspomniane w pytaniu, ale innym ważnym problemem, z którym nowicjusze mają trudności, jest współbieżność .

Jak wspomnieli inni, istnieje dodatkowy, nie konceptualny problem z niektórymi konstrukcjami języka programowania: jest tak, że nawet jeśli zrozumiemy, proste i uczciwe błędy w tych konstrukcjach mogą być niezwykle trudne do debugowania.

Wskaźniki i rekurencja to dwie osobne bestie i istnieją różne powody, które kwalifikują każdą z nich jako „trudną”.

Zasadniczo wskaźniki wymagają innego modelu mentalnego niż przypisanie wyłącznie zmiennej. Kiedy mam zmienną wskaźnika, to po prostu: wskaźnik do innego obiektu, jedyne dane, które zawiera, to adres pamięci, na który wskazuje. Na przykład, jeśli mam wskaźnik int32 i przypisuję mu wartość bezpośrednio, nie zmieniam wartości int, wskazuję na nowy adres pamięci (istnieje wiele fajnych sztuczek, które można z tym zrobić ). Jeszcze bardziej interesujące jest posiadanie wskaźnika do wskaźnika (dzieje się tak, gdy przekazujesz zmienną Ref jako funkcję parametru w C #, funkcja może przypisać zupełnie inny obiekt do parametru i ta wartość będzie nadal obowiązywać, gdy funkcja wychodzi.

Rekurencja wymaga niewielkiego skoku mentalnego podczas pierwszego uczenia się, ponieważ definiujesz funkcję pod względem samego siebie. Jest to szalona koncepcja, kiedy po raz pierwszy ją spotkasz, ale kiedy ją zrozumiesz, staje się drugą naturą.

Wróćmy jednak do tematu. Argument Joela nie dotyczy wskaźników ani rekurencji samych w sobie, ale raczej faktu, że uczniowie są usuwani z tego, jak naprawdę działają komputery. To jest nauka w informatyce. Istnieje wyraźna różnica między nauką programowania a nauką działania programów. Nie sądzę, żeby chodziło o to, że „nauczyłem się tego w ten sposób, więc każdy powinien się tego nauczyć”, argumentując, że wiele programów CS staje się sławnymi szkołami handlowymi.

Daję P. Brianowi +1, ponieważ czuję się tak, jak on: rekurencja jest tak fundamentalną koncepcją, że ten, kto ma z nią najmniejsze trudności, powinien lepiej rozważyć znalezienie pracy w Mac Donalds, ale nawet tam jest rekurencja:

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

Z pewnością brak zrozumienia dotyczy także naszych szkół. Tutaj należy wprowadzić liczby naturalne, takie jak Peano, Dedekind i Frege, abyśmy później nie mieli większych trudności.

Nie zgadzam się z Joelem, że problemem jest myślenie na wielu poziomach abstrakcji per se, myślę, że bardziej chodzi o to, że wskaźniki i rekurencja to dwa dobre przykłady problemów, które wymagają zmiany modelu mentalnego, jaki ludzie mają na temat działania programów.

Wskaźniki są, jak sądzę, prostszym przykładem do zilustrowania. Radzenie sobie ze wskaźnikami wymaga mentalnego modelu wykonywania programu, który uwzględnia sposób faktycznej pracy programów z adresami i danymi pamięci. Z mojego doświadczenia wynika, że ​​często programiści nawet o tym nie myśleli, zanim nie poznali wskaźników. Nawet jeśli znają to w abstrakcyjny sposób, nie przyjęli tego do swojego poznawczego modelu działania programu. Wprowadzenie wskaźników wymaga zasadniczej zmiany sposobu myślenia o działaniu kodu.

Rekurencja jest problematyczna, ponieważ istnieją dwa koncepcyjne bloki do zrozumienia. Pierwszy znajduje się na poziomie maszyny i podobnie jak wskaźniki można go pokonać, dobrze rozumiejąc, w jaki sposób programy są faktycznie przechowywane i wykonywane. Innym problemem związanym z rekurencją jest, jak sądzę, fakt, że ludzie mają naturalną tendencję do dekonstruowania problemu rekurencyjnego na nierekurencyjny, co zaburza rozumienie funkcji rekurencyjnej jako gestaltu. Jest to albo problem z ludźmi o niewystarczającym zapleczu matematycznym, albo modelem mentalnym, który nie wiąże teorii matematycznej z rozwojem programów.

Chodzi o to, że nie sądzę, aby wskaźniki i rekurencja były jedynymi dwoma obszarami, które są problematyczne dla ludzi tkwionych w niewystarczającym modelu mentalnym. Wydaje się, że równoległość jest kolejną dziedziną, w której niektórzy ludzie po prostu utknęli i mają trudności z dostosowaniem swojego modelu mentalnego do rozliczeń, po prostu często wskaźniki i rekurencja są łatwe do sprawdzenia w wywiadzie.

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

Pojęcie danych referencyjnych i kodu leży u podstaw definicji wskaźników i rekurencji. Niestety, powszechne zetknięcie się z imperatywnymi językami programowania skłoniło studentów informatyki do przekonania, że ​​muszą zrozumieć wdrożenie poprzez zachowanie operacyjne swoich środowisk uruchomieniowych, kiedy powinni zaufać tej tajemnicy funkcjonalnemu aspektowi języka. Sumowanie wszystkich liczb do stu wydaje się prostą kwestią, zaczynając od jednego i dodając go do następnego w sekwencji i robienia tego do tyłu za pomocą okrągłych funkcji odniesienia, wydaje się przewrotne, a nawet niebezpieczne dla wielu, którzy nie są przyzwyczajeni do bezpieczeństwa czyste funkcje.

Pojęcie samomodyfikujących danych i kodu leży u podstaw odpowiednio definicji obiektów (tj. Danych inteligentnych) i makr. Wspominam o nich, ponieważ są one jeszcze trudniejsze do zrozumienia, szczególnie gdy oczekuje się operacyjnego zrozumienia środowiska wykonawczego na podstawie kombinacji wszystkich czterech pojęć - np. Makro generującego zestaw obiektów, który implementuje rekurencyjny parser za pomocą drzewa wskaźników . Zamiast śledzić całą operację stanu programu krok po kroku przez każdą warstwę abstrakcji naraz, programiści muszą nauczyć się ufać, że ich zmienne są przypisywane tylko raz w ramach czystych funkcji i że powtarzane są wywołania tej samej czystej funkcji z te same argumenty zawsze dają ten sam wynik (tj. przejrzystość referencyjna), nawet w języku obsługującym również nieczyste funkcje, takim jak Java. Bieganie w kółko po czasie wykonywania jest bezowocnym przedsięwzięciem. Abstrakcja powinna uprościć.

Bardzo podobny do odpowiedzi Anona.
Oprócz trudności poznawczych dla początkujących, zarówno wskaźniki, jak i rekurencja są bardzo potężne i mogą być używane w tajemniczy sposób.

Minusem wielkiej mocy jest to, że dają ci wielką moc, by popsuć twój program w subtelny sposób.
Przechowywanie fałszywej wartości w normalnej zmiennej jest wystarczająco złe, ale przechowywanie czegoś fałszywego we wskaźniku może powodować różnego rodzaju opóźnione katastroficzne rzeczy.
Co gorsza, efekty te mogą ulec zmianie podczas próby zdiagnozowania / debugowania, co jest przyczyną dziwnego zachowania programu.

Podobnie z rekurencją. Może to być bardzo skuteczny sposób organizowania podstępnych rzeczy - poprzez wpychanie podstępów do ukrytej struktury danych (stosu).
Ale jeśli coś zostanie zrobione subtelnie źle, może być trudno zorientować się, co się dzieje.