Jakie są popularne formalne techniki potwierdzania poprawności kodu funkcjonalnego?

10

Chcę przedstawić dowody dla części programu Haskell, który piszę w ramach mojej pracy magisterskiej. Jednak jak dotąd nie udało mi się znaleźć dobrej pracy referencyjnej.

Książka wprowadzająca Grahama Huttona Programowanie w Haskell ( Google Books ) - którą czytam podczas nauki Haskell - porusza kilka technik rozumowania programów, takich jak

  • rozumowanie równań
  • za pomocą nienakładających się wzorów
  • indukcja listy

w rozdziale 13, ale nie jest to zbyt szczegółowe.

Czy są jakieś książki lub artykuły, które możesz polecić, które zawierają bardziej szczegółowy przegląd formalnych technik sprawdzania kodu Haskell lub innego funkcjonalnego kodu?

reference-request proof-techniques functional-programming books software-verification FK82
źródło

Odpowiedzi:

5

Jedną z faktycznych metod potwierdzania wyników w programowaniu funkcjonalnym jest grupa Richarda Birda.

W szczególności prosisz o dogłębne lub przynajmniej bardziej kompleksowe podejście do wnioskowania równań i indukcji listy, co zostało przedstawione w Wykładach o konstruktywnym programowaniu funkcjonalnym .

Mówiąc bardziej ogólnie, tekst „Algebra programowania” autorstwa Bird i de Moor dotyczy również poprawności algorytmów funkcjonalnych, takich jak problemy z optymalizacją i programowaniem dynamicznym.

Jeśli natrafisz na inne przydatne zasoby dotyczące tego problemu, proszę o nich wspomnieć, a być może możemy zamienić ten post w wiki.

Musa Al-hassy
źródło
Dziękuję Ci! Oczywiście, jeśli znajdę więcej zasobów, dodam je do mojego postu.
FK82
6

Możesz zacząć od

Tematy obejmują podstawowe pojęcia z zakresu logiki, komputerowego dowodzenia twierdzeń, asystenta dowodu Coq, programowania funkcjonalnego, semantyki operacyjnej, logiki Hoare'a i systemów typu statycznego. Ekspozycja przeznaczona jest dla szerokiego grona czytelników, od zaawansowanych studentów, doktorantów i badaczy. Nie zakłada się żadnego szczególnego tła w językach logiki lub programowania, choć pomocny będzie pewien stopień dojrzałości matematycznej.

Możesz pominąć (lub przejrzeć) części teorii języka programowania i nauczyć się, jak radzić sobie z formalnymi dowodami, poczynając od Wstępu aż po IndPrinciples. Książka jest naprawdę dobrze napisana i pouczająca.

Następnie możesz kontynuować

W tym tomie nauczysz się określać i weryfikować (potwierdzać poprawność) algorytmy sortowania, drzewa wyszukiwania binarnego, zrównoważone drzewa wyszukiwania binarnego i kolejki priorytetowe. Przed skorzystaniem z tej książki powinieneś trochę zrozumieć te algorytmy i struktury danych, dostępne w każdym standardowym podręczniku do algorytmów licencjackich. Powinieneś zrozumieć cały materiał z Software Foundations Volume 1 (Logic Foundation)

Uwaga: VFA jest wciąż w wersji beta!

Anton Trunov
źródło
(Twój drugi link prowadzi do niewłaściwego miejsca.) Ponadto w Agdzie znajduje się Verified Functional Programming ; który używa Agdy, formalnie języka programowania, ale używa Unicode, więc jest bliżej notacji matematycznej.
Musa Al-hassy
Poprawione, dziękuję. Tak, przeczytałem VFPiA, ale to nie w moim guście.
Anton Trunov
Dziękuję za Twoją odpowiedź! Myślę, że istnieje nieporozumienie. Nie szukam technik funkcjonalnych do sprawdzania algorytmów (takich jak asystent dowodu), ale technik sprawdzania kodu funkcjonalnego (na przykład do sprawdzania poprawności implementacji danego algorytmu) @ MusaAl-hassy odpowiedź jest bardzo bliska mojej pożądana odpowiedź. W przypadku, gdybym go przegapił i książki, które zacytowałeś, obejmują również ten aspekt, czy mógłbyś dodać odpowiednie rozdziały?
FK82
@ FK82 Oto Theorem app_assoc : ∀ l1 l2 l3 : natlist, (l1 ++ l2) ++ l3 = l1 ++ (l2 ++ l3)z rozdziału Listy . Czy ten przykład przypomina coś, co Cię interesuje? Zaczynają od programowania funkcjonalnego w Coq, a następnie przechodzą do wnioskowania o właściwościach programów funkcjonalnych. Rozdziały od Przedmowy do IndPrinciples obejmują oba z nich, i powiedziałbym, że programowanie i rozumowanie są ze sobą powiązane.
Anton Trunov,
1
@ FK82 (1) Całkowicie zgadzam się z tym komentarzem. (2) Warto zajrzeć do książki „Myślenie funkcjonalne z Haskellem” (2015) R. Birda. Książka zawiera mnóstwo przykładów rozumowania na temat Haskella. (3) Także „Perły projektowania algorytmu funkcjonalnego” (2010) tego samego autora mogą ci pomóc.
Anton Trunov
5

Okazuje się, że doskonałym źródłem technik dowodowych i przykładów do udowodnienia rzeczy o czysto funkcjonalnych językach są asystenci dowodowi, którzy zwykle zawierają jako część swojego języka specyfikacji czysty język funkcjonalny, w którym możliwe jest racjonalne uzasadnienie.

Ktoś może chcieć zajrzeć do książki takiej jak Certyfikowane programowanie z typami zależnymi, aby uzyskać szczegółowe wprowadzenie do tego rodzaju rozumowania w konkretnym asystencie dowodowym, a mianowicie Coq.

cody
źródło
Dzięki! Właściwie szukam technik w Haskell . Mój post został edytowany tak, aby zawierał cały kod funkcjonalny, ale to znacznie powyżej moich intencji.
FK82
1
Nie znam systemów zaprojektowanych specjalnie do weryfikacji Haskell, ale chciałbym zauważyć, że 1) Rdzeń funkcjonalny Coq (i Agda) jest zasadniczo nie do odróżnienia od rdzenia Haskell (z wyjątkiem ograniczenia do wszystkich funkcji) i 2) Programy zweryfikowane w Coq i Agda można wyodrębnić do Haskell (choć uważam, że ekstrakcja do Haskell jest lepiej obsługiwana w Agda, gdzie Coq jest bardziej zorientowany na Ocaml)
cody
Dobrze wiedzieć! Oznaczałoby to jednak, że przepisuję mój program (lub odpowiednie części) w Coq lub Agda. W moim przypadku nie wydaje mi się to rozsądne.
FK82
Istnieje kilka bardzo eksperymentalnych „frontonów”, które próbują przekonwertować Haskell na Isabelle lub bezpośrednio udowodnić równoważność za pomocą Isabelle, ale nie utrzymałbym zbyt dużej ilości zapasów w ich dojrzałości. Myślę, że przepisanie kodu byłoby w końcu mniej pracy.
cody
4

Sugeruję użycie logiki programu. Radzą sobie znacznie lepiej z efektami niż systemy pisania.

Istnieje wiele logiki programów dla języków funkcjonalnych. Staje się to interesujące z efektami. Patrz np. Logiczne uzasadnienie funkcji wyższego rzędu w stanie lokalnym .

Praca Arthura Charguérauda integruje logikę programu z asystentami dowodowymi, patrz np. Ta strona przeglądu .

Martin Berger
źródło