undefined | Better HN

0 pointsMerovius8mo ago0 comments

> You need to have something that uses those templates.

Exactly. That is what I said:

> because you need to know the actual type arguments used, regardless of what the constraints might say.

It is because type-checking concept code is NP complete - it is trivial to check that a particular concrete type satisfies constraints, but you can not efficiently prove or disprove that all types which satisfy one constraint also satisfy another. Which you must do to type-check code like that (and give the user a helpful error message such as “this is fundamentally not satisfiable, your constraints are broken”).

And it’s one of the shortcomings of C++ templates that Go was consciously trying to avoid. Go’s generics are intentionally limited so you can only express constraints for which you can efficiently do such proofs.

I described the details a while back: https://blog.merovius.de/posts/2024-01-05_constraining_compl...

0 comments

lenkite8mo ago

There are common solutions for the library issue. Authors of libraries for example can force instantiations for a dummy type that checks their concepts.

  template void foo(Dummy);

This can be done at the consumer side as well. I don't see a big deal of this. Dummy checks are common in Go too. For example, to check if a type satisfies an interface.

   var _ MyInterface = (*MyType)(nil)
   var _ SomeInterface = GenericType[ConcreteType]{}

After all, Go checks that a type implements an interface only at the point where you assign or use it as that interface type.

Thanks for your blog post. Unfortunately, the intentional limitations make the design space a massive headache and many times lead to very convoluted API. I would actually make the argument that it explodes complexity - for the developer, instead of constraining it.

MeroviusOP8mo ago

> There are common solutions for the library issue. Authors of libraries for example can force instantiations for a dummy type that checks their concepts.

But that just ensures that the code type-checks for `Dummy`. It doesn't ensure that the code type-checks for any type you can put into `foo`. And that's the point of type constraints: To give you the necessary and sufficient conditions under which a generic function can be used.

That is simply not the case with C++ templates and concepts. That doesn't mean you can't still like them. I'm not trying to talk you out of liking C++ or even preferring it over Go. I'm just trying to explain that C++ concepts where something that we looked at specifically and found that it has properties that we don't like. And that - to us - the fact that Go generics are limited in comparison is a feature, not a bug.

And let's not forget that despite specifically reducing the safety of concepts in this way, the design ended up being NP-complete anyways and you can make a compiler use functionally infinite memory and time to compile a very small program: https://godbolt.org/z/crK89TW9G

For a language like Go, that prides itself on fast compilation times it is simply unacceptable to require a SAT solver to type-check. Again, doesn't mean one has to dislike C++. But one should be able to acknowledge that it is reasonable to choose a different tradeoff.

> I would actually make the argument that it explodes complexity - for the developer, instead of constraining it.

The title is a pun. Because it is about the computational complexity of checking constraints.

lenkite8mo ago

> But that just ensures that the code type-checks for `Dummy`. It doesn't ensure that the code type-checks for any type you can put into `foo`

Sure, that is C++ specific design decision. Just like Go made the design decision of not type checking interfaces leading to tens-of-thousands of lines of dummy checking concrete types against interfaces in popular Go repos.

I understand the design thinking even if I don't fully agree as a standard user of Go. Thanks for the detailed explanation in the blog.

Minor nitpick: It isn't all that difficult to come up with type structural/generic edge cases for ANY language compiler where compilation takes forever and times out in a playground. Here is a small program of ~100 lines leveraging Go Generics: https://go.dev/play/p/XttCbEhonXg

This will build for several minutes on your laptop if you use `go build`. It can be easily extended to several hours with a few modifications.

1 more reply

j / k navigate · click thread line to collapse

0 pointsMerovius8mo ago0 comments

> You need to have something that uses those templates.

Exactly. That is what I said:

> because you need to know the actual type arguments used, regardless of what the constraints might say.

I described the details a while back: https://blog.merovius.de/posts/2024-01-05_constraining_compl...

0 comments

lenkite8mo ago

There are common solutions for the library issue. Authors of libraries for example can force instantiations for a dummy type that checks their concepts.

  template void foo(Dummy);

This can be done at the consumer side as well. I don't see a big deal of this. Dummy checks are common in Go too. For example, to check if a type satisfies an interface.

   var _ MyInterface = (*MyType)(nil)
   var _ SomeInterface = GenericType[ConcreteType]{}

After all, Go checks that a type implements an interface only at the point where you assign or use it as that interface type.

MeroviusOP8mo ago

> There are common solutions for the library issue. Authors of libraries for example can force instantiations for a dummy type that checks their concepts.

> I would actually make the argument that it explodes complexity - for the developer, instead of constraining it.

The title is a pun. Because it is about the computational complexity of checking constraints.

lenkite8mo ago

> But that just ensures that the code type-checks for `Dummy`. It doesn't ensure that the code type-checks for any type you can put into `foo`

I understand the design thinking even if I don't fully agree as a standard user of Go. Thanks for the detailed explanation in the blog.

This will build for several minutes on your laptop if you use `go build`. It can be easily extended to several hours with a few modifications.

1 more reply

j / k navigate · click thread line to collapse