3 ms·

Genuine question: How do type system that are so abstract and complex to become turing complete help? I definitely find it extremely helpful to be able to wri

Genuine question: How do type system that are so abstract and complex to become turing complete help? I definitely find it extremely helpful to be able to write containers of any type (like std::vector<T>), that saves a ton of code duplication, but beyond that what more is needed and why? What we're competing with here is: just write a function that operates on the data types you want and gets the job done. You're writing code for the CPU that has to actually do something, on actual known types. What programming task is simplified by having an "any" type or a type system that allows you to write pong-played-turn-by-turn-using-compiler-error-messages? It's cool that you can have an "any" type just like universal sets in set theory, but what real-life programming scenario does this simplify (you can already write containers that can contain anything you want without using such as thing as an "any" type)? At least not the kind of programming tasks I do, but admittely I think fairly low level and prefer my types to have exact known amounts of bits, known signed integer convention and endianness so I can efficiently use shifts and get the bits I need, preferably with as little undefined behavior as possible. Asked differently: If one were to design a programming language that only has basic types (primitives, structs/classes, ...) and templates to allow functions/classes to operate on any type (but not more than that; substitute template type with the actual type, compile this, nothing more), what feature will users of the language be missing and complain about?

gpderetta 3y ago
> You're writing code for the CPU that has to actually do something, on actual known types. (Partial) specialization, which is a feature used to get templates to do actual something on actual types is what principally allows templates to be turing complete.
widdershins 3y ago
It's about when you want to enable optimisations or conveniences depending on the parameterized type. For example, in the std::vector<T> type, if T supports being moved, you want to use that when growing your vector for performance. If T doesn't support being moved, you will have to copy it instead. Boom: you've ended up with template metaprogramming.
munificent 3y ago
> Asked differently: If one were to design a programming language that only has basic types (primitives, structs/classes, ...) and templates to allow functions/classes to operate on any type (but not more than that; substitute template type with the actual type, compile this, nothing more), what feature will users of the language be missing and complain about? This is a really good question. There are some languages that work as you describe: SML and some others in that family. There are generic functions and types, but the type parameters are basically just placeholders. You can't do anything with a value whose type is a type parameter, except store it and pass it to things that also take type parameters. That gives you enough to write a nice reusable vector type. But it doesn't let you easily write a nice reusable hash table. You can, but users have to pass in an explicit hash function that accepts the key type every time they create a hash table. It might be nice if a type itself could indicate whether it's hashable and, if so, what it's hash function is. Then, if you create a hash table with that key type, it automatically uses the hash function defined by that type. Now you need some sort of constraints or type bounds in your generics. That's what traits in Rust and bounds in Java and C# give you. (The literature calls it "bounded quantification".) It's a big jump in complexity. But it does mean that now you can call functions/methods on arguments/receivers whose type is a type parameter, and those calls can be type checked. Bounds are themselves types, so what kinds of types can you use in bounds? Can they be generic? If so, what kinds of type arguments are allowed? Can you use type parameters from the surrounding type? For example, which of these are OK and which aren't (using Java-ish syntax): class A<T extends Foo> {} // 1. class A<T extends Bar<Foo>> {} // 2. class B<T extends B<Foo>> {} // 3. class B<T extends Bar<T>> {} // 4. class B<T extends B<T>> {} // 5. Any kind of bounded quantification will give you 1-3. What about 4 and 5? This is called "F-bounded quantification". Why would you want such a thing? Collections with fast look-up are important, which is why we extended our generics to enable us to write nice reusable hash tables. But some data types aren't easily hashed but can be easily ordered. A sorted collection is faster than an unsorted one. How would we write a generic sorted collection? We could require you to always explicitly pass in an ordering function for any given element type, but it would be nice if the element type itself could supply is order function. You could define a "Comparable" interface that a type can implement to support comparing an instance against another object of some type, like: interface Comparable<T> { int compareTo(T other); } And then implement it on your type, like: class Color implements Comparable<Color> { int r, g, b; int compareTo(Color other) => ... } In our sorted collection, elements all have the same type, so the bound that we need looks like: class SortedCollection<T extends Comparable<T>> { ... } Notice that we have "T" inside the bound. That's F-bounded quantification. Using type parameters inside a bound isn't the only place recursive types like this show up. Let's say you wanted to make a generic type comparable. You'd do something like: class Pair<T> implements Comparable<Pair<T>> { T a, b; int compareTo(Pair<T> other) => ... } Now here, the implements clause is using not just the type parameter of the enclosing type, but the entire type. We had a couple of fairly modest goals: * Be able to create reusable hash tables where the hash function is inferred from the key type. * Be able to create reusable sorted collections where the comparison function is inferred from the element type. And in order to get there, we needed generics, bounds, and even F-bounded quantification. Adding even a little more usefulness to our collection types will quickly have us reaching for variance annotations, associated types, and even more exotic stuff.

gpderetta 3y ago

> You're writing code for the CPU that has to actually do something, on actual known types. (Partial) specialization, which is a feature used to get templates to do actual something on actual types is what principally allows templates to be turing complete.

widdershins 3y ago

It's about when you want to enable optimisations or conveniences depending on the parameterized type. For example, in the std::vector<T> type, if T supports being moved, you want to use that when growing your vector for performance. If T doesn't support being moved, you will have to copy it instead. Boom: you've ended up with template metaprogramming.

munificent 3y ago

> Asked differently: If one were to design a programming language that only has basic types (primitives, structs/classes, ...) and templates to allow functions/classes to operate on any type (but not more than that; substitute template type with the actual type, compile this, nothing more), what feature will users of the language be missing and complain about? This is a really good question. There are some languages that work as you describe: SML and some others in that family. There are generic functions and types, but the type parameters are basically just placeholders. You can't do anything with a value whose type is a type parameter, except store it and pass it to things that also take type parameters. That gives you enough to write a nice reusable vector type. But it doesn't let you easily write a nice reusable hash table. You can, but users have to pass in an explicit hash function that accepts the key type every time they create a hash table. It might be nice if a type itself could indicate whether it's hashable and, if so, what it's hash function is. Then, if you create a hash table with that key type, it automatically uses the hash function defined by that type. Now you need some sort of constraints or type bounds in your generics. That's what traits in Rust and bounds in Java and C# give you. (The literature calls it "bounded quantification".) It's a big jump in complexity. But it does mean that now you can call functions/methods on arguments/receivers whose type is a type parameter, and those calls can be type checked. Bounds are themselves types, so what kinds of types can you use in bounds? Can they be generic? If so, what kinds of type arguments are allowed? Can you use type parameters from the surrounding type? For example, which of these are OK and which aren't (using Java-ish syntax): class A<T extends Foo> {} // 1. class A<T extends Bar<Foo>> {} // 2. class B<T extends B<Foo>> {} // 3. class B<T extends Bar<T>> {} // 4. class B<T extends B<T>> {} // 5. Any kind of bounded quantification will give you 1-3. What about 4 and 5? This is called "F-bounded quantification". Why would you want such a thing? Collections with fast look-up are important, which is why we extended our generics to enable us to write nice reusable hash tables. But some data types aren't easily hashed but can be easily ordered. A sorted collection is faster than an unsorted one. How would we write a generic sorted collection? We could require you to always explicitly pass in an ordering function for any given element type, but it would be nice if the element type itself could supply is order function. You could define a "Comparable" interface that a type can implement to support comparing an instance against another object of some type, like: interface Comparable<T> { int compareTo(T other); } And then implement it on your type, like: class Color implements Comparable<Color> { int r, g, b; int compareTo(Color other) => ... } In our sorted collection, elements all have the same type, so the bound that we need looks like: class SortedCollection<T extends Comparable<T>> { ... } Notice that we have "T" inside the bound. That's F-bounded quantification. Using type parameters inside a bound isn't the only place recursive types like this show up. Let's say you wanted to make a generic type comparable. You'd do something like: class Pair<T> implements Comparable<Pair<T>> { T a, b; int compareTo(Pair<T> other) => ... } Now here, the implements clause is using not just the type parameter of the enclosing type, but the entire type. We had a couple of fairly modest goals: * Be able to create reusable hash tables where the hash function is inferred from the key type. * Be able to create reusable sorted collections where the comparison function is inferred from the element type. And in order to get there, we needed generics, bounds, and even F-bounded quantification. Adding even a little more usefulness to our collection types will quickly have us reaching for variance annotations, associated types, and even more exotic stuff.