Java Generics Are Turing Complete

[chvid]

In practice in means if you write stuff like this:

   interface Z {}
   interface N<x> {}
   interface L<x> {}
   interface Qlr<x> {}
   interface Qrl<x> {}
   interface E<x> extends
     Qlr<N<?super Qr<?super E<?super E<?super x>>>>>,
     Qrl<N<?super Ql<?super E<?super E<?super x>>>>> {}
   interface Ql<x> extends
     L<N<?super Ql<?super L<?super N<?super x>>>>>,
     E<Qlr<?super N<?super x>>> {}
   interface Qr<x> extends
     L<N<?super Qr<?super L<?super N<?super x>>>>>,
     E<Qrl<?super N<?super x>>> {}
   class Main {
       L<?super N<?super
       L<?super N<?super
       L<?super N<?super
       E<?super E<?super Z>>>>>>>>
     doit(
       Qr<? super E<? super E<? super Z>>> v
   ){
   return v;
   } }

You can make your compiler:

1. Bark out an odd error. (Loop for a while and then stop due to an internal stack overflow.)

2. Compile something that gives a runtime type error.

[Faint]

DING! This is what always happens. If you want to get useful manipulations done to code you'll eventually creep up to a Turing complete system. Now you have a type system where you could calculate any program transformation, albeit in really really convoluted, slow and ugly way.

It would have been SO much better to give the language proper macros to begin with. I mean, a library that's actually meant for doing AST manipulations, and a way to tell the compiler "apply this transformation to that code before doing anything else with it", instead of another compiler-only interpreted language inside the original language. People would not have to learn 2 different syntaxes, and compilation would probably be faster (well I'm thinking more of heavily templating dependant C++ libraries here).

[lmm]

I very much disagree. Even if they've ended up accidentally Turing complete (which, don't get me wrong, is bad), they at least guide you towards the right thing to be doing at compile time: simple, declarative transformations. I have never seen a macro system that wasn't immediately abused for unmaintainable clever-clever things, whereas this has only emerged ~10 years after Java introduced generics.

[gpderetta]

AST Macros are useful for AST level manipulation, but the problem is that usually at that point you do not have full type information (name resolution or even type inference hasn't run yet), so they can't take decision depending on types which is sometime what you want.

C++-like templates can be seen as type level macros (or rewrite rules) and run with full type information.

[curried_haskell]

Yo dawg, do you need a programming language inside your programming language?

[cromwellian]

An GWT engineer and former Scala guy, Lex Spoon, proved a similar theorem several years ago when we were upgrading generics for GWT-RPC. The GWT RPC code generator has to reason about return types of methods and which classes could possibly be deserialized say if you return a List of Foo.

Lex showed how to construct the peano arithmetic in Java generics and how to formulate problems such that solving the question of what types could be returned from An Rpc call with List would amount to deciding these small theorems or problems and therefore the GWT SerializationTypeOracleBuilder class would have to solve the halting theorem.

That's probably a wrong paraphrasing and maybe lex will see this and chime in but I think the original discussion was lost forever ironically when Wave, which was built with GWT, was shut down.

[cleeus]

btw, here is the URL for a Java-Generics-Program from the paper: https://gist.github.com/rgrig/b4cdaed3ed9a70dbdb6f158f14b572...

comment from the source:

  // Encodes a Turing machine that counts in binary, and then halts.
  // Gives stack overflow by default.
  // If you increase the stack size (javac -J-Xss100M Main.java),
  // then it type-checks, but it takes a lot of time.

[amelius]

Now the waiting is for the first compiler that compiles to Java Generics.

[brudgers]

So is XSLT: http://www.unidex.com/turing/utm.htm

[vesinisa]

What does this mean in practice? That I can compute an arbitrary algorithm with Java generics? How?

[rntz]

What it means in practice is that any Java typechecker is either (a) incomplete - it will disallow some programs that should typecheck; (b) unsound - it will allow some programs that shouldn't typecheck; or (c) non-total - it will fail to terminate on some programs. (Or some combination of these three.)

[scott_s]

The author answers this question in the Discussion section at the end:

To summarize, Theorem 1 has two practical implications:

1. If one intends to implement a formally verified type checker for Java, it is necessary to choose a subset of the type system that is decidable.

2. If reified generics are added to Java, then one needs to find some solution for not turning instanceof into a security problem.

[lmm]

Yes, that's what it means. I guess read the paper to find out how; another comment linked to https://gist.github.com/rgrig/b4cdaed3ed9a70dbdb6f158f14b572... as an example.

[btilly]

Is there a link to the paper?

Preferably one that you don't have to be at a university to read?

[cwmma]

http://arxiv.org/pdf/1605.05274v1.pdf in the upper right corner of the page

[magnumkarter]

Just click PDF in the right hand corner.

[ngrilly]

The title sounds like a bad news to my ears.

[Avshalom]

Eh, turing complete is a really low bar to clear. In practice it just means the compiler can't be proved to halt on valid code.

Avoiding turing completeness requires either very very careful design OR (trivially) a hard limit on size/iterations the compiler is allowed to make (a sufficiently small limit, obviously we call many things turing complete colloquially that have very low limits anyway like 8-bit cpus with ~kb of memory)

[lmm]

On one level yes. On the other hand it should hopefully reduce the FUD around alternatives with better type systems (Scala), if the type system is turing-complete in any case.

[kodfodrasz]

Too bad they are still pretty much useless in many cases because of type erasure, and many type constraints cannot be expressed (eg. constructor constraints)...

Still way better than no generics at all, but if you are used to better implementations these random limitations can be really painful..

[alimbada]

Don't know why this is being downvoted. I've been on a Java project for the last ~6 months after ~8 years of doing C#/.NET development. My brain hurts from seeing all the stupid workarounds in Java because it doesn't have real generics.

[cel1ne]

Kotlin, which is 100% java-interoperable has much nicer generics (declaration-site variance and type projections instead of wildcards).

https://kotlinlang.org/docs/reference/generics.html

[kailuowang]

I actually think type erasure might even be the right way to implement generics. You see, the point of static types is to provide compilation time check. That is, types are compilation time concern. So yeah, type erasure did introduce some inconvenience but if you need to access them during runtime, either you did it wrong or the compiler fails at some point.

So, claiming type erasure making generic useless is a false argument.

[vvanders]

Or my personal favorite where intrinsic types aren't objects so I can't use them in generics with makes the whole Lambda/Stream api a complete disaster.

Sure, I could use Integer/etc, but now each stage of my transform is creating a ton of garbage and I no longer get data locality.

[bad_user]

You don't need reified generics with a more powerful type system. You might be feeling that C# .NET is better than Java, but it's actually a symptom that C#'s type-system also sucks. Basically whenever you have to do an `instanceof` check, that's a sign that the type system isn't strong enough and hence needs to be solved at runtime.

One such thing missing from .NET for example are higher-kinded types. Basically people end up with the need for `instanceOf` because they aren't able to write generic code that abstracts over containers such as List[T].

And this holds back language development on top of .NET actually. There are good reasons for why alternative languages flourished on top of the JVM and not on top of .NET, in spite of its original marketing, which is a little ironic. Not the only reason mind you, other reasons where availability on Linux, having an easier time to generate bytecode along with debugging symbols, more mature tooling, etc, but having reified generics in the runtime either means that you have to limit your language (e.g. C#'s type-system with a different syntax), or it means that you have to do the type erasure yourself and always have performance problems and be considered a second class citizen. Lack of higher-kinded types is actually what's holding F# back as an FP language, because in FP there is a lot of opportunity to abstract over M[T] types, that are just not doable in a static language without HKT.

And don't get me wrong, I like dynamic typing as well, but the problem with languages like Java and C# are that they are neither here, nor there, in many ways being the worst of both worlds.

And the only advantage that .NET's reified generics have over Java is actually the specialization it is doing for primitives. Which is nice for performance reasons, since you avoid boxing and so on, but doing specialization doesn't necessarily need to be a runtime feature, when it can very well be a feature of the language's compiler. And we weren't talking about performance anyway.

[galdosdi]

Eh, there are hacks around both of those... Gratuitous "typedef classes" for the first problem (instead of using a List<Sandwich> when you want runtime to be able to sniff the type, declare a class/interface SandwichList extends List<Sandwich> and use that) and just wrapping static factory methods around constructors to handle the generic part (to handle the second problem)

Admittedly this is a little annoying, possibly even "really painful" so this doesn't really contradict your view... I don't find it really painful, just a little annoying, but that could be because I haven't used C# or another language people say has better generics so I don't know what I'm missing...

[curried_haskell]

After spending several years programming with Scala and Haskell, doing back to Java feels like being placed in a straightjacket.

[acjohnson55]

Java generics are cumbersome for sure, but if they're useless, it's not because of type erasure. As a Scala programmer, I've very rarely run into a situation where type-erasure has been an inconvenience.

[joegaudet]

Said much more clearly than I could:

http://stackoverflow.com/questions/20918650/what-are-the-ben...

[bitmapbrother]

If it weren't for type erasure we wouldn't have the abundance of dynamic languages on the JVM. Developing dynamic languages on runtimes that have reified generics is a PIA.

[rubenolivares]

whine whine whine. go make a language of your own then, that way it's going to be perfect and have no flaws. oh wait, you wouldn't even know where to start.

[hepta]

You don't need to be a good chef to know a meal is awful. A lot of people use the language (me included) and make it work, doesn't mean it's without fault.

[dang]

We've banned this user for repeatedly violating the HN guidelines.

https://news.ycombinator.com/newsguidelines.html

We detached this subthread from https://news.ycombinator.com/item?id=11777678 and marked it off-topic.