Non-terminating compilation in Java | Hacker News Reader

Non-terminating compilation in Java

gist.github.com

84 pointsDanielRibeiro43 comments

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

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

Non-terminating compilation in Common Lisp:

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

  #.(loop)

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

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

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

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

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

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

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

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

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

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

I tried it:

    error: #include nested too deeply

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

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

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

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

If so, it should be a relatively easy fix.

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

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.

Looks like it terminated.

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.

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.

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

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.

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

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

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

Well deserved.

Here's a non-terminating compilation in Perl:

perl -wle'BEGIN {1 while 1}'

Heh.

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

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.

So that isn't really non-terminating compilation, but rather non-terminating execution?

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

A non-terminating compilation is a non-terminating execution.

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

"the syntax" and "where you explicitly tell the compiler" are the exact same thing. Syntax is, fundamentally, instructions to the compiler.

Some languages don't contain instructions that can instruct the compiler to loop or recurse (C, assembly, brainfuck). Some languages contain a sub-language or meta-language which can instruct the compiler to recurse (java, C++). Some languages use their native syntax to instruct the compiler, making looping or recursion trivial (Perl, Lisp).

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.

// Windows

#include "aux"

#include "con"

// And off course

#include __FILE__

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.

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

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

I heard the next release will fix that.

With the myriad unprovable universe theories (GUT) that are coming out anything is possible :)

Reply on news.ycombinator.com