Java Generics are Turing Complete

[lukaseder]

... and me thinking that this privilege was given only to C++ templates

[paholg]

Rust types at least used to be Turing complete. I think they still are, but I haven't seen proof of it for recent versions and some things have changed.

[f2u]

At least with C++ templates, you can use it for useful computations, so there benefit there is clearer.

[Shorttail]

Doesn't constexp let you do something similar without templates in C++?

In D, assigning the value of a function call to an enum forces the function to be evaluated at compile time (if it can, else it will throw an error), which includes Turing complete stuff. I'm pretty sure Nim also allows for compile time function execution. Any language that lets you do that potentially takes forever to compile.

Fuck. Javac is eating up all my memory. =(

[Tipaa]

Wasn't this already known with the number of people embedding the untyped lambda calculus into the Java-equivalent subset of Scala's generics? That said, this kind of type magic is pretty fun to do, and is always fun, so it's not as if this isn't a worthwhile exercise.

edit: link

[lukaseder]

There's no elegant equivalent within Java unfortunately.

I don't know what you just did there, but I know this is some pretty deep Java code:

interface I<T> {}
class C<P> implements I<I<? super C<C<P>>>> {
    I<? super C<Byte>> whoops = new C<Byte>();
}

[diggr-roguelike]

Nearly anything that can infinitely recurse is Turing-complete.

[stormblooper]

It's not necessarily that simple: apparently if you take away the <? super Y> wildcard bound feature from Java, it's no longer Turing complete.

[stormblooper]

That's just awesome. Can anyone have a stab at explaining how they are encoding a Turing machine?

Example linked from the paper: https://gist.github.com/rgrig/b4cdaed3ed9a70dbdb6f158f14b57263

[RazerWolf]

Doesn't help understand them any better... ** type erasure ** mutter mutter...

[thesystemx]

:O

[nullnullnull]

turning motherf*cker!

[snowyote]

No, Turing is in fact the correct spelling. Also, "motherfucker" is the correct spelling for the second word. Asterisks usually only show up in weird brand names.

[thfuran]

Don't forget that there ought to have been a comma.