proposal: Go 2: Type parameterized interface default methods

[smyrman]

This proposal is motivated by the following article. The proposal have some similar characteristics to #33410, but takes a different approach, and aims for the built-in types to implement interfaces rather than contracts. The proposal could hopefully take some inspiration implementation wise from the initial contracts proposal, where types where considered to implement a contract if a certain stub of code compiled.

The motivation for this proposal is to allow code based on interfaces to cover some (additional) generic use cases. The goal is not to create an extensive generics proposal, but rather to improve Go in a limited way that adds real value, and could make the language more fun and productive.

There is a lot you cannot do with this proposals, that you can do with other, more extensive, proposals; most noteworthy the latest contracts draft proposal. However, a goal would be for a final version of this proposal to be designed in such a way that it provides well founded building-blocks for adding more type parameterization to the language through future language feature proposals.

Proposal overview

The proposal is to allow an interface to declare default method implementations that utilize type parameterization of the method receiver type. The proposal should be differentiated from previous proposals to add interface default methods without type parameterization, in that this proposal can add real value. It is also distinguishable from other generics proposals in that it can likely allow existing code based on interfaces to be changed in a backwards-compatible way to support more types.

With the proposed default method implementations, a significant portion of the burden of implementing an interface can be moved from the package user to the package maintainer in some well-suited cases. A type that lacks a given function declared in the interface could be considered to still implement the interface if the default method implementation compiles for the given type.

The following characteristics will apply for interface default method implementations:

• An implementation's signature must match a signature declared in the interface method set. It is not possible to provide default implementations for any method signature that isn't part of the interface method set.
• A declaration is distinguishable from methods defined on types by the fact that the method receiver type is parameterized. It is not possible, as part of this proposal, to parameterize any other parameter type than the method receiver type.

The following characteristics match the behavior expected for other Go types:

• It is not possible to declare more than one default method with a given name or signature on a given interface.
• Interface default methods are inherited trough embedded fields the same way type methods are inherited for embedded fields in structs. When two or more embedded interfaces declare default implementations for the same signature, none of the implementations are inherited to prevent ambiguousness.
• Implementations of default methods on an interface override any implementation made available through embedded fields on the interface.

Example syntax

This is an example syntax only, used to illustrate the proposal.

The example syntax follows the following rules:

• If a method receiver type name is prefixed by a dollar-sign $, the type is considered to be parameterized. The compiler will need to replace all occurrences of $<TYPE NAME>, with the type that the method is being compiled for.

For this proposal in particular, the syntax can be used in two places:

1. For the receiver type of an interface default method declaration line.
2. To access the receiver type within an interface default method body.

type Equaler interface {
    Equal(other interface{}) bool
}

func (e $Equaler) Equal(other interface{}) bool {
    o, ok := other.($Equaler)
    return ok && o == e
}

This is the minimal syntax addition I can imagine for making the receiver type on a method parameterized. A final syntax should be developed to ensure that it's reusable for adding more generics functionality through later proposals.

Example use-cases

sort

Consider that the sort.Interface type is updated with the following type parameterized default methods:

type Interface interface{
    Len() int
    Less(i, j int) bool
    Swap(i, j int)
}
func (s $Interface) Len() int { return len(s) }
func (s $Interface) Less(i, j int) bool { return s[i] < s[j] }
func (s $Interface) Swap(i, j int) {s[i], s[j] = s[j], s[i] }

With this three lines of additional code, all of the following types would become eligible for direct use with the sort.Sort and sort.Stable functions:

• Slices of comparable types ([]<comparable type>)
• Maps of int to comparable types (map[int]<comparable type>)
• Fixed-size arrays of comparable types ([N]<comparable type>)

For cases where an adapter type is needed, e.g. []MyStruct, explicit method must only be added for the cases where the coo-responding default implementation doesn't compile:

// AscGivenName allows ordering users by GivenName in ascending order.
type AscGivenName []User

func (s AscGivenName) Less(i, j int) bool {
    return s[i].GivenName < s[j].GivenName
}

// AscSurname allows ordering users by Surname in ascending order.
type AscSurname []User

func (s AscSurname) Less(i, j int) bool {
    return s[i].Surname < s[j].Surname
}

Example of ordering by Surname, then GivenName through use of stable sort:

users := []User{ ... } // consider to contain several entries.
sort.Order(AscGivenName(users))
sort.Stable(AscSurname(users))

Room for future extension

An important goal for this proposal is to ensure that it can be added in such a way that it doesn't only fit orthogonally into existing Go language features, but in a way that facilitates future extension.

Perhaps everything described in the contracts draft proposal doesn't need to become possible, but there are some key concepts that I think should remain possible to implement.

E.g. I believe interface type parameterization must eventually be allowed more places. We can for instance imagine some form of the contracts draft proposal using interfaces in place of contracts:

type hasher interface {...} // built-in interface or contract

type SyncMap(K hasher, V interface{}) struct {
    l sync.RWMutex
    m map[K]V
}

func (sm *SyncMap(K hasher, V interface{})) Set(k K, v V) {
    sm.l.Lock()
    sm.m[k] = v
    sm.l.Unlock()
}

func (sm *SyncMap(K hasher, V interface{})) Get(k K) (V, bool) {
    sm.RLock()
    v, ok := sm.m[k]
    defer sm.RUnlock()
    return v, k
}

This is an indication that the example syntax used to illustrate the proposals isn't a good final syntax.

Further work

To proceed with this proposal, I need help. Here are some topics I can think of:

• Are there any obvious issues with this proposals that makes it hard to implement?
• Are there more use-case where this proposal will work well?
• Can a proto-type of this reasonably be implemented?
• Can a syntax be developed that works well for this proposal and allows future extension?

[smyrman]

I was just curious to see, if this was implemented (if it's possible to implement), how much of what's described in the contracts draft could we reasonably be able to do on top?

As an experiment I have attempted to rewrite parts of the contracts draft spec to make that assumption, and explore if we could write type parameterized types (as described in the contract draft proposal) without contracts.

• https://gist.github.com/smyrman/4f8c4201647b0bab4c196510a538e82c

The linked text is not actually a proposal, it's just an experiment.

Some personal assessments

Why not use interfaces instead of contracts?

It seams we can, just not all of the time. There are already two ways of defining contracts, so maybe one could use interfaces + something else...

(...) It is unclear how to represent operators using interface methods.

This seam to be solvable (for the most part) with the introduction of type parameterized interface default methods in a combination with applying type parameterization to the interface definition; interfaces are also types, so why not.

There is however at least one noticeable exception that I couldn't solve with interfaces alone: there isn't an obvious way (for me) to describe that a type must be viable for use as a map key in a type declaration. In the linked experiment I introduced something called kinds to work-around this, which is not to far from @pcostanza's suggestion of how contracts could work: #33410 (comment):

I should have been clearer: My suggestion is to have a list of predefined contracts, and not provide any means to define your own at all.

Kinds and interfaces with default methods have however a lot of overlapping use-cases that an actual proposal should iron out. Perhaps one should make way for the other, or perhaps they could be altered to behave as similar as possible.

Mutually referencing type parameters

It appears possible (maybe) to do this with a special variant of type parameterized interfaces that in the experiment is called "self-referencing interfaces". It appeared possible (although more complex to understand) with "normal" type parameterized interfaces as well. A question I cannot answer, is how easy it would be for the compiler to understand.

Either way, the contract based code appear more clear to me. This is defiantly one of the places where contracts appear to shine.

Accept a combination of built-in types and custom-types with relevant methods

This appears one of the main strengths of the interface default methods, and doesn't appear to be possible with use of contracts. This is illustrated by sort example above or as part of the type parameterized interface example in the experiment.

[griesemer]

This is a summary of the proposal as I understand it:

1. For each method m of an interface type T one may declare a default implementation (at most one).

2. The default implementation of a method m looks like any other method declaration except that a) the receiver type name T (which is the name of the interface) must be preceded with a $ as in $T, and b) the signature must match the existing method signature of m in the interface type.

3. Inside a default method, $T denotes the actual (concrete) type of the receiver.

4. A concrete (non-interface) type C implements such an interface T if C implements all methods which don't have a default implementation (more accurately: which don't have a default implementation that compiles for C).

(Then there is some fine print regarding embedding, etc. which doesn't seem relevant to understand the basic idea.)

First of all, I think this could be simplified: Instead of requiring that method signatures must match (which is only extra work for a compiler, and requires that two signatures be kept in sync by a programmer), why not simply permit that concrete methods may be added to an interface type as we allow for other types? Then we don't need the special rules. We can just write:

type Interface interface{}

func (s $Interface) Len() int { return len(s) }
func (s $Interface) Less(i, j int) bool { return s[i] < s[j] }
func (s $Interface) Swap(i, j int) {s[i], s[j] = s[j], s[i] }

The default methods would be part of the method set, of course, and they could be implemented by concrete types as before. The signature is the same. (This doesn't change the proposal's capabilities.)

The problem with this specific example though is that for many types, the default implementation doesn't compile (as you mention yourself), because many type don't understand indexing (in this example). In that case you suggest one has to provide default implementations for the relevant methods. But the only way to find out about this in general is by compiling the default methods (over and over, for each type C) again (note that a default method may be hugely complicated). Worse, the default method doesn't compile, it's not obviously clear what's wrong (with the concrete type) because the error depends on some implementation detail. This is something we absolutely want to avoid (and we do avoid it in the current contracts design draft). From a client's perspective it also seems odd that sometimes one doesn't have to provide an implementation for a default method, and sometimes one does, entirely depending on the internals of the default method.

Implementation-wise, default methods may often have to be custom-generated for each concrete type because they are effectively generic methods.

In summary, I don't see why we would not rather provide parameterized types and constraints (contracts) instead of a more restricted approach such as this which nevertheless has all the same problems. For instance, with the current contracts design, we can write:

// The existing sort.Interface.
type Interface interface{
    Len() int
    Less(i, j int) bool
    Swap(i, j int)
}

// A sort.Interface default implementation for a type T.
type Default(type T Indexable) T

func (s Default(T)) Len() int { return len(s) }
func (s Default(T)) Less(i, j int) bool { return s[i] < s[j] }
func (s Default(T)) Swap(i, j int) {s[i], s[j] = s[j], s[i] }

where Indexable is a contract that says that T must be a type that understands indexing (and thus len).

[smyrman]

Your understanding of the proposal is correct. The syntax is preliminary, but it is intended to work as you describe it.

Your suggestion for simplification by omitting the default method signatures in the interface declaration sounds good to me, if the proposal should continue developing.

On your criticism of accepted types being determined by implementation detail, you are of course also right. I think the proposal as it stands could work very well for small and short default implementation, but that obviously isn't something you could possibly guarantee. I hadn't fully realized the consequence of determining acceptable types based on implementation detail as the complexity of the default method grows. I also hadn't realized that this means backwards compatibility of a package could in principal be (more easily) broken with no change in the public interface, which sounds bad. Of course, the same is true today for functions accepting interface{} as it's up to implementation detail to determine what types are actually accepted. The only difference is that this happens runtime now, but will happen compile time with this proposal.

Moving on, to your example using contracts, do you mean that as an alternative to develop this proposal, or something that can be done in the draft contract design already today? Could you elaborate a bit more on how it would work? I want to point out that Indexable is not enough though, the Less function requires the < operator (while the others don't). It would be super cool if I could for a single implementation of sort.Sort pass in either a type that supports the < operator, say []int, or a type where I bring my own Less, say []MyStruct. Although not particular relevant in this example, the same goes for the other methods; it would be good to only implement what is absolutely necessary for each passed in type.

I think the desire of this proposal boils down to, for an incoming type:

• Allow both a built-in and a method-based implementation for an operation X.
• Allow writing a minimal amount of code to implement an interface.

[smyrman]

Solution to example using the latest generics proposal as I understand it:

type Interface interface {
	Len() int
	Less(i, j int) bool
	Swap(i, j int)
}

type comparable interface {
	type int, int8, int16, int32, int64, uint, uint8, uint16, uint32, uint64, float32, float64, string
}

type comparableSlice[T comparable] []T

func (s comparableSlice[T]) Len() int           { return len(s) }
func (s comparableSlice[T]) Less(i, j int) bool { return s[i] < s[j] }
func (s comparableSlice[T]) Swap(i, j int)      { s[i], s[j] = s[j], s[i] }

type comparableMap[T comparable] map[int]T

func (s comparableMap[T]) Len() int           { return len(s) }
func (s comparableMap[T]) Less(i, j int) bool { return s[i] < s[j] }
func (s comparableMap[T]) Swap(i, j int)      { s[i], s[j] = s[j], s[i] }

type Restraint[T comparable] interface {
	type Interface, comparableSlice[T], comparableMap[T]
}

Usage

a := []int{3, 2, 1}
sort.Sort(comparableSlice(a))

I guess the only improvement here, is if your could do just:

a := []int{3, 2, 1}
sort.Sort(a)

But maybe we actually can do this with the new type-list interfaces?

type Restraint[T comparable] interface {
	type Interface, comparableSlice[T], comparableMap[T]
}

func Sort[T comparable](data Restraint[T]) {

  /// no code changes.
}

[smyrman]

This doesn't currently seam to work in the playground:

• https://go2goplay.golang.org/p/WEbvPoVL_ra

The variant not defining a Restraint type list, does indeed work:

• https://go2goplay.golang.org/p/zKS1FII7bJi

[ianlancetaylor]

Thanks, but now that Go has generics, we aren't going to do this.

[evanphx]

@ianlancetaylor Sorry to bring this up again, I'm curious how you see generics solving this? I gave it a shot and ran into the case here:

type Wrapper[T Sort] struct {
  T
}

Attempting to create a wrapper type so that wrapper can define it's own default versions. But the current generics do not allow this. Perhaps I'm missing something then, I'm unclear how generics close the gap with regard to default implementations on interfaces.

Thanks! (and sorry again for ping an old, closed issue).