Non-terminating compilation in Java

[trurl]

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

[trurl]

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]

Non-terminating compilation in Common Lisp:

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

[ced]

  #.(loop)

[yxhuvud]

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

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

[derleth]

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

[dill_day]

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

[lell]

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]

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

[malkia]

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

[finnw]

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

If so, it should be a relatively easy fix.

[DanielRibeiro]

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

[exDM69]

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.

[lurker17]

Looks like it terminated.

[andrewflnr]

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

[spectre]

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.

[kamkha]

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.

[cgag]

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

[dekz]

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

[kodablah]

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

[michaelfeathers]

Well deserved.

[dodedo]

Here's a non-terminating compilation in Perl:

perl -wle'BEGIN {1 while 1}'

Heh.

[pyre]

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

[malkia]

// Windows

#include "aux"

#include "con"

// And off course

#include __FILE__

[DrJokepu]

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]

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