Type parameter embedded field

[Sylvain Rabot]

Hi,

I am wondering if Type Parameter embedding is something that is likely to happen ? e.g.:

type Nullable[T any] struct {
T
valid bool
}

Regards.

[Axel Wagner]

Hi,

I think the reason this has not happened is that it makes code using such a type invalid, depending on the type-argument - in ways not captured by the constraint. For example:

type X[T any] struct {

    T

    *bufio.Reader

}

func main() {

    var x X[int]

    x.Read // definitely refers to X.Reader.Read

    var y X[*strings.Reader]

    y.Read // ambiguous

}

Note, in particular, that this might happen very deeply in the call stack, as you can have a generic function instantiating a generic type with a type parameter as well.

func main() {

    F[*strings.Reader]()

}

func F[T any]() {

    G[T]()

}

func G[T any]() {

    var x X[T]

    x.Read

}

For us to actually allow embedding that way, one of three things would need to happen:

1. We would have to decide to be happy with type-checking of generic code only to happen at the instantiation site. That is what C++ is doing. It seems very unlikely to me, that Go would ever do that - in fact "we shouldn't do that" was one of the design constraints put unto generics. It is bad if a seemingly innocuous and backwards-compatible change in a library can break your code. Imagine that F and G above live in separate modules and G introduces the x.Read call in a debug release - because it seems innocuous and they tested it with their code and it works - because *they* never instantiate it with an io.Reader. Then, after their release, *your* code breaks, because you do.

2. We would have to enrich the constraint language to allow you to express that kind of constraint. i.e. X's constraint would mention, that it can only be instantiated with types that don't have a Read (or ReadByte, ReadLine, …) field or method. Again, this seems very unlikely to me, as it would require a really rich constraint language for relatively little benefit. In particular, it seems likely that such a language would be NP-complete to type check and we're unlikely to be happy about that. In fact, if I may shamelessly plug that, I recently gave a talk about another instance of a far more useful extension to the constraint language that we disallow for that very reason.

3. Someone comes up with a clever new compromise. To me, this actually is one of the more likely cases where a clever compromise could happen (compared to things like "allowing methods in unions", or "allowing to pass around uninstantiated generic functions" or "adding generic methods"). But I'm not aware of anyone having proposed or seriously working on anything like that.

So, in my opinion: I wouldn't hold my breath. I think it's unlikely this will happen and definitely not any time soon.

On Fri, Jan 5, 2024 at 1:07 AM 'Sylvain Rabot' via golang-nuts <golan...@googlegroups.com> wrote:

type Nullable[T any] struct {
T
valid bool
}

Just as an aside: I think this is actually a pretty interesting example. Because in my opinion, you absolutely *don't* want embedding to work here. Because it would mean that you could use an invalid `Nullable[T]` as if it was a valid one. And ISTM the entire point of a `Nullable[T]` should be, to prevent those kinds of bugs. In fact, `*T` seems *strictly preferable* over a `Nullable[T]` as described here, because at least it might catch these bugs at runtime.

But of course, there are other cases where embedding type parameters might be useful.

 

Regards.

--
You received this message because you are subscribed to the Google Groups "golang-nuts" group.
To unsubscribe from this group and stop receiving emails from it, send an email to golang-nuts...@googlegroups.com.
To view this discussion on the web visit https://groups.google.com/d/msgid/golang-nuts/f2b8c317-9530-45ff-b9f2-e9fe209a062cn%40googlegroups.com.

[Mike Schinkel]

On Friday, January 5, 2024 at 12:59:25 AM UTC-5 Axel Wagner wrote:

3. Someone comes up with a clever new compromise. 

Here is a strawman proposal:  Allow `Nullable`:

type Nullable[T any] struct {
T
valid bool
}

By generating a compile error when a developer attempts to use a type as a parameter that would create ambiguity, e.g. throw a compile error on these lines from your examples: 

    var y X[*strings.Reader]

And:

    F[*strings.Reader]()

I do recognize that deep call stacks may cause difficulty for this proposal, but my logical reasoning about them (vs. me knowing how it would to be implemented) tells me that `main()` should be able to see the generic type that `F()` requires because `F()` should be able to see the generic type that `G()` requires which is type `X`, and type `X` implements a `Read()` thus making it ambiguous with `*strings.Reader`:

type X[T any] struct {

    T

    *bufio.Reader

}

func F[T any]() {

    G[T]()

}

func G[T any]() {

    var x X[T]

    x.Read

}

Unless it is effectively not possible to implement that type of logic in the Go compiler because of design decisions — possibly related to compilation performance — then it seems logical the Go compiler should be able to recognize the conflict and generate a compile error on such combinations at the point of passing the type parameter, explicitly or implicitly.  

While not a perfect solution — since it would disallow edge cases where a developer feels they really must create a struct with both type parameters and use with types that create ambiguity — such a compromise would stop perfect from being the enemy of the good.

Anyway, as stated this is a strawman proposal. Please shoot holes in it if there are any opportunities to do so.

-Mike

[Axel Wagner]

On Fri, Jan 5, 2024 at 1:29 PM Mike Schinkel <mi...@newclarity.net> wrote:

I do recognize that deep call stacks may cause difficulty for this proposal, but my logical reasoning about them (vs. me knowing how it would to be implemented) tells me that `main()` should be able to see the generic type that `F()` requires because `F()` should be able to see the generic type that `G()` requires which is type `X`, and type `X` implements a `Read()` thus making it ambiguous with `*strings.Reader`:

[…]

Unless it is effectively not possible to implement that type of logic in the Go compiler because of design decisions — possibly related to compilation performance — then it seems logical the Go compiler should be able to recognize the conflict and generate a compile error on such combinations at the point of passing the type parameter, explicitly or implicitly.  

No doubt that would be possible. It is what C++ does. But as I said, the issue is that a seemingly innocuous change - like calling a generic function, not an API, but purely a code change - could cause compilation to fail. If the signature of a function says you are allowed to call the function, you should be allowed to call the function.

It was a conscious decision during the generics design to *not* do type-checking of generic function bodies during instantiation time, but to be able to compile the body of a generic function and the caller of a generic function separately.

 

While not a perfect solution — since it would disallow edge cases where a developer feels they really must create a struct with both type parameters and use with types that create ambiguity — such a compromise would stop perfect from being the enemy of the good.

Anyway, as stated this is a strawman proposal. Please shoot holes in it if there are any opportunities to do so.

-Mike

--

You received this message because you are subscribed to the Google Groups "golang-nuts" group.
To unsubscribe from this group and stop receiving emails from it, send an email to golang-nuts...@googlegroups.com.

To view this discussion on the web visit https://groups.google.com/d/msgid/golang-nuts/eaf71dec-e078-48bd-907c-ed7ff1ada222n%40googlegroups.com.

[Mike Schinkel]

On Friday, January 5, 2024 at 9:12:13 AM UTC-5 Axel Wagner wrote:

If the signature of a function says you are allowed to call the function, you should be allowed to call the function.

While I'd argue we would be best to stick to objective arguments and not ones that affirm the consequent, I'll nonetheless revise the proposal that does include all knowledge in the signature, see below.

It was a conscious decision during the generics design to *not* do type-checking of generic function bodies during instantiation time, but to be able to compile the body of a generic function and the caller of a generic function separately.

Unless I am misunderstanding how the compiler works, I was proposing type-checking during compile-time, not instantiation time.  Besides, prior decisions should not in-and-of themselves eclipse hindsight after-the-fact.  As even Rob Pike said in his keynote[1] just a few days ago, there are "still lingering problems" to do with generics, and "sometimes it takes many years to figure something out."  So to lean into commitment bias ensures future improvements will be less than they could be.

 

On to the revised proposal.  Assuming your example type again:

type X[T any] struct {
  T
  *bufio.Reader
}

Let us agree that it should not compile because of the stated conflicts.  

Instead, let us assume an extension to type constraints that would allow us to say that "A valid type is `any` type, except for those that implement the methods of type Y."  Using `!` as an placeholder sigil for that intent, and adding the sigil `&`, we could have the following type constraint:

type Xable interface {
  any & !*bufio.Reader
}

(While `!` is probably a bad choice — which is why I said it was a placeholder — it allows me to illustrate the concept in potential code.)

Alternately, maybe using `-` would be better?:

type Xable interface {
  any -*bufio.Reader
}

From the type constraint `Xable` it seems to me we could have the following, which should allow the compiler to do compile-type checking, without having to reach into deeply nested dependencies:

type X[T Xable] struct {
  T
  *bufio.Reader
}

 

The above should give the OP all reasonable functionality I believe they were requesting and usefully expand the capabilities of generics. That is, unless there are objective arguments for why that can't reasonably be compiled, or there are unintended conflict elsewhere in the language?

-Mike

[1] https://www.youtube.com/watch?v=yE5Tpp2BSGw

[Axel Wagner]

On Sat, Jan 6, 2024 at 12:34 PM Mike Schinkel <mi...@newclarity.net> wrote:

While I'd argue we would be best to stick to objective arguments and not ones that affirm the consequent

This thread was not a proposal to change the language and it was not a question of whether it would be a good idea to do so. The question was "how likely is it, that this is going to happen?" (and I would read an implied "over the next few years" into that, which is admittedly interpretation).

Saying that for that to happen, we would have to re-litigate design constraints that have been in place for years of discussion about Go generics *is* an objective argument. I am being predictive, not prescriptive.

If it helps, I do think we might re-investigate this particular design assumption. I don't think that's because of embedded type parameters (the benefits here are too small, in my estimation - and as I said, I'm not even convinced this case *is* in favor, not against), but there are other cases where it pops up as well and if the pain about those becomes large enough, it might be worth talking about this. That doesn't mean it would happen soon, though. And it doesn't mean that the outcome of that conversation is to change this design constraint. And if we did, it doesn't mean we would necessarily allow embedding type parameters.

All of that goes into my prediction of "I do not believe this would happen any time soon".

, I'll nonetheless revise the proposal that does include all knowledge in the signature, see below.

It was a conscious decision during the generics design to *not* do type-checking of generic function bodies during instantiation time, but to be able to compile the body of a generic function and the caller of a generic function separately.

Unless I am misunderstanding how the compiler works, I was proposing type-checking during compile-time, not instantiation time.

"instantiation time" is during compilation. I'm refering to type-checking the body of a generic function once it gets instantiated with a type argument, instead of simply based on its signature and type parameter constraints.

 

On to the revised proposal.  Assuming your example type again:

type X[T any] struct {
  T
  *bufio.Reader
}

Let us agree that it should not compile because of the stated conflicts.  

Instead, let us assume an extension to type constraints that would allow us to say that "A valid type is `any` type, except for those that implement the methods of type Y."  Using `!` as an placeholder sigil for that intent, and adding the sigil `&`, we could have the following type constraint:

type Xable interface {
  any & !*bufio.Reader
}

(While `!` is probably a bad choice — which is why I said it was a placeholder — it allows me to illustrate the concept in potential code.)

I took this idea into account in my original message. It is bullet point 2. The case against this is that it would likely make type-checking Go code (co-)NP-complete.

If you watch my talk about methods in union elements (or read the supplemental blog post about it), you'll see that I have to spend a bit of work on constructing a negation to prove (co-)NP-completeness.

If we just put in a negation operator, that work would no longer even be necessary and the proof becomes trivial. In fact, C++ concepts *have* a plain negation operator in their constraint language and are known to be NP-complete to type-check.

 

Alternately, maybe using `-` would be better?:

type Xable interface {
  any -*bufio.Reader
}

From the type constraint `Xable` it seems to me we could have the following, which should allow the compiler to do compile-type checking, without having to reach into deeply nested dependencies:

type X[T Xable] struct {
  T
  *bufio.Reader
}

 

The above should give the OP all reasonable functionality I believe they were requesting and usefully expand the capabilities of generics. That is, unless there are objective arguments for why that can't reasonably be compiled, or there are unintended conflict elsewhere in the language?

-Mike

[1] https://www.youtube.com/watch?v=yE5Tpp2BSGw

--
You received this message because you are subscribed to the Google Groups "golang-nuts" group.
To unsubscribe from this group and stop receiving emails from it, send an email to golang-nuts...@googlegroups.com.

To view this discussion on the web visit https://groups.google.com/d/msgid/golang-nuts/67c3cf8d-a6ae-4968-991f-df09e9f86475n%40googlegroups.com.

[Mike Schinkel]

On Saturday, January 6, 2024 at 7:58:55 AM UTC-5 Axel Wagner wrote:

I took this idea into account in my original message. It is bullet point 2. The case against this is that it would likely make type-checking Go code (co-)NP-complete.

If you watch my talk about methods in union elements (or read the supplemental blog post about it), you'll see that I have to spend a bit of work on constructing a negation to prove (co-)NP-completeness.

If we just put in a negation operator, that work would no longer even be necessary and the proof becomes trivial. In fact, C++ concepts *have* a plain negation operator in their constraint language and are known to be NP-complete to type-check.

 

One of the things I have really appreciated about the Go language — and a main reason I was drawn to it — was how the Go team has been pragmatic in the past instead of allowing conceptual purity to block functionality that would be useful in service of software engineering.

Specifically to your argument about negation and NP-completeness, yes in the general case unrestrained negation could result in NP-completeness.  

However, a better and more pragmatic approach would be to restrain negation to those things that can be performed efficiently. 

Alternately the Go team could recast the solution as something other than negation; e.g. an "exception" as in "allow `any` type, excepting those types that conflict with type `Y`."  

For the case of type embedding, the methods of `Y` are known at compile time and the type methods can be compared as efficiently with the type parameter as checking methods of an interface parameter. That is unless there is some other unintended consequences I am not seeing and you have not mentioned.

-Mike 

P.S. Ironically, ensuring the benefits of embedded type parameters are "too small" is itself a class of NP problem.

[Axel Wagner]

On Sat, Jan 6, 2024 at 3:16 PM Mike Schinkel <mi...@newclarity.net> wrote:

One of the things I have really appreciated about the Go language — and a main reason I was drawn to it — was how the Go team has been pragmatic in the past instead of allowing conceptual purity to block functionality that would be useful in service of software engineering.

Specifically to your argument about negation and NP-completeness, yes in the general case unrestrained negation could result in NP-completeness.  

However, a better and more pragmatic approach would be to restrain negation to those things that can be performed efficiently.

Your proposal does not allow efficient computation (under the generally accepted assumption that P≠NP). It allows a direct translation of a boolean formula into a Go interface, by

1. introducing a `type X struct{}` for every variable `X` in the formula

2. then writing out the formula as an interface, replacing ¬X with "!X", ∨ with `|` and ∧ with `;`

When I said "your proposal makes type-checking Go NP-complete", I was not being dismissive or facetious, I was stating a simple fact. And it is confirmed by the fact that C++ *has* this constraint language and you can write programs that crash common C++ compilers.

Note that this does not mean we can't do it. In fact, in my talk and my post I explicitly say that it is an option to accept an NP-completeness, if we so choose. Again, the fact that this is an option should be clear from the fact that C++ made that choice, consciously. I don't believe we should (and I would predict that we won't), but I am just one voice in the Go project among many. You can disagree with me and that's fine - but you should be aware what the implications of what you are proposing are.

I am also clear, FWIW, that it would be possible to choose compromises, that would give us *some* power, while avoiding having to solve NP-complete problems. If you want to propose such a compromise, that is great and I will certainly be happy to try to give my opinion on that as well. So, that would be another way you can react to the assertion that your proposal poses NP-complete questions - by modifying it, so that it doesn't.

The reason I am referring to my talk - despite the fact that it is about a *different* extension of Go's type system - is that I genuinely believe it gives a good overview over the problem, its subtleties, ways to address that and why those ways are still difficult. Not impossible, but they require work that you should do, if you want to make such a proposal.

Again, all of this is just my personal opinion, as one long-time member of the Go community. I neither can nor want to shut down your voice, just add my own.

 

For the case of type embedding, the methods of `Y` are known at compile time and the type methods can be compared as efficiently with the type parameter as checking methods of an interface parameter. That is unless there is some other unintended consequences I am not seeing and you have not mentioned.

I'm pretty sure I mentioned consequences.

 

-Mike 

P.S. Ironically, ensuring the benefits of embedded type parameters are "too small" is itself a class of NP problem.

--
You received this message because you are subscribed to the Google Groups "golang-nuts" group.
To unsubscribe from this group and stop receiving emails from it, send an email to golang-nuts...@googlegroups.com.

To view this discussion on the web visit https://groups.google.com/d/msgid/golang-nuts/5f4208fe-730b-41cb-bd55-62f7d9bdbb58n%40googlegroups.com.

[roger peppe]

On Fri, 5 Jan 2024 at 05:58, 'Axel Wagner' via golang-nuts <golan...@googlegroups.com> wrote:

Hi,

I think the reason this has not happened is that it makes code using such a type invalid, depending on the type-argument - in ways not captured by the constraint. For example:

type X[T any] struct {

    T

    *bufio.Reader

}

func main() {

    var x X[int]

    x.Read // definitely refers to X.Reader.Read

    var y X[*strings.Reader]

    y.Read // ambiguous

}

Note, in particular, that this might happen very deeply in the call stack, as you can have a generic function instantiating a generic type with a type parameter as well.

func main() {

    F[*strings.Reader]()

}

func F[T any]() {

    G[T]()

}

func G[T any]() {

    var x X[T]

    x.Read

}

For us to actually allow embedding that way, one of three things would need to happen:

To my mind, there's a reasonably obvious way through the issue you outlined above (although there may well be more):

allow a static reference to a field/method if all the embedded types are known, and not otherwise.

So in the above example, `x.Read` in `main` is fine; `y.Read` in `main` is ambiguous due to two methods at the same level as you say;

`x.Read` in `G` is not allowed because we don't statically know the method set of `x`. Likewise, we couldn't assign `x` to an `io.Reader`,

but we could convert to `any` and then do a dynamic type conversion to `io.Reader` if we wished (which would fail in the *strings.Reader case

but succeed in the int case).

ISTM those semantics would be reasonably intuitive, and good compiler error messages could make it quite clear why we aren't allowed to reference such methods statically.

  cheers,

    rog.

[Axel Wagner]

I think that might work, yes. At least I don't see a major issue with it right now.