Dlaczego funkcjonalne języki programowania wymagają wyrzucania elementów bezużytecznych?

14

Co powstrzymuje ghc przed przetłumaczeniem Haskell na konkatenatywny język programowania, taki jak logika kombinacyjna, a następnie po prostu użycie alokacji stosu do wszystkiego? Według Wikipedii tłumaczenie z rachunku lambda na logikę kombinacyjną jest banalne, a także konkatenatywne języki programowania mogą polegać wyłącznie na stosie przy alokacji pamięci. Czy to możliwe, aby wykonać to tłumaczenie, a tym samym wyeliminować zbieranie śmieci dla języków takich jak Haskell i ocaml? Czy są to wady?

EDYCJA: przeniesiono tutaj /programming/39440412/why-do-functional-programming-languages-require-garbage-collection

functional-programming haskell Mikołaj Grasevski
źródło
Cat język programowania wygląda na przykładzie języka funkcyjnego, a na stosie.
Petr Pudlák,
1
To nie jest kwestia badawcza, ponieważ wywóz śmieci jest objęty kursami licencjackimi na temat języków programowania (jak również potrzeby). Przejdź na stronę cs.stackexchange.com
Andrej Bauer,
Mój błąd. Czy znasz odpowiedź na moje pytanie?
Nicholas Grasevski,
5
Wydaje mi się, że na to pytanie należy odpowiedzieć na poziomie badawczym, ponieważ pamiętam, że miałem z tym problem również w trakcie studiów: wszystko w języku takim jak Haskell wygląda jak aplikacja funkcyjna, która żyje na stosie. Wydaje mi się, że wyjaśnienie, dlaczego zamknięcia są konieczne, dlaczego żyją na stercie, i być może to, co mają z tym wspólnego „dane uciekające przed zakresem funkcji”, byłyby bardzo pouczającą odpowiedzią (czego nie jestem pewien, czy mam kwalifikacje do udzielenia, Niestety).
cody
2
λ

Odpowiedzi:

16

Wszystkie poniższe komentarze opierają się na wyborze standardowej strategii implementacji przy użyciu zamknięć do reprezentowania wartości funkcji i kolejności oceny według wartości:

  1. W przypadku rachunku czystego lambda zbieranie śmieci nie jest konieczne. Wynika to z faktu, że nie można tworzyć cykli w stercie: każda nowo przydzielona wartość może zawierać tylko odwołania do wcześniej przydzielonych wartości, dlatego wykres pamięci tworzy DAG - zliczanie odniesień wystarcza do zarządzania pamięcią.

  2. Większość implementacji nie korzysta z liczenia referencji z dwóch powodów.

    1. Obsługują one formę typu wskaźnika (np. refKonstruktor typu w ML), dzięki czemu można tworzyć prawdziwe cykle w stercie.
    2. Od tego czasu liczenie referencji jest znacznie mniej wydajne niż zbieranie śmieci
      • wymaga dużo dodatkowej przestrzeni, aby zachować liczbę referencji, oraz
      • aktualizowanie liczników jest zwykle marnowaną pracą, oraz
      • aktualizacje zliczeń tworzą spór o zapis, który zabija równoległą wydajność.

  3. Języki o typie liniowym mogą wyeliminować liczbę odwołań (zasadniczo dlatego, że liczby wynoszą 0-1: albo wartość ma jedno odniesienie do niej, albo jest martwa i można ją zwolnić).

  4. Jednak alokacja stosu wciąż nie wystarcza. Jest tak, ponieważ możliwe jest tworzenie wartości funkcji, które odnoszą się do zmiennych swobodnych (tj. Musimy zaimplementować zamknięcia funkcji), jeśli przydzielisz rzeczy na stosie, wówczas wartości na żywo mogą być przeplatane z wartościami martwymi, co spowoduje niepoprawną asymptozę wykorzystanie miejsca.

  5. Możesz uzyskać właściwą asymptotę, zastępując stos „stosem spaghetti” (tj. Zaimplementuj stos jako listę połączoną w stosie, aby w razie potrzeby wyciąć martwe ramki).

  6. Jeśli chcesz prawdziwej dyscypliny stosu, możesz użyć systemów typów opartych na „logice uporządkowanej” (zasadniczo typy liniowe minus zamiana).

Neel Krishnaswami
źródło
2
Czy nie jest bardziej podstawowym powodem (2), że - nawet bez zauważalnych skutków ubocznych - wdrożenia chcą mieć wydajnego operatora dla (wzajemnej) rekurencji, tj. Takiego, który faktycznie tworzy cykl na stosie?
Andreas Rossberg,
@andreasrossberg: Pomyślałem o tym, ale o tym zapomniałem, ponieważ można użyć kombinatora y do rekurencji.
Neel Krishnaswami,