Dlaczego pisanie kompilatora w języku funkcjonalnym jest łatwiejsze? [Zamknięte]

88

Bardzo długo myślałem o tym pytaniu, ale naprawdę nie mogłem znaleźć odpowiedzi w Google, podobnie jak podobne pytanie w Stackoverflow. Jeśli istnieje duplikat, przepraszam za to.

Wiele osób zdaje się mówić, że pisanie kompilatorów i innych narzędzi językowych w językach funkcjonalnych, takich jak OCaml i Haskell, jest znacznie bardziej wydajne i łatwiejsze niż pisanie ich w językach imperatywnych.

Czy to prawda? A jeśli tak - dlaczego pisanie ich w językach funkcjonalnych jest tak wydajne i łatwe, a nie w języku imperatywnym, takim jak C? Ponadto - czy narzędzie językowe w języku funkcjonalnym nie jest wolniejsze niż w jakimś języku niskiego poziomu, takim jak C?

— wvd
źródło

5

Nie powiedziałbym, że to łatwiejsze. Ale funkcjonalny charakter zadań kompilacji, takich jak parsowanie, prawdopodobnie w naturalny sposób nadaje się do programowania funkcjonalnego. Języki funkcjonalne, takie jak OCaml, mogą być niezwykle szybkie, rywalizując z prędkością C.

— Robert Harvey

17

Ludzie, czy to naprawdę kłótliwe? Z pewnością ktoś ma wgląd. Chciałbym poznać siebie.

— Robert Harvey

Myślę, że powinny istnieć przynajmniej dobre powody, dla których należy używać języka funkcjonalnego zamiast imperatywnego. Znalazłem artykuł, który w zasadzie dotyczył tego, że języki funkcjonalne nie mają skutków ubocznych i tym podobne. Ale nie było to wcale jasne. Jeśli jednak jest to dyskusyjne, lepiej byłoby je zamknąć lub przeformułować pytanie.

— wvd

12

Czy przyznanie, że niektóre nisze lepiej pasują do określonego stylu języka, jest naprawdę dyskusyjne? „Dlaczego C jest lepszy od Javascript do pisania sterowników urządzeń” nie byłoby kontrowersyjne, myślę, że ...

— CA McCann

1

Myślałem, że będzie odwrotnie. Czytam "super malutki kompilator" i wszędzie używa on zmiennych mutacji.

— Rolf

101

Często kompilator dużo pracuje z drzewami. Kod źródłowy jest analizowany w drzewie składni. To drzewo można następnie przekształcić w inne drzewo z adnotacjami typu w celu sprawdzenia typu. Teraz możesz przekształcić to drzewo w drzewo zawierające tylko podstawowe elementy języka (konwertowanie składniowych notacji przypominających cukier do postaci bez cukru). Teraz możesz wykonać różne optymalizacje, które są w zasadzie transformacjami w drzewie. Następnie prawdopodobnie utworzyłbyś drzewo w jakiejś normalnej formie, a następnie iterowałbyś po tym drzewie, aby utworzyć kod docelowy (asemblerowy).

Język funkcjonalny ma cechy, takie jak dopasowywanie wzorców i dobrą obsługę wydajnej rekurencji, co ułatwia pracę z drzewami, dlatego są ogólnie uważane za dobre języki do pisania kompilatorów.

— sepp2k
źródło

Jak dotąd najbardziej kompletna odpowiedź, oznaczę ją jako zaakceptowaną, jednak myślę, że odpowiedź Pete'a Kirkhama jest również dobra.

— wvd

1

A co z „udowadnianiem poprawności”, skoro poprawność kompilatora jest ważnym atrybutem, często słyszałem, że fani języków funkcyjnych w jakiś sposób włączają „dowód” poprawności do swojego przepływu pracy. Nie mam pojęcia, co to naprawdę oznacza w praktyce, ale ponieważ niezawodność kompilatora jest ważna, wydaje się to opłacalne.

— Warren P

3

@WarrenP: Koncepcja „kodu przenoszącego dowód” wywodzi się z języków funkcjonalnych z typami statycznymi. Chodzi o to, że używasz systemu typów w taki sposób, że funkcja może sprawdzać typ tylko wtedy, gdy jest poprawna, więc fakt kompilacji kodu jest dowodem poprawności. Oczywiście nie jest to w pełni możliwe przy zachowaniu kompletności języka i sprawdzania typów. Ale im silniejszy system typów, tym bliżej możesz zbliżyć się do tego celu.

— sepp2k

3

Powodem, dla którego ta koncepcja jest popularna głównie w społeczności funkcjonalnej, jest to, że w językach ze zmiennym stanem musiałbyś również zakodować informacje o tym, kiedy i gdzie następuje zmiana stanu w typach. W językach, w których wiesz, że wynik funkcji zależy tylko od jej argumentów, o wiele łatwiej jest zakodować dowód w typach (znacznie łatwiej jest również ręcznie sprawdzić poprawność kodu, ponieważ nie musisz brać pod uwagę, który stan globalny jest możliwe i jak wpłynie to na zachowanie funkcji). Jednak nic z tego nie jest szczególnie związane z kompilatorami.

— sepp2k

3

Moim zdaniem najważniejszą cechą jest dopasowywanie wzorców. Optymalizacja abstrakcyjnego drzewa składniowego z dopasowywaniem wzorców jest głupio łatwa. Robienie tego bez dopasowywania wzorców jest często frustrująco trudne.

— Bob Aman

38

Wiele zadań kompilatora polega na dopasowywaniu wzorców w strukturach drzewiastych.

Zarówno OCaml, jak i Haskell mają potężne i zwięzłe możliwości dopasowywania wzorców.

Trudniej jest dodać dopasowanie wzorców do języków imperatywnych, ponieważ każda wartość, która jest oceniana lub wyodrębniana w celu dopasowania do wzorca, musi być wolna od skutków ubocznych.

— Pete Kirkham
źródło

Brzmi jak rozsądna odpowiedź, ale czy to jedyna rzecz? np. czy takie rzeczy jak rekurencja ogona również odgrywają jakąś rolę?

— wvd

To wydaje się wskazywać, że jest to bardziej kwestia systemu typów niż rzeczywistego modelu wykonania. Coś opartego na programowaniu imperatywnym z niezmiennymi wartościami zamiast typów strukturalnych może być w porządku.

— Donal Fellows

@wvd: Optymalizacja rekurencji ogona jest szczegółem implementacji, a nie funkcją języka jako taką, która sprawia, że liniowe funkcje rekurencyjne są równoważne pętli iteracyjnej. Rekurencyjna funkcja przechodzenia po połączonej liście w C przyniosłaby z tego taką samą korzyść, jak rekurencja na liście w Scheme.

— CA McCann

@wvd gcc C ma eliminację wywołań ogonowych, podobnie jak inne zmienne języki stanowe

— Pete Kirkham

3

@camccann: Jeśli standard języka gwarantuje tco (lub przynajmniej gwarantuje, że funkcje rekurencyjne o określonej formie nigdy nie spowodują przepełnienia stosu lub liniowego wzrostu zużycia pamięci), uznałbym to za funkcję języka. Jeśli standard tego nie gwarantuje, ale kompilator i tak to robi, jest to funkcja kompilatora.

— sepp2k

15

Jednym z ważnych czynników do rozważenia jest to, że duża część każdego projektu kompilatora polega na tym, że możesz samodzielnie hostować kompilator i „jeść własną karmę dla psów”. Z tego powodu, gdy patrzysz na języki takie jak OCaml, w których są one przeznaczone do badań językowych, mają one zwykle świetne funkcje do rozwiązywania problemów związanych z kompilatorami.

W mojej ostatniej pracy w stylu kompilatora używaliśmy OCaml właśnie z tego powodu podczas manipulowania kodem w C, było to po prostu najlepsze narzędzie do tego zadania. Gdyby ludzie z INRIA zbudowali OCaml z różnymi priorytetami, mogłoby to nie być tak dobre.

To powiedziawszy, języki funkcjonalne są najlepszym narzędziem do rozwiązania każdego problemu, więc logicznie wynika, że są najlepszym narzędziem do rozwiązania tego konkretnego problemu. CO BYŁO DO OKAZANIA.

/ me: wraca do moich zadań w Javie trochę mniej radośnie ...

— Ukko
źródło

4

-1 dla „Języki funkcjonalne są najlepszym narzędziem do rozwiązywania wszelkich problemów”. Gdyby to była prawda, wszyscy używalibyśmy ich wszędzie. ;)

— Andrei Krotkov

15

@Andrei Krotkov: Dzisiejsze słowo dnia to fa · ce · tious Wymowa: \ fə-ˈsē-shəs \ Funkcja: przymiotnik Etymologia: środkowofrancuski facetieux, od facetie jest, z łaciny facetia Data: 1599 1: żartowanie lub żartowanie często niewłaściwie : żartobliwy <po prostu żartobliwy> 2: miał być żartobliwy lub zabawny: niepoważny <a żartobliwa uwaga> synonimy widzę dowcipny Poza brakiem żartu, twoja logika jest nadal błędna. Zakładasz, że wszyscy ludzie są racjonalnymi aktorami i obawiam się, że nie jest to uczciwe założenie.

— Ukko

5

Wydaje mi się, że przegapiłem żart, ponieważ znam ludzi w prawdziwym życiu, którzy powiedzieliby prawie dokładnie, z wyjątkiem całkowicie poważnych. Chyba prawo Poego. tvtropes.org/pmwiki/pmwiki.php/Main/PoesLaw

— Andrei Krotkov

13

@Andrei: Używając argumentum ad populum : „Jeśli rozum jest lepszy niż emocjonalna ignorancja, wszyscy używalibyśmy go wszędzie”.

— Tim Schaeffer

9

Zasadniczo kompilator to transformacja z jednego zestawu kodu do innego - ze źródła na IR, z IR na zoptymalizowany IR, z IR na assembler, itp. Dokładnie do tego celu służą języki funkcjonalne - czysta funkcja to po prostu przemiana z jednej rzeczy w drugą. Funkcje rozkazujące nie mają tej właściwości. Chociaż możesz napisać tego rodzaju kod w języku imperatywnym, języki funkcjonalne są do tego wyspecjalizowane.

— Gdakanie
źródło

6

Zobacz też

Wzorzec projektowy F #

FP grupuje rzeczy „według operacji”, podczas gdy obiekt OO grupuje rzeczy „według typu”, a „według operacji” jest bardziej naturalne dla kompilatora / interpretera.

— Brian
źródło

3

Odnosi się to do tego, co w niektórych kręgach teorii języka programowania nazywa się „problemem wyrażeń”. Na przykład, spójrz na to pytanie , w którym pokazuję naprawdę okropny kod Haskella, który robi rzeczy w sposób „rozszerzalny”. W przeciwieństwie do tego, zmuszanie języka OOP do stylu „operacji rozszerzalnych” ma tendencję do motywowania wzorca gościa.

— CA McCann

6

Jedną z możliwości jest to, że kompilator ma tendencję do bardzo uważnego radzenia sobie z wieloma przypadkami narożnymi. Poprawienie kodu jest często łatwiejsze dzięki zastosowaniu wzorców projektowych, które strukturyzują implementację w sposób odpowiadający regułom, które implementuje. Często kończy się to jako projekt deklaratywny (dopasowanie wzorców, „gdzie”), a nie imperatyw (sekwencjonowanie, „kiedy”), a zatem łatwiejszy do zaimplementowania w języku deklaratywnym (a większość z nich jest funkcjonalna).

— BCS
źródło

4

Wygląda na to, że wszyscy przegapili inny ważny powód. Bardzo łatwo jest napisać osadzony język specyficzny dla domeny (EDSL) dla parserów, który wygląda bardzo podobnie do (E) BNF w normalnym kodzie. Kombinatory parsera, takie jak Parsec, są dość łatwe do napisania w językach funkcjonalnych przy użyciu funkcji wyższego rzędu i kompozycji funkcji. Nie tylko łatwiejsze, ale bardzo eleganckie.

Zasadniczo najprostsze parsery generyczne reprezentujesz jako zwykłe funkcje i masz specjalne operacje (zwykle funkcje wyższego rzędu), które pozwalają ci skomponować te prymitywne parsery w bardziej skomplikowane, bardziej szczegółowe parsery dla twojej gramatyki.

Nie jest to oczywiście jedyny sposób na stworzenie ram parowania.

— snk_kid
źródło