Dlaczego programy funkcjonalne korelują między sukcesem kompilacji a poprawnością?

12

Od 4 lat mam tendencję do programowania funkcjonalnego, odkąd zacząłem pracę z LINQ. Niedawno napisałem czysty funkcjonalny kod C # i zauważyłem z pierwszej ręki to, co czytałem o programach funkcjonalnych - że po skompilowaniu mają tendencję do poprawności.

Próbowałem wskazać, dlaczego tak jest, ale mi się nie udało.

Można się domyślać, że stosując zasady OO, masz „warstwę abstrakcji”, która nie jest obecna w programach funkcjonalnych, a ta warstwa abstrakcji umożliwia poprawność kontraktów między obiektami, podczas gdy implementacja jest błędna.

Czy ktoś pomyślał o tym i przedstawił abstrakcyjny powód korelacji między sukcesem kompilacji a poprawnością programu w programowaniu funkcjonalnym?

Aaron Anodide
źródło
9
Lisp jest językiem funkcjonalnym, ale nie ma żadnych sprawdzeń czasu kompilacji. To samo dotyczy kilku innych języków funkcjonalnych. Bardziej dokładna charakterystyka języków, o których mówisz, to: Języki z potężnymi systemami formalnymi (przynajmniej Hindley-Milner).
1
@delnan Nie powiedziałbym, że Lisp jest funkcjonalnym językiem programowania, chociaż można go używać do pisania funkcjonalnego kodu programowania. Clojure, który jest dialektem Lisp, jest funkcjonalnym językiem programowania
sakisk
2
Zgadzam się z @delnan. To stwierdzenie jest bardziej związane ze statycznymi typami funkcjonalnych języków programowania, zwłaszcza Haskell, który korzysta z systemu Hindley-Milner. Myślę, że główną ideą jest to, że jeśli dobrze dopasujesz typy, zwiększy się pewność, że twój program jest poprawny.
sakisk
1
Kod funkcjonalny może mieć tyle samo abstrakcji i pośredników, co typowy główny kod OOP (jeśli nie więcej). Diabeł tkwi w szczegółach - mniej skutków ubocznych i brak wartości zerowej oznacza mniej niewidzialny stan do śledzenia i mniejsze szanse na popsucie. Zauważ, że możesz zastosować te same zasady w imperatywnych językach głównego nurtu, to po prostu więcej pracy i często więcej gadatliwości (np. Bicie finalwszystkiego).
Doval
1
Nie pełna odpowiedź, ale wpisanie programu jest prostą formalną formalną weryfikacją programu. W ogólnym Object Oriented programy albo skomplikowane albo bardzo proste systemy typu jak podmiany potrzeby należy wziąć pod uwagę - w większości przypadków są one wykonane niezdrowe dla wygody. OTOH systemy podobne do ML mogą w pełni korzystać z CH, więc możesz zakodować dowód tylko w typach i użyć kompilatora jako sprawdzania dowodu.
Maciej Piechotka,

Odpowiedzi:

12

Mogę napisać tę odpowiedź jako ktoś, kto wiele rzeczy udowadnia, więc dla mnie poprawność to nie tylko to, co działa, ale to, co działa i jest łatwe do udowodnienia.

Pod wieloma względami programowanie funkcjonalne jest bardziej restrykcyjne niż programowanie imperatywne. W końcu nic nie powstrzymuje cię przed zmutowaniem zmiennej w C! Rzeczywiście, większość funkcji w językach FP jest łatwa do omówienia w kategoriach tylko kilku podstawowych funkcji. Wszystko sprowadza się do lambdas, zastosowania funkcji i dopasowania wzoru!

Ponieważ jednak zapłaciliśmy piperowi z góry, mamy o wiele mniej do czynienia i mamy o wiele mniej możliwości rozwiązania problemów. Jeśli jesteś fanem z 1984 roku, wolność jest rzeczywiście niewolnictwem! Używając 101 różnych schludnych sztuczek dla programu, musimy myśleć o rzeczach tak, jakby coś z tych 101 rzeczy mogło się zdarzyć! To naprawdę trudne, jak się okazuje :)

Jeśli zaczniesz od nożyczek bezpieczeństwa zamiast miecza, bieganie jest umiarkowanie mniej niebezpieczne.

Teraz patrzymy na twoje pytanie: jak to wszystko pasuje do „kompiluje się i działa!” zjawiska Myślę, że duża część tego jest z tego samego powodu, dla którego łatwo jest udowodnić kod! W końcu, kiedy piszesz oprogramowanie, konstruujesz jakiś nieformalny dowód, że jest poprawny. Z tego powodu to, co jest objęte twoimi naturalnymi ręcznymi dowodami i własne pojęcie poprawności (sprawdzanie typów) kompilatorów jest dość duże.

Gdy dodajesz funkcje i skomplikowane interakcje między nimi, to, co nie jest sprawdzane przez system typów, rośnie. Jednak twoja umiejętność konstruowania nieformalnych dowodów nie poprawia się! Oznacza to, że jest więcej rzeczy, które mogą przedostać się przez pierwszą inspekcję i muszą zostać złapane później.

Daniel Gratzer
źródło
1
Podoba mi się twoja odpowiedź, ale nie rozumiem, jak odpowiada na pytanie OP
sakisk,
1
@faif Rozszerzyłem moją odpowiedź. TLDR: każdy jest matematykiem.
Daniel Gratzer
„Używając 101 różnych schludnych sztuczek dla programu, musimy myśleć o rzeczach, jakby którakolwiek z tych 101 rzeczy mogła się zdarzyć!”: Czytałem gdzieś, że musisz być genialny, aby programować z mutacją, ponieważ musisz tak zachować wiele informacji w twojej głowie.
Giorgio,
12

abstrakcyjny powód korelacji między sukcesem kompilacji a poprawnością programu w programowaniu funkcjonalnym?

Zmienny stan.

Kompilatory sprawdzają rzeczy statycznie. Sprawiają, że twój program jest dobrze uformowany, a system typów zapewnia mechanizm próby zapewnienia, że ​​odpowiedni rodzaj wartości jest dozwolony w odpowiednich miejscach. System typów stara się również zapewnić, że właściwy rodzaj semantyki jest dozwolony w odpowiednich miejscach.

Gdy tylko program wprowadzi stan, to ostatnie ograniczenie staje się mniej przydatne. Nie tylko musisz się martwić o właściwe wartości we właściwych miejscach, ale musisz także uwzględnić zmianę tej wartości w dowolnych punktach programu. Musisz uwzględnić semantykę kodu zmieniającą się wraz z tym stanem.

Jeśli dobrze programujesz funkcjonalnie, nie ma (lub bardzo mało) stanu zmiennego.

Istnieje tu jednak pewna debata na temat związku przyczynowego - jeśli programy bez stanu działają po kompilacji częściej, ponieważ kompilator może wykrywać więcej błędów lub jeśli programy bez stanu działają po kompilacji częściej, ponieważ ten styl programowania powoduje mniej błędów.

To prawdopodobnie mieszanka obu z mojego doświadczenia.

Telastyn
źródło
2
„W moim doświadczeniu jest to prawdopodobnie mieszanka obu.”: Mam takie same doświadczenia. Pisanie statyczne wychwytuje błędy w czasie kompilacji, także podczas używania języka rozkazującego (np. Pascal). W FP unikanie zmienności i, dodam, użycie bardziej deklaratywnego stylu programowania ułatwia zrozumienie kodu. Jeśli język oferuje oba, zyskujesz obie zalety.
Giorgio,
7

Mówiąc prościej, ograniczenia oznaczają, że istnieje mniej poprawnych sposobów łączenia rzeczy, a pierwszorzędne funkcje ułatwiają rozróżnianie rzeczy, takich jak struktury pętli. Zapoznaj się z tą odpowiedzią , na przykład:

for (Iterator<String> iterator = list.iterator(); iterator.hasNext();) {
    String string = iterator.next();
    if (string.isEmpty()) {
        iterator.remove();
    }
}

Jest to jedyny bezpieczny sposób w Javie, aby usunąć element z kolekcji podczas iteracji. Istnieje wiele sposobów, które wyglądają bardzo blisko, ale są błędne. Ludzie nieświadomi tej metody czasami przechodzą przez zawiły sposób, aby uniknąć problemu, na przykład poprzez iterację przez kopię.

Stworzenie tego generycznego nie jest trudne, więc będzie działać na więcej niż tylko kolekcjach Stringsif kodu , ale bez pierwszorzędnych funkcji nie można zastąpić predykatu (warunku wewnątrz ), więc ten kod ma tendencję do kopiowania i wklejania i nieznacznie zmodyfikowany.

Połącz pierwszorzędne funkcje, które dają ci możliwość przekazania predykatu jako parametru, z ograniczeniem niezmienności, co czyni go bardzo denerwującym, jeśli tego nie zrobisz, i wymyślisz proste bloki konstrukcyjne filter, jak w tym kodzie Scala robi to samo:

list filter (!_.isEmpty)

Pomyśl teraz o tym, co sprawdza system typów w czasie kompilacji w przypadku Scali, ale te kontrole są również wykonywane przez systemy typów dynamicznych przy pierwszym uruchomieniu:

  • listmusi być jakimś typem obsługującym filtermetodę, a mianowicie kolekcją.
  • Elementy listmuszą mieć isEmptymetodę, która zwraca wartość logiczną.
  • Dane wyjściowe będą (potencjalnie) mniejszą kolekcją z tym samym typem elementów.

Po sprawdzeniu tych rzeczy, jakie inne sposoby mogą zostać zepsute przez programistę? Przypadkowo zapomniałem !, co spowodowało bardzo oczywistą awarię przypadku testowego. To właściwie jedyny błąd, jaki można popełnić, i popełniłem go tylko dlatego, że bezpośrednio tłumaczyłem z kodu, który przetestował warunek odwrotny.

Ten wzór powtarza się w kółko. Funkcje pierwszej klasy umożliwiają przekształcenie rzeczy w małe narzędzia wielokrotnego użytku z precyzyjną semantyką, ograniczenia takie jak niezmienność dają bodziec do tego, a sprawdzanie typu parametrów tych narzędzi nie pozostawia wiele miejsca na ich pomijanie.

Oczywiście wszystko zależy od programisty, który wie, że taka funkcja upraszczania filterjuż istnieje, i jest w stanie ją znaleźć lub rozpoznać korzyści wynikające z jej stworzenia. Spróbuj to zaimplementować wszędzie wszędzie, używając tylko rekurencji ogona, a wrócisz w tej samej łodzi złożoności co wersja imperatywna, tylko gorzej. Tylko dlatego, że można napisać bardzo prosty sposób, nie oznacza, że prosta wersja jest oczywista.

Karl Bielefeldt
źródło
„Po sprawdzeniu tych rzeczy, jakie inne sposoby programista może spieprzyć?”: To w jakiś sposób potwierdza moje doświadczenie, że (1) pisanie statyczne + (2) styl funkcjonalny pozostawia mniej sposobów na popsucie rzeczy. W rezultacie mam tendencję do szybszego uzyskiwania poprawnego programu i muszę pisać mniej testów jednostkowych podczas korzystania z FP.
Giorgio,
2

Nie sądzę, aby istniała istotna korelacja między kompilacją programowania funkcjonalnego a poprawnością środowiska uruchomieniowego. Może istnieć pewna korelacja między statyczną kompilacją a poprawnością środowiska wykonawczego, ponieważ przynajmniej możesz mieć odpowiednie typy, jeśli nie przesyłasz.

Aspektem języka programowania, który może w jakiś sposób korelować udaną kompilację z poprawnością typu środowiska wykonawczego, jak to opisujesz, jest pisanie statyczne, a nawet wtedy, tylko jeśli nie osłabiasz sprawdzania typu rzutowaniami, które można zapewnić tylko w czasie wykonywania (w środowiskach z mocno wpisane wartości lub miejsca, np. Java lub .Net) lub wcale (w środowiskach, w których informacje o typie są zagubione lub przy słabym pisaniu, np. C i C ++).

Jednak programowanie funkcjonalne samo w sobie może pomóc na inne sposoby, takie jak unikanie wspólnych danych i stanu zmiennego.

Oba aspekty razem mogą mieć znaczącą korelację poprawności, ale musisz mieć świadomość, że brak błędów kompilacji i błędów w czasie wykonywania nic nie mówi, mówiąc ściśle, o poprawności w szerszym znaczeniu, ponieważ w programie robi to, co ma robić, i szybko się nie udaje z powodu nieprawidłowego wejścia lub niekontrolowanej awarii środowiska wykonawczego. W tym celu potrzebujesz reguł biznesowych, wymagań, przypadków użycia, asercji, testów jednostkowych, testów integracyjnych itp. W końcu, przynajmniej moim zdaniem, zapewniają one znacznie więcej pewności niż programowanie funkcjonalne, pisanie statyczne lub jedno i drugie.

acelent
źródło
To. Prawidłowości programu nie można ocenić po udanej kompilacji. Jeśli kompilator może zrozumieć często sprzeczne i niedokładne wymagania każdej osoby, które przyczyniły się do specyfikacji programu, być może udaną kompilację można uznać za poprawność. Ale ten mityczny kompilator nie potrzebuje programisty! Chociaż może istnieć nieco wyższa ogólna korelacja między kompilacją a poprawnością programów funkcjonalnych w porównaniu z imperatywnymi, jest to tak niewielka część oceny całkowitej poprawności, że myślę, że jest to w zasadzie nieistotne
Jordan Rieger,
2

Wyjaśnienie dla menedżerów:

Program funkcjonalny jest jak jedna duża maszyna, do której wszystko jest podłączone, rury, kable. [Samochód]

Program proceduralny jest jak budynek z pokojami zawierającymi małą maszynę, przechowujący częściowe produkty w pojemnikach, odbierający częściowe produkty z innego miejsca. [Fabryka]

Kiedy więc funkcjonalna maszyna już do siebie pasuje: musi coś wyprodukować. Jeśli działa kompleks proceduralny, mógłbyś nadzorować określone efekty, wprowadzać chaos, nie gwarantować funkcjonowania. Nawet jeśli masz listę kontrolną wszystkiego, co jest poprawnie zintegrowane, istnieje tak wiele stanów, możliwych sytuacji (częściowe leżenie produktów, przepełnione wiadra, brak), że trudno dać gwarancje.


Ale poważnie, kod proceduralny nie określa semantyki pożądanego wyniku tak bardzo, jak kod funkcjonalny. Programiści proceduralni mogą łatwiej uciec od poszlakowego kodu i danych oraz wprowadzić kilka sposobów na wykonanie jednej czynności (niektóre z nich są niedoskonałe). Zwykle tworzone są dane obce. Funkcjonalni programiści mogą zająć więcej czasu, gdy problem stanie się bardziej złożony?

Język funkcjonalny o silnym typie maszynowym może nadal zapewniać lepszą analizę danych i przepływu. W języku proceduralnym cel programu często musi być zdefiniowany poza programem, jako formalna analiza poprawności.

Joop Eggen
źródło
1
Lepsza anologia: programowanie funkcjonalne jest jak biuro pomocy bez klientów - wszystko jest cudowne (o ile nie kwestionujesz celu ani wydajności).
Brendan,
@Brendan car & factory nie stanowi tak złej analogii. Stara się wyjaśnić, dlaczego programy (na małą skalę) w języku funkcjonalnym mają większe szanse na działanie i są mniej podatne na błędy niż „fabryka”. Ale na ratunek powiedzmy, że OOP przychodzi z tego, że fabryka może produkować kilka rzeczy i jest większa. Twoje porównanie jest trafne; jak często słyszy się, że FP może zrównoważyć i zoptymalizować ogromnie, ale w efekcie (bez słów) zapewnia powolne wyniki. Nadal trzymam się FP.
Joop Eggen,
Programowanie funkcjonalne na dużą skalę działa całkiem dobrze w przypadku en.wikipedia.org/wiki/Spherical_cow Zachowaj lokalność .
Den
@Den Ja sam bałem się żadnych problemów z wykonalnością pracując nad projektem FP na dużą skalę. Nawet to uwielbiam. Uogólnienie ma swoje ograniczenia. Ale ponieważ to ostatnie stwierdzenie jest również uogólnieniem ... (dzięki za kulistą krowę)
Joop Eggen