Dlaczego funkcja „nic nie rób” Haskella, id, pochłania mnóstwo pamięci?

112

Haskell ma funkcję tożsamości, która zwraca dane wejściowe w niezmienionej postaci. Definicja jest prosta:

id :: a -> a
id x = x

Więc dla zabawy powinno to dać 8:

f = id id id id id id id id id id id id id id id id id id id id id id id id id id id
main = print $ f 8

Po kilku sekundach (i około 2 GB pamięci według Menedżera zadań) kompilacja kończy się niepowodzeniem ghc: out of memory. Podobnie mówi tłumacz ghci: out of memory.

Ponieważ idjest to dość prosta funkcja, nie spodziewałbym się, że będzie obciążała pamięć w czasie wykonywania lub kompilacji. Do czego służy cała pamięć?

haskell ghc

— Ryan
źródło

Chcesz skomponować te idpliki. W VIM, z kursorem w sprawie definicji f, to zrobić: :s/id id/id . id ./g.

— Tobias Brandt

135

Znamy rodzaj id,

id :: a -> a

A kiedy specjalizujemy się w tym id id, lewa kopia idma typ:

id :: (a -> a) -> (a -> a)

A potem, kiedy to specjalizują się ponownie do najbardziej na lewo idw id id id, można uzyskać:

id :: ((a -> a) -> (a -> a)) -> ((a -> a) -> (a -> a))

Widzisz więc, że każdy iddodajesz, podpis typu skrajnego lewego idjest dwukrotnie większy.

Pamiętaj, że typy są usuwane podczas kompilacji, więc zajmie to tylko pamięć w GHC. Nie zajmie pamięci w twoim programie.

— Dietrich Epp
źródło

Pamiętam, że Okasaki miał podobne kłopoty, kiedy pisał kalkulator RPN wbudowany w Haskell.

— dfeuer

Być może pytanie brzmi, czy GHC powinien znaleźć sposób na radzenie sobie z tego rodzaju sprawami w bardziej wdzięczny sposób. W szczególności typ jest bardzo duży, gdy jest zapisywany w całości, ale występuje ogromna ilość duplikatów - czy udostępnianie może posłużyć do skompresowania takich rzeczy? Czy istnieje skuteczny sposób ich przetwarzania?

— dfeuer

@dfeuer Spróbuj zapytać o typ w ghci. Po szybkości reakcji zobaczysz, że musi wykonywać odpowiednie udostępnianie. Podejrzewam, że to udostępnianie jest utracone - z oczywistych powodów - po przetłumaczeniu na inną reprezentację pośrednią (np. Rdzeń).

— Daniel Wagner

Oznacza to, że jeśli idjest powtarzane nrazy, przestrzeń tego typu jest proporcjonalna do 2^n. Typ wywnioskowany w kodzie Ryana wymagałby 2^27odniesień do jego zmiennej typu oprócz innej struktury potrzebnej do reprezentowania typu, która jest prawdopodobnie znacznie większa niż można by się spodziewać po większości typów.

— David

Naiwne wnioskowanie o typie jest podwójnie wykładnicze, dzięki sprytnemu użyciu udostępniania w wyrażeniach typu można sprowadzić to do wykładniczego. Ale bez względu na to, co zrobisz, będzie kilka raczej prostych wyrażeń, które spowodują eksplozję kontrolera typów. Na szczęście nie ma to miejsca w praktycznym programowaniu.

— augustss