6 ms·
Non-terminating compilation in Java
- lurker17 15y agoLooks like it terminated.
- spectre 15y agowhile the compilation does technically terminate it is doing so with a StackOverflowError which along with the resulting stack-trace most likely indicates a non-terminating recursion. It only terminates due to a finite limit on the size of the stack.
- gujk 15y agoStack depth limits avoid some non-termination by changing them into crashes. It is still a failure, of course, but a bit different and generally less troublesome than say, a tailcall eliminating recursion that actually spins for hours until a human notices and interrupts it.
- andrewflnr 15y agoThe Turing machine we're interested in didn't terminate. It got a stick stuck in it by the outer Turing machine. :)
- cgag 15y agoMy understanding of java generics is pretty weak, could someone break this down?
- dekz 15y agoEssentially a cyclic reference between an interface and a class exploited with generics.
- kodablah 15y agoHappens w/ JDT in Eclipse too. Just paste it in a Java file and watch the incremental compiler break.
- DrJokepu 15y agoWhile I would never miss a chance to bash Java, it really looks like it's just a bug in the compiler. The input that triggers it is definitely not code that you see in production every day. I'm sure that it will be fixed eventually.
- deleted 15y ago[deleted]
- kmm 15y agoThis looks like a self-referential issue. If anything, it's a bug in mathematics.
- dill_day 15y agoSee also: Taming Wildcards in Java's Type System http://cseweb.ucsd.edu/~rtate/publications/tamewild/tamewild-tate-pldi11.pdf http://cseweb.ucsd.edu/~rtate/publications/tamewild/tamewild... (Section 3 Non-Termination in Subtyping)
- dodedo 15y agoHere's a non-terminating compilation in Perl: perl -wle'BEGIN {1 while 1}' Heh.
- pyre 15y agoI'm confused. How does the begin block execute prior to compilation?
- skimbrel 15y agoBegin blocks execute during compilation, immediately after they've been parsed. They're compiled themselves, and execute within the Perl interpreter before it finishes compiling the rest of the containing module. So they don't really execute prior to all compilation, but they execute prior to the compilation of anything sequentially after them in the source.
- ars 15y agoSo that isn't really non-terminating compilation, but rather non-terminating execution?
- ekiru 15y agoIt's non-terminating execution during compilation, similar to the example elsewhere in the comments using nonterminating macro definitions in Common Lisp. A compilation process that involves executing and waiting for the termination of a program that doesn't terminate can't itself terminate.
- dodedo 15y agoA non-terminating compilation is a non-terminating execution.
- pyre 15y agoI don't consider this to be 'true' non-terminating compilation then. Interesting cases to me would be ones where the syntax itself throws the compiler into an infinite loop, not one where you explicitly tell the compiler to execute an infinite loop.
- trurl 15y agoFor what it is worth, the equivalent Scala code is trait Pong[T] {} class Ping[T] extends Pong[Pong[X forSome { type X >: Ping[Ping[T]]}]] { def Ping() { val Ping : Pong[X forSome { type X >: Ping[Long]}] = new Ping[Long](); } } which produces the errors Test.scala:3: error: illegal cyclic reference involving class Ping class Ping[T] extends Pong[Pong[X forSome { type X >: Ping[Ping[T]]}]] { ^ Test.scala:5: error: type mismatch; found : Ping[Long] required: Pong[X forSome { type X >: Ping[Long] }] Note: Long <: X forSome { type X >: Ping[Long] }, but trait Pong is invariant in type T. You may wish to define T as +T instead. (SLS 4.5) val Ping : Pong[X forSome { type X >: Ping[Long]}] = new Ping[Long]();
- trurl 15y agoHowever, if you set the symbol locking depth larger (-Yrecursion n) you'll also get a stack overflow as well. So it isn't necessarily that Scala has an algorithmically better approach to subtyping. The symbol locking algorithm is more of a catchall...
- rayiner 15y agoNon-terminating compilation in Common Lisp: (defmacro get-stuck (x) (labels ((infinite () (infinite))) (infinite) x)) (get-stuck 3)
- ced 15y ago#.(loop)
- calibraxis 15y agoLess likely to terminate. (Like if you happen to use a Common Lisp implementation which doesn't optimize tail calls, heavy recursion can signal an error. Which some people consider a good thing, signaling they may have a bug rather than merely a long-running computation.)
- derleth 15y agoAnd you can do precisely the same thing in C++ if you're willing to write somewhat non-trivial template code. This kind of thing is more surprising to Java programmers, I daresay, because the idea compiling a program being Turing-complete is not covered in most Java programming courses. (Problems are Turing-complete; languages are Turing-equivalent, if you ignore the fact the Universe is finite.)
- danieldk 15y agoSomething like this? https://gist.github.com/1388217 https://gist.github.com/1388217 Crashes clang, reaches maximal template depth in g++. Seems there is no tail call optimization for templates ;).
- exDM69 15y ago"And you can do precisely the same thing in C++ if you're willing to write somewhat non-trivial template code." The template code required to cause non-termination in template instantiation is a very trivial infinite loop. Simple metaprogramming with templates is not very hard, it's kind of like doing lisp with template parameters. Variadic templates (in c++11) make this a whole lot simpler.
- lell 15y agoAnyone have a non-terminating C compile? (Other than X11. I compiled that from scratch back in ancient times and it took a whole day. At least it seemed like it wasn't going to terminate.)
- machrider 15y agoC doesn't support metaprogramming, unless you count the preprocessor language. With the preprocessor, you could have a couple files mutually #include each other...
- ars 15y agoI tried it: error: #include nested too deeply
- malkia 15y agostruct cthulhu { char b[1024 * 1024 * 1024]; const char* name; } F = { {0}, "cthulhu" };
- lell 15y agoIndeed, this crashed my gcc. How does it work? If I had enough memory would it terminate? looks like it.
- malkia 15y agoBecause the structure is initialized, the compiler has to lay it out in memory, and fill out the fields. If it was left uninitialized, it would've simply reserve space for it, but won't allocate anything in memory (compiler memory), and then the linker is just going to increase the BSS section (uninitialized data) with it's size. Later the program may or may not run. Some systems might allow many gigabytes of uninitialized data. Others simply won't.
- finnw 15y agoLooks like a missing "occurs check." http://en.wikipedia.org/wiki/Occurs_check http://en.wikipedia.org/wiki/Occurs_check If so, it should be a relatively easy fix.
- DanielRibeiro 15y agoActually seems to be a bit more involved: according to the submitter[1] Java is trying to prove something that is undecidable on Java's current type system. To solve it you'd have to make it stricter. [1] http://www.reddit.com/r/programming/comments/mlbna/scala_feels_like_ejb_2/c31zdbd http://www.reddit.com/r/programming/comments/mlbna/scala_fee...
- exDM69 15y agoUnfortunately, adding an occurs check here is not the right way to go. The possibility of an infinite loop is there for a reason (to make the generics more expressive) and adding an occurs check will make the language less expressive. I don't see a problem with non-terminating compilation. It makes sense to add more power to the compiler, but it comes at a cost. The possibility of non-termination is not a huge price to pay for it. In practice, the recursion will never go very deep so a simple max recursion depth check is enough to keep the compiler from hogging cpu and memory.
- malkia 15y ago// Windows #include "aux" #include "con" // And off course #include __FILE__
- kamkha 15y agoHere's a block of code that will cause most versions of the Java compiler to hang that doesn't use loops or templates: class compilehang { public static void main(String[] args) { double d = 2.2250738585072012e-308; System.out.println("Value: " + d); } } From http://www.exploringbinary.com/a-closer-look-at-the-java-2-2250738585072012e-308-bug/ http://www.exploringbinary.com/a-closer-look-at-the-java-2-2...: apparently the constant in the code above causes Java's double value correction loop to oscillate between two values, thus causing the compiler to hang.
- michaelfeathers 15y agoWell deserved.