Proposal: make generic code clearer

[xushiwei]

Refer: https://blog.golang.org/why-generics

My first question is how to define a generic type or function.

func New (type Node, Edge G) (nodes []Node) *Graph(Node, Edge) {
    ...
}

I think this code is terrible. Go's function prototype is more complex than other languages.

Generics make it more terrible.

Maybe the following code is clearer.

[Node, Edge G]
func New(nodes []Node) *Graph[Node, Edge] {
    ...
}

My second question is how to define a contract.

contract Ordered(T) {
    T int, int8, int16, int32, int64,
        uint, uint8, uint16, uint32, uint64, uintptr,
        float32, float64,
        string
}

Maybe the following code is clearer.

contract Ordered(T) {
    (T) < (T) bool
}

The following is a completed example.

package example

// --------------------------------------------------------------------------

contract builtinLesser(T) {
    (T) < (T) bool
}

[T builtinLesser]
func Less(a, b T) bool {
    return a < b
}

contract lesser(T) {
    (T) Less(T) bool
} 

[T lesser]
func Less(a, b T) bool {
    return a.Less(b)
}

contract Lessable(T) {
    Less(a, b T) bool
}

// --------------------------------------------------------------------------

[T Lessable]
func Min(a ...T) T {
    v := a[0]
    for i := 1; i < len(a); i++ {
        if Less(a[i], v) {
            v = a[i]
        }
    }
    return v
}

[T Lessable]
func Min(a, b T) T { // Specialization
    if Less(a, b) {
        return a
    }
    return b
}

// --------------------------------------------------------------------------

contract G(Node, Edge) {
    (Node) Edges() []Edge
    (Edge) Nodes() (from Node, to Node)
}

[Node, Edge G]
type Graph struct {
    // ...
}

[Node, Edge G]
func New(nodes []Node) *Graph[Node, Edge] {
    ...
}

// --------------------------------------------------------------------------

[xushiwei]

My third question is what the relation of contract and interface is.

I think 'contract' is a generic concept of 'interface'.

So, an interface is a contract.

Generic code:

[Reader io.Reader]
func ReadUint32le(v *uint32, ar Reader) { // uint32 little endian
    // ...
}

If we use a contract, it becomes the following code.

contract Readable(T) {
    (T) Read(b []byte) (n int, err error)
}

[Reader Readable]
func ReadUint32le(v *uint32, ar Reader) { // uint32 little endian
    // ...
}

Polymorphic code:

func ReadUint32le(v *uint32, ar io.Reader) { // uint32 little endian
    // ...
}

[xushiwei]

My 4th question is how to be compatible with non generic code.

For example. If I have a serialization package. Its code is the following.

type uint16be uint16
type uint32be uint32
type cstring string // with '\0' as EOS.

[Archive io.Reader]
func ReadByte(v *byte, ar Archive)

[Archive io.Reader]
func ReadUint16le(v *uint16, ar Archive)

[Archive io.Reader]
func ReadUint16be(v *uint16be, ar Archive)

[Archive io.Reader]
func ReadUint32le(v *uint32, ar Archive)

[Archive io.Reader]
func ReadUint32be(v *uint32be, ar Archive)

[Archive io.Reader]
func ReadCstring(v *cstring, ar Archive)

How can I let it more generic? I think the simplest way is the following.

[T, Archive io.Reader]
func Read(v *T, ar Archive) = (
    ReadByte
    ReadUint16le
    ReadUint16be
    ReadUint32le
    ReadUint32be
    ReadCstring
)

contract Readable(T) {
    [Archive io.Reader]
    Read(v *T, ar Archive)
}

The following is a completed example.

package example

// --------------------------------------------------------------------------

type uint16be uint16
type uint32be uint32
type cstring string // with '\0' as EOS.

[Archive io.Reader]
func ReadByte(v *byte, ar Archive)

[Archive io.Reader]
func ReadUint16le(v *uint16, ar Archive)

[Archive io.Reader]
func ReadUint16be(v *uint16be, ar Archive)

[Archive io.Reader]
func ReadUint32le(v *uint32, ar Archive)

[Archive io.Reader]
func ReadUint32be(v *uint32be, ar Archive)

[Archive io.Reader]
func ReadCstring(v *cstring, ar Archive)

// --------------------------------------------------------------------------

contract ObjectReader(T) {
    [Archive io.Reader]
    (T) ReadObject(ar Archive)
}

[T ObjectReader, Archive io.Reader]
func ReadObject(v T, ar Archive) {
    v.ReadObject(ar)
}

[T, Archive io.Reader]
func Read(v *T, ar Archive) = (
    ReadByte
    ReadUint16le
    ReadUint16be
    ReadUint32le
    ReadUint32be
    ReadCstring
    ReadSlice
    ReadObject
)

contract Readable(T) {
    [Archive io.Reader]
    Read(v *T, ar Archive)
}

// --------------------------------------------------------------------------

[T Readable, Archive io.Reader]
func ReadArray(arr []T, ar Archive) {
    for i := 0; i < n; i++ {
        Read(&arr[i], ar)
    }
}

[Archive io.Reader]
func ReadArray(b []byte, ar Archive) { // Specialization
    // ...
}

[T Readable, Archive io.Reader]
func ReadSlice(v *[]T, ar Archive) {
    var n uint16
    ReadUint16le(&n, ar)
    *v = make([]T, int(n))
    ReadArray(*v, ar)
}

// --------------------------------------------------------------------------

[griesemer]

Hello @xushiwei; thanks for the feedback!

Here are (my) preliminary answers to your questions:

1. Now that I have written quite a bit of generic code using my work-in-progress prototype, I also feel that func New (type Node, Edge G) (nodes []Node) *Graph(Node, Edge) is not all that great for readability. That said, currently we are concentrating on the semantics a bit more and leaving the notation alone, simply to make progress. Once we are confident with the semantics, it's relatively easy to polish/update the syntax.

Your suggestion of writing

[Node, Edge G]
func New(nodes []Node) *Graph[Node, Edge] {
    ...
}

does read pretty nicely, but it doesn't match the function invocation (at least if type parameters are passed explicitly which is necessary here because the Edge type cannot be inferred). How would one call this function and pass in the Edge type?

2. Regarding the "operator notation" you are advocating: Yes, we have been thinking about this as well. Earlier generics proposals did exactly what you are suggesting. The problem is not (binary) operators, though. The problem is that there are a lot of additional operations such as conversions, assignability, etc. that we need to express as well, and there is no "obvious" method notation for those constraints. The current notation of enumerating the types works surprisingly well; but it also closes the door a bit on operator methods. But see 1): For now we concentrate on the semantics to make some progress.

3. I agree with you that a contract is a form of generic interface. Please see https://golang.org/cl/187317, specifically the Commit message of that CL. Internally, a contract is disassembled into interfaces. In other words, in my mind, a contract is simply syntactic sugar for a set of interfaces.

4. Interesting suggestion. I have to think a bit more about it. That said, for now, we like to get the basics correct before venturing further afield. The basics we are concerned about right now are the following questions:

• what exactly is the connection between interfaces and contracts (my current thinking is that contracts are syntactic sugar for interfaces)?
• can we do better that enumerate a list of types for operator constraints?

And on the syntactic side:

• can we improve the type parameter notation to make type-parameterized function signatures more readable?

[xushiwei]

1. How would one call this function and pass in the Edge type?

This only change the notation, not the semantic. So we just call

New[Node, Edge](nodes)

to pass in the Edge type.

[xushiwei]

what exactly is the connection between interfaces and contracts (my current thinking is that contracts are syntactic sugar for interfaces)?

I don't think contracts are syntactic sugar for interfaces.

Suppose we don't change the semantic of "an interface is a value". We can't disassemble the following contract

contract ObjectReader(T) {
    [Archive io.Reader]
    (T) ReadObject(ar Archive)
}

into interfaces:

interface ObjectReader {
    [Archive io.Reader]
    ReadObject(ar Archive)
}

Why? Because here 'ReadObject' is not a normal method. It is a template method. If the interface 'ObjectReader' is legal, it is not a value.

And more, contracts maybe need to support global functions. For example:

[T io.Reader]
func Foo(r T) {
    // ...
}

[T io.Writer]
func Bar(w T) {
    // ...
}

[T XXX]
func Example(t T) {
    Foo(t)
    Bar(t)
}

Of course, here 'XXX' can be 'io.ReadWriter'. But it also can be:

contract FooBarable(T) {
    Foo(T)
    Bar(T)
}

Now, 'FooBarable' is equivalent to 'io.ReadWriter'.

Why need support global function? Let's see a previous example:

[T, Archive io.Reader]
func Read(v *T, ar Archive) = (
    ReadByte
    ReadUint16le
    ReadUint16be
    ReadUint32le
    ReadUint32be
    ReadCstring
    ReadSlice
    ReadObject
)

Here, the type 'T' isn't given a contract. but in fact its contract is:

contract Readable(T) {
    T byte, uint16, uint16be, uint32, uint32be, cstring, []T, ObjectReader
}

So, If a function need call the global 'Read' function, we use the following equivalent contract:

contract Readable(T) {
    [Archive io.Reader]
    Read(v *T, ar Archive)
}

[xushiwei]

can we do better that enumerate a list of types for operator constraints?

The last question is: do we support operator overload?

If we don't, I think a list of types is good, if we given some builtin constraints. For example, contracts.Integer, contracts.Float, contracts.Comparable, etc.

Operator functions are very special. They exist in the global namespace, not in packages. So I agree not to support operator overload.

The principle maybe is:

Only template function/method can be overloaded.

The following is an example.

func Foo(v int) { ... }
func Foo(v string) { ... } // BAD!

func BarInt(v int) { ... }
func BarString(v string) { ... }

[T] func Bar(v T) = ( // GOOD!
    BarInt
    BarString
)

[urandom]

We could borrow notes from SQL, as well as rust, and add a where clause for type parameters that need constraints.

Consider the following example (with interface contstraints, due to its verbosity)

func f(type P1 I1(P1), P2 I2(P1, P2), P3) (x P1, y P2) P3 

We could potentially break that down to:

func f(type P1, P2, P3) (x P1, y P2) P3 where
    P1: I1(P1), P2: I2(P1, P2)

Or a step further from this proposal:

[P1, P2, P3]
func f(x P1, y P2) P3 where
    P1: I1(P1), P2: I2(P1, P2)

Overall its more verbose, but it might be more readable, especially with more type parameters

[griesemer]

One issue I see with the notation

[T Readable, Archive io.Reader]
func ReadArray(arr []T, ar Archive)

is that the call of ReadArray - when types are not inferred, doesn't match the declaration: In the declaration, the type parameters are declared before the function name, in the call they are passed after the function name. This is an aspect we have paid attention to in the past. I am not saying it cannot be changed, but it's something to be aware of.

We have played with a lot of different notations for the type parameters, including using [ and ] and < and >. They all have their problems. [ is surprisingly cumbersome in situations such as x[T] where we would allow a trailing comma (as in x[T,] if the [T] is a type parameter list (because we allow a trailing comma in all parameter lists for consistency); but we can't allow a trailing comma if x[T] is a index expression. Unfortunately we can't know until type checking time at which point it's too late. It can be made to work, but it's not great.

We've also been playing with more condensed forms of type parameter lists, for instance:

func ReadArray(type T Readable, Archive io.Reader : arr []T, ar Archive)

or

func ReadArray(type T Readable, Archive io.Reader ; arr []T, ar Archive)

This latter version would allow the following form (because of automatic semicolon insertion):

func ReadArray(
   type T Readable, Archive io.Reader
   arr []T, ar Archive
)

I personally like the latter because it's light-weight in the simple case, and allows for nice notation across multiple lines in the more complex case w/o extra overhead.

Anyway, I prefer not debating the syntax for now because that's something we can change relatively easily once we have everything else nailed down. What we have now is workable to make progress.

Regarding contracts: I am feeling very strongly that a contract is simply syntactic sugar for a set of interfaces. Specifically, given a general contract

contract C(T1, T2, ... Tn) {
   T1 m11()
   T1 m12()
   ...
   T2 m21()
   T2 m22()
   ...
}

etc. we have to represent the type bounds for each type parameter. The type bounds for type parameter Ti are all the contract entries referring to Ti. If we bundle these together, and if we do this for all type parameters, we get a set of parameterized interfaces, as in:

type I1(type T1, T2, ... Tn) interface {
   m11()
   m12()
   ...
}

type I2(type T1, T2, ... Tn) interface {
   m21()
   m22()
   ...
}
...

This is of course cumbersome to write but it is easy for the type-checker to create these interfaces from a contract. Everything that we can express in a contract we can express in an (extended) interface. For this to work, we also extend interfaces to have type lists, such as in (for example):

type Adder(type T) interface {
   Add(x T) T
   type int, float32, complex64
}

Whether we should allow such interfaces in places outside type parameter bounds is not clear yet, but it's very clear that this makes implementation straight-forward and explainable. More importantly, using interfaces as type bounds does fit with the type theory of generic type systems.

Finally, considering contracts as syntactic sugar for interfaces also resolves the dilemma of what it means to mix contracts and interfaces. The dilemma disappears. A contract is simple a set of interfaces which (sometimes, but not always) may be less cumbersome to write down in form of a contract. I believe in the vast majority of cases, there will be exactly one type parameter, and in the vast majority of cases that type parameter has very simple constraints. Often it will be an interface such as io.Reader or can be written in place. In those cases, a contract is more work.

Using parameterized interfaces also resolves the issue with what you call template methods - which is not a term we have defined for Go or know what it means. In refining our design at this point (syntax aside) it's really important to boil it down to the fine-grained semantics that permits us to implement a type checker that is understood and sound. We should not invent arbitrary mechanisms that are not fundamentally grounded in type theory. We are deliberately not trying to implement something like C++ templates, for that matter (as they cannot be type-checked seperately, w/o instantiation, which is the primary reason the resulting error messages are unreadable if there's a mistake somewhere).

Regarding your last example (contract FooBarable) I don't understand that notation. At least as you have written, that contract is not permitted in the current design draft (each constraint in the contract must be preceded by a type parameter). More generally, a contract does not specify global functions ever - it's representing constraints on a type parameter. But more importantly, I don't see what you gain from being able to specify a specific set of global functions. Both Foo and Bar operate on any type that implements an io.Reader (for Foo) or an io.Writer (for Bar), respectively. Clearly, for Example to work, the type of t must support both. So what's wrong with XXX just being io.ReadWriter?

(As an aside, I just verified that

package p

import "io"

func Foo (type T io.Reader) (r T)

func Bar (type T io.Writer) (w T)

func Example (type T io.ReadWriter) (t T) {
   Foo(t)
   Bar(t)
}

type-checks fine with the current prototype, as expected.)

[beoran]

@griesemer I really like the way you are currently thinking, especially the idea of extending interfaces to also have type lists and be parametrable. Like that, it becomes possible to group a few concrete types together without having to implement a marker method on them, or to use the native types directly through an interface. Please do consider allowing these extensions to interfaces everywhere, not just within the confines of generics.

As for the syntax, I also like the ; idea. That looks quite readable. But you are right, first semantics, then syntax.

[alanfo]

I agee with everything @beoran has just said. In particular, I prefer the ; idea to both the original syntax and the present proposal as we would not then need any more brackets than we do for non-generic functions.

Although I personally think that contracts are a 'nicer' vehicle for expressing relationships between type parameters, the fact remains that in the majority cases only one type parameter will be required (or if two or more are needed there will be no relationship between them).

Consequently, if the compiler is going to split contracts up into interfaces anyway, we might as well bite the bullet and go with explicit interfaces for everything. This will make the implementation simpler and, of course, will mean that a new keyword will not be required - just a new 'comparable' built-in.

I also agree that it would be a good idea to not just confine interfaces with type clauses to generics. As was discussed in #19412, restricting interfaces to a finite set of types would get us most of the way towards a form of 'discriminated union' which a lot of people feel would be a worthwhile addition to the language. All that would be needed to complete the picture is a way to specify that a listed type did not include any derived types (as it would for generics) and a type switch which would check that only listed types were catered for and could therefore be exhaustive.

[jimmyfrasche]

@griesemer

type Adder(type T) interface {
   Add(x T) T
   type int, float32, complex64
}

Looks like it would be constraining instantiations of Adder rather thanT.

Was it meant to be the following:

type Adder(type T) interface {
   Add(x T) T
   type T = int, float32, complex64
}

It seems like that would be needed if there were two parameters with different underlying type constraints.

[alanfo]

I think myself it's correct as @griesemer had it:

type Adder(type T) interface {
   Add(x T) T
   type int, float32, complex64
}

It's saying that the Adder(T) interface can only be satisfied by types derived from int, float32 or complex64 which have a method with signature Add(x T) T.

[alanfo]

Incidentally, there's an example with two type parameters in @griesemer's prototype where:

contract C(P1, P2) {
    P1 m1(x P1)
    P2 m2(x P1) P2
    P2 int, float64
}

disassembles into the two interfaces:

type I1(type P1) interface {
    m1(x P1)
}

type I2(type P1, P2) interface {
    m2(x P1) P2
    type int, float64
}

i.e. one for each type parameter. So P1 has to satisfy I1 and P2 has to satisfy I2.

Presumably, the corresponding contract for the Adder interface would be:

contract AdderContract(T) {
    T Add(x T) T
    T int, float32, complex64
}

[jimmyfrasche]

Thanks, I had missed that when I skimmed the CL (I went straight to the examples).

I do like the idea of using interfaces instead of contracts. If they can do everything that contracts can do, I'm not sure why there would also be contracts, though, even if sometimes they're more convenient. Is it just for comparability or is that also an interface like #27481?

I'm not terribly enthusiastic about expressing type restrictions in interfaces, though. If you embed interfaces with type restrictions, wouldn't you need to take the intersection of the restrictions instead of their union? When that intersection is whittled down to ∅ doesn't that mean that no type satisfies it, making it distinct from not having a restriction at all? When using an interface as an interface instead of as a constraint, does it still work with the underlying types?

[alanfo]

If contracts were replaced entirely by interfaces, which I agree makes sense, then comparable would just become a built in interface rather than a contract as there would be no way to express it in normal Go.

Although I'm on the fence about whether discriminated unions are a good idea for Go, they do seem popular and 'restricted interfaces' look like a convenient way of implementing them which would cause minimal disruption to the language.

If that were done, then we'd need some syntax to indicate that the interface only applied to the listed types and not to types derived from them (I think I suggested const type in the previous discussion without any great conviction.) In practice, it's unlikely that specifying methods which the listed types would need to satisfy would be very useful from a discriminated union viewpoint though I wouldn't necessarily rule them out altogether.

If you then embedded one restricted interface in another, the listed types would be the union of the listed types in the two interfaces and those types would need to satisfy the union of the listed methods (if any). In theory this could result in an interface which no type could ever satisfy but we already have that possibility with generic contracts so I don't think it's a fatal problem.

[xushiwei]

@griesemer

Regarding your last example (contract FooBarable) I don't understand that notation. At least as you have written, that contract is not permitted in the current design draft (each constraint in the contract must be preceded by a type parameter). More generally, a contract does not specify global functions ever - it's representing constraints on a type parameter. But more importantly, I don't see what you gain from being able to specify a specific set of global functions. Both Foo and Bar operate on any type that implements an io.Reader (for Foo) or an io.Writer (for Bar), respectively. Clearly, for Example to work, the type of t must support both. So what's wrong with XXX just being io.ReadWriter?

For a simple example, XXX just being io.ReadWriter is good. But if it is a complex example:

func ReadInt32(v *int32, ar io.Reader) { ... }
func ReadInt16(v *int16, ar io.Reader) { ... }
func ReadUint32(v *uint32, ar io.Reader) { ... }
func ReadUint16(v *uint16, ar io.Reader) { ... }

func Read(type T XXX; v *T, ar io.Reader) = (
    ReadInt32
    ReadInt16
    ReadUint32
    ReadUint16
    ...
)

In this case, XXX is very complex:

contract XXX(T) {
    T int32, int16, uint32, uint16, ...
}

When adding a new type for 'Read' function, we have to change both the 'Read' function and XXX contract to support this type.

If we support global function, we just define XXX contract as following:

contract XXX(T) {
    Read(v *T, ar io.Reader)
}

And now we just need to change the 'Read' function.

[xushiwei]

@griesemer

Regarding contracts: I am feeling very strongly that a contract is simply syntactic sugar for a set of interfaces. Specifically, given a general contract

contract C(T1, T2, ... Tn) {
T1 m11()
T1 m12()
...
T2 m21()
T2 m22()
...
}

In fact, contract C isn't the most general contract. It doesn't consider generic methods (ie. template methods). For example:

contract C(T) {
   T Read(type Reader io.Reader; v *int32, ar Reader)
}

Of course, we may disassemble it into:

type C interface {
    Read(type Reader io.Reader; v *int32, ar Reader)
}

But the interface 'C' isn't a normal interface, because it has a generic method. So we can't define a variable of 'C':

var xxx C  // BAD!!! we can't instantiate interface 'C', because it isn't a value.

[xushiwei]

func ReadArray(type T Readable, Archive io.Reader ; arr []T, ar Archive)

It sounds good. Only a little flaw needs to consider. For example:

func Foo(
    type A, B, C
    a A
    ) (B, C)

Because types A, B, C are declared in function parameters, It seems a little strange to use them in return types.

[alanfo]

Because types A, B, C are declared in function parameters, It seems a little strange to use them in return types.

Personally, I don't really regard that as a flaw.

The type parameters are, in effect, a kind of 'input' parameter (you either need to supply them explicitly when you call the function or they are inferred) and I don't therefore think it is inappropriate to include them with the function parameters, albeit roped off into their own section by the final semi-colon.

The type parameters may, of course, be used in the body of the function and would need to be if the result parameters are, or include, them. If the result parameters are named then they are effectively part of the body anyway i.e. they behave as if they were declared at the head of the body and initialized with their zero values.

But what really matters here is that the type parameters are declared after the function name and before they are used and both the existing generics design and the ; idea would achieve that.

It's only a suggestion anyway and as @griesemer intimated earlier we can worry about the syntax after the semantics have been sorted out. I've only commented on it at this stage as I wanted to express support for reducing the brackets needed which I think we all agree is a worthwhile objective.

[ianlancetaylor]

I've only commented on it at this stage as I wanted to express support for reducing the brackets needed which I think we all agree is a worthwhile objective.

A number of people have commented that the syntax in the current design draft makes sense to them, as it clearly expresses that type parameters are parameters and type arguments are arguments. While certainly a number of people don't like the additional parameter list, I don't think there is universal agreement that it is bad.

[alanfo]

While certainly a number of people don't like the additional parameter list, I don't think there is universal agreement that it is bad.

Sorry, I was being a bit presumptuous there :)

I don't think it's bad either but, after playing around with it a bit, I'd concluded that including the type and function parameters in the same set of parentheses was more readable. In fact I was going to suggest this (using the vertical bar character | as a separator) but was then persuaded that a semi-colon would be preferable for the reason @griesemer gave.

[deanveloper]

I actually like the parentheses-rich syntax that was proposed in the draft. It does get a bit verbose at times though, and stuffs too much information into a single line. However, the reason that I liked it is because it truly shows what a type parameter is, it's a type as a parameter to the function. This proposal takes that away, as it takes away the idea that one is essentially (but not literally) calling a function that returns a function with the given types that we want to use.

Also, (T) < (T) bool is technically incorrect as the < operator evaluates to an untyped boolean, not a bool, but that's probably not a big deal.

[ianlancetaylor]

Upon discussion with Go 2 proposal review committee, we would like to fold this issue into the general generics issue #15292. Please also feel free to add a link to this issue to https://golang.org/wiki/Go2GenericsFeedback. We don't think it will be helpful to keep multiple generics syntax issues open simultaneously, spreading the discussion to too many different places.

-- for @golang/proposal-review