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: refined generics design #39328

Closed
sorenvonsarvort opened this issue May 31, 2020 · 10 comments
Closed

proposal: Go 2: refined generics design #39328

sorenvonsarvort opened this issue May 31, 2020 · 10 comments

Comments

@sorenvonsarvort
Copy link

@sorenvonsarvort sorenvonsarvort commented May 31, 2020

Refined Generics Design

Hey, dear community. Here is my vision on generics.

Features

I believe I have got achieved this qualities with my design. Still I could make some mistakes. So here is what I at least aimed at:

  1. Backwards-compatibility
  2. Easy to implement
  3. Easy to use (and the design already got some guidelines and methodology)
  4. Solves some problems
  5. Doesn't make new
  6. Compile-time application

Abstract

Contracts Concept

Current design is great. Still I believe the issue with the contracts concept is that they have too much granularity. My arguments are:

  1. Contracts boil down to specifying what types do we basically support. So why not to specify them directly, not just by saying what operators do we want them to support?

  2. What if we do want some function to be implemented only for, say, int8 and int32 for some weird reason. Do the contracts help much?

  3. Golang has types that support several kinds of operators at once. But, for example, it doesn't have any type bitwise that has bitwise operators support only.

That's to say, we cannot write such a code:

func main() {
    var a bitwise = something
}

Defining a contract supporting bitwise operations means involving int8, int16 and so on.

Proposed Design

Basically, we got two problems when we think generics are the solution. First one is when we need to convert an []int variable to an []interface{} one (or similar). The second is when we need to convert a func(a int) variable to a func(a interface{}) one (or similar). Or vise-versa. Let's call these two processes "generalization" and "specialization" like in the previous design draft.

So, we are introducing 6 new expressions to the language:

  1. Generic type
type T // generic type T definition, it can be specialized basically to any value
type addable int | int8 | int16 | int32 | int64 // generic type addable definition, type addable can be specialized only to int or int8 or int16 and so on.
  1. Type generalization
// the syntax is much like one of function
// we defining our type array parametrized by a new type T
type array(type T)[]T
  1. Type specification
// array(int) expression is the same as []int expression
var items array(int) = []int{1, 5, 3}
  1. Generic function

Generic function is a function having a generic parameter (like t T). But it can have 0 parameters and be generic too. More precise definition and full syntax is on the next point

  1. Function generalization
// Do is a function generalization parametrized by a type T returning a function having a generic parameter `a T`
func Do(type T) func(a T) {
    // we do return a generic function pretty much like a closure
    return func(a T) {
        
    }
}

func main() {
    // Do(int) is a function of type func(int)
    var doInt func(int) = Do(int)
    do(5)
}

The compiler can easily infer the type of doInt

func main() {
    doInt := Do(int)
    do(5)
}
func Do(type T) func() {
    // it also can have 0 parameters and still it is generic
    return func() {
        
    }
}

Function generalization is a separate expression in the language evaluating to a function. And it can also have a "switch by generic type" expression in it.

func Add(type T) func(a, b T) T {
    switch T {
        case string:
        return func(a, b string) string {
            return a + b
        }
        
        default:
        // we cannot write T here, since it is a generic type, but we are expected to return a specific one, like int
        return func(a, b T) T {

        }
        // What do we need to return here? nil?
        // Maybe the compiler needs to infer by itself what type is there
        // Or maybe we need some other syntax like this instead of "default" case
        
        case Z := T: // Z captures a specific type of T
        // and now we are able to return such a function, since it has got correct signature with all specific types
        return func(a, b Z) Z {
            return Z{} // zero value of type Z?
            // we cannot return a + b
            // since type Z is an unknown type
        }
    }
}
  1. Function specification
func main() {
    var addInt func(a, b int) int = Add(int)
    var x int = addInt(1, 3)
}
type Array(type T) []T 

type Predicate(type T) func(a, b T) bool

// You can write directly []T instead of Array(T) this is done only for illustration purposes
func Sort(type T) func(Array(T), Predicate(T)) {
    return func(items Array(T), check Predicate(T)) {
        // sorts by a predicate
        
        // we can range, since items is []T
        // but we cannot perform `item + item` operation, for example, since we do not know what is T
        for i := 0; i < len(items); i++ {
            if check(item[i], items[i+1]) {
                // ...
            }
        }
    }
}

func main() {
    var longer Predicate(string) = func(a, b string) bool {
        return len(a) > len(b)
    }

    sort := Sort(string)

    items := Array(string){"x", "xxxx", "", "xxxxxxxx", "xx", "xxx"}

    sort(items, longer)
}

Do we really need to flip type T into T type? I guess no, since we've got no first-class types and do not support runtime specialization.

When we write type T - it really defines some internal type called T and parametrizes a type or function.

When we write T type - that means we have an argument of type type which is kinda strange.

Here is an example of function that uses a generic type, but it specializes it staying specialized too (and not generic).

type array(type T) []T

func Do(a array(int), b int) {
    return []int, 0
}

There is no problem with defining a generic function with several parameters.

func Add(type T, type Z) func() {
    return func() {

    }
}

func main() {
    add := Add(int, string)
}

This design also compatible with functions having receivers. But it does not really make them useful:

type MyType int

// we define a generalized type T and specializing it right after the definition
func ((type T)(MyType)) Add() {

}

func main() {
    var x MyType := MyType(1)

    x.Add()
}

What about interfaces?

// useless version
type Z interface {
    Do((type T)(int)) 
}

// useful version
type X (type T) interface {
    Do(T)
}

type z int

func (z) Do(int) {
    fmt.Println("1")
}

type x int

func (x) Do(int) {
    fmt.Println("2")
}

type s int

func (s) Do(string) {
    fmt.Println("3")
}

func main() {
    var zSample Z = z(0)
    zSample.Do(4) // prints 1

    var xSample X(int) = z(0)
    xSample.Do(8) // also 1

    var xSample2 X(int) = x(0)
    xSample2.Do(11) // 2

    var sSample X(string) = s(5)
    sSample.Do("something") // 3
}

But I do not really find generalized interface types that useful.

The syntax of all the things can be tweaked a bit, but I think it is a matter of taste:

func(type T) Add(a, b T) {

}

// vs

func Add(type T) (a, b T) {

}

// vs current

func Add(type T) func(a, b T) {
    // possibly switch
    return func {
        // 
    }
}

The whole idea is that, You need specialize before use. If You want to use a generic type in a function - generalize the function too.

Conclusion

Does this generic concept solves "same api for all types" problem?

func AddInt(int) {

}

func AddInt32(int32) {

}

// ...

Well, yes and no. You still need to define different functions for each type, though the usage is simpler.

func Add(type T int | int32) func(a, b T) T {
    switch {
        case int:
        return func(a, b int) int {
            return a + b
        }

        case int32
        return func(a, b int32) int32 {
            return a + b
        }

        // do we need to specify "default" case?
    }
}

What You need is some kind of macro or codegen support, since int + int is not the same expression as int32 + int32. And that is really a different problem not really related to generics.

As a workaround an internal addable type can be introduced in the language, and a addable + addable operation can be defined.

func Add(type T addable) func(a, b T) T {
    switch {
        case Z := T:
        return func(a, b Z) Z {
            return a + b
        }
    }
}

Conclusion

I believe this proposal brings generics syntax on a new level providing a new understanding and vision of it, while remaining familiar. Please, let's start a discussion, I would really appreciate any feedback!

@ianlancetaylor
Copy link
Contributor

@ianlancetaylor ianlancetaylor commented Jun 1, 2020

I don't think I really understand your proposal.

At the very end you suggest that you may need something like addable. In the current generics design draft, we explicitly decided to avoid that kind of thing, because there are many possible combinations, and they each become a new name in the language that everybody has to learn.

Can you show how to write some of the examples at https://go.googlesource.com/proposal/+/refs/heads/master/design/go2draft-contracts.md#examples using your proposal? Thanks.

@sorenvonsarvort
Copy link
Author

@sorenvonsarvort sorenvonsarvort commented Jun 1, 2020

I don't think I really understand your proposal.

At the very end you suggest that you may need something like addable. In the current generics design draft, we explicitly decided to avoid that kind of thing, because there are many possible combinations, and they each become a new name in the language that everybody has to learn.

Can you show how to write some of the examples at https://go.googlesource.com/proposal/+/refs/heads/master/design/go2draft-contracts.md#examples using your proposal? Thanks.

Sure.

As far as I understand, it is not clear what the differences are between this proposal and the existing one (which I will call "current design" in this comment)? Of course, I would like to show a few points with examples that could be named major changes.

  1. My opinion is contracts are a great idea, but I guess explicitly listing types is still a good option, that is why I define a generalized type concept instead.

Current design advantages:

1.1. The reason of contracts is the author does not want explicitly list types, but wants to do describe them.

1.2. The second reason is there are to many combinations with types to include them to the standard library.

Current design disadvantages:

1.1. Still author says we need something important like comparable contract built in. And this contract is basically a list of types. So, why not to define a generalized type comparable instead which is exactly a list of types supporting == and !=?

1.2. Contracts act like interfaces, so why we do not just use the interfaces?

In the current design there is an example:

contract stringer(T) {
	T String() string
}

This is such a strange syntax for me, why no to write just like this?

type Stringer interface{
    String() string
}

Sure, You can say You can combine contracts in such way as bellow and interfaces are not suitable for this:

contract NumericAbs(T) {
	Numeric(T)
	T Abs() T
}

But instead this is what I propose:

type Numeric int8 | int16 | int32 | ... // Still I think this type can be defined somewhere, like in package `generic` or maybe built in to the language, since it is an important case too.

// generic interface Abser when instantiated (specialized) with type `int32`, for example, becomes an interface matching any type with method `Abs() int32`
type Abser(type T Numeric) interface{
    Abs() T
}

Usage:

type X struct{}

func (X) Abs() int {
    return 0
}

func main() {    
    // Abser(int) means interface{Abs() int}
    var x Abser(int) = X{}
    
    fmt.Println(x.Abs())
}
  1. Yes, I agree we do not need to define a type addable and operation + for it. But instead I mean we can allow such a thing implicitly.

So, this explicit code having explicit int32 + int32 and int64 + int64

type X int32 | int64

func Add(type T) func(a, b X) X {
    switch T {
        case int32:
        // 1
        return func(a, b int32) int32 {
            return a + b
        }
        case int64:
        return func(a, b int64) int64 {
            return a + b // the issue is we have the same code for each type, though it could be different.
        }
    }
}

Usage:

func main() {
    // add is now the function 1
    add := Add(int32) 
    fmt.Println(add(4, 6))
}

Turns into this code having the same operations implicit:

type X int32 | int64

func Add(type T) func(a, b X) X {
    // := here is not an assignment operator
    // it is a "type instantiation" operator
    // which means it takes generic type T and returns a certain type of it at compile time when the Add function is specialized
    // so, Z is holding either `int32` or `int64` but not a generic type int32 | int64
    // and compiler can check that both `int32` and `int64` types allow `+` operation no matter what X is
    switch Z := T {
        return func(a, b Z) Z {
            // if Z is int32 then + is the int32 + int32 operator
            // if Z is int64 then + is the int64 + int64 operator
            // since we need expression Add(int32) return a specific function func(a, b int32) int32
            // but not a func(a, b T) T which i think must be impossible
            return a + b
        }
    }
}

Usage:

func main() {
    // add is now a func(a, b int32) int32 {
    //    return a + b
    // }
    add := Add(int32) 
    fmt.Println(add(4, 6))
}

A bigger and more complicated example.

Before:

// OrderedNumeric matches numeric types that support the < operator.
contract OrderedNumeric(T) {
	T int, int8, int16, int32, int64,
		uint, uint8, uint16, uint32, uint64, uintptr,
		float32, float64
}

// Complex matches the two complex types, which do not have a < operator.
contract Complex(T) {
	T complex64, complex128
}

// OrderedAbs is a helper type that defines an Abs method for
// ordered numeric types.
type OrderedAbs(type T OrderedNumeric) T

func (a OrderedAbs(T)) Abs() OrderedAbs(T) {
	if a < 0 {
		return -a
	}
	return a
}

// ComplexAbs is a helper type that defines an Abs method for
// complex types.
type ComplexAbs(type T Complex) T

func (a ComplexAbs(T)) Abs() T {
	r := float64(real(a))
	i := float64(imag(a))
	d := math.Sqrt(r * r + i * i)
	return T(complex(d, 0))
}

Usage?

If I got it right, the usage is:

func main() {
    // OrderedAbs is still a generic type holding a value -5?
    // Or is it now an int variable?
    var a OrderedAbs = -5

    // what method Add of what type do we call?
    a.Add() 
}

After:

Abs defined as a function (not a method):

// ordered is a generic type which can be specialized as int, int8 and so on
type ordered int | int8 | int16 | int32 | int64 | uint | uint8 | uint16 | uint32 | uint64 | uintptr | float32 | float64 
type complex complex64 | complex128
// Numeric is a generic type which can be specialized to any type of ordered or to any type of complex
type Numeric ordered | complex

// Abs is a function calculating an absolute value
// it has one implementation for real numbers
// and a completely different one for complex ones
// while having absolutely the same simple interface and usage
func Abs(type T Numeric) func(T) T {
    switch T {
        case Z := ordered:
        // 1
        return func(a Z) Z {
            if a < 0 {
		        return -a
	        }
	        return a
        }
        case Z := complex:
        // 2
        return func(a Z) Z {
            r := float64(real(a))
	        i := float64(imag(a))
	        d := math.Sqrt(r * r + i * i)
	        return Z(complex(d, 0))
        }
    }
}

Usage:

func main() {
    var a int = -5
    // abs is now a function 1 from the previous code
    // having func(int) int signature
    abs := Abs(int)

    fmt.Println(abs(a)) // prints 5
}

Shorter version:

func main() {
    var a int = -5

    fmt.Println(Abs(int)(a)) // prints 5
}

Even shorter version with inference from the compiler:

func main() {
    var a int = -5

    fmt.Println(Abs(a)) // prints 5
}

I do not think it is okay to define methods using contracts, since it allows to define a method for int type, for example, which I think must be impossible. You need to specialize before defining a method.

If You want to define a method - it must be defined for a specific type:

type Number int

func (a Number) Add(b Number) Number {
    return a + b
}

Since it must be a concrete implementation for a concrete type fitting a certain interface.

If You want Number to be a generic type, You need something like templates or codegen, which allows You to define several types and methods for them with the same code. And as far as I know this is a problem - when You are defining too many methods that are not used, so that You need a good linker to eliminate such an unused code, but I may be wrong.

The issue You need to "specialize" somewhere - You need to call this method Add from a certain type and pass a type that You want to specialize with, but how can you call a method of a type that is not specialized? If we have a type int which has no defined method Add in the language, but it has in a few different packages, how can we call the Add method?

If You do not "specialize" - You are risking to generate too many unused code, since who knows where it can be used.

// ComplexAbs is a helper type that defines an Abs method for
// complex types.
type ComplexAbs(type T Complex) T

So, if it is a helper type, it is not an int, right?

But what if You want add a variable of that type to an int(2)? You need a conversion.

Here is a simple case:

type MyType int

func main() {
	fmt.Println(MyType(2) + int(2))
}

But in case MyType is a "helper" type but generic, how the conversion must look like?

That is why I did my example using a function not a method. Still it is possible to design some imaginary syntax.

These are the tricky examples I want to use as an arguments for my design. I will provide a few more in a short time just to show some more easy cases.

@sorenvonsarvort
Copy link
Author

@sorenvonsarvort sorenvonsarvort commented Jun 1, 2020

Dot Product Example

Before:

// Numeric is a contract that matches any numeric type.
// It would likely be in a contracts package in the standard library.
contract Numeric(T) {
	T int, int8, int16, int32, int64,
		uint, uint8, uint16, uint32, uint64, uintptr,
		float32, float64,
		complex64, complex128
}

func DotProduct(type T Numeric)(s1, s2 []T) T {
	if len(s1) != len(s2) {
		panic("DotProduct: slices of unequal length")
	}
	var r T
	for i := range s1 {
		r += s1[i] * s2[i]
	}
	return r
}

Usage?

After:

// Numeric is a generic type allowing to be specialized to any of the listed types
type Numeric int | int8 | int16 | int32 | int64 | uint | uint8 | uint16 | uint32 | uint64 | uintptr | float32 | float64 | complex64 | complex128

// DotProduct is a generic function definition returning a concrete function for each type
// function(s1, s2 []int) int for ints 
// function(s1, s2 []float32) float32 for floats
func DotProduct(type T Numeric) func(s1, s2 []T) T {
    switch T {
        case Z := T:
        return func(s1, s2 []Z) Z {
            if len(s1) != len(s2) {
                panic("DotProduct: slices of unequal length")
            }
            var r T
            for i := range s1 {
                r += s1[i] * s2[i]
            }
            return r
        }
    }
}

Usage:

func main() {
    dotProduct := DotProduct(int)

    fmt.Println(dotProduct([]int{1,2,3}, []int{5,6,7})) // prints some number which is a dot product
}

We can make compiler infer many things, but I think explicit code is better for illustration purposes.

Yeah, I still can make minor mistakes since it kinda hard to write code without any suggestions and checks, but I hope it made it clear. Did I?

@sorenvonsarvort
Copy link
Author

@sorenvonsarvort sorenvonsarvort commented Jun 1, 2020

Could also the guy who put a dislike comment out issues he found, please.

@proyb6
Copy link

@proyb6 proyb6 commented Jun 1, 2020

@sorenvonsarvort
Copy link
Author

@sorenvonsarvort sorenvonsarvort commented Jun 1, 2020

@sorenvonsarvort #19412

Thank You for the link, I know the sum types proposal is there, but I believe there is a slight difference.

I do not get what is the exact question. Do You ask what is the difference? It is very tricky to understand and answer this question, but let me try.

Sum types are much like a unions in C: #19412 (comment)

Generic type is not a type at all, so a variable of "generic type" cannot hold a value. Instead a generic type is an expression evaluating to a type.

Example 1

My Proposal

type X int32 | int64 // generic type X that can specialize to int32 or int64

func main() {
    // You cannot write it like this
    // ok, the compiler can conduct some inference, but let's assume it is not there for this demo
    var x X = int32(5)
    


    // instead You need to write it like this and z becomes exactly an int variable
    var z X(int32) = int32(5) 


    z = int64(17) // error: z is an int32, this doesn't work
}

Sum Type Proposal

A sum type can handle a value of any of its types:

type X int32 | int64 // creates a type taking 64-bits in memory

func main() {
    var x X = int32(5) // ok
    x = int64(17) // still ok
}

Example 2

My Proposal

type X int | int32

func main() {
    var x X // doesn't work
    var x X(int) // ok

    fmt.Println(reflect.TypeOf(x)) // prints int
}

Sum Type Proposal

type X int | int32

func main() {
    var x X // ok

    fmt.Println(reflect.TypeOf(x)) // prints X?
}

If the sum proposal is accepted, we can change the syntax of generic types to avoid any conflicts.

I think also sum type cannot be implemented without a compiler tweaking and a real language change. Since it needs to hold somewhere a real union and manage it.

My proposal can be implemented with a not complicated codegen and adds almost no overhead. It can be really considered a syntax sugar allowing type parametrization.

I hope I made it clear, did I answer Your question?

@ianlancetaylor
Copy link
Contributor

@ianlancetaylor ianlancetaylor commented Jun 2, 2020

Can you show us how you would write something like the orderedmap.Map example (https://go.googlesource.com/proposal/+/refs/heads/master/design/go2draft-contracts.md#containers) using this proposal? Thanks.

@sorenvonsarvort
Copy link
Author

@sorenvonsarvort sorenvonsarvort commented Jun 3, 2020

Can you show us how you would write something like the orderedmap.Map example (https://go.googlesource.com/proposal/+/refs/heads/master/design/go2draft-contracts.md#containers) using this proposal? Thanks.

Ordered Map Example

Before

The link: https://go.googlesource.com/proposal/+/refs/heads/master/design/go2draft-contracts.md#containers

Criticism

I still think the generics are not good for defining functions with receivers. In my opinion it is a bottleneck and a weak place in the current design. And I also believe "generic functions having a receiver" is a whole separate proposal with a really different implementation.

Mostly, because we cannot define a function having a primitive type receiver (like int), or a receiver from another package (like http.Client).

type T // generic type

func (t T) Do() {
    fmt.Println(t)
}

func main() {
    x := 6
    x.Do() // how does this work?

    y := "hello"
    y.Do() // should this work too?
}

The second reason is, as I said in the previous comments, we do not really know what function we are going to call.

// file /a/a.go
package a

type T

func (t T) Do() {
    fmt.Println("hello")
}

// file /b/b.go
package b

type T

func (t T) Do() {
    fmt.Println("world")
}

// file /main.go
package main

func main() {
    x := 5
    x.Do()  // hello or world? how did we import type T?
}

So, You can say we can do this:

func main() {
    var x a.T = 5 
    var y b.T = "test"
    x.Do() // "hello"
    y.Do() // "world"
}

But no, we cannot, because of this:

func Check(x a.T) {
    fmt.Println(x)
}

func main() {
    var x a.T = 5 // x is kinda an int
    var y b.T = "test" // and y is kinda a string, right?
    x.Do() // "hello" // but how can we call a method of an int? so it is a variable of type a.T, right? 
    y.Do() // "world" // so this is a b.T
    Check(y) // and this must fail, since it expects an a.T and we pass a b.T?
}

The type T is not a type, it is a generic type, or a parametrized type. And it needs to be specialized (or "instantiated", or You name it) in order to evaluate to a type that can be used.

And the most important argument is such a feature involves too much code generation. We cannot expect the compiler will just substitute all T's with the type provided (or not) later somewhere. Methods are a part of a type. We define them and do not care if someone will use them, they just exist. What if we define a method Do for a generic type (which basically means Do is defined now for every type)? What if someone has defined such a method in some package? Should I import it before? What if there is some interface that is not satisfied without a method based on a generic type? I guess these are the primary reasons we cannot define a method for a primitive type in the current Golang version.

And I understand this can be tweaked and checked somehow by the compiler, and I understand such a problem can potentially be solved just like it is solved in some languages allowing contracts. Still I am afraid it is too complicated and costly both for implementation and use. I also may be wrong, this is just my honest opinion.

It was freaking tricky to explain, hope my point is clear, useful and no one is offended.

After

Before rewriting, I had to figure out the original problem.

So, the problem is to write a map with a binary tree under the hood.

I found one major issue with the solution from the example: it must be just a binary tree implementation, allowing finding a node just by its value.

I mean, why to have K and V fields if we can have a value of type struct{Key int; Value int}?

So, this code from the example:

type node(type K, V) struct {
    key         K
    val         V
    left, right *node(K, V)
}

Can be rewritten just like this:

type node(type T) struct {
    value T
    left  *node(T)
    right *node(T)
}

The next thing is we do not really need Map type, since we will use functions, instead of methods.

// file /tree/tree.go
package tree

type Node(type T) struct {
    Value T
    Left  *Node(T)
    Right *Node(T)
}

type Comparator(type T) func(T, T) int

func Find(type T) func(root *Node(T), value T, compare Comparator(T)) *Node(T) {
    switch T {
        // capturing type T, as I explained in examples bellow,
        // so Z is a specific type, and the compiler can infer it
        // after the specialization (instantiation)
        case Z := T:
        return func(root *Node(Z), value Z, compare Comparator(Z)) *Node(Z) {
            currentNode := root
            for currentNode != nil {
                switch cmp := compare(value, currentNode.Value); {
                case cmp < 0:
                    currentNode = currentNode.Left
                case cmp > 0:
                    currentNode = currentNode.Right
                default:
                    return currentNode
                }
            }
            return currentNode
        }
    }
}

func Insert(type T) func(root *Node(T), value T, compare Comparator(T)) bool {
    switch T {
        case Z := T:
        return func(root *Node(Z), value Z, compare Comparator(Z)) bool {
            currentNode := Find(root, value, compare)
            if currentNode != nil {
                currentNode.Value = value
                return false
            }

            // again, we can specialize generic type to a specific type
            // only using a specific type as a parameter
            // since value is Z (which is specific, inferred by the compiler)
            // and Node(Z) is struct{Value Z; Left *Node(Z); Right Node(Z)}
            // it is okay
            *currentNode = Node(Z){Value: value}
            return true
        }
    }
}

// file /main.go
package main

import "tree"

type KeyValue struct {
    Key   string
    Value int
}

// Imagine we really want to compare just by the key length
func CompareKeyValueByKeyLen(a KeyValue, b KeyValue) int {
    aKeyLen := len(a.Key) 
    bKeyLen := len(b.Key)

    if aKeyLen > bKeyLen {
        return 1
    }
    if aKeyLen == bKeyLen {
        return 0
    }
    return -1
}

func main() {

    var myTreeBasedMap tree.Node(KeyValue)

    insert := tree.Insert(KeyValue)

    // inserting a bunch of nodes
    insert(myTreeBasedMap, KeyValue{"xxx", 5}, CompareKeyValueByKeyLen)
    insert(myTreeBasedMap, KeyValue{"xxxxx", 17}, CompareKeyValueByKeyLen)
    insert(myTreeBasedMap, KeyValue{"xx", -13}, CompareKeyValueByKeyLen)
    
    find := tree.Find(KeyValue)
    node := find(myTreeBasedMap, KeyValue{Key: "xx"}, CompareKeyValueByKeyLen)
    fmt.Println(node) // should print {xx, -13}
}

We can use closures in the tree package to allow a user pass the comparator only one time. So the usage will look like this:

func main() {
    var myTreeBasedMap tree.Node(KeyValue)

    insert := tree.Insert(KeyValue)(CompareKeyValueByKeyLen)

    // inserting a bunch of nodes
    insert(myTreeBasedMap, KeyValue{"xxx", 5})
    insert(myTreeBasedMap, KeyValue{"xxxxx", 17})
    insert(myTreeBasedMap, KeyValue{"xx", -13})
    
    find := tree.Find(KeyValue)(CompareKeyValueByKeyLen)

    node := find(myTreeBasedMap, KeyValue{Key: "xx"})
    
    fmt.Println(node) // should print {xx, -13}
}

Also we can use a type Comparable(type T) interface{ Compare (T) int } instead of a value, depends on the goal. When we use such an interface, we allow exactly one sorting method for a type. And I guess this approach may fit a bit better. The full source code will look like this:

// file /tree/tree.go
package tree

type Comparable(type T) interface{ Compare (T) int }

type Node(type T Comparable) struct {
    Value T
    Left  *Node(T)
    Right *Node(T)
}

func Find(type T) func(root *Node(T), value T) *Node(T) {
    switch T {
        case Z := T:
        return func(root *Node(Z), value Z) *Node(Z) {
            currentNode := root
            for currentNode != nil {
                switch cmp := value.Compare(currentNode.Value); {
                case cmp < 0:
                    currentNode = currentNode.Left
                case cmp > 0:
                    currentNode = currentNode.Right
                default:
                    return currentNode
                }
            }
            return currentNode
        }
    }
}

func Insert(type T) func(root *Node(T), value T) bool {
    switch T {
        case Z := T:
        return func(root *Node(Z), value Z) bool {
            currentNode := Find(root, value)
            if currentNode != nil {
                currentNode.Value = value
                return false
            }

            *currentNode = Node(Z){Value: value}
            return true
        }
    }
}

// file /main.go
package main

import "tree"

type KeyValue struct {
    Key   string
    Value int
}

func (a KeyValue) Compare(b KeyValue) int {
    aKeyLen := len(a.Key) 
    bKeyLen := len(b.Key)

    if aKeyLen > bKeyLen {
        return 1
    }
    if aKeyLen == bKeyLen {
        return 0
    }
    return -1
}

func main() {

    var myTreeBasedMap tree.Node(KeyValue)

    insert := tree.Insert(KeyValue)

    // inserting a bunch of nodes
    insert(myTreeBasedMap, KeyValue{"xxx", 5})
    insert(myTreeBasedMap, KeyValue{"xxxxx", 17})
    insert(myTreeBasedMap, KeyValue{"xx", -13})
    
    find := tree.Find(KeyValue)
    node := find(myTreeBasedMap, KeyValue{Key: "xx"})
    fmt.Println(node) // should print {xx, -13}
}

Another trick is to use generic functions for a method implementations. It gets kinda tricky, but here is the code:

// Tree definition
type Comparable(type T) interface{
    Compare(T) int
}

type Tree(type T Comparable) interface{
    Value T
    Left() T
    Right() T
    Find(T) T
    Insert(T) bool
}

// Map implementation
type KV struct {
    Key   string
    Value int
}

func (a KV) Compare(b KV) int {
    return 0 // imagine we are actually comparing it by the key
}

// MyMap becomes struct {
//     Value KV
//     Left *KV
//     Right *KV
// }
type MyMap tree.Node(KV) 

func (m MyMap) Value() KV {
    return m.Value
}

func (m MyMap) Left() KV {
    return m.Left
}

func (m MyMap) Right() KV {
    return m.Right
}

func (m MyMap) Find(i KV) KV {
    return tree.Find(KV)(m, i) // yeah, we are using it from our previously written package
}

func (m MyMap) Insert(i KV) bool {
    return tree.Insert(KV)(m, i) // and again
}

func main() {
    var myAwesomeMap Tree(KV) = MyMap{}

    myAwesomeMap.Insert(KV{"a", 14})
    myAwesomeMap.Insert(KV{"b", 25})
    myAwesomeMap.Insert(KV{"c", -9})

    myAwesomeMap.Find(KV{"c"})
}

In this way we are implementing our map as a specific structure having some methods, but we kinda have a generic tree interface here and we are using generic implementations of the find and insert algorithms (which are specialized before the uses with a specific KV type fitting Comparable interface).

So, yeah, I guess, this approach still helps a user to write generic containers both in functional style (with plain functions and closures) and OOP (with objects and methods), while this design can be implemented in a simple pre-processor generating zero unused code.

I did not show any example on Iterator thing from the link, because it kinda takes long to write (and it is easy to make some mistakes), but I promise it is implemented in the same trivial way. And yes, I kinda modified the example a bit (I mean I turned K, V into T), but i think it changes really nothing about the proposal, but more about the library and business logic of the treemap.

Let me know if You need anything more, and please provide some feedback on the examples.

@ianlancetaylor
Copy link
Contributor

@ianlancetaylor ianlancetaylor commented Jun 3, 2020

One of the main reasons that people want generics is the ability to write container types like OrderedMap.

In all honesty it seems to me that the OrderedMap code in the design draft is easier to write and easier to use than the code that you show above.

@sorenvonsarvort
Copy link
Author

@sorenvonsarvort sorenvonsarvort commented Jun 3, 2020

One of the main reasons that people want generics is the ability to write container types like OrderedMap.

In all honesty it seems to me that the OrderedMap code in the design draft is easier to write and easier to use than the code that you show above.

Basically we can think my proposal allows people to write generic functions like make or append. So, if we imagine there would be find and insert among them - You still need to write some wrapper around them, though they contain the whole algorithm. I guess this is why You consider it is harder - it requires an additional step.

I totally understand and accept this downside of the proposal. But I also think it would be great if someone else also considered it. Or maybe someone has a better idea on "generic function with receiver" proposal.

I guess it is up to You to decide whether to close this issue and decline the proposal or not.

Thank You for Your time.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Projects
None yet
Linked pull requests

Successfully merging a pull request may close this issue.

None yet
4 participants
You can’t perform that action at this time.