Por que a função “não fazer nada” de Haskell, id, consome toneladas de memória?

112

Haskell tem uma função de identidade que retorna a entrada inalterada. A definição é simples:

id :: a -> a
id x = x

Então, para se divertir, isso deve resultar 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

Após alguns segundos (e cerca de 2 gb de memória de acordo com o Gerenciador de Tarefas), a compilação falha com ghc: out of memory. Da mesma forma, o intérprete diz ghci: out of memory.

Como idé uma função muito simples, não esperaria que fosse uma carga de memória em tempo de execução ou tempo de compilação. Para que toda a memória está sendo usada?

haskell ghc Ryan
fonte
11
Você quer compor esses ids. No VIM, com o cursor sobre a definição de f, faça o seguinte: :s/id id/id . id ./g.
Tobias Brandt

Respostas:

135

Sabemos o tipo de id,

id :: a -> a

E quando nos especializamos nisso id id, a cópia esquerda de idtem tipo:

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

E então quando você se especializar isso de novo para o mais à esquerda idem id id id, você obtém:

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

Assim, você verá que cada um que idvocê adiciona, a assinatura de tipo da extremidade esquerda idé duas vezes maior.

Observe que os tipos são excluídos durante a compilação, portanto, isso ocupará apenas memória no GHC. Não vai ocupar memória em seu programa.

Dietrich Epp
fonte
Lembro-me de Okasaki enfrentando problemas semelhantes quando escreveu uma calculadora RPN embutida em Haskell.
dfeuer
3
A questão, talvez, é se o GHC deveria encontrar uma maneira de lidar com esse tipo de coisa com mais elegância. Em particular, o tipo é muito grande quando escrito por extenso, mas há uma quantidade enorme de duplicação - o compartilhamento poderia ser usado para compactar essas coisas? Existe uma maneira eficiente de processá-los?
dfeuer
5
@dfeuer Tente pedir o tipo em ghci. Você verá pela velocidade da resposta que ele deve estar fazendo o compartilhamento apropriado. Suspeito que esse compartilhamento seja perdido - por razões óbvias - assim que você traduzir para alguma outra representação intermediária (por exemplo, núcleo).
Daniel Wagner
4
Isso significa que se idfor repetido nvezes, o espaço de seu tipo é proporcional a 2^n. O tipo inferido no código de Ryan precisaria de 2^27referências à sua variável de tipo, além da outra estrutura necessária para representar o tipo, que provavelmente é muito maior do que você esperaria que a maioria dos tipos fosse.
David
58
Fazer inferência de tipo ingenuamente é duplamente exponencial; ao usar inteligentemente o compartilhamento nas expressões de tipo, você pode reduzi-lo para apenas exponencial. Mas não importa o que você faça, haverá algumas expressões bastante simples que farão o verificador de tipos explodir. Felizmente, isso não ocorre na programação prática.
agosto