3 ms·

Fascinating behavior. Since this is an edge, would it ever occur in human-written code? Could there be a situation where a computer would end up generating such

• spacemanaki 12y ago
  It's unlikely to occur as the type is exponential in size and thus quite unwieldy to do anything with! I haven't worked with generated ML or Haskell code, but I still think it's unlikely to be an issue in "real" code.
  • nostrademons 12y ago
    It's rarely a compile-time performance issue because O(2^N) algorithms perform well on modern hardware when N ~= 3. You could nest the `double` example from the article 6 times and it would still only be a 64x slowdown. Where it does show up, annoyingly, is in error messages. You actually see this all the time with GCC's STL error messages (C++ templates provide a parameterized type system very similar to Haskell or ML, but without the inference, at least until C++11). STL containers are usually parameterized not only over the key and value, but over the comparator and allocator. Nest a couple of them and you suddenly have a type with several dozen variables. GCC expands the whole type out, without typedefs, when printing error messages, which means that you will sometimes get compile errors that are 10 pages long. Clang fixes this by preserving the typedefs, without which you wouldn't want to write such a type. Haskell has the same problem, except worse because it infers types, but GHC has gone to great pains to format error messages so they are at least readable if verbose.
  • ubernostrum 12y ago
    XML/SGML people know this sort of thing (exponential resource use due to expanding references) as the "billion laughs" attack. There are real-world consequences to this sort of stuff.
• rwmj 12y ago
  I've written a lot of OCaml code and I don't recall having the compiler blow up on hand-written code. The OCaml type inference engine works well except on objects where you sometimes need to annotate variables to tell it what object type it is. (But then we rarely use OO in OCaml). It's a different matter with generated code. For a while I had a program that generated OCaml code (from descriptions of Linux kernel structs). That would result in 100000+ line generated OCaml programs which frequently caused very long compile times (eg 20 minutes and more), with the time being spent in the type inference part of the compiler.
• lmm 12y ago
  I've had this kind of thing happen when I try to use dependent types in Scala. E.g. if you want to select a HList sublist out of another HList (using the types) then that's quadratic, because just figuring out that a HList contains a particular type takes linear time. (The idea was to do DI using HLists, to get something like Spring but that worked at compile time. It worked, but as the program got larger the compile times became too long for it to be practical)
• freyrs3 12y ago
  No, HM algorithm has terrible worst case complexity, but the worst cases don't correspond to programs humans write and generally it works perfectly in practice.
  • seanmcdirmid 12y ago
    Humans tend to surprise in what they wind up writing. All HM has to do is fail 5% of the time to be very annoying.
    • rwosync 12y ago
      In my experience the failure rate is far below 5% for vanilla HM algorithm. I've never seem a pathological input in the wild that wasn't contrived specifically to test the typechecker.
  • ufo 12y ago
    IIRC, the algorithm used by the ocaml implementation is guaranteed to be close to linear time as long as you dont have this sort of nested polymorphic lets.