Czy Haskell potrzebuje śmieciarki?

Jestem ciekaw, dlaczego implementacje Haskell używają GC.

Nie przychodzi mi do głowy przypadek, w którym GC byłaby konieczna w czystym języku. Czy jest to tylko optymalizacja w celu ograniczenia kopiowania, czy rzeczywiście jest to konieczne?

Szukam na przykład kodu, który przeciekałby, gdyby nie było GC.

Jak inni już zauważyli, Haskell wymaga automatycznego , dynamicznego zarządzania pamięcią: automatyczne zarządzanie pamięcią jest konieczne, ponieważ ręczne zarządzanie pamięcią jest niebezpieczne; dynamiczne zarządzanie pamięcią jest konieczne, ponieważ w przypadku niektórych programów czas życia obiektu można określić tylko w czasie wykonywania.

Weźmy na przykład pod uwagę następujący program:

main = loop (Just [1..1000]) where
  loop :: Maybe [Int] -> IO ()
  loop obj = do
    print obj
    resp <- getLine
    if resp == "clear"
     then loop Nothing
     else loop obj

W tym programie lista [1..1000]musi być przechowywana w pamięci, dopóki użytkownik nie wpisze „wyczyść”; więc czas życia tego musi być określany dynamicznie, i dlatego konieczne jest dynamiczne zarządzanie pamięcią.

W tym sensie automatyczna alokacja dynamicznej pamięci jest niezbędna, co w praktyce oznacza: tak , Haskell wymaga modułu odśmiecania pamięci, ponieważ czyszczenie pamięci jest automatycznym menedżerem pamięci dynamicznej o najwyższej wydajności.

Jednak...

Chociaż garbage collector jest konieczny, możemy spróbować znaleźć kilka specjalnych przypadków, w których kompilator może użyć tańszego schematu zarządzania pamięcią niż czyszczenie pamięci. Na przykład podane

f :: Integer -> Integer
f x = let x2 = x*x in x2*x2

możemy mieć nadzieję, że kompilator wykryje, że x2można bezpiecznie cofnąć przydział przy zwrocie f(zamiast czekać, aż moduł odśmiecania pamięci zwolni przydziałx2 ). Zasadniczo prosimy, aby kompilator przeprowadził analizę ucieczki, aby przekonwertować alokacje na stertę zebraną bez pamięci na alokacje na stosie, jeśli to możliwe.

Nie jest to zbyt nierozsądne, aby poprosić o: kompilator jhc haskell robi to, chociaż GHC tego nie robi. Simon Marlow mówi, że generowany przez GHC garbage collector sprawia, że ​​analiza ucieczki jest w większości niepotrzebna.

jhc w rzeczywistości wykorzystuje wyrafinowaną formę analizy ucieczki znaną jako wnioskowanie o regionie . Rozważać

f :: Integer -> (Integer, Integer)
f x = let x2 = x * x in (x2, x2+1)

g :: Integer -> Integer
g x = case f x of (y, z) -> y + z

W tym przypadku uproszczona analiza ucieczki zakończyłaby się wnioskiem, że x2ucieka z f(ponieważ jest zwracana w krotce), a zatem x2musi zostać przydzielona na stercie zebranym z pamięci. Z drugiej strony wnioskowanie o regionie jest w stanie wykryć, że x2można to cofnąć, kiedyg zwrotu; chodzi tutaj o to, x2aby alokować w gregionie, a nie w fregionie.

Poza Haskellem

Chociaż wnioskowanie o regionie jest pomocne w niektórych przypadkach, jak omówiono powyżej, wydaje się, że trudno jest go skutecznie pogodzić z leniwą oceną (patrz komentarze Edwarda Kmetta i Simona Peytona Jonesa ). Weźmy na przykład pod uwagę

f :: Integer -> Integer
f n = product [1..n]

Można by pokusić się o przydzielenie listy [1..n] na stosie i zwolnienie jej po fzwróceniu, ale byłoby to katastrofalne: zmieniłoby się fz używania pamięci O (1) (w ramach czyszczenia pamięci) na pamięć O (n).

W latach 90. i na początku 2000 r. Przeprowadzono obszerne prace nad wnioskiem o regiony dla ścisłego języka funkcjonalnego ML. Mads Tofte, Lars Birkedal, Martin Elsman, Niels Hallenberg napisali dość czytelną retrospektywę na temat ich pracy nad wnioskiem o regiony, z których większość zintegrowali z kompilatorem MLKit . Eksperymentowali z zarządzaniem pamięcią opartym wyłącznie na regionach (tj. Bez modułu wyrzucania elementów bezużytecznych), a także z zarządzaniem pamięcią opartą na regionach / gromadzeniu elementów bezużytecznych i stwierdzili, że ich programy testowe działają „od 10 razy szybciej do 4 razy wolniej” niż czyste zebrane wersje.

Weźmy trywialny przykład. Biorąc to pod uwagę

f (x, y)

musisz (x, y)gdzieś przydzielić parę, zanim zadzwonisz f. Kiedy można zwolnić tę parę? Nie masz pojęcia. Nie można go cofnąć, gdy fzwraca, ponieważ fmogłaby umieścić parę w strukturze danych (np. f p = [p]), Więc czas życia pary może być dłuższy niż powrót z f. Powiedzmy, że para została umieszczona na liście, czy ktokolwiek rozdzieli listę, może cofnąć przydział tej pary? Nie, ponieważ para może być współdzielona (np let p = (x, y) in (f p, p).). Dlatego naprawdę trudno jest stwierdzić, kiedy para może zostać zwolniona.

To samo dotyczy prawie wszystkich przydziałów w Haskell. To powiedziawszy, możliwe jest przeprowadzenie analizy (analiza regionu), która daje górną granicę czasu życia. Działa to dość dobrze w językach ścisłych, ale mniej w językach leniwych (języki leniwe mają tendencję do przeprowadzania o wiele więcej mutacji niż języki ścisłe w implementacji).

Więc chciałbym odwrócić pytanie. Jak myślisz, dlaczego Haskell nie potrzebuje GC. Jak sugerowałbyś alokację pamięci?

Twoja intuicja, że ​​ma to coś wspólnego z czystością, ma w sobie trochę prawdy.

Haskell jest uważany za czysty częściowo dlatego, że efekty uboczne funkcji są uwzględniane w sygnaturze typu. Więc jeśli funkcja ma efekt uboczny drukowania czegoś, musi istnieć plikIO gdzieś w jej typie zwracanym.

Ale jest funkcja, która jest używana niejawnie wszędzie w Haskell i której sygnatura typu nie wyjaśnia, co jest w pewnym sensie efektem ubocznym. Mianowicie funkcja, która kopiuje niektóre dane i zwraca dwie wersje. Pod maską może to działać dosłownie, powielając dane w pamięci lub „wirtualnie”, zwiększając dług, który musi zostać spłacony później.

Możliwe jest projektowanie języków z jeszcze bardziej restrykcyjnymi systemami czcionek (czysto „liniowymi”), które nie pozwalają na funkcję kopiowania. Z punktu widzenia programisty w takim języku Haskell wygląda na trochę nieczystego.

W rzeczywistości Clean , krewny Haskella, ma typy liniowe (ściślej: unikalne), co może dać wyobrażenie o tym, jak by to było, gdybyśmy zabronili kopiowania. Ale Clean nadal umożliwia kopiowanie dla „nieunikalnych” typów.

Jest wiele badań w tej dziedzinie i jeśli wystarczająco dobrze wygooglujesz, znajdziesz przykłady czystego kodu liniowego, który nie wymaga czyszczenia pamięci. Znajdziesz wszystkie rodzaje systemów typów, które mogą sygnalizować kompilatorowi, jakiej pamięci można użyć, umożliwiając kompilatorowi wyeliminowanie części GC.

W pewnym sensie algorytmy kwantowe są również czysto liniowe. Każda operacja jest odwracalna, więc żadne dane nie mogą być tworzone ani kopiowane ani niszczone. (Są również liniowe w zwykłym matematycznym sensie).

Interesujące jest również porównanie z Forth (lub innymi językami opartymi na stosie), które mają wyraźne operacje DUP, które wyjaśniają, kiedy zachodzi duplikacja.

Innym (bardziej abstrakcyjnym) sposobem myślenia o tym jest zauważenie, że Haskell jest zbudowany z prostego rachunku lambda, który jest oparty na teorii zamkniętych kategorii kartezjańskich i że takie kategorie są wyposażone w funkcję diagonalną diag :: X -> (X, X). Język oparty na innej kategorii kategorii może nie mieć czegoś takiego.

Ale ogólnie programowanie czysto liniowe jest zbyt trudne, aby było użyteczne, więc decydujemy się na GC.

Standardowe techniki implementacji zastosowane w Haskell w rzeczywistości wymagają GC bardziej niż większość innych języków, ponieważ nigdy nie mutują poprzednich wartości, zamiast tego tworzą nowe, zmodyfikowane wartości na podstawie poprzednich. Ponieważ oznacza to, że program stale alokuje i wykorzystuje więcej pamięci, w miarę upływu czasu duża liczba wartości zostanie odrzucona.

Dlatego programy GHC mają zwykle tak wysokie całkowite wartości alokacji (od gigabajtów do terabajtów): stale alokują pamięć i tylko dzięki wydajnemu GC odzyskują ją przed wyczerpaniem.

Jeśli język (dowolny język) umożliwia dynamiczne przydzielanie obiektów, istnieją trzy praktyczne sposoby radzenia sobie z zarządzaniem pamięcią:

1. Język pozwala tylko na przydzielenie pamięci na stosie lub podczas uruchamiania. Jednak te ograniczenia poważnie ograniczają rodzaje obliczeń, które może wykonywać program. (W praktyce. Teoretycznie można emulować dynamiczne struktury danych w (powiedzmy) Fortranie, przedstawiając je w dużej tablicy. Jest to STRASZNE ... i nie dotyczy tej dyskusji.)

2. Język może zapewnić wyraźne free lub disposemechanizm. Ale to zależy od programisty, aby zrobić to dobrze. Każdy błąd w zarządzaniu pamięcią może spowodować wyciek pamięci ... lub gorzej.

3. Język (a ściślej implementacja języka) może zapewnić automatyczny menedżer pamięci dla dynamicznie przydzielanej pamięci; czyli jakaś forma garbage collectora.

Jedyną inną opcją jest to, aby nigdy nie odzyskiwać pamięci przydzielonej dynamicznie. Nie jest to praktyczne rozwiązanie, z wyjątkiem małych programów wykonujących małe obliczenia.

Stosując to do Haskell, język nie ma ograniczenia 1. i nie ma ręcznej operacji zwalniania przydziału zgodnie z 2. Dlatego, aby być użytecznym do rzeczy nietrywialnych, implementacja Haskella musi zawierać moduł odśmiecania pamięci .

Nie przychodzi mi do głowy przypadek, w którym GC byłaby konieczna w czystym języku.

Przypuszczalnie masz na myśli czysty język funkcjonalny.

Odpowiedź jest taka, że ​​GC jest wymagany pod maską, aby odzyskać obiekty sterty, które język MUSI utworzyć. Na przykład.

• Czysta funkcja musi tworzyć obiekty sterty, ponieważ w niektórych przypadkach musi je zwrócić. Oznacza to, że nie można ich przydzielić na stosie.

• Fakt, że mogą istnieć cykle (wynikające let recna przykład z a ) oznacza, że ​​podejście zliczania referencji nie będzie działać dla obiektów sterty.

• Są też zamknięcia funkcji ... których również nie można zaalokować na stosie, ponieważ mają czas życia, który jest (zazwyczaj) niezależny od ramki stosu, w której zostały utworzone.

Szukam na przykład kodu, który przeciekałby, gdyby nie było GC.

Prawie każdy przykład obejmujący zamknięcia lub struktury danych w kształcie wykresu przeciekłby w takich warunkach.

Odśmiecacz nigdy nie jest potrzebny, pod warunkiem, że masz wystarczającą ilość pamięci. Jednak w rzeczywistości nie mamy nieskończonej pamięci, więc potrzebujemy jakiejś metody, aby odzyskać pamięć, która nie jest już potrzebna. W nieczystych językach, takich jak C, możesz wyraźnie stwierdzić, że masz już trochę pamięci, aby ją zwolnić - ale jest to operacja mutacji (pamięć, którą właśnie uwolniłeś, nie jest już bezpieczna do czytania), więc nie możesz użyć tego podejścia w czysty język. Więc albo w jakiś sposób statycznie przeanalizuj, gdzie możesz zwolnić pamięć (prawdopodobnie niemożliwe w ogólnym przypadku), wyciek z pamięci jak sito (działa świetnie, dopóki się nie skończy), albo użyj GC.

GC to „must have” w czystych językach FP. Czemu? Operacje przydzielone i bezpłatne są nieczyste! Drugim powodem jest to, że niezmienne, rekurencyjne struktury danych potrzebują GC do istnienia, ponieważ łączenie wsteczne tworzy zawiłe i niemożliwe do utrzymania struktury dla ludzkiego umysłu. Oczywiście backlinkowanie jest błogosławieństwem, ponieważ kopiowanie struktur, które z niego korzystają, jest bardzo tanie.

W każdym razie, jeśli mi nie wierzysz, po prostu spróbuj zaimplementować język FP, a zobaczysz, że mam rację.

EDYCJA: zapomniałem. Lenistwo jest PIEKŁEM bez GC. Nie wierzysz mi? Po prostu spróbuj bez GC, na przykład w C ++. Zobaczysz ... rzeczy

Haskell nie jest surowym językiem programowania, ale większość implementacji używa wywołania według potrzeby (lenistwa) do implementacji braku ścisłości. W wywołaniu według potrzeby oceniasz rzeczy tylko wtedy, gdy zostaną osiągnięte w czasie działania przy użyciu mechanizmu „thunks” (wyrażeń, które czekają na ocenę, a następnie nadpisują się, pozostając widocznymi, aby ich wartość mogła zostać ponownie użyta w razie potrzeby).

Tak więc, jeśli leniwie zaimplementujesz swój język za pomocą thunks, odłożyłeś wszelkie rozumowania dotyczące czasu życia obiektów do ostatniej chwili, czyli czasu wykonania. Ponieważ teraz nie wiesz nic o wcieleniach, jedyne, co możesz rozsądnie zrobić, to zbieranie śmieci ...