Go generics and bloating

[Guillaume Lescure]

Hello,

I remember a paper about Go Generics but I cannot find it again.
It was a scientist paper (with a lot of maths far beyond my understanding ^^).
Title was something like "Lightweigh generics for Go" or something like that.
I believe the background of the website was red (not sure either).
If someone has the url, please share it :)

In the same idea, I believed the Go Generics solves the "bloating binary" issue. If so, I don't understand why I see the "same instructions" at ligne 68-71 and at ligne 81-84 in this exemple : https://godbolt.org/z/cqY19PT7q. I'm not fluent with assembler but, for me there is a bloating there.

Can someone explain it to me ? :)
Thanks in advance

[Axel Wagner]

You are looking for "Featherweight Go", I believe.

https://arxiv.org/abs/2005.11710

--
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/0ffd9802-3094-41b5-95c0-5f800dc6f3dan%40googlegroups.com.

[Andrew Harris]

https://planetscale.com/blog/generics-can-make-your-go-code-slower is the best breakdown I've seen of current implementation details as they hit assembly. There is a little bit of oil/water thing with interfaces and generics - they don't exactly mix, but you can cook however you like ...

[Guillaume Lescure]

Thanks a lot Axel that's the paper I was looking for :D

Thanks for the article, I will read it.
But if someone has more explanation for my little exemple, I'm still listening :)

[Brian Candler]

On Tuesday, 16 August 2022 at 21:15:03 UTC+1 axel.wa...@googlemail.com wrote:

You are looking for "Featherweight Go", I believe.

https://arxiv.org/abs/2005.11710

That's an interesting paper - at least the early parts that I could understand!

I tried converting their main motivating example from fig 8, but got stuck by not being able to put a method on a parameterised type:

func (e Plus[a Evaler]) Eval() int {

    return e.left.Eval() + e.right.Eval()

}

// ./prog.go:21:16: syntax error: unexpected Evaler, expecting ]

func (e Plus[Evaler]) Eval() int {
    return e.left.Eval() + e.right.Eval()
}

// ./prog.go:24:16: e.left.Eval undefined (type Evaler has no field or method Eval)

// ./prog.go:24:33: e.right.Eval undefined (type Evaler has no field or method Eval)

func (e Plus[a]) Eval() int {
    return e.left.Eval() + e.right.Eval()
}

// ./prog.go:24:16: e.left.Eval undefined (type a has no field or method Eval)

// ./prog.go:24:33: e.right.Eval undefined (type Evaler has no field or method Eval)

Is this what is meant by:

Another result is the proposal for covariant receiver typing, a feature required by The Expression Problem. It is not part of the Go team’s current design, but they have noted it is backward compatible and are considering adding it in the future.

?

[Axel Wagner]

On Wed, Aug 17, 2022 at 10:43 AM Brian Candler <b.ca...@pobox.com> wrote:

That's an interesting paper - at least the early parts that I could understand!

I tried converting their main motivating example from fig 8, but got stuck by not being able to put a method on a parameterised type:

func (e Plus[a Evaler]) Eval() int {

    return e.left.Eval() + e.right.Eval()

}

// ./prog.go:21:16: syntax error: unexpected Evaler, expecting ]

func (e Plus[Evaler]) Eval() int {
    return e.left.Eval() + e.right.Eval()
}

// ./prog.go:24:16: e.left.Eval undefined (type Evaler has no field or method Eval)

// ./prog.go:24:33: e.right.Eval undefined (type Evaler has no field or method Eval)

func (e Plus[a]) Eval() int {
    return e.left.Eval() + e.right.Eval()
}

// ./prog.go:24:16: e.left.Eval undefined (type a has no field or method Eval)

// ./prog.go:24:33: e.right.Eval undefined (type Evaler has no field or method Eval)

Is this what is meant by:

Another result is the proposal for covariant receiver typing, a feature required by The Expression Problem. It is not part of the Go team’s current design, but they have noted it is backward compatible and are considering adding it in the future.

?

Yes, that's what is meant by that. Though the issue is not putting a method on a parameterized type - you can do that. And it's not even putting a method with extra type parameters on a type - you can't do that and it doesn't seem possible under the current design restrictions put on generics in Go.

But to have a method with a receiver more tightly constrained than the type itself (personally, I've been calling that "refined method constraints", in lieu of a better term). That seems an entirely possible future extension.

But not yet. We should first try out generics as they are for a while.

 

--
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/528c0c73-e2db-4153-a505-6003deb886f2n%40googlegroups.com.

[Brian Candler]

So when I write

    func (e Plus[Evaler]) Eval() int {
 

IIUC, it is effectively treated as if it were the following (not currently valid syntax):

    func (e Plus[Evaler any]) Eval() int {

- i.e. inside this function "Evaler" is a local type parameter whose name just happens to shadow the outer type definition, and is not constrained.

Aha: I think I can see the lack of covariance explicitly if I try to do this:

func (e Plus[a]) Eval() int {

    ee := any(e).(Plus[Evaler])
    return ee.left.Eval() + ee.right.Eval()
}

// panic: interface conversion: interface {} is main.Plus[main.Expr], not main.Plus[main.Evaler]

OK. So whilst I know that e has struct fields 'left' and 'right', because it's one of the Plus[a] family of types, I don't know anything at compile time about the types of those fields.  But I can assert it at runtime, and now I have some code that runs, albeit ugly and without compile-time checks:

func (e Plus[a]) Eval() int {

    return any(e.left).(Evaler).Eval() + any(e.right).(Evaler).Eval()
}

Aside: I can't see that there's much use for the type parameter 'a', except if I needed to declare variables of that type:

func (e Plus[a]) Eval() int {
    var left a = e.left
    var right a = e.right
    return any(left).(Evaler).Eval() + any(right).(Evaler).Eval()
}

[Andrew Harris]

This particular example might be hiding some benefits of having the type parameter in the method signature. The type parameter can be useful in something like:

func (lhs BinaryPlusOp[T]) Eval( rhs T) T

Or, for being explicit about why

func (t Number[T]) Sum( []T ) T 

can't accept a slice of varying number types

[Axel Wagner]

On Wed, Aug 17, 2022 at 11:17 AM Brian Candler <b.ca...@pobox.com> wrote:

So when I write

    func (e Plus[Evaler]) Eval() int {
 

IIUC, it is effectively treated as if it were the following (not currently valid syntax):

    func (e Plus[Evaler any]) Eval() int {

- i.e. inside this function "Evaler" is a local type parameter whose name just happens to shadow the outer type definition, and is not constrained.

Aha: I think I can see the lack of covariance explicitly if I try to do this:

func (e Plus[a]) Eval() int {
    ee := any(e).(Plus[Evaler])
    return ee.left.Eval() + ee.right.Eval()
}

// panic: interface conversion: interface {} is main.Plus[main.Expr], not main.Plus[main.Evaler]

OK. So whilst I know that e has struct fields 'left' and 'right', because it's one of the Plus[a] family of types, I don't know anything at compile time about the types of those fields.  But I can assert it at runtime, and now I have some code that runs, albeit ugly and without compile-time checks:

func (e Plus[a]) Eval() int {
    return any(e.left).(Evaler).Eval() + any(e.right).(Evaler).Eval()
}

Yes. The benefit is that instead of having the `Eval` method exist and panic if the type argument does not implement `Evaler`, you can have it exist *only* if the type argument implements `Evaler`. That is, the benefit is in the increased type safety that a) you are being more "honest" about what methods `Plus` has, to your caller and b) you are being kept more honest about what methods are available to you, when you write your `Eval` method.

 

To view this discussion on the web visit https://groups.google.com/d/msgid/golang-nuts/420a41f5-ad94-41a9-969b-e71aa2ab698fn%40googlegroups.com.

[Keith Randall]

On Tuesday, August 16, 2022 at 1:03:22 PM UTC-7 guil.l...@gmail.com wrote:

Go generics takes a step towards fixing the bloating binary issue, "solved" is too strong a word.

Instead of generating one implementation per instantiation, we generate one per "instantiation shape". In your example, int and uint must have different shapes because the > operator requires different code for each of them (JGE vs JCC).

But if you had

type A int

type B int

then max[A], max[B], and max[int] would all use the same instantiation.

 

Thanks in advance

[Guillaume Lescure]

Thank you very much Keith, that answers my question :)