Go: proposal: Go 2: Generics based on contract switches

[hdu-hh]

I'm proposing some extensions to the contract proposal. The design has some merits

• it feels like Go
• it allows generics to work with fundamental and custom types
• it meets the goals stated for Go generics

The proposal extends the Go 2 contracts (generics) draft design in four ways:

• contract outcomes
• contract switches
• customized error reporting
• multiple contracts per generic type

The gist of it is that the use of contracts should be explicit.
For this contracts should act as their own adapters.
Fundamental and custom types can be coerced to behave in a common way.
The proposed contract switch is essential for this.
Contracts need to become real executable code with a few special rules.

Contract Outcomes

Contracts can declare their intended outcomes. They become real code for adapting types to this outcome:

contract WithLength(a T) int {
    return len(a)
}

Applying contract outcomes

Contract outcomes can be applied directly:

func Max(type T Less)(first T, other ...T) T {
    max := first
    for _, val := range other {
        if Less(max, val) {
            max = val
        }
    }
    return max
}

var x = Max(5, 3, 8)

Contracts with no declared outcomes cannot be applied.

As types can abide multiple contracts it is helpful to know which contract is applied where. Using the contract name for that purpose led to a design with contracts becoming their own adapters.

Contract Switches

Contract switches react on the semantics of their case statements.

contract Less(a,b T) bool {
    switch {
    case: return a.Less(b)
    case: return a < b
    }
}

Case statements with semantic errors are silently ignored. Syntax errors are treated as always.
The first applicable case statement is taken.

A type is considered to abide a contract if there is a valid code path to an explicit return statement.
Contracts without declared outcomes don't need the return statement though.
This allows contracts to steer types to behave in the most suitable way if any.

Control Flow Constraints

In contracts the control flow must not change outside of contract switch case statements.

Customized Error Reporting

Contracts may customize error reporting for specific cases. A code path that ends in a panic() reports its message as error:

contract Hash(t T) uint {
    switch {
    case: t = []byte{}; panic("byte slice hashing is not supported yet")
    case: return t.Hash()
    case: return uint(t)
    }
}

Multiple Contracts per Generic Type

Conformance to multiple contracts is a common trait of types.
Requiring extra contracts just to combine them is bothersome,
so a syntax for declaring multiple contracts per generic type is proposed:

type HashMap(type K Equal*Hash, type V) struct {
    buckets [][]struct{key K; val V}
}

contract Equal(a, b T) bool {
    switch {
    case: return a.Equals(b)
    case: return a == b
    case: return string(a) == string(b)
    }
}

contract Hash(t T) uint {
    switch {
    case: return t.Hash()
    case: return uint(t)
    }
}

[ianlancetaylor]

This is a big step toward metaprogramming, in which programs include code that is executed at compile time. That is a significant increase in language complexity.

[DeedleFake]

Although I'm rather wary of metaprogramming, I definitely agree with the intent of this proposal, which seems to be primarily a way to adapt operators to methods/functions in a way that is limited only to use of contracts/generics. Due to the lack of operator overloading, which is _not_ something that I want to see in the language, generics in the current draft are incapable of closing certain typing gaps, namely that of built-in types and user-defined ones. This means that in a lot of cases you'll still wind up needing multiple copied definitions of something, such as a binary tree. Should it use < or a Less() method? I think that some way of fixing this discrepancy is a must-have in any kind of finalized generics design.

There was some talk about a contracts package that would have some predefined contracts. Maybe it could have some special contracts that allow things not otherwise possible. For example, a contracts.Less which matches types with a Less(T) bool method but also matches a < operator. Using the type inside of a function that uses the contract requires the use of a Less() method, though.

In other words:

func Min(type T contracts.Less)(v1, v2 T) v1 {
  if v1.Less(v2) {
    return v1
  }
  return v2
}

type Example struct { v int }

func (e Example) Less(other Example) bool { return e.v < other.v }

func main() {
  Min(Example{2}, Example{5}) // Valid.
  Min(3, 2) // Also valid, despite the lack of methods on built-in types.
}

Not sure how I feel about having special, otherwise undeclarable contracts, though. Or maybe there could be some other way to do this, like a special syntax that's only legal inside of contract definitions that means essentially the same thing as this. contract Less(T) { T < T }, for example. That would require explicit definition of contracts, though, and it also kind of makes things like contracts.Numeric pointless.

Whatever the case, I definitely think that calling operators via methods is definitely a better direction than the reverse.

[ianlancetaylor]

For the specific case of < vs. Less, my current thinking is

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

contract LessableOp(T) {
    T int8, etc.
}

type WrapLessableOp(type T LessableOp) T
func (w WrapLessableOp(T)) Less(v T) bool { return w < v }

Now when calling a generic function that takes a type argument that implements Lessable, if you have a type that implements <, you can pass WrapLessableOp(T).

But I haven't really thought this through and I don't know how well it will work in practice. In particular it seems to break type inference. So more thought is needed.

[hdu-hh]

This is a big step toward metaprogramming, in which programs include code that is executed at compile time. That is a significant increase in language complexity.

In the proposal the contract code is not executed at compile time. It is just checked for semantic errors for given types to identify its iinstantiable function. E.g. in the Max(3,5,9) example T is an int and the Less contract becomes something like:

func Less_int(a,b int) bool {
    //switch {
    //case:
    //  return a.Less(b) // ignored because type int has no field or method Less
    //case:
        return (a < b)
    //}
}

i.e. with the commented out code removed

func Less_int(a,b int) bool { return a < b }

The instantiation of the Max function would be Max_int() which calls the easily inlined Less_int().

[ianlancetaylor]

This characteristic--don't compile invalid code--is at the core of C++ template metaprogramming, where it is known as SFINAE (https://en.wikipedia.org/wiki/Substitution_failure_is_not_an_error).

[hdu-hh]

This characteristic--don't compile invalid code--is at the core of C++ template metaprogramming, where it is known as SFINAE (https://en.wikipedia.org/wiki/Substitution_failure_is_not_an_error).

I'm aware of that as I borrowed the SFINAE idea from C++ and adapted it to go by removing its horrors:

• all that is needed is in the one contract instead of being distributed all over the source
• using real code instead of type declaration marathons such as this example monster from fluentcpp

template<typename T_ = T>
    void f(T&& x,
           typename std::enable_if<!std::is_reference<T_>::value,
           std::nullptr_t>::type = nullptr);

[DeedleFake]

@ianlancetaylor:

Now when calling a generic function that takes a type argument that implements Lessable, if you have a type that implements <, you can pass WrapLessableOp(T).

The blog post that went up today mentioned that

A different way of using interfaces for generics, which could get around the need to write the methods yourself, would be to have the language define methods for some kinds of types. That isn't something the language supports today, but, for example, the language could define that every slice type has an Index method that returns an element. But in order to use that method in practice it would have to return an empty interface type, and then we lose all the benefits of static typing.

Generics solve this problem, though. You could have a built-in At(int) T method on slices with a return type that matches the element type of the slice. Then, if you want to do generic slice operations, you can just use

contract Index(T, E) {
  T At(int) E
}

And now not only can a function that uses that contract use user-defined indexable types, but slice-types would just work without the need to create a manual wrapper every time you want to use a built-in type. The mappings of operators to methods could be listed in the builtin pseudo-package for documentation purposes.

This doesn't solve the other problem that this proposal does, though, in that it doesn't allow you to write specialized code paths for specific types. In other words, you can't have it handle ints differently than other valid types for optimization purposes, for example.

[rocket049]

Not very beautiful!
I like this:

func Mehthod(a T, b E) int : type T ,E {
    var res int
    ......
    return res
}

It is easy to parse and not need to change common functions.

[hdu-hh]

The new blog post mentioned above is very interesting:

• The inverse operator overloading shrinks the gap between builtin and custom types which is also an important goal of this proposal.
• The tree in the blog post with its compare function would already be very useful, but it may be hard to inline the compare functions so that quite some optimization potential is lost compared to containers with behavior defined by their type. This proposal allows type trait specific code paths that help with such containers and also for treating strings as []byte, using boxing for bigger types, optimized handling for constants or bools.

[hdu-hh]

Thinking more about the inverse operator overloading hinted at in the blog article: they are just wonderful. Thanks @Deedlefake for highlighting that important part and for following it up with #33410 for advancing this great idea.

And for the blog's container example with function references it would also be possible to replace function steered generics with functor steered generics that have their behavior baked in, which would allow all optimizations possible from inlining, unrolling, vectorizing, eliminating, etc.

That is a good way. The type specialization of this proposal that would allow further improvements (e.g. treating strings as []byte, using boxing for bigger types, optimized handling for constants or bools) can be reintroduced when generics are established in golang. Then the switch statement reacting on semantics proposed here may come in handy again. I'm withdrawing my generics proposal. Thanks for the feedback and insights!