Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

proposal: go 2: a simpler approach to generics with "concrete" interfaces #33627

Open
ghost opened this issue Aug 13, 2019 · 4 comments

Comments

@ghost
Copy link

commented Aug 13, 2019

A summary is available at the end for the less patient of you!

The problem with contracts

Much constructive criticism has already been expressed against contracts. Here is a brief list of good arguments I've read:

  • It does not provide a clean, systematic way of indicating which operations are allowed on a type. For example, two different contracts may describe the same idea in two very different ways (taken from this blog post):

    contract comparable(t T) {
        t == t
    }
    
    contract mapkey(t T) {
        var _ map[t]bool
    }
    
  • They can also describe very different things even though they look similar. Consider this example:

    contract add(t T) {
        t = t + t
    }
    
    contract mult(t T) {
        t = t * t
    }
    

    It looks like both would refer to numeric types, right? Not quite: add is also compatible with string.

  • But there is more: mult implicitly allow operations that would most likely not produce a compilation error:

    func Halve(type T mult) (a T) T {
        return a / 2
    }
    

    The whole point of contracts was that you state what you can do with a type outside of the function body. Will programmers be thorough enough in explicitly listing all the operations they need if some can be omitted? I don't think so.

  • On the contrary, it can and will end up as a game of one-lining constraints, akin to the (c = getchar()) != EOF && isalpha(c) ? toupper(c) : '\0' follies in C and C++:

    contract pointer(t T) {
        t == nil
    }
    
    contract magic(t T) {
        (t + t) == string(t)
    }
    
    contract impossible(t T, s S) {
        t == ((s + t) == t)
    }
    

    Is it clear that pointer could be a slice or a map as well? How about magic, what could it even be? Will the compiler produce an error if a contract is impossible? The horrors of real-world code should not be underestimated.

  • A contract exposes the internals of types to the users: it can be both exported and require a given type to be implemented in some way only, which is for example a huge step back from the decision of leaving fields out of interfaces.

  • A substantial amount of the standard library and existing code from the outside world may end up being rewritten with contracts to only mimic what was done with interfaces until now, leading to projects with a random mixture of contracts and interfaces depending on each contributor's habit on the matter.

  • It is overall too clever, as formulated by Chris Siebenmann. He also adds:

    Go contracts do not seem designed to be read by anything but the compiler. This is a mistake; computer languages are in large part about communicating with other people, including your future self, not with the computer.

  • Operators can only be used on the very small set of primitive types anyway: the amount of distinct, meaningful contracts that can be written with operators is thus very small. It means that in general, a contract will describe the methods and fields of a composite type, making it a lot like an extended, generic version of interfaces.

This is exactly what I am going to present next: an extended, generic version of interfaces.

A case study

Let's say we want to write a generic Min() function. It should probably look like this:

func Min(a T, b T) T {
    if a.Less(b) {
        return a
    }
    return b
}

It is ambiguous whether T refers to an existing type, or any type. We still want the compiler to report errors when mistakenly using non-existent types, so at least we need a way to indicate that T is a parameter as well. The syntax proposed in the current draft design is almost just fine:

func Min(T type) (a T, b T) T {
    ...
}

See how the position of type differs from the draft: by switching it at the end, it now looks like a function definition — which it is, since we use generic functions just like functions on types:

// More on that import later
import "types"

var minInt = Min(types.Int)

It eliminates the cognitive burden of using Min(types.Int) just like a function, but defining it a different way. In short, it just reads better.

But this is not all, it also enables two possible additions to the language in the future that would then fit naturally:

  • "Pseudo-"partial applications, by extending the idea of "chaining" parameter lists to build higher order functions:

    func SumOfThree(a int) (b int) (c int) int {
        return a + b + c
    }
    
    f := SumOfThree(2)  // f is of type func(int)(int) int
    g := f(3)           // g is of type func(int) int
    fmt.Println(g(4))   // Prints 9
    

    I say "pseudo-"partial because technically this wouldn't be allowed:

    func SumOfThree(a, b, c int) int {
        return a + b + c
    }
    
    fmt.Println(SumOfThree(2)(3)(4)) // WRONG
    

    That is, Go wouldn't have full currying. Which is good, as forgetting an argument would raise an error at compilation, instead of silently producing a partial application.

  • type reads a lot like the "type" of T. Why not add new "types" of types, then? They could be used to introduce new semantics on type parameters:

    // A possible solution to our example, see further down
    func Min(T ordered) (a T, b T) T {
        ...
    }
    

    In my opinion, it would look much better than the current draft design:

    func Min(type T ordered) (a T, b T) T {
        ...
    }
    

    Note that in the current draft design ordered would be a contract, which means that we could very well still add contracts as "types" of types in the future if what I suggest next is implemented.

Now back to our example. We want to indicate that T should have a method called Less(), which takes an argument of type T and returns a boolean. If T was known, then what we would need is exactly an interface; it makes perfect sense to first attempt to extend the semantics of interface to something that works for any T. By reusing the same syntax, we could try:

type Ordered(T type) interface {
    Less(T) bool
}

func Min(T type) (a Ordered(T), b T) T {
    if a.Less(b) {
        // Wait a minute...
        return a
    }
    return b
}

This is actually wrong: we don't know that a is of type T! What I suggest is extremely simple... Embed T to indicate that Ordered(T) should behave like T:

type Ordered(T type) interface {
    T
    Less(T) bool
}

It only makes sense when you think of it with other interfaces:

type WithClose(T type) interface {
    T
    Close() error
}

type ReadCloser WithClose(io.Reader)

I call this a "concrete" interface (hence the title): it specifically refers to a given type in contrast with "normal" interfaces, referring to any type matching their description.

I feel that a number of points need to be addressed before continuing any further:

  • Writing it differently, such as:

    type Ordered(T type) interface {
        T Less(T) bool
    }
    

    much like how it is suggested for contracts would not only look weird, but would also become unnecessarily repetitive, and would allow to write impossible declarations:

    type Numbers(T, S type) interface {
        T One()
        T Two()
        T Three()
        S Four()    // IMPOSSIBLE
    }
    

    The last case is possible if, and only if T == S which has no reason to occur in real-life situations and most probably is a bug, so it should raise an error at compilation anyway. The proposed syntax avoids this error, and repetitions as well.

  • For the same reason, the following code:

    type Union(T, S type) interface {
        T
        S
        ...
    }
    

    should produce an error at compilation since, in general, T != S. That means a concrete interface must be associated with exactly one type parameter. If there are zero associated types, then basically it is a normal generic interface. If there are more than one, then it is an error.

  • If we have, for example:

    import "net/http"
    
    type WithGet(T type) interface {
        T
        Get(string) (*http.Response, error)
    }
    
    var c WithGet(http.Client)
    

    What is the type of c? Of course, it should be http.Client. That means a concrete interface acts like an assertion on type properties at compilation: it takes a type as an argument, and returns it if it corresponds to the specifications, otherwise the compilation fails. This is why I strongly advise naming concrete interfaces with the prefix With to indicate that a particular property is expected. Our initial example would be better rewritten as:

    type WithOrder(T type) interface {
        T
        Less(T) bool
    }
    
    func Min(T type) (a, b WithOrder(T)) T {
        if a.Less(b) {
            return a
        }
        return b
    }
    
  • Embedding other concrete interfaces should be possible, but recursion on the associated type forbidden:

    type WithOrder(T type) interface {
        T
        Less(T) bool
    }
    
    type WithClose(T type) interface {
        T
        Close() error
    }
    
    type WithOrderAndClose(T type) interface {
        // As it embeds concrete interfaces associated with the same
        // type T, embedding T is not required
        WithOrder(T)
        WithClose(T)
    }
    
    type Recursion(T type) interface {
        T
        Recursion(T) // IMPOSSIBLE
    }
    

    Note that embedding concrete interfaces is equivalent to chaining their application:

    var x WithOrderAndClose(SomeType)
    
    // Equivalent
    var x WithOrder(WithClose(SomeType))
    

A first major drawback is that you can't specify fields with an interface, which is a good design decision in my opinion. I assume that the initial philosophy was that when exporting an API, only how you can interact with an object matters, not its inner working. Contracts, on the other hand, allow exposing the internals to the users, and may restrict how a structure is implemented.

If yet, such a possibility is desired, we could naively think at first of some way using generic structures. Let's say, for a new example, that we want to write a generic ValueOf() function that takes a structure with a Value field, and return its value:

func ValueOf(T, S type) (x T) S {
    return x.Value
}

Following the same logic than with interfaces, we would think of something similar to this:

type WithValue(T, S type) struct {
    T
    Value S
}

type Integer struct {
    Value int
}

func ValueOf(T, S type) (x WithValue(T, S)) S {
    return x.Value
}

// Wait a minute...
fmt.Println(ValueOf(Integer, int)(Integer{12))

... This time, WithValue(Integer, int) is not the same type as Integer! Indeed, it has an extra Integer field representing the embedded structure.

At this point, there are two solutions:

  • Abandon the possibility to specify fields, in accordance to the principle that the internals should not be fiddled with by the outside world

  • Extend the semantics of concrete interfaces again to indicate which fields are required, with the exception that exporting such an interface, or a function using such an interface is an error at compilation:

    // Not exportable
    type withValue(T, S type) interface {
        T
        Value S
    }
    
    // Not exportable
    func valueOf(T, S type) (x withValue(T, S)) S {
        return x.Value
    }
    

I strongly support this second option. Since interfaces containing field requirements cannot be exported, there is good practice to write separate, unexported interfaces containing field requirements only. It would still be very useful inside of a package to indicate constraints, and would prevent exposing the internals of the package when used by someone else.

The second drawback is what probably motivated the idea of contracts in the first place: operators. In our example with Min() I took great care of writing a.Less(b) instead of a < b, and for a very good reason: for as long as Go refuses to implement operator methods (I don't hold an opinion on that), there will be no choice but to write two versions of every function working on both composite and primitive types:

contract ordered(t T) {
    t < t
}

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

func Min1(type T ordered) (a T, b T) {
    if a < b {
        return a
    }
    return b
}

func Min2(type T withLess) (a T, b T) {
    if a.Less(b) {
        return a
    }
    return b
}

Whether contracts are implemented or not in the end, code duplication will still occur with primitive types. Since composite types are more frequent than primitive types, a generic function will most likely end up using methods rather than operators; therefore using methods should be preferred. Given this perspective, we should try to find a suitable solution with interfaces one more time, using what the language already permits.

As stated before in the preliminary criticisms of contracts, some operators are implicitly allowed (t * t implies t / t), others don't make sense when used together (for example t && t and t + t), and overall the set of meaningful contracts using operators is very small. An excellent idea brought forward by Matt Sherman, and named by Axel Wagner are "pseudo-interfaces". Instead of adding a way to list which operations are possible, we add a small set of builtin identifiers grouping operators that only make sense together:

Pseudo-interface Allowed operators
comparable ==, !=
ordered <, <= > >=
boolean ||, &&, !
bitwise ^, %, &, |, &^, <<, >>
arith +, -, *, /
concat +
complex real(z), imag(z)
nilable v == nil
pointer *v
...

As the name suggests, they can be used like interfaces:

type num interface {
    comparable
    ordered
    arith
}

func GreaterThanThree(a num) bool {
    return a > 3
}

A number of derived interfaces could be predeclared as well:

Pseudo-interface Definition
num interface { comparable; ordered; arith }
integral interface { num; bitwise }
...

With a set of sane, predeclared pseudo-interfaces, developers would only need to refer to the standard Go documentation to find out what they mean, instead of tediously trying to guess what a contract implies:

contract num(t T) {
    t == (t - (t * t))  // Is it obvious?
}

A small issue arises when you think about how to write a generic Min() function again. We still need to know what type we're referring to, as ordered in our case is merely an interface. The code would then look like this:

type WithOrder(T type) {
    T
    ordered
}

func Min(T type) (a, b WithOrder(T)) T {
    if a < b {
        return a
    }
    return b
}

Of course, it works. But we'd rather write the function this way:

func Min(T ordered) (a, b T) T {
    if a < b {
        return a
    }
    return b
}

I suggest we might as well just do that: pseudo-interfaces (and them only) can also be used as "types" of types as it was referred to earlier:

func Select(T num, S type) (z T, a S, b S) S {
    if z == 0 {
        return a
    }
    return b
}

At last, we still have the problem that every generic function will have to be written twice: one for the primitive types, one for the composite types. As a convenience, and for performance reasons, I would encourage the introduction of a new "pseudo-"package named types, which provides a number of structures and interfaces wrapping the operations on the primitive types:

package types

type Int struct {
    ...
}

func (i Int) Add(j Int) Int {
    ...
}

func (i Int) Less(j Int) bool {
    ...
}

This way we can write a definitive, generic Min() function that also applies
to integers:

import "types"

fmt.Println(Min(types.Int{5}, types.Int{3}))    // Prints 3

Using dark magic with the compiler, we could natively translate types.Int into int at compilation, avoiding the extra overhead of wrapping everything into an actual structure with methods. The package don't really exist as source code, hence the prefix "pseudo". A number of generic structures could be provided by types as well:

import "types"

var m types.Map(string, int)
m.Set("foo", 5)

fmt.Println(m.Get("foo"))   // Get has signature func(string) (int, bool)
fmt.Println(m.Get("bar"))   // Prints 0 false

If methods from types are assigned (for example f := m.Get) or the types from types are embedded to create substructures, the compiler could fall back to an actual implementation of the structures in pure Go. Since these types would be standard and supposedly widely used, we still may find ways to optimize such situations in the future, to the benefit of everyone.

types could also include concrete interfaces, being the general counterpart of the aforementioned pseudo-interfaces:

Interface Definition
comparable ==, !=
types.Comparable interface(T type) { T; Equal(T) bool }
...

That is, if type x is compatible with pseudo-interface p, then type types.X (notice the capital letter) is compatible with concrete interface types.P. This would break the rule of naming concrete interfaces with the prefix With, but at least it is memorable and coherent with everything else. We can write at last:

import "types"

func Min(T type) (a, b types.Ordered(T)) T {
    if a.Less(b) {
        return a
    }
    return b
}

Summary

  • Invert the syntax to declare type parameters, and make it look like a function declaration. (type T) becomes (T type):

    // Can also be written as (K, V type)
    func Keys(K type, V type) (m map[K]V) []K {
        ...
    }
    
  • Exactly one type argument can be embedded to a generic interface, turning it "concrete":

    // Name should always start with "With..."
    type WithClose(T type) interface {
        T                // Type embedding should go at the top
        Close() error
    }
    
  • A concrete interface should be read in code as an assertion on a type, returning the type if the assertion succeeds:

    type WithAny(T type) interface {
        T
    }
    
    var x WithAny(int)   // x has type int
    var y WithClose(int) // ERROR! int does not have a Close() method
    
  • A normal interface embedding a concrete interface turns into a concrete interface, because of the rule stated above:

    type WithReadAndClose(T type) interface {
        WithClose(T)                 // Same as embedding T
        Read([]byte) (int, error)
    }
    
  • Fields can be specified by an interface, but then the interface cannot be exported:

    // Name must start with lower case
    type withValue(T, S type) interface {
        T
        Value S
    }
    
  • A function using an interface specifying fields cannot be exported either:

    // Name must start with lower case
    func valueOf(T, S type) (x withValue(T, S)) S {
        return x.Value
    }
    
  • A number of identifiers, called "pseudo-interfaces", are added to access operators: they can be used like interfaces, and group operators together in a meaningful and documented way:

    type num interface {
        comparable   // They can be embedded, and start with lower case
        ordered      // ordered is compatible with any type using <, <=, >, >=
        arith
    }
    
    func GreaterThanThree(a num) bool {
        return a > 3
    }
    
  • Pseudo-interfaces can also be used as "types" of types to concisely refer to type parameters on which operators can be used:

    // Note how (T type) has changed into (T ordered)
    func Min(T ordered) (a, b T) T {
        if a < b {
            return a
        }
        return b
    }
    
  • A new package named types is added to provide a standard interface to primitive types and ease the writing of generic functions:

    import "types"
    
    x, y := types.Int{5}, types.Int{3}
    fmt.Println(x.Less(y))               // Prints false
    
    var m types.Map(string, int)
    m.Set("foo", 3)
    if v, ok := m.Get("foo"); ok {
        fmt.Println(v)                   // Prints 3
    }
    
  • types exports the composite counterpart of primitve types and pseudo-interfaces by using a capital letter:

    import "types"
    
    // types.Ordered(T) requires T to have a method Less(T) bool
    func Min(T type) (a, b types.Ordered(T)) T {
        if a.Less(b) {
            return a
        }
        return b
    }
    
  • The current draft proposal on generic structures is just fine, with the extra care that structures using concrete interfaces specifying fields cannot be exported either:

    type Tree(T type) struct {
        Node     T
        Children []*Tree(T)
    }
    
    // Not exportable
    type valueTree(T, S type) struct {
        Node     withValue(T, S)
        Children []*valueTree(T, S)
    }
    

EDIT. Just to be clear, type Name(T type) keyword { ... } is sort of (but not exactly) syntactic sugar for Name := keyword(T type) { ... }, pretty much how func Name(a Type) { ... } is sort of (but not exactly) syntactic sugar for Name := func(a Type) { ... }. I see no reason to forbid writing things like this:

var x struct(T type) { Value T }(int)

What do you all think?

@gopherbot gopherbot added this to the Proposal milestone Aug 13, 2019

@gopherbot gopherbot added the Proposal label Aug 13, 2019

@target-san

This comment has been minimized.

Copy link

commented Aug 15, 2019

Disclaimer: I read only summary section, keep that in mind.

Overall this looks really interesting except few things

  1. Making whole interface concrete is a big restriction IMO. Maybe it would be easier to introduce Self pseudo-type to interface declaration and make any method which uses it "concrete". Then, "concrete" methods cannot be used in dynamic context.
  2. I'm not sure about "interface fields" part.
@ghost

This comment has been minimized.

Copy link
Author

commented Aug 15, 2019

@target-san I'm not exactly sure to understand what you mean, but "concrete" was just a word I came up with to describe the property of a generic interface to be associated to one of its type parameters. How it translates into an actual implementation is still to be worked on. In particular, it would be nice to be able to write type ReadCloser WithClose(io.Reader) and mean it : following a basic substitution rule should produce an interface identical to io.ReadCloser. My goal was to avoid coming up with new keywords, or notions that would cover part of what you can almost already do with interface, so I don't really know about "self pseudo-types".

EDIT. More on concrete interfaces: I see that I wrote they "should be read in code as an assertion on a type", but this is just a hint in how the programmer should think when they see one, not an actual rule on how they should be implemented. It's easier to remember that WithClose(T) means that we test whether type T has a Close() method rather than how things are operated in the background.

On the "interface fields" part I anticipated it would be hard to accept. This is why I suggested forbidding to export interfaces using them in order to sort of keep the original spirit of interfaces (which is in my opinion, as I state in my presentation, a good design decision from the original authors). Or, we could still set this aside and maybe make a decision in a later version of Go 2; and be content with generic structures for now. Maybe this would require a deeper analysis of the existing real-world codebase to decide whether it should be added or not.

@ianlancetaylor

This comment has been minimized.

Copy link
Contributor

commented Aug 16, 2019

Your discussion about contracts appears to refer to the earlier draft. Please take a look at the most recent draft (https://go.googlesource.com/proposal/+/master/design/go2draft-contracts.md) as it has significant differences.

It would help if you could explain how to implement the Graph/Nodes/Edges idea with your suggested syntax. Thanks.

@target-san

This comment has been minimized.

Copy link

commented Aug 19, 2019

@ianlancetaylor
I guess OP's main idea is "why have separate entity for compile-time interfaces?".

@kantbell
On the other hand, unification of interfaces and contracts looks a bit questionable. While they partially "overlap" semantically, they cover different sub-domains of language polymorphism. Such unification will require smth similar to Rust traits, which in turn are more powerful yet more complex than interfaces and traits combined. I doubt core team would pursue such goal.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Projects
None yet
3 participants
You can’t perform that action at this time.