Non-terminating compilation in Java

https://gist.github.com/1387113

by DanielRibeiro • 15 years ago

84 43 15 years ago

gist.github.com

lurker17• 15 years ago

Looks like it terminated.

spectre• 15 years ago

while 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• 15 years ago

Stack 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• 15 years ago

The Turing machine we're interested in didn't terminate. It got a stick stuck in it by the outer Turing machine. :)

cgag• 15 years ago

My understanding of java generics is pretty weak, could someone break this down?

dekz• 15 years ago

Essentially a cyclic reference between an interface and a class exploited with generics.

kodablah• 15 years ago

Happens w/ JDT in Eclipse too. Just paste it in a Java file and watch the incremental compiler break.

DrJokepu• 15 years ago

While 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.

kmm• 15 years ago

This looks like a self-referential issue. If anything, it's a bug in mathematics.

skrebbel• 15 years ago

> If anything, it's a bug in mathematics.

I heard the next release will fix that.

dill_day• 15 years ago

See also: Taming Wildcards in Java's Type System http://cseweb.ucsd.edu/~rtate/publications/tamewild/tamewild... (Section 3 Non-Termination in Subtyping)

trurl2• 15 years ago

For 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]();

trurl2• 15 years ago

However, 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• 15 years ago

Non-terminating compilation in Common Lisp:

    (defmacro get-stuck (x) 
        (labels ((infinite () (infinite))) 
            (infinite) x))
    (get-stuck 3)

ced• 15 years ago

  #.(loop)

calibraxis• 15 years ago

Less 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• 15 years ago

And 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.)

microtonal• 15 years ago

Something like this?

https://gist.github.com/1388217

Crashes clang, reaches maximal template depth in g++. Seems there is no tail call optimization for templates ;).

exDM692• 15 years 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.

philbarr• 15 years ago

You're suggesting that Turing-completeness of compilers IS covered in most C++ programming courses? I doubt it.

yxhuvud• 15 years ago

At least the parsing is simple, as opposed to some other languages...

http://www.perlmonks.org/?node_id=663393

lell2• 15 years ago

Anyone 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• 15 years ago

C doesn't support metaprogramming, unless you count the preprocessor language. With the preprocessor, you could have a couple files mutually #include each other...

ars2• 15 years ago

I tried it:

    error: #include nested too deeply

malkia3• 15 years ago

struct cthulhu { char b[1024 * 1024 * 1024]; const char* name; } F = { {0}, "cthulhu" };

lell2• 15 years ago

Indeed, this crashed my gcc. How does it work? If I had enough memory would it terminate? looks like it.

dodedo4• 15 years ago

Here's a non-terminating compilation in Perl:

perl -wle'BEGIN {1 while 1}'

Heh.

pyre2• 15 years ago

I'm confused. How does the begin block execute prior to compilation?

skimbrel• 15 years ago

Begin 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.

dodedo4• 15 years ago

Perl is a dynamic language and can execute Perl during compilation. Some languages such as C++ allow metaprogramming via templates or other special compile-time meta-language constructs. Perl simply allows metaprogramming via Perl.

From the reception to my comment it seems HN readers aren't very familiar with dynamic languages. Perhaps I invited those subject to dunning-kruger by providing an overly simplified example.

finnw• 15 years ago

Looks like a missing "occurs check." http://en.wikipedia.org/wiki/Occurs_check

If so, it should be a relatively easy fix.

DanielRibeiro• 15 years ago

Actually 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_fee...

exDM692• 15 years ago

Unfortunately, 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.

malkia3• 15 years ago

// Windows

#include "aux"

#include "con"

// And off course

#include __FILE__

kamkha• 15 years ago

Here'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-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• 15 years ago

Well deserved.

Non-terminating compilation in Java

Related Stories