Co faktycznie powinien udowodnić dowód poprawności dla sprawdzającego typ?

Programuję od kilku lat, ale nie znam teoretycznej CS. Niedawno próbowałem uczyć się języków programowania, a w ramach tego sprawdzania i wnioskowania.

Moje pytanie brzmi: jeśli spróbuję napisać program wnioskowania i sprawdzania języka programowania i chcę udowodnić, że mój program do sprawdzania typów działa, jaki dokładnie jest dowód, którego szukam?

Mówiąc prościej, chcę, aby mój moduł sprawdzania typu mógł identyfikować wszelkie błędy w kodzie, które mogą wystąpić w czasie wykonywania. Jeśli miałbym użyć czegoś takiego jak Coq, aby spróbować udowodnić, że moja implementacja jest poprawna, co dokładnie ten „dowód poprawności” będzie próbował pokazać?

Pytanie można interpretować na dwa sposoby:

• Czy implementacja implementuje dany system pisania ?$T$
• Czy system pisania zapobiega błędom, które Twoim zdaniem powinny?$T$

To pierwsze jest tak naprawdę pytaniem przy weryfikacji programu i ma niewiele wspólnego z pisaniem. Wystarczy wykazać, że twoja implementacja spełnia specyfikację, patrz odpowiedź Andreja.

Pozwól mi porozmawiać o późniejszym pytaniu. Jak powiedział Andrej, z abstrakcyjnego punktu widzenia system pisania wydaje się wymuszać właściwości programów. W praktyce Twój system pisania na klawiaturze ma na celu zapobieganie występowaniu błędów, co oznacza, że ​​programy do pisania nie powinny wykazywać klasy błędów. Aby pokazać, że T robi to, co według ciebie powinno, musisz zrobić dwie rzeczy.$T$$T$

• Po pierwsze, formalnie definiujesz, co to znaczy, że program ma natychmiastowy błąd w pisaniu . Można to zdefiniować na wiele sposobów - to zależy od Ciebie. Zazwyczaj chcemy zapobiegać takim programom 2 + "hello". Innymi słowy, musisz zdefiniować podzbiór programów, nazwać je Bad , który zawiera dokładnie programy z bezpośrednim błędem pisania.

• Następnie musisz udowodnić, że programy, które można pisać, nigdy nie mogą przekształcić się w programy w Bad . Sformalizujmy to. Niech twój wyrok pisania będzie Przypomnijmy, że należy czytać jako: Program M ma typu alfa , zakładając, że zmienne wolne są wpisane podane przez środowisko y . Zatem twierdzenie, które chcesz udowodnić, brzmi:$\Gamma \vdash M : \alpha.$$M$$\alpha$$\Gamma$

  Twierdzenie. Ilekroć i M → ⋯ → N, a następnie N ∉ Źle .$\Gamma \vdash M : \alpha$$M \rightarrow \cdots \rightarrow N$$N \notin$

  Jak udowodnić to twierdzenie, zależy od szczegółów języka, systemu pisania i wyboru Bad .

Jeden standardowy sposób definiowania zły to znaczy: a termin ma natychmiastowy typu błędu, jeśli nie jest to ani wartości ani nie ma etapu redukcji M → N . (W tym przypadku M jest często określane jako utknięcie ). Działa to tylko w przypadku semantyki operacyjnej na małym etapie. Jednym standardowym sposobem udowodnienia twierdzenia jest wykazanie tego$M$$M \rightarrow N$$M$

• i M → N razem oznaczają Γ ⊢ N : α . Nazywa się to „redukcją podmiotu”. Zazwyczaj jest to udowodnione przez równoczesną indukcję na podstawie oceny pisania na maszynie i długości redukcji.$\Gamma \vdash M : \alpha$$M \rightarrow N$$\Gamma \vdash N : \alpha$

• Ilekroć wówczas M nie jest w złym stanie . Zazwyczaj jest to również udowodnione przez indukcję na podstawie oceny pisania.$\Gamma \vdash M : \alpha$$M$

Zauważ, że nie wszystkie systemy pisania mają „redukcję tematów”, na przykład typy sesji. W takim przypadku wymagane są bardziej wyrafinowane techniki sprawdzania.

To dobre pytanie! Pyta, czego oczekujemy od typów w języku pisanym na maszynie.

Najpierw zauważ, że za pomocą unitype możemy wpisać dowolny język programowania : po prostu wybierz literę, powiedz Ui powiedz, że każdy program ma typ U. Nie jest to szczególnie przydatne, ale ma sens.

Istnieje wiele sposobów rozumienia typów, ale z punktu widzenia programisty następujące, które moim zdaniem są przydatne. Pomyśl o typie jako specyfikacji lub gwarancji . Powiedzieć, że ma typ A to znaczy, że „możemy zagwarantować / oczekiwać / popytu że e spełniają własności kodowanego przez A ”. Często A jest czymś prostym , w którym to przypadku właściwość jest po prostu „liczbą całkowitą”.$e$$A$$e$$A$$A$int

Nie ma końca, jak wyraziste mogą być twoje typy. Zasadniczo mogą to być wszelkiego rodzaju logiczne stwierdzenia, mogą wykorzystywać teorię kategorii i tak dalej itd. Na przykład typy zależne pozwolą ci wyrazić rzeczy takie jak „ta funkcja mapuje listy na listę, tak że dane wyjściowe są posortowane”. Możesz pójść dalej, w tej chwili słucham wykładu na temat „logiki separacji współbieżnej”, która pozwala mówić o tym, jak współbieżne programy działają ze stanem współdzielonym. Fantazyjne rzeczy.

Sztuka pisania w języku programowania polega na równoważeniu ekspresji i prostoty :

• bardziej ekspresyjne typy pozwalają nam bardziej szczegółowo wyjaśnić (sobie i kompilatorowi), co się dzieje
• prostsze typy są łatwiejsze do zrozumienia i mogą być łatwiej zautomatyzowane w kompilatorze. (Ludzie wymyślają typy, które zasadniczo wymagają asystenta dowodu i wkładu użytkownika w celu sprawdzenia typu).

Nie należy lekceważyć prostoty, ponieważ nie każdy programista ma doktorat z teorii języków programowania.

Wróćmy więc do pytania: skąd wiesz, że twój system typów jest dobry ? Cóż, udowodnij twierdzenia, które pokazują, że twoje typy są zrównoważone. Będą dwa rodzaje twierdzeń:

1. Twierdzenia, które mówią, że twoje typy są przydatne . Wiedza, że ​​program ma typ, powinna oznaczać pewne gwarancje, na przykład, że program się nie utknie (byłoby to twierdzenie dotyczące bezpieczeństwa ). Inna rodzina twierdzeń połączyłaby typy z modelami semantycznymi , abyśmy mogli zacząć używać prawdziwej matematyki do dowodzenia rzeczy o naszych programach (byłyby to twierdzenia o adekwatności i wiele innych). Powyższy unitype jest zły, ponieważ nie ma tak użytecznych twierdzeń.

2. Twierdzenia, które mówią, że twoje typy są proste . Podstawową zasadą byłoby rozstrzygnięcie, czy dane wyrażenie ma dany typ. Inną funkcją prostoty jest podanie algorytmu wnioskowania o typie. Inne twierdzenia dotyczące prostoty brzmiałyby: że wyrażenie ma co najwyżej jeden typ lub że wyrażenie ma główny typ (tj. „Najlepszy” spośród wszystkich typów, które ma).

Trudno jest być bardziej szczegółowym, ponieważ typy są bardzo ogólnym mechanizmem. Ale mam nadzieję, że zobaczysz, o co powinieneś strzelać. Podobnie jak większość aspektów projektowania języka programowania, nie ma absolutnej miary sukcesu. Zamiast tego istnieje przestrzeń możliwości projektowania, a ważne jest, aby zrozumieć, gdzie w przestrzeni jesteś lub chcesz być.

Jest kilka różnych rzeczy, które możesz rozumieć przez „udowodnij, że mój sprawdzanie typów działa”. Co, jak sądzę, jest częścią tego, o co pyta twoje pytanie;)

Połowa tego pytania dowodzi, że twoja teoria typów jest wystarczająco dobra, aby udowodnić wszelkie właściwości języka. Odpowiedź Andreja bardzo dobrze radzi sobie z tym obszarem. Druga połowa pytania brzmi - zakładając, że język i jego system typów są już naprawione - w jaki sposób możesz udowodnić, że Twój konkretny moduł sprawdzania poprawności faktycznie implementuje system typów? Widzę tutaj dwie główne perspektywy.

Po pierwsze: w jaki sposób możemy kiedykolwiek ufać, że niektóre konkretne wdrożenia są zgodne ze specyfikacją? W zależności od wymaganego stopnia pewności możesz być zadowolony z dużego pakietu testowego lub może potrzebujesz formalnej weryfikacji lub, bardziej prawdopodobne, połączenia obu tych metod . Zaletą tej perspektywy jest to, że naprawdę uwypukla ona znaczenie wyznaczania granic dla twoich twierdzeń: co dokładnie oznacza „poprawne”? jaka część kodu jest sprawdzana, a która część to zakładana poprawna TCB? itp. Minusem jest to, że zbyt intensywne myślenie o tym prowadzi do jednej filozoficznej dziury w królikach - cóż, „wady”, jeśli nie lubisz tych króliczych dziur.

Druga perspektywa to bardziej matematyczne podejście do poprawności. Kiedy zajmujemy się językami w matematyce, często tworzymy „modele” dla naszych „teorii” (lub odwrotnie), a następnie próbujemy udowodnić: (a) wszystko, co możemy zrobić w teorii, co możemy zrobić w modelu, i (b) wszystko, co możemy zrobić w modelu, możemy zrobić w teorii. (Są to: solidność i kompletnośćtwierdzenia. Który z nich zależy od tego, czy „zacząłeś” od teorii składniowej, czy od modelu semantycznego.) Przy takim sposobie myślenia możemy myśleć o twojej implementacji sprawdzania typu jako szczególnym modelu dla omawianej teorii typów. Więc chcesz udowodnić tę dwukierunkową zgodność między tym, co twoja implementacja może zrobić, a tym, co według teorii powinieneś być w stanie zrobić. Zaletą tej perspektywy jest to, że naprawdę koncentruje się na tym, czy omówiłeś wszystkie najważniejsze przypadki, czy twoja implementacja jest kompletna w sensie nie pomijania żadnych programów, które powinna zaakceptować jako bezpieczna dla typu, oraz czy twoja implementacja jest solidna poczucie, że nie wpuszcza żadnych programów, które powinien odrzucić jako źle napisane. Minusem jest to, że Twój dowód korespondencji prawdopodobnie zostanie dość oddzielony od samego wdrożenia,