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

20

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.

P.Brian.Mackey
źródło
31
Przestań się martwić, co Joel może o tobie myśleć. Jeśli uznasz, że rekurencja jest łatwa, to dobrze. Nie wszyscy inni to robią.
FrustratedWithFormsDesigner
6
Rekursja jest z definicji łatwa (funkcja wywołująca siebie), ale trudna jest wiedza, kiedy jej użyć i jak ją uruchomić.
JeffO
9
Złóż podanie o pracę w Fog Creek i daj nam znać, jak to wygląda. Wszyscy jesteśmy bardzo zainteresowani Twoją autopromocją.
Joel Etherton
4
@ P.Brian.Mackey: Nie jesteśmy nieporozumieniami. Pytanie tak naprawdę niczego nie zadaje. To rażąca autopromocja. Jeśli chcesz wiedzieć, o co pyta Joel o wskaźniki / rekurencję, zapytaj go: [email protected]
Joel Etherton
19
Duplikat tego pytania ?
ozz

Odpowiedzi:

38

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.

Joel Spolsky
źródło
4
„bardzo, bardzo nienaturalnie jest myśleć o algorytmie w kategoriach„ przypadek podstawowy + przypadek indukcyjny ”” - Myślę, że to nie jest nienaturalne, po prostu dzieci nie są odpowiednio szkolone.
Ingo
14
gdyby to było naturalne, nie musiałbyś być szkolony. : P
Joel Spolsky
1
Dobra uwaga :), ale czy nie potrzebujemy szkolenia z matematyki, logiki, fizyki itp., Które w szerszym sensie są najbardziej naturalne. Co ciekawe, niewielu programistów ma problemy ze składnią języków, ale jest pełna rekurencji.
Ingo
1
Na moim uniwersytecie pierwszy kurs rozpoczął się od programowania funkcjonalnego i rekursji niemal natychmiast, na długo przed wprowadzeniem mutacji i tym podobnych. Odkryłem, że niektórzy studenci bez doświadczenia lepiej rozumieli rekursję niż ci z pewnym doświadczeniem. To powiedziawszy, najwyższą klasę tworzą ludzie z dużym doświadczeniem.
Tikhon Jelvis
2
Myślę, że niemożność zrozumienia wskaźników i rekurencji jest związana z a) ogólnym poziomem IQ oraz b) złym wykształceniem matematycznym.
quant_dev
23

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.

Charles Salvia
źródło
1
Wdrożenie rekurencyjnego porządnego parsera miało miejsce, gdy naprawdę poczułem, że mam pewien wpływ na rekurencję. Wskaźniki są łatwe do zrozumienia na wysokim poziomie, jak powiedziałeś; Dopóki nie przejdziesz do sedna implementacji zajmującej się wskaźnikami, zrozumiesz, dlaczego są one skomplikowane.
Chris
Wzajemna rekurencja między wieloma funkcjami jest zasadniczo taka sama jak goto.
starblue
2
@starblue, niezupełnie - ponieważ każda ramka stosu tworzy nowe wystąpienia zmiennych lokalnych.
Charles Salvia
Masz rację, tylko rekurencja ogona jest taka sama jak goto.
starblue
3
@wnoise int a() { return b(); }może być rekurencyjne, ale zależy to od definicji b. Więc to nie jest tak proste, jak się wydaje ...
alternatywa
14

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

Zaraz
źródło
5
Wskaźniki jako takie są szczegółem. Używanie referencji w Javie nie jest bardziej skomplikowane niż używanie lokalnych zmiennych w C. Nawet mieszanie ich w taki sposób, jak robią to implementacje Lisp (atom może być liczbą całkowitą o ograniczonym rozmiarze, znakiem lub wskaźnikiem) nie jest trudne. Robi się trudniej, gdy język pozwala na lokalny lub referencyjny ten sam rodzaj danych, z inną składnią, i naprawdę włochaty, gdy język pozwala na arytmetykę wskaźników.
David Thornley,
@David - um, co to ma wspólnego z moją odpowiedzią?
Anon
1
Twój komentarz na temat wskaźników obsługujących Javę.
David Thornley,
msgstr "gdzie spieprzyłeś wskaźnik (rzadko jest to punkt znaleziony w ścieżce stosu)." Jeśli masz szczęście, aby uzyskać stacktrace.
Omega Centauri
5
Zgadzam się z Davidem Thornleyem; Java nie obsługuje wskaźników, chyba że mogę utworzyć wskaźnik do wskaźnika do wskaźnika do wskaźnika int. Co może przypuszczam, że mógłbym, tworząc 4-5 klas, z których każda odwołuje się do czegoś innego, ale czy to naprawdę wskazuje, czy to brzydkie obejście?
alternatywny
12

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.

John Bode
źródło
Zgadzam się, miałem lata / dekady Fortranu, zanim zobaczyłem rzeczywiste wskazówki, więc korzystałem już z własnego sposobu robienia tego samego, zanim dałem szansę, aby lanquage / kompilator zrobił to za mnie. Myślę też, że składnia C dotycząca wskaźników / adresów jest bardzo myląca, nawet jeśli koncepcja wartości przechowywanej pod adresem jest bardzo prosta.
Omega Centauri
jeśli masz link do Quicksort zaimplementowany w Fortran IV, chciałbym go zobaczyć. Nie mówiąc, że nie da się tego zrobić - w rzeczywistości zaimplementowałem go w języku BASIC około 30 lat temu - ale byłbym zainteresowany, aby to zobaczyć.
Anon
Nigdy nie pracowałem w Fortran IV, ale zaimplementowałem kilka algorytmów rekurencyjnych w implementacji VAX / VMS w Fortran 77 (istniał haczyk pozwalający na zapisanie celu goto jako specjalnego rodzaju zmiennej, abyś mógł pisać GOTO target) . Myślę jednak, że musieliśmy zbudować własne stosy czasu wykonywania. To było wystarczająco dawno temu, że nie pamiętam już szczegółów.
John Bode
8

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.

Apalala
źródło
Użycie tej funkcji zwróci prawidłowy wskaźnik, ale zmienna jest w zakresie wyższym niż zakres, który wywołał funkcję, więc wskaźnik może (zakładać, że) zostanie unieważniony, gdy używany jest malloc.
prawej strony
4
@Radek S: Nie, nie będzie. Zwróci nieprawidłowy wskaźnik, który w niektórych środowiskach działa przez chwilę, dopóki coś innego go nie nadpisze. (W praktyce będzie to stos, a nie stos. Nie malloc()jest to bardziej prawdopodobne niż jakakolwiek inna funkcja.)
wnoise,
1
@Radeck W przykładowej funkcji wskaźnik wskazuje na pamięć, którą gwarantuje język programowania (w tym przypadku C), gdy funkcja powróci. Tak więc zwrócony wskaźnik wskazuje na śmieci . Języki z wyrzucaniem elementów bezużytecznych utrzymują obiekt przy życiu, o ile jest przywoływany w dowolnym kontekście.
Apalala
Nawiasem mówiąc, Rust ma wskazówki, ale bez tych problemów. (gdy nie jest w niebezpiecznym kontekście)
Sarge Borsch
2

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.

Michael Brown
źródło
1

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.

Ingo
źródło
6
To cofanie ogona, które prawdopodobnie pęka.
Michael K
6
Niestety, dla mnie zapętlenie jest prawdopodobnie rekurencją ogona :)
Ingo
3
@Ingo: :) Funkcjonalny fanatyk!
Michael K
1
@Michael - hehe, rzeczywiście !, ale myślę, że można argumentować, że rekurencja jest bardziej fundamentalną koncepcją.
Ingo
@Ingo: Rzeczywiście możesz (przykład pokazuje to dobrze). Jednak z jakiegoś powodu ludzie mają trudności z programowaniem - wydaje nam się, że potrzebujemy tego dodatkowego goto topz jakiegoś powodu IME.
Michael K
1

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.

Cercerilla
źródło
1
  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ć.

Niekonkurencyjny
źródło
-1

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.

Omega Centauri
źródło