Czy funkcje Haskella można udowodnić/sprawdzić / zweryfikować z poprawnością właściwości?

Prawdopodobnie najbliższą rzeczą do tego, o co prosisz jest Haskabelle, narzędzie, które jest dostarczane z asystentem dowodu Isabelle, które może przetłumaczyć pliki Haskella na teorie Isabelle i pozwala udowodnić rzeczy na ich temat. O ile rozumiem, to narzędzie jest rozwijane w ramach projektu hol-ML-Haskell i strona dokumentacji zawiera pewne informacje o teorii stojącej za tym.

Nie jestem zbytnio zaznajomiony z tym projektem i niewiele wiem o tym, co z nim zrobiono. Ale wiem, że Brian Huffman bawił się tymi rzeczami, sprawdzał jego dokumenty i rozmowy, powinny zawierać istotne rzeczy.

Nie jestem pewien, czy to, o co prosisz, jest tym, co cię uszczęśliwi. :-)

Sprawdzanie modelu w języku ogólnego przeznaczenia jest prawie niemożliwe, ponieważ modele muszą być specyficzne dla danej dziedziny, aby były praktyczne. Ze względu na twierdzenie Gödla o niekompletności nie ma po prostu metody automatycznego znajdowania dowodów w wystarczająco ekspresyjnej logice.

Oznacza to, że musisz samemu napisać dowody , co rodzi pytanie, czy wysiłek jest wart czasu wydane. Oczywiście wysiłek tworzy coś bardzo cennego, a mianowicie pewność, że twój program jest poprawny. Pytanie nie brzmi, czy jest to must-have, ale czy czas spędzony jest zbyt duży koszt. Rzecz w dowodach polega na tym, że chociaż możesz mieć "intuicyjne" zrozumienie, że twój program jest poprawny , często bardzo trudno jest sformalizować to zrozumienie jako dowód. Problem z intuicyjnym zrozumieniem polega na tym, że jest bardzo podatny na przypadkowe błędy (literówki i inne głupie błędy). Jest to podstawowy dylemat pisania poprawnych programów.

Badania poprawności programu polegają więc na ułatwieniu sformalizowania dowodów i automatycznego sprawdzania ich poprawności. Programowanie jest integralną częścią "łatwości formalizacji"; bardzo ważne jest, aby pisać programy w stylu, który jest łatwy do rozumowania. Obecnie mamy następujące spektrum:

• Język imperatywny jak C, C++, Fortran, Python: bardzo trudno tu cokolwiek sformalizować. Testy jednostkowe i ogólne rozumowanie to jedyny sposób na uzyskanie przynajmniej pewnej pewności. Statyczne typowanie łapie tylko trywialne błędy (co znacznie lepsze niż ich nie łapanie!).

• Języki czysto funkcjonalne, takie jak Haskell, ML: Expressive type system pomaga złapać nietrywialne błędy i błędy. Ręczne udowodnienie poprawności jest praktyczne dla fragmentów do około 200 linii, powiedziałbym. (Zrobiłem dowód dla mojego pakiet operacyjny , na przykład.) Quickcheck testowanie jest tanim substytutem sformalizowanych dowodów.

• Zależne typy języków i asystentów sprawdzających, takich jak Agda, Epigram, Coq: udowodnienie poprawności całych programów jest możliwe dzięki automatycznej pomocy w formalizacji i wykrywaniu dowodów. Jednak obciążenie jest nadal wysokie.

Moim zdaniem aktualnym slodkim plusem pisania poprawnych programów jest programowanie czysto funkcjonalne . Jeśli życie zależy od poprawności programu, lepiej przejść poziom wyżej i użyć Asystenta dowodu.

Brzmi jakbyś chciał ESC / Haskell: http://research.microsoft.com/en-us/um/people/simonpj/papers/verify/index.htm

Aha, a Agda ma teraz web framework (przynajmniej proof of concept): http://www.reddit.com/r/haskell/comments/d8dck/lemmachine_a_web_framework_in_agda/

Widziałeś quickcheck? Może zaoferować niektóre z rzeczy, których potrzebujesz.

Http://www.haskell.org/haskellwiki/Introduction_to_QuickCheck

Twój pozornie prosty przykład, add (a, b), jest naprawdę trudny do zweryfikowania - zmiennoprzecinkowy, overflow, underflow, interrupts, czy kompilator jest zweryfikowany, czy sprzęt jest zweryfikowany, itp.

Habit jest uproszczonym dialektem Haskell, który pozwala na udowodnienie właściwości programu.

Hume jest językiem z 5 poziomami, z których każdy jest bardziej ograniczony, a więc łatwiejszy do weryfikacji:

Full Hume
  Full recursion
PR−Hume
  Primitive Recursive functions
Template−Hume
  Predefined higher−order functions
  Inductive data structures
  Inductive  Non−recursive first−order functions
FSM−Hume
  Non−recursive data structures
HW−Hume
  No functions
  Non−recursive data structures

Oczywiście najpopularniejszą obecnie metodą sprawdzania właściwości programu jest jednostka testowanie, które dostarcza silnych twierdzeń, ale te twierdzenia są zbyt specyficzne. "typy uważane za szkodliwe", Pierce, slide 66

Spójrz na Zeno. Cytowanie strony wiki:

Zeno jest zautomatyzowanym systemem sprawdzającym Właściwości programu Haskell; opracowany w Imperial College London przez Williama Sonnexa, Sophię Drossopoulou i Susan Eisenbach. Jego celem jest rozwiązanie ogólnego problemu równości dwóch terminów Haskella dla dowolnej wartości wejściowej.

Wiele dostępnych obecnie narzędzi do weryfikacji programów ma odmianę sprawdzania modeli; jest w stanie przemierzyć bardzo dużą, ale skończoną przestrzeń wyszukiwania szybko. Są one dobrze dostosowane do problemów z dużym opisem, ale bez rekurencyjnych typów danych. Zeno z drugiej strony jest zaprojektowany do indukcyjnego wykazywania właściwości w nieskończonej przestrzeni wyszukiwania, ale tylko tych z małą i prostą specyfikacją.

Z pewnością można formalnie udowodnić Niektóre właściwości programów Haskell. Musiałem to zrobić na egzaminie FP: podając dwa wyrażenia, udowodnij, że oznaczają tę samą funkcję. Nie jest to możliwe w ogóle, ponieważ Haskell jest Turing-complete, więc każdy mechaniczny Prower musi być albo asystent dowodu (półautomatyczny z wytycznymi użytkownika) lub sprawdzania modelu.

Były próby w tym kierunku, patrz np. P-logic: weryfikacja właściwości dla Programy Haskell lub dowodzące poprawności programów funkcjonalnych za pomocą Mizar . Oba są pracami naukowymi opisującymi metody bardziej niż implementacje.

Kilka ostatnich wysiłków MSR Cambridge: http://research.microsoft.com/en-us/um/people/simonpj/papers/verify/hcc-popl.pdf

Narzędzie AProVE jest (przynajmniej) w stanie udowodnić zakończenie programów Haskell, co jest częścią udowodnienia poprawności. Więcej informacji można znaleźć w niniejszej pracy (krótsza wersja ).

Poza tym mogą Cię zainteresować typy zależne . Tutaj system typów jest rozszerzony i używany w celu uniemożliwienia niewłaściwych programów.

Możesz użyć narzędzia hs-to-coq aby przekształcić Haskell głównie automatyczne do Coq, a następnie użyć pełnej mocy Coq udowodnić asystent do weryfikacji kodu Haskell. Zobacz dokumenty https://arxiv.org/abs/1803.06960 i https://arxiv.org/abs/1711.09286 aby uzyskać więcej informacji.