← Back to context

Comment by Merovius

2 days ago

I don't disagree that Go's generics are pretty limited. But I find it a strange complaint, when contrasted with C++ templates. Which, as I understand, are literally not part of the type system and thus there seems to be a far stronger case, that they can not be called generics.

The main difference between Go's generics and C++ templates (and where some of the restrictions come from) is that Go insists that you can type-check both the body of a generic function and the call to it, without one having to know about the other. My understanding is, that with C++ templates (even including concepts), the type checking can only happen at the call-site, because you need to know the actual type arguments used, regardless of what the constraints might say.

And this decision leads to most of the complaints I've heard about C++ generics. The long compile times, the verbose error messages and the hard to debug type-errors.

So, if you prefer C++ templates, that's fair enough. But the limitations are there to address complaints many other people had about C++ templates specifically. And that seems a reasonable decision to me, as well.

12 comments

Merovius

Reply
lenkite  2 days ago

> the type checking can only happen at the call-site, because you need to know the actual type arguments used, regardless of what the constraints might say.

No longer true after C++ 20. When you leverage C++20 concepts in templates, type-checking happens in the template body more precisely and earlier than with unconstrained templates.

In the below, a C++ 20+ compliant compiler tries to verify that T satisfies HasBar<T> during template argument substitution, before trying to instantiate the body

    template<typename T> 
      requires HasBar<T>
    void foo(T t) {
      t.bar();
    }

The error messages when you use concepts are also more precise and helpfully informative - like Rust generics

  • Merovius  2 days ago

    As I said in the other comment, I'm not a C++ user, so I'm relying on cargo-culting and copy-paste. But I think gcc disagrees - otherwise this would not compile, as line 14 is provably invalid: https://godbolt.org/z/P8sWKbEGP

    Or am I grossly holding this wrong?

    • lenkite  2 days ago

      You need to have something that uses those templates. In your godbolt example, add a struct S

          struct S {
      bool M() { return true; }
    };


    int main() {
      S s;
      foo(s); // this now will check foo<S>
    }

      Now you will get compile errors saying that the constraint is not satisfied and that there is no matching function for call to 'bar(S&)' at line 14.

      6 replies →

eru  2 days ago

C++ templates are duck typed at compile time.

Look at Haskell type classes or Rust's traits for some classic examples of how to 'type' your generics. (And compare to what Go and C++ are doing.)

  • lenkite  2 days ago

    > C++ templates are duck typed at compile time.

    This is not really true after C++ 20. C++ templates can leverage concepts that specify compile-time constraints and type checking on template parameters during template argument substitution

  • Merovius  2 days ago

    > C++ templates are duck typed at compile time.

    "Compile time" is not the right distinction. This is about "instantiation time". Go's implementation specifically allows to type-check the body and the call separately. That is, if you import a third-party package and call a generic function, all the type checker needs to look at to prove correctness is the signature of the function. It can ignore the body.

    This is especially relevant, if you call a generic function from a generic function. For C++, proving that such a call is correct is, in general, NP-complete (it directly maps to the SAT problem, you need to prove that every solution to one arbitrary boolean formula satisfies a different boolean formula). So the designers made the conscious decision to just not do that, instead delaying that check to the point at which the concrete type used to instantiate the generic function is known (because checking that a specific assignment satisfies a boolean formula is trivial). But that also means that you have to (recursively) type-check a generic function again and again for every type argument provided, which can drive up compilation time.

    A demonstration is this program, which makes gcc consume functionally infinite amount of memory and time: https://godbolt.org/z/crK89TW9G (clang is a little bit more clever, but can ultimately be defeated using a similar mechanism).

    Avoiding these problems is a specific cause for a lot of the limitations with Go's generics.

    > Look at Haskell type classes or Rust's traits for some classic examples of how to 'type' your generics. (And compare to what Go and C++ are doing.)

    Yes, those are a different beasts altogether and the differences between what Go is doing and what Haskell and Rust are doing requires different explanations.

    Though it's illustrative, because it turns out Rust also intentionally limited their generics implementation, to solve the kinds of performance problems Go is worried about. Specifically, Rust has the concept of "Dyn compatibility" (formerly "Object safety") which exists because otherwise Rusts goal of zero-cost abstractions would be broken. Haskell doesn't have this problem and will happily allow you to use the less efficient but more powerful types.

    (All of this should have the caveat that I'm not an expert in or even a user of any of these languages. It's half-knowledge and I might be wrong or things might have changed since I last looked)