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?
Odpowiedzi:
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.
źródło
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.
źródło
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 ...
źródło
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.
źródło
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.
źródło
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).
źródło
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.
źródło