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