Java Generics Are Turing Complete

The Java culture fetishizes code generation. It's like somebody decreed "We want to take over the world, and one measure of that is lines of code. So there should be a hell of a lot more Java code: start writing Java code that generates more Java code!"

C++ is a spectacularly bad example, it's not always like that.

> * easy and standard way of doing the most often used things (like replacing type identifier with another)

I think you're talking about a conventional type system, or something close to it.

> I mean, if you've ever seen errors that C++ compilers gurgle out from heavily templated code, I don't imagine macro library being any worse off a priori. Basically, when the compiler puts out a 3 screen error message, it's almost always much faster to just eye which lines it's referring to and read the code, than trying to decipher what the error message is actually trying to say...

Honestly I think the biggest problem with macros is the compiler/tooling side - if you allow compilation to just run arbitrary code that does whatever, there's no structure for the tools to make use of.

I would agree that compilers need to make error handling a lot more first-class and offer good support for that kind of use case. Rust is a positive example, with a lot of emphasis on good compiler errors - needed because they know how hard it is to satisfy their borrow checker. It would be great to apply that same level of support to errors from custom code (and really there's no reason Rust-style ARM couldn't be ordinary library functions in a language with good high-level constructs - you can use monadic regions to express the same behaviour).

>I believe that type checking in unextended Hindley-Milner type systems is exponential

Yes it recursively solves for function typing parameters though the call graph. This isn't guaranteed to exit.

If the language you are using annotates function argument's with types[1] then this behavior is avoided and Hindly-Milner becomes effectively linear. This is why type-inference is starting to become a common feature in most languages.

[1] Nearly every language does this, but inline clojure are sometimes type inferred. Depends on language/language family.

"the compiler might get yell at you when you hit the maximum allowed type recursion limit" is an example of the compiler failing to compile something which is valid in the type system.

We don't yet have a lot of solid empirical evidence, sure - mostly because we don't have a good measure of productivity. But the fact that we can't measure it well doesn't mean it doesn't exist. There is a fact of the matter to be found, it's more than just personal preference.

> And the "FUD" is nothing more than the very real reality that many teams find those language far too clever for their taste.

I've heard people literally say "we shouldn't use Scala because its type system is Turing complete" (in an organization that was already using Java). I call that FUD.

I believe the intent is that it is not a very informative bar to cross. Consider that Conway's Game of Life is Turing complete. Doesn't really increase the usage of it for solving problems.

Basically, the expressiveness of a language is unrelated to it being Turing complete. And is much more relevant for most conversations.

Basically all you need for turing completeness is the ability to jump/branch/ignore-some-bits on some criteria see SUBLEQ or cyclical tag systems or XY combinators.

it's actually very hard to avoid in a system that is supposed to do some sort of computation.

It's a low bar in that it's easy to achieve. So easy that it's often done by accident, as is the case here and in many other cases (C++ templates are another example). It often takes more work to define a useful language not to be Turing complete.

Plenty of languages today have Turing complete type systems. I believe even Haskell with GHC extensions is.

It very much is necessary. Take the linux kernel's eBPF interpreter for example. Since the code runs in kernel scope and in many critical places (system call interception, network processing) it's important that the code executes within a bounded amount of time.

I think its restrictions are that it only allows forward jumps and a limited amount of instructions.

I agree that it is not necessary in practice, no, and it is of limited theoretical use because a halting algorithm might still take ten years to do so.

However, Turing-incomplete sublanguages can be very helpful in practice, for the same reason that a `for` loop is very helpful even though it is not essential and we can solve all of our problems with `goto` which is ultimately what our compilers generate anyway. Why do most people prefer `for` to `goto`? because with the former, you pick up a writer's discipline which makes it harder to create infinite loops and to accidentally miss parts of the data structure.

Well, in any Turing-incomplete subset, it is impossible to make an infinite loop and usually very hard to miss parts of the data structure (since there is usually only a few ways to enter that data structure that the computer can prove won't halt) -- and, if you want, you can build tooling which checks your algorithms to guarantee these things. It guarantees that even any recursive handling you do with the data structure is not going to be infinite.

With that said, there are some examples of perfectly valid algorithms which don't nicely support that sort of structural recursion, e.g. if you can "jump down" to a much smaller (and sometimes hardly-related) data structure rather than incrementally descending into it. A great example of this is the GCD algorithm,

    function gcd(x, y) {
        if (y < x) {
            return gcd(y, x);
        }
        return x == 0 ? y : gcd(y % x, x);
    }

We can easily prove that this halts for positive integers by simply looking at the second parameter; each recursive call makes it strictly closer to 0, which means that it must hit 0 and stop recursing. But a Turing-incomplete subset would probably balk at both of the recursive calls, if, say, we tried to encode integers as lists of booleans to get a "binary"-ish representation: it will say "hey, you can't recurse on gcd(y, x) or gcd(y % x, x), because you're supposed to be going in gcd(x, y) from x to a substructure of x, but y and y % x are not substructures of x!"

You might be able to do it by encoding everything as a list of nulls and then first invoking some sort of decrement-increment step to swap x and y, then doing something similar for the modulus, but it means that your runtime might be something like min(x, y) * max(x, y) or something -- ugly.

Last week wanted to use GSON in a generic method to deserialize to a type which is generic type parameter, in a method of the abstract base class. Unfortunately it could not be done without the implementations passing up their .class via super constructor.

IMHO deserializing JSON is quite a common application code.

If you are really interrested I'd create example code, but (as being lazy, and the mentioned code not being my property) I'd hope to take my word for granted :)

edit: I wrote useless in many cases!

> I guess it's one thing to claim Java generics have problems and another to claim they are "useless".

I guess that's why the original comment said useless in many cases. Not completely useless. The next sentence also said they are way better than no generics.

In C# you can often avoid reflection using dynamic.

Java generics problems: "primitive types" cannot be used as type parameters. Type erasure makes type parameters unavailable at runtime, which sometimes causes many problems.

When you see java code passing a .class as a constructor/method parameter, that is often a workaround.

Try Stream.toArray(). Type erasure makes it a pain and forces you to provide an array Supplier.

Other Example: you cannot have overloads of a method one taking Function<T,U>, other taking Supplier<T> because their erased signatures are equivalent.

Disclaimer: I still prefer Java when C# is not an option, yet I reserve the right to criticize its shortcomings.

The most common annoyance is along these lines:

interface List<T> { T[] toArray(T[] item); }

You need to pass in a T[] because arrays keep their types at runtime but the generics don't.

Out of curiosity, what would you say is missing? My one big beef with templates is lack of constraints and somewhat ugly syntax, but hopefully concepts will remedy the former.

For me, it's mainly that you know the runtime type of the type parameter, so you can do things like new T() in your generic class.

Unboxed values; this primarily affects performance, particularly memory performance, but with a sufficiently smart compiler could be worked around. It's unlikely any very clever JVM optimizations would see wins here though, as the assumption that everything is boxed is idiomatic.

Having a type argument available; as adevine mentions, performing type-level things rather than just instance-level things. A smarter language than Java could handle this with hidden arguments, or passing along a dispatch table for type-specific actions when constructing a generic type. Things get trickier when you're e.g. storing a reference to a static generic method.

In reality, there's a continuum between C++-style generics-as-parameterized-syntax-trees and Java's generics-as-ignorable-type-checker-façade. Going full C++ isn't what you want; the error messages on failure to instantiate are unpleasant. Going full Java leaves you with a few holes. C# is probably a small bit too far in the C++ direction - instantiations can add up, despite .NET reusing instantiations where the type arguments are object references (that is, the CLR will effectively erase types if your type arguments are reference types, but you can't observe this without escaping the type system).

You can now use lambdas as generic type references http://benjiweber.co.uk/blog/2015/08/04/lambda-type-referenc...

Is there a reason to take a look at Gosu instead of Kotlin?