Dlaczego kompilatory są tak niezawodne?

Używamy kompilatorów na co dzień, jakby ich poprawność była podana, ale kompilatory są również programami i mogą potencjalnie zawierać błędy. Zawsze zastanawiałem się nad tą niezawodnością. Czy kiedykolwiek napotkałeś błąd w samym kompilatorze? Co to było i jak zdałeś sobie sprawę, że problem tkwi w samym kompilatorze?

... a jak nie robią kompilatory tak wiarygodne?

Są one dokładnie testowane pod kątem użytkowania przez tysiące, a nawet miliony programistów w czasie.

Również problem do rozwiązania jest dobrze zdefiniowany (poprzez bardzo szczegółową specyfikację techniczną). Charakter zadania łatwo poddaje się testom jednostkowym / systemowym. To znaczy, zasadniczo tłumaczy tekstowe dane wejściowe w bardzo specyficznym formacie na wyjściowe w innym rodzaju dobrze zdefiniowanym formacie (jakiś kod bajtowy lub kod maszynowy). Łatwo jest więc tworzyć i weryfikować przypadki testowe.

Co więcej, zwykle błędy są również łatwe do odtworzenia: oprócz dokładnej informacji o platformie i wersji kompilatora, zwykle wszystko, czego potrzebujesz, to fragment kodu wejściowego. Nie wspominając o tym, że użytkownicy kompilatora (jako sami programiści) zwykle wydają znacznie bardziej szczegółowe i szczegółowe raporty błędów niż jakikolwiek przeciętny użytkownik komputera :-)

Oprócz wszystkich wspaniałych dotychczasowych odpowiedzi:

Masz „uprzedzenie obserwatora”. Nie obserwujesz błędów i dlatego zakładasz, że ich nie ma.

Myślałem tak jak ty. Potem zacząłem pisać kompilatory profesjonalnie i powiem ci, że jest tam wiele błędów!

Nie widzisz błędów, ponieważ piszesz kod, który jest jak 99,999% całej reszty kodu, który ludzie piszą. Prawdopodobnie piszesz całkowicie normalny, prosty, wyraźnie poprawny kod, który wywołuje metody i uruchamia pętle i nie robi nic szczególnego ani dziwnego, ponieważ jesteś normalnym programistą rozwiązującym normalne problemy biznesowe.

Nie widzisz żadnych błędów kompilatora, ponieważ błędów kompilatora nie ma w łatwych do analizy, prostych, normalnych scenariuszach kodu; błędy dotyczą analizy dziwnego kodu, którego nie piszesz.

Z drugiej strony mam przeciwne nastawienie obserwatora. Cały dzień widzę szalony kod, więc dla mnie kompilatory wydają się być pełne błędów.

Jeśli usiądziesz ze specyfikacją języka dowolnego języka i weźmiesz jakąkolwiek implementację kompilatora dla tego języka i naprawdę spróbujesz ustalić, czy kompilator dokładnie zaimplementował specyfikację, czy nie, koncentrując się na niejasnych narożnych przypadkach, już wkrótce znajdziesz błędy kompilatora dość często. Dam ci przykład, oto błąd kompilatora C #, który dosłownie znalazłem pięć minut temu.

static void N(ref int x){}
...
N(ref 123);

Kompilator podaje trzy błędy.

• Argument ref lub out musi być zmienną, którą można przypisać.
• Najlepsze dopasowanie dla N (ref int x) zawiera nieprawidłowe argumenty.
• Brak „ref” w argumencie 1.

Oczywiście pierwszy komunikat o błędzie jest poprawny, a trzeci błąd. Algorytm generowania błędów próbuje dowiedzieć się, dlaczego pierwszy argument był nieprawidłowy, patrzy na niego, widzi, że jest stałą i nie wraca do kodu źródłowego, aby sprawdzić, czy został oznaczony jako „ref”; raczej zakłada, że ​​nikt nie byłby na tyle głupi, aby oznaczyć stałą jako ref, i decyduje, że ref musi być pominięty.

Nie jest jasne, jaki jest prawidłowy trzeci komunikat o błędzie, ale to nie jest to. W rzeczywistości nie jest jasne, czy drugi komunikat o błędzie jest poprawny. Czy rozwiązanie przeciążenia powinno zawieść, czy też „ref 123” powinno być traktowane jako argument ref odpowiedniego typu? Muszę teraz przemyśleć i omówić to z zespołem zajmującym się segregacją, abyśmy mogli ustalić, jakie jest prawidłowe zachowanie.

Nigdy nie widziałeś tego błędu, ponieważ prawdopodobnie nigdy nie zrobiłbyś czegoś tak głupiego, aby spróbować przekazać 123 ref. A jeśli tak, prawdopodobnie nawet nie zauważysz, że trzeci komunikat o błędzie jest bezsensowny, ponieważ pierwszy jest poprawny i wystarczający do zdiagnozowania problemu. Ale staram się robić takie rzeczy, ponieważ próbuję złamać kompilator. Jeśli spróbujesz, zobaczysz również błędy.

Czy ty żartujesz? Kompilatory też mają błędy, ładują się naprawdę.

GCC jest prawdopodobnie najbardziej znanym kompilatorem typu open source na świecie i zapoznaj się z bazą danych błędów: http://gcc.gnu.org/bugzilla/buglist.cgi?product=gcc&component=c%2B%2B&resolution=-- -

Pomiędzy GCC 3.2 a GCC 3.2.3 sprawdź, ile błędów zostało naprawionych: http://gcc.gnu.org/gcc-3.2/changes.html

Co do innych, takich jak Visual C ++, nawet nie chcę zaczynać.

Jak uczynić kompilatory niezawodnymi? Na początek mają mnóstwo testów jednostkowych. I cała planeta używa ich, więc nie brakuje testerów.

Poważnie, twórcy kompilatorów, o których lubię wierzyć, są lepszymi programistami i chociaż nie są nieomylni, pakują się dość mocno.

W ciągu dnia spotkałem dwóch lub trzech. Jedynym prawdziwym sposobem na jego wykrycie jest sprawdzenie kodu asemblera.

Chociaż kompilatory są wysoce niezawodne z powodów wskazanych przez inne plakaty, myślę, że niezawodność kompilatora jest często samospełniającą się oceną. Programiści zwykle postrzegają kompilator jako standard. Kiedy coś pójdzie nie tak, zakładasz, że to Twoja wina (bo to 99,999% czasu), i zmieniasz kod tak, aby obejść problem kompilatora, a nie na odwrót. Na przykład zawieszanie się kodu przy ustawieniu wysokiej optymalizacji jest zdecydowanie błędem kompilatora, ale większość ludzi po prostu ustawia go nieco niżej i przechodzi bez zgłaszania błędu.

Kompilatory mają kilka właściwości, które prowadzą do ich poprawności:

• Domena jest bardzo dobrze znana i badana. Problem jest dobrze zdefiniowany, a oferowane rozwiązania są dobrze zdefiniowane.
• Zautomatyzowane testowanie jest wystarczające do wykazania poprawności działania kompilatorów
• Kompilatory mają bardzo obszerne, zwykle publiczne, zautomatyzowane i jednostkowe testy, które gromadzą się z czasem, aby objąć większą przestrzeń błędów niż w przypadku większości innych programów
• Kompilatory mają bardzo dużą liczbę gałek ocznych obserwujących ich wyniki

Na co dzień korzystamy z kompilatorów

... i jak sprawiają, że kompilatory są tak niezawodne?

Oni nie. My robimy. Ponieważ wszyscy używają ich przez cały czas, błędy znajdują się szybko.

To gra liczbowa. Ponieważ kompilatory są tak wszechobecne, bardzo prawdopodobne jest, że ktoś wywoła jakiś błąd , ale ponieważ jest tak duża liczba użytkowników, jest bardzo mało prawdopodobne , że ktoś będzie tobą konkretnie.

To zależy od twojego punktu widzenia: u wszystkich użytkowników kompilatory są wadliwe. Ale to jest bardzo prawdopodobne, że ktoś inny będzie sporządzili podobny kawałek kodu, zanim zrobił, więc jeśli ich było błędem, byłoby uderzyć, nie ty, więc ze swojego indywidualnego punktu widzenia, wygląda na to, że błąd został nigdy tam nie ma.

Oczywiście możesz dodać tutaj pozostałe odpowiedzi: kompilatory są dobrze zbadane, dobrze zrozumiane. Istnieje mit, że trudno jest napisać, co oznacza, że ​​tylko bardzo inteligentni, bardzo dobrzy programiści próbują napisać jeden, i robią to bardzo ostrożnie. Na ogół są one łatwe do przetestowania, a także łatwe do przeprowadzenia testu warunków skrajnych lub testu Fuzz. Użytkownicy kompilatorów zwykle sami są programistami, co prowadzi do wysokiej jakości zgłoszeń błędów. I na odwrót: autorzy kompilatorów zwykle są użytkownikami własnego kompilatora.

Oprócz wszystkich odpowiedzi już chciałbym dodać:

Ja wierzę wiele razy, sprzedawcy jedzą własne jedzenie psa. Oznacza to, że piszą kompilatory w sobie.

Często napotykałem błędy kompilatora.

Możesz je znaleźć w ciemniejszych zakątkach, gdzie jest mniej testerów. Na przykład, aby znaleźć błędy w GCC, powinieneś spróbować:

• Zbuduj kompilator krzyżowy. W skryptach konfiguracji i kompilacji GCC znajdziesz dosłownie dziesiątki błędów. Niektóre powodują błędy kompilacji podczas kompilacji GCC, a inne powodują niepowodzenie kompilatora krzyżowego w tworzeniu działających plików wykonywalnych.
• Zbuduj ItCC wersję GCC za pomocą bootstrap profilu. Ostatnie kilka razy, gdy próbowałem tego na GCC 4.4 i 4.5, nie udało się wygenerować działającego modułu obsługi wyjątków C ++. Niezoptymalizowana wersja działała dobrze. Nikt nie wydawał się zainteresowany naprawieniem zgłoszonego przeze mnie błędu i zrezygnowałem z samodzielnego naprawiania go po próbie wykopania tego, co psuje specyfikacje pamięci asm GCC.
• Spróbuj zbudować własny działający GCJ na podstawie najnowszych rzeczy, nie wykonując skryptu budowania dystrybucji. Wyzywam cię.

Kilka powodów:

• Autorzy kompilatorów „ jedzą własną karmę dla psów ”.
• Kompilatory oparte są na dobrze zrozumiałych zasadach CS.
• Kompilatory są zbudowane według bardzo wyraźnej specyfikacji .
• Kompilatory są testowane .
• Kompilatory nie zawsze są bardzo niezawodne .

Zazwyczaj są bardzo dobrzy przy -O0. W rzeczywistości, jeśli podejrzewamy błąd kompilatora, porównujemy -O0 z każdym poziomem, którego próbujemy użyć. Wyższe poziomy optymalizacji wiążą się z większym ryzykiem. Niektóre są nawet celowo tak oznaczone i jako takie w dokumentacji. Spotkałem bardzo wielu (przynajmniej sto w czasie), ale ostatnio stają się znacznie rzadsze. Niemniej jednak w pogoni za dobrymi numerami specjalnymi (lub innymi wzorcami ważnymi dla marketingu) pokusa, by przekraczać granice, jest wielka. Mieliśmy problemy kilka lat temu, gdy sprzedawca (który nie ma nazwy) zdecydował, że naruszenie nawiasów będzie domyślne - raczej niż jakaś specjalna, wyraźnie oznaczona opcja kompilacji.

Zdiagnozowanie błędu kompilatora może być trudne w porównaniu do powiedzenia o zbłąkanym odwołaniu do pamięci, ponowna kompilacja z różnymi opcjami może po prostu zmieszać względne położenie obiektów danych w pamięci, więc nie wiesz, czy to Heisenbug kodu źródłowego, czy też błąd kompilator. Również wiele optymalizacji wprowadza uzasadnione zmiany w kolejności operacji, a nawet algebraiczne uproszczenia algebry, które będą miały różne właściwości w odniesieniu do zaokrąglania zmiennoprzecinkowego i niedopełnienia / przepełnienia. Trudno jest oddzielić te efekty od PRAWDZIWYCH błędów. Z tego powodu obliczenia zmiennoprzecinkowe na twardym rdzeniu są trudne, ponieważ błędy i wrażliwość numeryczna często nie są łatwe do rozwiązania.

Błędy kompilatora nie są tak rzadkie. Najczęstszym przypadkiem jest zgłaszanie przez kompilator błędu w kodzie, który powinien zostać zaakceptowany, lub kompilatora w celu zaakceptowania kodu, który powinien zostać odrzucony.

Tak, wczoraj napotkałem błąd w kompilatorze ASP.NET:

Gdy używasz silnie typowanych modeli w widokach, istnieje ograniczenie liczby szablonów parametrów. Oczywiście nie może zająć więcej niż 4 parametry szablonu, więc oba poniższe przykłady sprawiają, że kompilator nie może sobie poradzić:

ViewUserControl<System.Tuple<type1, type2, type3, type4, type5>>

Nie skompiluje się tak, jak jest, ale zostanie type5usunięty.

ViewUserControl<System.Tuple<MyModel, System.Func<type1, type2, type3, type4>>>

Kompilowałby się, gdyby type4został usunięty.

Pamiętaj, że System.Tuplema wiele przeciążeń i może zająć do 16 parametrów (to szalone, wiem).

Czy kiedykolwiek napotkałeś błąd w samym kompilatorze? Co to było i jak zdałeś sobie sprawę, że problem tkwi w samym kompilatorze?

Tak!

Dwa najbardziej pamiętne to pierwsze dwa, na jakie natknąłem się. Obaj byli w kompilatorze Lightspeed C dla komputerów Mac 680x0 około 1985-7.

Pierwszy z nich polegał na tym, że w niektórych okolicznościach operator przyrostowej liczby całkowitej nic nie zrobił - innymi słowy, w określonym fragmencie kodu „i ++” po prostu nic nie zrobił z „i”. Wyciągałam włosy, dopóki nie spojrzałam na demontaż. Potem zrobiłem przyrost w inny sposób i przesłałem raport o błędzie.

Drugi był nieco bardziej skomplikowany i był naprawdę źle przemyślaną „funkcją”, która poszła nie tak. Wczesne komputery Mac miały skomplikowany system do wykonywania operacji na dyskach niskiego poziomu. Z jakiegoś powodu nigdy nie zrozumiałem - prawdopodobnie związanego z tworzeniem mniejszych plików wykonywalnych - zamiast kompilatora po prostu generującego instrukcje operacji na dysku w kodzie obiektu, kompilator Lightspeed wywołałby funkcję wewnętrzną, która w czasie wykonywania wygenerowała operację na dysku instrukcje na stosie i wskoczyłem tam.

To działało świetnie na procesorach 68000, ale kiedy uruchomiłeś ten sam kod na procesorze 68020, często robiłoby to dziwne rzeczy. Okazało się, że nową funkcją 68020 była prymitywna pamięć podręczna instrukcji 256-bajtowa. Ponieważ pamięć podręczna procesora była wczesna, nie miała pojęcia, że ​​pamięć podręczna jest „brudna” i wymaga ponownego napełnienia; Wydaje mi się, że projektanci procesorów w Motoroli nie myśleli o kodzie własnym. Więc jeśli wykonałeś dwie operacje dyskowe wystarczająco blisko siebie w sekwencji wykonania, a środowisko wykonawcze Lightspeed zbudowało rzeczywiste instrukcje w tym samym miejscu na stosie, procesor błędnie pomyślałby, że trafił bufor pamięci podręcznej i dwukrotnie uruchomił pierwszą operację dyskową.

Znów wymyślenie tego wymagało trochę rozkopywania za pomocą deasemblera i wielu pojedynczych kroków w debuggerze niskiego poziomu. Moim obejściem było poprzedzenie każdej operacji dysku wywołaniem funkcji, która wykonała 256 instrukcji „NOP”, które zalały (a tym samym wyczyściły) pamięć podręczną instrukcji.

Przez 25 lat od tego czasu widziałem coraz mniej błędów kompilatora w czasie. Myślę, że jest kilka powodów:

• Istnieje stale rosnący zestaw testów sprawdzających poprawność kompilatorów.
• Nowoczesne kompilatory są zazwyczaj podzielone na dwie lub więcej części, z których jedna generuje kod niezależny od platformy (np. LLVM celuje w coś, co można uznać za wyobrażony procesor), a druga, co przekłada to na instrukcje dla twojego docelowego sprzętu. W kompilatorach wieloplatformowych pierwsza część jest używana wszędzie, więc dostaje mnóstwo testów w świecie rzeczywistym.

Znaleziono rażący błąd w Turbo Pascal 5,5 lat temu. Błąd występujący ani w poprzedniej (5.0), ani w następnej (6.0) wersji kompilatora. I taki, który powinien był być łatwy do przetestowania, ponieważ wcale nie był to przypadek narożny (tylko połączenie, które nie jest tak często używane).

Ogólnie rzecz biorąc, na pewno komercyjni twórcy kompilatorów (zamiast projektów hobbystycznych) będą mieli bardzo obszerne procedury kontroli jakości i kontroli jakości. Wiedzą, że ich kompilatory to ich sztandarowe projekty i że wady będą na nich wyglądać bardzo źle, gorzej niż w przypadku innych firm wytwarzających większość innych produktów. Deweloperzy oprogramowania są niewybaczalną grupą, nasi dostawcy narzędzi zawiedli nas, że prawdopodobnie pójdziemy szukać alternatyw, zamiast czekać na poprawkę od dostawcy, i bardzo prawdopodobne jest, że przekażemy ten fakt naszym rówieśnikom, którzy mogą śledzić nasze przykład. W wielu innych branżach tak nie jest, więc potencjalna strata dla twórcy kompilatora w wyniku poważnego błędu jest znacznie większa niż w przypadku twórcy oprogramowania do edycji wideo.

Jeśli zachowanie twojego oprogramowania jest inne po skompilowaniu z -O0 i z -O2, oznacza to błąd kompilatora.

Kiedy zachowanie twojego oprogramowania różni się od tego, czego oczekujesz, istnieje prawdopodobieństwo, że błąd znajduje się w kodzie.

Występują błędy kompilatora, ale zwykle znajdują się w dziwnych zakątkach ...

W kompilatorze VAX VMS C firmy Digital Equipment Corporation pojawił się dziwny błąd w latach 90

(Miałem na pasku cebulę, tak jak była wówczas moda)

Zewnętrzny średnik w dowolnym miejscu poprzedzającym pętlę for zostałby skompilowany jako treść pętli for.

f(){...}
;
g(){...}

void test(){
  int i;
  for ( i=0; i < 10; i++){
     puts("hello");
  }
}

W danym kompilatorze pętla jest wykonywana tylko raz.

to widzi

f(){...}
g(){...}

void test(){
  int i;
  for ( i=0; i < 10; i++) ;  /* empty statement for fun */

  {
     puts("hello");
  }
}

To kosztowało mnie dużo czasu.

Starsza wersja kompilatora PIC C, który (kiedyś) zadawaliśmy doświadczeniom zawodowym, nie była w stanie wygenerować kodu, który poprawnie używał przerwania o wysokim priorytecie. Trzeba było czekać 2-3 lata i uaktualnić.

Kompilator MSVC 6 miał sprytny błąd w linkerze, powodował błąd segmentacji i od czasu do czasu umarł bez powodu. Czysta wersja ogólnie to naprawiła (ale westchnienie nie zawsze).

W niektórych domenach, takich jak oprogramowanie awioniki, obowiązują bardzo wysokie wymagania certyfikacyjne dotyczące kodu i sprzętu, a także kompilatora. Na temat tej ostatniej części znajduje się projekt, którego celem jest utworzenie formalnie zweryfikowanego kompilatora C o nazwie Compcert . Teoretycznie ten rodzaj kompilatora jest tak niezawodny, jak to tylko możliwe.

Widziałem kilka błędów kompilatora, sam zgłosiłem kilka (w szczególności w F #).

To powiedziawszy, myślę, że błędy kompilatora są rzadkie, ponieważ ludzie, którzy piszą kompilatory, są ogólnie bardzo zadowoleni z rygorystycznych koncepcji informatyki, dzięki którym są naprawdę świadomi matematycznych implikacji kodu.

Większość z nich przypuszczalnie bardzo dobrze zna takie rzeczy, jak rachunek lambda, weryfikacja formalna, semantyka denotacyjna itp. - rzeczy, które przeciętny programista taki jak ja ledwo rozumie.

Ponadto w kompilatorach jest zwykle dość proste mapowanie od wejścia do wyjścia, więc debugowanie języka programowania jest prawdopodobnie o wiele łatwiejsze niż debugowanie, powiedzmy, silnika blogów.

Znalazłem błąd w C # kompilator nie tak dawno temu, można zobaczyć, jak Eric Lippert (który jest w zespole projektu C #) zorientowali się, jaka była pluskwa tutaj .

Oprócz udzielonych już odpowiedzi chciałbym dodać jeszcze kilka rzeczy. Projektanci kompilatorów są często bardzo dobrymi programistami. Kompilatory są bardzo ważne: większość programów jest wykonywana przy użyciu kompilatorów, dlatego konieczne jest, aby kompilator był wysokiej jakości. Dlatego w najlepszym interesie firm produkujących kompilatory leży umieszczanie na nich najlepszych ludzi (a przynajmniej bardzo dobrych: najlepsi mogą nie lubić projektu kompilatora). Microsoft bardzo chciałby, aby ich kompilatory C i C ++ działały poprawnie, w przeciwnym razie reszta firmy nie może wykonywać swoich zadań.

Ponadto, jeśli budujesz naprawdę skomplikowany kompilator, nie możesz po prostu zhakować go razem. Logika stojąca za kompilatorami jest zarówno bardzo złożona, jak i łatwa do sformalizowania. Dlatego programy te często są budowane w bardzo „solidny” i ogólny sposób, co zwykle powoduje mniej błędów.