Czy Haskell wymaga śmieciarza?
Jestem ciekaw dlaczego Haskell używa GC.
Nie przychodzi mi do głowy przypadek, w którym GC byłoby konieczne w czystym języku. Czy jest to tylko optymalizacja w celu ograniczenia kopiowania, czy jest to rzeczywiście konieczne?
Szukam przykładowego kodu, który wyciekłby, gdyby nie było GC.
8 answers
Jak już zauważyli inni, Haskell wymaga automatycznego, dynamic memory management: automatyczne zarządzanie pamięcią jest konieczne, ponieważ ręczne zarządzanie pamięcią jest niebezpieczne; dynamiczne zarządzanie pamięcią jest konieczne, ponieważ dla niektórych programów, żywotność obiektu może być określona tylko w czasie wykonywania.
Na przykład, rozważ 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 napisze " Wyczyść"; tak więc żywotność tego musi być określana dynamicznie i dlatego konieczne jest dynamiczne zarządzanie pamięcią.
Więc w tym sensie, automatyczna alokacja pamięci dynamicznej jest konieczna, a w praktyce oznacza to: tak , Haskell wymaga garbage Collectora, ponieważ garbage Collect jest najwyższej wydajności automatycznym menedżerem pamięci dynamicznej.
Jednakże...
Chociaż Śmieciarz jest niezbędny, możemy spróbować znaleźć pewne szczególne przypadki gdzie kompilator może użyć tańszego schematu zarządzania pamięcią niż garbage collection. Na przykład, given
f :: Integer -> Integer
f x = let x2 = x*x in x2*x2
Możemy mieć nadzieję, że kompilator wykryje, że x2 może być bezpiecznie dealokowany, gdy f powróci (zamiast czekać na dealokację przez garbage collector x2). Zasadniczo prosimy, aby kompilator wykonał analizę ucieczki w celu konwersji alokacji w stercie śmieci na alokacje na stosie w miarę możliwości.
Nie jest to zbyt nieuzasadnione, aby prosić: kompilator JHC haskell robi to, chociaż GHC nie robi. Simon Marlow mówi, że generacyjny garbage collector GHC sprawia, że analiza ucieczki jest w większości niepotrzebna.
Jhc faktycznie używa wyrafinowanej formy analizy ucieczki znanej jako wnioskowanie regionu . Rozważmy
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 wnioskowałaby, że x2 ucieka z f (ponieważ jest zwracana w tuple), a zatem x2 muszą być przydzielone na stercie śmieci. Z drugiej strony, wnioskowanie o regionie jest w stanie wykryć, że x2 może być dealokowany, gdy g zwraca; idea tutaj jest taka, że x2 powinien być alokowany w regionie g, a nie w regionie f.
Beyond Haskell
Chociaż wnioskowanie regionalne jest pomocne w niektórych przypadkach, jak omówiono powyżej, wydaje się być trudne do skutecznego pogodzenia z leniwą oceną (patrz Edwarda Kmetta i Simon Peyton Jones' komentarze). Na przykład, rozważmy
f :: Integer -> Integer
f n = product [1..n]
Można by pokusić się o przydzielenie listy [1..n] na stosie i dealokację jej po zwróceniu f, ale byłoby to katastrofalne: zmieniłoby to f z użycia pamięci O(1) (pod garbage collection) na pamięć o(n).
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-03-31 06:50:19
Weźmy trywialny przykład. Given this
f (x, y)
Musisz przydzielić parę (x, y) gdzieś przed wywołaniem f. Kiedy można zmniejszyć tę parę? Nawet nie masz pojęcia. Nie można go dealokować, gdy f zwraca, ponieważ f mogło 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 wpisana na listę, czy ktokolwiek ją rozdzieli, może ją rozdzielić? Nie, ponieważ para może być dzielona (np. let p = (x, y) in (f p, p)). Więc naprawdę trudno powiedzieć, kiedy para może być dealocated.
To samo dotyczy prawie wszystkich przydziałów w Haskell. To powiedziawszy, możliwe jest przeprowadzenie analizy (analiza regionu), która daje górną granicę życia. Działa to dość dobrze w językach ścisłych, ale mniej w językach leniwych (języki leniwe mają tendencję do znacznie większej mutacji niż języki ścisłe w implementacji).
Więc chciałbym odwrócić to pytanie. Jak myślisz, dlaczego Haskell nie potrzebuje GC. Jak sugerujesz przydział pamięci?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-03-31 13:22:13
Twoja intuicja, że to ma coś wspólnego z czystością, ma w tym trochę prawdy.
Haskell jest uważany za czysty, częściowo dlatego, że skutki uboczne funkcji są uwzględniane w sygnaturze typu. Jeśli więc funkcja ma efekt uboczny wydrukowania czegoś, musi istnieć IO gdzieś w jej typie zwrotnym.
Ale istnieje funkcja, która jest używana bezwarunkowo wszędzie w Haskell i której sygnatura typu nie uwzględnia, co jest w pewnym sensie, efektem ubocznym. Mianowicie funkcja, która kopiuje niektóre dane i daje dwie wersje z powrotem. Pod maską może to działać dosłownie, powielając dane w pamięci lub "wirtualnie", zwiększając dług, który należy spłacić później.
Możliwe jest projektowanie języków z jeszcze bardziej restrykcyjnymi systemami typów (czysto "liniowymi"), które uniemożliwiają kopiowanie funkcji. Z punktu widzenia programisty w takim języku, Haskell wygląda trochę nieczysty.
W rzeczywistości czysty , krewny z Haskell, ma liniowe (ściślej: unikalne) typy, a to może dać pewien pomysł, jak to jest, aby uniemożliwić kopiowanie. Ale Clean nadal pozwala na kopiowanie dla" nie-unikalnych " typów.
Jest wiele badań w tej dziedzinie i jeśli Wygooglujesz wystarczająco dużo, znajdziesz przykłady czystego kodu liniowego, który nie wymaga zbierania śmieci. Znajdziesz wszystkie rodzaje systemów typu, które mogą zasygnalizować kompilatorowi, jakiej pamięci można użyć, pozwalając kompilatorowi wyeliminować niektóre z GC.
Istnieje sens, w którym algorytmy kwantowe są również czysto liniowe. Każda operacja jest odwracalna, więc żadne dane nie mogą być tworzone, kopiowane, ani niszczone. (Są również liniowe w zwykłym sensie matematycznym.)
Interesujące jest również porównanie z Forth (lub innymi językami stosowymi), które mają wyraźne operacje DUP, które wyjaśniają, kiedy następuje duplikacja.
Innym (bardziej abstrakcyjnym) sposobem myślenia o tym jest zwrócenie uwagi na to, że Haskell jest zbudowany w górę od zwykłego rachunku lambda, który opiera się na teorii kartezjańskich kategorii zamkniętych i że takie kategorie są wyposażone w funkcję diagonalną diag :: X -> (X, X). Język oparty na innej klasie kategorii może nie mieć czegoś takiego.
Ale ogólnie rzecz biorąc, programowanie czysto liniowe jest zbyt trudne, aby było użyteczne, więc zadowalamy się GC.
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-04-01 15:46:42
Standardowe techniki implementacji stosowane w Haskell 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 zużywa więcej pamięci, duża liczba wartości zostanie odrzucona w miarę upływu czasu.
Dlatego programy GHC mają tak wysokie wartości całkowitej alokacji (od gigabajtów do terabajtów): są stale przydzielają pamięć i tylko dzięki wydajnemu GC odzyskują ją przed wyczerpaniem się.
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-03-31 03:07:40
Jeśli język (dowolny język) pozwala na dynamiczne przydzielanie obiektów, to istnieją trzy praktyczne sposoby radzenia sobie z zarządzaniem pamięcią:
Język umożliwia przydzielanie pamięci tylko na stosie lub przy starcie. Ale te ograniczenia poważnie ograniczają rodzaje obliczeń, które program może wykonać. (W praktyce. Teoretycznie można emulować dynamiczne struktury danych w (powiedzmy) Fortranie, reprezentując je w dużej tablicy. To straszne ... i nie istotne dla tej dyskusji.)
Język może zapewnić jawny mechanizm
freeLUBdispose. Ale to zależy od programisty, aby to zrobić dobrze. Każdy błąd w zarządzaniu pamięcią masową może spowodować wyciek pamięci... albo gorzej.Język (a ściślej implementacja języka) może zapewnić automatyczny Menedżer pamięci dla dynamicznie przydzielanej pamięci masowej, tj. jakąś formę garbage collector.
Jedyną inną opcją jest nigdy nie odzyskuj dynamicznie przydzielonej przestrzeni dyskowej. Nie jest to praktyczne rozwiązanie, z wyjątkiem małych programów wykonujących małe obliczenia.
Stosując to do Haskella, język nie ma ograniczenia 1. i nie ma ręcznej operacji dealokacji, jak na 2. Dlatego, aby być użytecznym dla nietrywialnych rzeczy, implementacja Haskella musi zawierać garbage collector.
Nie przychodzi mi do głowy przypadek, w którym GC byłoby konieczne w czystej język.Prawdopodobnie masz na myśli czysty język funkcjonalny.
Odpowiedź jest taka, że GC jest wymagane 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 przypisać do stosu.
Fakt, że mogą istnieć cykle (wynikające np. z
let rec) oznacza, że odniesienie liczenie nie będzie działać dla obiektów sterty.Następnie są zamknięcia funkcji ... które również nie mogą być przypisane do stosu, ponieważ mają czas życia, który jest (zazwyczaj) niezależny od ramki stosu, w której zostały utworzone.
Szukam przykładowego kodu, który wyciekłby, gdyby nie było GC.
Prawie każdy przykład związany z zamknięciami lub strukturami danych w kształcie grafu wyciekłby w tych warunkach.
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-03-31 04:15:08
Garbage collector nigdy nie jest potrzebny, pod warunkiem, że masz wystarczającą pamięć. Jednak w rzeczywistości nie mamy nieskończonej pamięci, więc potrzebujemy jakiejś metody odzyskiwania pamięci, która nie jest już potrzebna. W nieczystych językach, takich jak C, możesz wyraźnie stwierdzić, że masz dość pamięci, aby ją uwolnić - ale jest to operacja mutująca (pamięć, którą właśnie uwolniłeś, nie jest już bezpieczna do odczytu), więc nie możesz używać tego podejścia w czystym języku. Więc albo jakoś statycznie analizować, gdzie można zwolnij pamięć (prawdopodobnie niemożliwe w ogólnym przypadku), wyciek pamięci jak sito (działa świetnie, dopóki się nie skończy), lub użyj GC.
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-03-31 02:59:23
Haskell jest niestrudzonym językiem programowania, ale większość implementacji korzysta z funkcji call-by-need (lenistwo), aby zaimplementować niestrudzenie. W call-by-need oceniasz rzeczy tylko wtedy, gdy zostaną osiągnięte podczas runtime przy użyciu maszynerii "thunks" (wyrażenia, które oczekują na ocenę, a następnie nadpisują się, pozostając widoczne dla ich wartości do ponownego użycia w razie potrzeby).
Więc jeśli zaimplementujesz swój język leniwie używając thunków, odłożysz wszelkie rozumowanie o życiu obiektu do ostatnia chwila, czyli runtime. Ponieważ teraz nie wiesz nic o życiu, jedyną rzeczą, którą możesz rozsądnie zrobić, jest zbieranie śmieci...
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-03-31 10:30:03
GC jest "must have" w czystych językach FP. Dlaczego? Operacje alloc i free są nieczyste! Drugim powodem jest to, że niezmienne rekurencyjne struktury danych potrzebują GC do istnienia, ponieważ backlinking tworzy zawiłe i niemożliwe do utrzymania struktury dla ludzkiego umysłu. Oczywiście backlinking 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, spróbuj zaimplementować język FP, a zobaczysz, że mam rację.
EDIT: zapomniałem. Lenistwo to piekło bez GC. Nie wierzysz mi? Po prostu spróbuj bez GC np. w C++. Zobaczysz ... rzeczy
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
2015-09-15 18:09:27