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: type assertion extensions, defined type assertions and generics #39716

Closed
markusheukelom opened this issue Jun 19, 2020 · 4 comments
Labels
FrozenDueToAge generics Issue is related to generics LanguageChange Proposal v2 A language change or incompatible library change
Milestone

Comments

@markusheukelom
Copy link

markusheukelom commented Jun 19, 2020

Proposal: type assertion extensions, defined type assertions and generics

Introduction

Currently, type assertions can be used on interface values to determine the dynamic type of a value:

var val interface{}
//...
x, ok := val.(int)                  // an int type assertion: x is of type int 
s, ok := val.(strings.Stringer)	    // a satisfaction test: s if op type strings.Stringer and not nil if ok 

Type switches borrow the type assertion syntax:

switch x := val.(type) {
case string:            // x is a string
case bool:              // x is a bool
case float32, float64:  // x is an interface{} value containing an float32 or float64
default:	
	// x is an interface{} value containing any type
}

This document contains a set of 6 proposals to extend on this idea.

Proposal 1 - Allow multiple types in type assertions

Extend the type assertion syntax to allow multiple types, just as in the switch case statements:

x, ok := val.(float32,float64)	// if ok, x has dynamic type float32 or float64, otherwise it is nil

This works just like in a type switch case: if val holds an int or float64 ok will be true and x will have a the dynamic type of float32 or float64.

Proposal 2. Allow defined type assertions

A defined type assertion is declared using the new keyword meta:

meta Float {float32,float64}    
meta Int {int,int8,int16,int32,int64}


meta {} // all types 

Because of the keyword meta a defined type assertion is also called a meta type. A defined type assertion or meta type can be used anywhere where an "inline" type assertion can be used.

var val interface{} = 1
x, ok := val.(Int)	// ok = true
x, ok = val.(Float) 	// ok = false

swich x := val.(type) {
case Float:
	// x has dynamic type of any type in Float
case Int:
    // x contains and int (of any type in Int)
	// x is int
case int:
    // x is an int
}

Like types, meta types are exported if starting with a capital character. Meta types can include other meta types:

package types

meta SignedInt {int,int8,int16,int32,int64}             // all signed integer types
meta UnsignedInt {uint,uint8,uint16,uint32,uint64}      // all unsigned integer types
meta Int {SignedInt,UnsignedInt}                        // all integer types
meta Float {float32,float64}                            // all floating point types
meta Complex {complex64,complex64}                      // all complex types
meta Real {Int,Float,Complex,rune,byte}                 // all real number types
meta Number {Real,Complex}                              // all number types

meta Meta{int,bool,Meta}                                 // error: meta type self inclusion 
meta Meta{int,bool,Meta}                                 // error: meta type self inclusion 

Proposal 3. Extended type assertions to include type kinds

The reflect packages uses the concept of type kinds to identify types as kind of types such as functions, channels, etc. Type assertions are extended to support the same idea.

f, ok := val.(func) // true if f is a function, f has as dymanic type some function
c, ok := val.(chan) // true if c is a channel, c has as dymanic type some channel type

The full list is illustrated using a type switching statement:

switch x := val.(type) {
    case func: 		
    case chan:		
    case struct:	
    case map:        		
    case []:		// slice types
    case [3]:		// array types of length 3
    case [.]:		// array types of any length
    case *:	        // pointer types
}

// type kinds can be used in defined type assertions as well
meta F {func}       // a meta type containing the set of all functions 
meta S {struct}     // all structs
meta PS {[]*struct} // all types that are a slice of pointer to struct

// like types, meta types can be recursively defined
meta R {Float,*R} // a float, a pointer to a float, a pointer to a pointer to a float, etc

Meta types using type kinds may help to write more concise and clearer documentation and can be used to validate function arguments of type interface{}:

package json

// M is the set of all types that are marshallable to JSON.
// NOTE: compare this with the description in the JSON package of marshallable types 
meta M {		
	*M,     
	bool,
	int,
	float64
	string,
	[]M,
	struct,
	Marshaller,
}

func ParseJSON(r io.Reader, dest interface{}) error {
    if _, ok := dest.(*M); !ok {
        return fmt.Errorf("dest is not a pointer or the value pointed to is not marshallable to JSON", dest)
    }
    ... // use type switching (and package reflect for structs) for rest of implementation
}

More intricate examples of using type kinds are given after generics have been discussed.

Proposal 4. Extend type assertions to include comparison operators

if _, ok := val.(<); !ok {
    fmt.Println("val is not comparable")
} 

meta Equatable {==}
// Find is a silly function to showcase the use of comparison operator type assertions
func Find(needle interface{}, haystack ...interface{}) (int, error) {
	if _, ok := needle.(Equatable); !ok {
		return 0, ...
	}
}

More intricate examples are given in the generic section.

Proposal 5. Generics can be based on meta types

A generic function is declared by using a meta type in its signature.

meta C {<} // C is the set of all comparable types
meta E {==}

// a generic function: it uses the meta type C in the function signature
func Min(a, b C) C {
	if a < b {
		return a
	}
	return b
}

// Find is also generic because it uses meta type E
func Find(needle E, haystack []E) int {
    for i, value := range haystack {
        if value == needle {
            return i
        }    
    return len(haystack)
}

A generic type is defined by using a meta type in its definition.

meta T {}

// a generic struct: it uses the meta type T in its field definitions
type ListNode struct {
	prev *ListNode 
	next *ListNode 
	Payload T
}

type MyGenericChannel chan T

meta K (==)
meta V {}
type Pair struct {         
    Key K 
    Value V
}

type HashTable struct {
    Table []Pair(K,V)
    HashFn func(value V) int    
}   

A generic type may include a meta type signature directly after its name.

// same definition of the generic Pair type but with explicit meta type signature (K,V)
type Pair(K,V) struct {      
    Key K 
    Value V
}

If the meta type signature is omitted it defaults to the order of appearance of the used meta types.

// Min is a generic function with a meta type signature (T) consisting of a single meta type T
func Min(T)(a T, b T) T {...}	        // (T) is the explicit meta signature.

// these declarations all define the same generic function type 
type MinFn(T) func(a, b T)              // meta signature (T) is inferred here automatically
type MinFn func(a, b T) 

func DotProduct(a, b Vector(T)) T       // meta signature (T) is inferred here automatically
func DotProduct(T)(a, b Vector(T)) T    // explicit meta sig (T)

func FanIn(chans []chan T) chan T  {...}

// example with multi meta types
func Keys(m map[K]V) []K {...}          // meta signature (K,V) is inferred here automatically
func Keys(K,V)(m map[K]V) []K {...}     // same thing but with an explicit meta type signature.

// struct examples
type LiseNode(T) struct {               // explicit meta signature
    prev *ListNode 
    	next *ListNode 
    	Payload T
}

type Bimap(K,V) struct {		// meta type signature (K,V) is required here - see below
	forward map[K]V
	reverse map[K]V
}

In general, the meta type signature will be omitted whenever possible because it is shorter and therefore more readable. A common case where the type signature is required is when a meta type is used only in non-exported struct fields, but the type self is exported. This is case for the Bimap(K,V) example above.
Some less common cases where meta type signature is required are:

  1. when a meta type is used only by the function's implementation and is not present in the function's signature
  2. for backwards compability; for example the order of struct fields that uses meta types have changed

A common reason to include the meta signature although not required would be clarity, for example because a different meta type order is more natural.

If a meta signature is provided, all meta types must be listed. Partial lists are not allowed.

Generic struct types cannot be specialized for specific types such as for example in C++.

It is not necessary to repeat the meta type signature on generic type methods, but it may be done so for reason of clarity.

func (b *Bimap) GetValueByKey(key K) V {
    return b.foward[key]
} 

func (b *Bimap(K,V)) GetKeyByValue(value Value) V { // ok - but not needed
    return b.reverse[value]
} 

meta T {K}

func (b *Bimap(T,V)) GetKeyByValue(value Value) V { // error - illegal type signature (T,V) (expected (K,V)
    return b.reverse[value]
} 
 

It is recommended that a package that exports generics types use one or two type meta types at most. They should be name with single capital letter like T, K, V etc. This would make than easily recognisable.

An exception would be a types packages for example that defines Ints, Floats, etc. These meta types could be used for both generics, type assertions and type switching.

When using a generic type or or function, each meta type identifier must be bound to a concrete type. This process is called type binding.

In many case, type binding can be done automatically by the compiler using the context in which an generic type is used. In cases where this is not possible, or where the inferred binding is not desired, the binding must be given explicitly.

package stats
meta T {int,float32,float64}

func Sum(a, b T) T {
	return a + b
}

stats.fsum(1, 1)                    // ok - T is inferred to type int
stats.fsum(1.0, 1.0)                // ok - T is inferred to type float64
stats.fsum(float32)(1.0, 1.0)       // ok - T is explicitly set to type float64

node := ListNode{Payload: "Gophers!"}                   // ok - T is inferred to type string
var node ListNode(string)                               // ok - T is explicitly set
type MyNode ListNode(string)                            // ok - MyNode has type struct { ..., Payload string }

When instantiating a generic type, the types that are (automatically or implicitly) bound to the meta types are compile-time type asserted using the meta type by the compiler.

stats.Sum("go", "c++")              // compile error: type string is not in stats.T
stats.Sum(byte)                     // compile error: type byte is not in stats.T

meta S {io.Reader}
fund MyReader(val S) {...}

stringReader := MyReader(string)        // compile error: string does not satisfy io.Reader
fileReader := MyReader(file)            // ok - fileReader has type func(*os.File)

A meta type can only bind to a single concrete type.

stats.Sum(1, 1.0)                   // compile error: attempt to bind stats.T to both int and float64.

fsum := stats.Sum                   // compile error: no type is provided for stats.T
fsum := stats.Sum(float64)          // ok - fsum is a function with signature (a, b float64) float64

When implementing generic functions, a compilation error occurs when an operation is attempted that is not supported by all types in the meta type.

meta T {}
meta C {<}

func Max(a, b T) T {
    if a > b {		// compile error: operator < is not supported by all types in T
        return b
    }
    return a
}
          
func Min(a, b C) C {
    if a < b {		// ok - all types in C support < operator (as per its definition)
        return b
    }
    return a
}

func Max(a, b C) C {
    if a > b {		// also fine: the compiler knows that all types that support <, also support >
        return b
    }
    return a
}

func MyFunc(val C) {
        val.String()  // compile error: method String is not supported by all types in C 
}

meta S {fmt.Stringer}  // S is the set of all types that satisfy interface fmt.Stringer 
func Concat(values []S) string {
    var result s
    for _, v := range values {
        s += v.String()         // ok
    }    
    return s 
}

type interface One { 
    A()
    B()
}

type interface Two { 
    B()
    C()
}

meta Q {One,Two}    

func contrived(q Q) {
    q.B()               // ok: all types in Q have B
    q.A()               // compile error: A() is not supported by all types in Q
}

Besides the common applications of generics, in Go generics can also be used to provide a type safe signature to functions that are otherwise implemented using reflection.

package sql
meta R {struct} 

// ScanRow uses generics only to provide a type safe function signature 
func ScanRow(row *sql.Row, dest *R) error {
	return scanRow(row, dest)	// scanRow is the non-generic implementation, separated out to prevent unnecessary code duplication.
}

var person Person
sql.ScanRow(r, person)	// compile error: argument person of type Person is not of meta type *sql.R
sql.ScanRow(r, &person)	// ok

var count int
sql.ScanRow(r, &count)	// compile error: argument count of type *int is not of meta type *sql.R

// package json
// M is the set of all types that are marshallable to JSON.
meta M {		
	*M,     
	bool,
	int,
	float64
	string,
	[]M,
	struct,
	Marshaller,
}

func Unmarshall(r io.Reader, dest *M) error { // type safe interface
    return parse(r, m) // function parse is not generic and is implemented using reflection
}

json.Unmarshall(..., person)    // compile error -  person (type Person) is not of meta type *json.Marshallable
json.Unmarshall(..., &person)   // ok

c := make(chan int)
json.Unmarshall(..., &c)       // compile error - c (type chan int) is not of meta type *json.Marshallable c

Proposal 6. compile blocks in generic functions compile different code depending on type

This is best explained using an example.

package linalg 

// Field is an interface to types that support arithmetic using +,-,* and /.
// NOTE: big.Int/Rat/Float could implement Field
type Field interface {
	// in the field operations below, f is the right operand
	AddField(f Field) Field
	SubField(f Field) Field
	MultField(f Field) Field
	DivField(f Field) Field
}

meta N {types.Ints,types.Float,types.Complex} 
meta T {N,Field}

type Vector {
	Elems []T
}

func DotProduct(a, b Vector(T)) T {
    var result T
    for i := range len(a.Elems) {

        // compile different code depending on type
        compile T.(type) {
        case Field: 
            // code in this block is included only for types that satisfy Field
			
            prod := a.Elems[i].MultField(b.Elems[i])
            result = result.AddField(prod).(T)  

        case N: 
            // code is included for types in N
            result += a.elems[i] * b.elems[i]
        }
    }
    return result
}

func (* Matrix) Mult(other Matrix(T)) Matrix(T) {
    // compile blocks are against used to provide (optimized) implementation
}

Another example.

// package goclapack
import la "math.linalg"

type N {float64,float32,complex64,complex128}

func SVD(m la.Matrix(N)) (la.Matrix(N), la.Matrix(N), la.Matrix(N), error) {
	s := m la.NewMatrix(N)(...)
    v := m la.NewMatrix(N)(...)
    d := m la.NewMatrix(N)(...)
    
    var err error

    // compile blocks used to call correct routine directly on the elements in matrix m, s,v and d.
    compile N.(type) {
    case float32:
    	C.fgesvd('A', 'A', c.size_t(m.rows), c.size_t(m.cols), unsafe.Pointer(&m.elem[0]))
        // detect err
        err = ...
    case float64:
        C.dgesvd('A', 'A', c.size_t(m.rows), c.size_t(m.cols), unsafe.Pointer(&m.elem[0]))
    
    // etc
    }
    
    return s, v, d, err

}
@markusheukelom markusheukelom changed the title type assertion extensions, defined type assertions and generics Proposal: Go2: type assertion extensions, defined type assertions and generics Jun 19, 2020
@gopherbot gopherbot added this to the Proposal milestone Jun 19, 2020
@ianlancetaylor ianlancetaylor changed the title Proposal: Go2: type assertion extensions, defined type assertions and generics proposal: Go 2: type assertion extensions, defined type assertions and generics Jun 19, 2020
@ianlancetaylor ianlancetaylor added v2 A language change or incompatible library change LanguageChange generics Issue is related to generics labels Jun 19, 2020
@DeedleFake
Copy link

Proposal 3, as currently stated, is inherently not backwards compatible. For example:

Playground

package main

type CustomInt int

func Example(v interface{}) {
	switch v.(type) {
	case int:
		println("built-in")
	case CustomInt:
		println("custom")
	}
}

func main() {
	Example(CustomInt(0))
}

Currently, this will print custom, but it sounds like your change, as stated, would make it print built-in since it would now treat built-in types as kinds in type switches.

@icholy
Copy link

icholy commented Jun 23, 2020

In the new generics draft, interfaces can contain a list of valid underlying types.

type Int interface {
  type int, int8, int116, int32, int64, uint, uint8, uint16, uint32, uint64
}

These can only be used as type parameters. A simpler proposal would be to allow using these in type assertions and type switches.

x := v.(Int)

switch x := v.(type) {
    case Int:
}

However, I don't really see the value.

@deanveloper
Copy link

Proposal 3, as currently stated, is inherently not backwards compatible. For example:

Playground

package main

type CustomInt int

func Example(v interface{}) {
	switch v.(type) {
	case int:
		println("built-in")
	case CustomInt:
		println("custom")
	}
}

func main() {
	Example(CustomInt(0))
}

Currently, this will print custom, but it sounds like your change, as stated, would make it print built-in since it would now treat built-in types as kinds in type switches.

@DeedleFake This doesn't seem to be the case, I think you may have misinterpreted. int is still a built-in type, not a kind. It seems that the only thing that Proposal 3 states is that things like someVal.(func) (which is not currently valid) can be used in type-switches to describe any function.

@DeedleFake
Copy link

If that was true, then the example M type wouldn't, as it claims, be all of the possible marshallable types:

// M is the set of all types that are marshallable to JSON.
// NOTE: compare this with the description in the JSON package of marshallable types 
meta M {		
  *M,     
  bool,
  int,
  float64
  string,
  []M,
  struct,
  Marshaller,
}

If int isn't a kind, then if I do type A int, M won't match A. Although, this example also doesn't cover int8, int16, and so on, or any of the uint types.

@golang golang locked and limited conversation to collaborators Sep 17, 2021
Sign up for free to subscribe to this conversation on GitHub. Already have an account? Sign in.
Labels
FrozenDueToAge generics Issue is related to generics LanguageChange Proposal v2 A language change or incompatible library change
Projects
None yet
Development

No branches or pull requests

6 participants