3 ms·
Virtually any compiled programming language has had an infinite-loop bug in the compiler at some point or other. E.g. Java has a notoriously simplistic type sys
by lmm 7y ago
Virtually any compiled programming language has had an infinite-loop bug in the compiler at some point or other. E.g. Java has a notoriously simplistic type system, but still had a famous case.
Typing an ML-like language is technically exponential in the length of the program, but really the way to look at it is that it's exponential in the depth of the most deeply nested block (for certain kinds of block). There's a certain symmetry with how program runtime is naturally exponential in the depth of the most deeply nested loop - and, in the same way, while deeply nested blocks are possible, they're generally bad code.
I've hit troublesome compile times in Scala a couple of times. One of them was due to a naively implemented type-level intersection operation and lead me to abandon that project (I was trying to write a compile-time dependency injection framework, so you'd have a set of types representing what you had already instantiated and a set of types representing what each service needed to instantiate itself, so you could only add a service if you already had all of its dependencies available. But it was all using linear search, since types (in Scala) are not hashable as far as I know, and even if they were, I don't know that I'm up to implementing a hashtable using type-level programming).