Dlaczego pisanie kompilatora w języku funkcjonalnym jest łatwiejsze? [zamknięte]
Myślałem nad tym pytaniem bardzo długo, ale naprawdę nie mogłem znaleźć odpowiedzi w Google, jak również podobne pytanie na Stackoverflow. Jeśli jest duplikat, przepraszam za to.
Wiele osób zdaje się mówić, że pisanie kompilatorów i innych narzędzi językowych w językach funkcyjnych, takich jak OCaml i Haskell, jest o wiele wydajniejsze i łatwiejsze niż pisanie ich w językach imperatywnych.
Czy to prawda? A jeśli tak, to dlaczego tak wydajnie i łatwo je napisać w języki funkcyjne zamiast w języku imperatywnym, jak C? Poza tym -- czy narzędzie językowe w języku funkcjonalnym nie jest wolniejsze niż w jakimś języku niskopoziomowym, takim jak C?
7 answers
Często zdarza się, że kompilator dużo pracuje z drzewami. Kod źródłowy jest przetwarzany w drzewie składni. To drzewo może zostać przekształcone 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 (przekształcając składniowe notacje przypominające cukier do postaci niesugarowanej). Teraz możesz wykonywać różne optymalizacje, które są zasadniczo transformacjami na drzewie. Potem prawdopodobnie stworzyłbyś drzewo w jakimś postać normalną, a następnie iterację nad tym drzewem, aby utworzyć kod docelowy (assembly).
Język funkcjonalny posiada funkcje takie jak dopasowanie wzorców i dobre wsparcie dla efektywnej rekurencji, które ułatwiają pracę z drzewami, dlatego są ogólnie uważane za dobre języki do pisania kompilatorów.
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/doraprojects.net/template/agent.layouts/content.php on line 54
2010-05-25 15:40:04
Wiele zadań kompilatora polega na dopasowywaniu wzorców na strukturach drzewiastych.
Zarówno OCaml, jak i Haskell mają potężne i zwięzłe możliwości dopasowania wzorców.
Trudniej jest dodać dopasowanie wzorca do języków imperatywnych, ponieważ każda wartość jest oceniana lub wyodrębniana, aby dopasować wzór do wzorca, musi być wolna od skutków ubocznych.
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/doraprojects.net/template/agent.layouts/content.php on line 54
2010-05-25 15:40:12
Ważnym czynnikiem, który należy wziąć pod uwagę, jest to, że dużą częścią każdego projektu kompilatora jest możliwość samodzielnego hostowania kompilatora i " zjedzenia własnej karmy dla psa."Z tego powodu, gdy spojrzymy na języki takie jak OCaml, gdzie są one przeznaczone do badań nad językami, zwykle mają świetne funkcje dla problemów typu kompilatora.
W mojej ostatniej pracy kompilatora używaliśmy OCaml dokładnie z tego powodu podczas manipulowania kodem C, było to po prostu najlepsze narzędzie do tego zadania. Gdyby ludzie z INRII mieli zbudowany OCaml z różnymi priorytetami może nie być tak dobrym dopasowaniem.
To powiedziawszy, języki funkcyjne 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. QED.
/ja: trochę mniej radośnie wraca do moich zadań w Javie...
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/doraprojects.net/template/agent.layouts/content.php on line 54
2012-08-09 09:53:18
Zasadniczo kompilator jest transformacją z jednego zestawu kodu do drugiego - ze źródła do IR, z IR do zoptymalizowanego IR, z IR do assembly, itp. Właśnie do tego są zaprojektowane języki funkcyjne - czysta funkcja to tylko transformacja z jednej rzeczy do drugiej. Funkcje imperatywne nie mają takiej jakości. Chociaż można pisać tego rodzaju kod w języku imperatywnym, języki funkcyjne są do tego wyspecjalizowane.
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/doraprojects.net/template/agent.layouts/content.php on line 54
2010-05-25 16:53:39
Zobacz też
FP grupuje rzeczy 'po operacji', podczas gdy OO grupuje rzeczy 'po typie', a 'po operacji' jest bardziej naturalne dla kompilatora / interpretera.
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/doraprojects.net/template/agent.layouts/content.php on line 54
2017-05-23 12:02:56
Jedną z możliwości jest to, że kompilator ma tendencję do bardzo ostrożnego radzenia sobie z całą gamą przypadków narożnych. Poprawienie kodu jest często łatwiejsze dzięki zastosowaniu wzorców projektowych, które układają implementację w sposób równoległy do reguł, które implementuje. Często, że kończy się jako deklaratywny (pattern matching, "gdzie"), a nie imperatywny (sekwencjonowanie, "kiedy") projekt i tym samym łatwiejsze do zaimplementowania w języku deklaratywnym (i większość z nich są funkcjonalne).
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/doraprojects.net/template/agent.layouts/content.php on line 54
2010-05-25 17:03:18
Wygląda na to, że każdy przeoczył inny ważny powód. Jest to dość łatwe do napisania osadzony Domain specific language (EDSL)dla parserów, które wyglądają podobnie jak (E) BNF w normalnym kodzie. kombinatory parserów podobnie jak Parsec są dość łatwe do napisania w językach funkcyjnych przy użyciu funkcji wyższego rzędu i kompozycji funkcji. Nie tylko łatwiejsze, ale bardzo elegancko.
Zasadniczo reprezentujesz najprostsze ogólne parsery jako tylko funkcje i masz specjalne operacje (zazwyczaj funkcje wyższego rzędu), które pozwalają skomponować te prymitywne parsery w bardziej skomplikowane, bardziej szczegółowe parsery dla Twojej gramatyki.
Nie jest to jedyny sposób, aby zrobić parer Framework oczywiście.
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/doraprojects.net/template/agent.layouts/content.php on line 54
2010-05-25 16:34:56