Opened 2 years ago

Closed 2 years ago

Last modified 2 years ago

#5622 closed bug (invalid)

Out of memory in such a simple case

Reported by: quux Owned by:
Priority: normal Milestone:
Component: Compiler Version: 7.2.1
Keywords: Cc:
Operating System: Windows Architecture: x86_64 (amd64)
Type of failure: Compile-time crash Difficulty:
Test Case: Blocked By:
Blocking: Related Tickets:

Description

GHCi, version 7.2.1: http://www.haskell.org/ghc/  :? for help
Loading package ghc-prim ... linking ... done.
Loading package integer-gmp ... linking ... done.
Loading package base ... linking ... done.
Loading package ffi-1.0 ... linking ... done.
Prelude> id 5
5
Prelude> id id id id id 5
5
Prelude> id id id id id id id id id id id id id id 5
5
Prelude> 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 5
<interactive>: out of memory

Change History (3)

comment:1 Changed 2 years ago by quux

  • Component changed from GHCi to Compiler
  • Summary changed from GHCI is out of memory in such a simple case to Out of memory in such a simple case
  • Type of failure changed from GHCi crash to Compile-time crash

Not GHCi only bug:

test x = 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 id id id id id id id x

main = print ":("
$ ghc id.hs
ghc id.hs
[1 of 1] Compiling Main             ( id.hs, id.o )
ghc: out of memory

comment:2 Changed 2 years ago by simonpj

  • Resolution set to invalid
  • Status changed from new to closed

It is well known that Hindley-Milner type inference has worst-case exponential time and space, and I think this is one such example. Remember that GHC "fills in" the missing type arguments. So if you write

  id True

GHC translates it to

  id @Bool True

because we are instantiating id's type with Bool. Even compilers that don't genreate the elaborated program do something internally in the type inference engine that is more or less the same thing.

Now consider your example, with the type arguments filled in.

id id True
==> id @(Bool -> Bool) (id @Bool) True

id id id True
==> id @((Bool->Bool) -> (Bool->Bool)) (id @(Bool -> Bool)) (id @Bool) True
...and so on

You can see that the types get big fast. As you add each new id the size of the type doubles; hence the exponential.

Happily type inference is usually fine in practice. But its worst case is Bad.

Simon

comment:3 Changed 2 years ago by maeder

hugs (September 2006) answers this instantly!

Note: See TracTickets for help on using tickets.