search

golang / go

The Go programming language
https://go.dev
BSD 3-Clause "New" or "Revised" License
122.68k stars 17.49k forks source link

proposal: Go 2: type of types #44153

Closed Konstantin8105 closed 3 years ago

Konstantin8105 commented 3 years ago

Create that proposal in according to https://github.com/golang/proposal#the-proposal-process .

Type of type

In according to questions from template:

Minimal example

package main

import "fmt"

// T is slice of types.
var T = []type{int, float32}

// summ resurn summary of values
func summ(vs ...T) T {
    var res T
    for _, v := range vs{
        res += v
    }
    return res
}

func main() {
    fmt.Printf("%d\n", summ[T:int](1,2,3,4))                  // show "10"
    fmt.Printf("%T\n", summ[T:int])                           // show "func (...int) int"
    fmt.Printf("%.2f\n", summ[T:float32](1.0, 2.0, 3.0, 4.0)) // show "10.00"
    //                       -----------
    //                      specific type

    fmt.Printf("%d\n", summ(1,2,3,4))          // Error: type T is undefined
    fmt.Printf("%d\n", summ[T:int32](1,2,3,4)) // Error: type `int32` is not in types slice T
}

For present language design:

Types slice manipulation

Types slice:

Acceptable types slice initialization

// Empty is empty slice of types.
// Exported.
var Empty []type

// ut is slice of unsigned types.
// Not exported.
var ut = []type{uint, uint8, uint16, uint32, uint64}

// num is slice of types from some external package `types`
var num = types.Numbers

Not acceptable slice of types

var (
    One  type = int // Error : type `type` is not slice of type `[]type`.
    Many []type = _ // Error : slice of types is not limited.
)

type A = One // Error : type `One` is not a type

Useful operations

Create a copy of types slice

var (
    N  = []type{float32, float64}
    NC []type
)

func init() {
    NC = N
}

Append new type

var N []type

func init() {
    N = append(N, float64)
}

Append types slice to types slice

var (
    floats = []type{float32,float64}
    ints  = []type{int,int32,int64}
    mix   []type
)

func init() {
    mix = append(mix, floats...)
    mix = append(mix, ints...)
}

Append new type to external package

package main

import "types"

func init() {
    types.Numbers = append(types.Numbers, float64)
}

Remove type from external package

package main

import "types"

func init() {
    for i,t := range types.Numbers{
        if t.(type) == uint32 {
            types.Numbers = append(types.Numbers[:i], types.Numbers[i+1:]...)
            break
        }
    }
}

Scope

Type slice is cannot by changed in any functions, methods, except function func init() {...}. So, we can create a tests for avoid some types in types slice.

package main

import "fmt"

var floats =[]type{float32, float64}

func main() {
    floats = append(float32, int) // Error: cannot append types slice
    floats[0] = int               // Error: cannot change types slice

    floats[0],floats[1] = floats[1], floats[0] // Error: cannot change types slice

    fmt.Println(floats) // Show : "[]type{float32, float64}"
    for i, v := range floats{
        fmt.Println(v) // Show correctly types slice per line
    }
}

Generic prototype with one types slice

Examlpe 1

External package tools with empty types slice

package tools

var Numeric []type // empty types slice

// Min return minimal of 2 number with same type
func Min(a, b Numeric) Numeric {
    if a < b {
        return a
    }
    return b
}

Use package tools:

package main

import "fmt"
import "tools"

func init() {
    tools.Numeric = append(tools.Numeric, int, float32)
}

func main() {
    fmt.Println(tools.Min[Numeric: int](1,2))          // show: 1
    fmt.Println(tools.Min[Numeric: float32](1.2,-2.1)) // show: -2.1

    Numeric := 12 // initialization variable `Numeric` with same name as types slice
    fmt.Println(tools.Min[Numeric: float32](1.2,-2.1)) // Error: slice `tools.Min` index `float32` is not valid. Function `tools.Min` is not slice.
}

Example 2

Example based on code from https://blog.golang.org/why-generics.

package tree

var E []type

type Tree struct {
    root    *node
    compare func(E, E) int
}

type node struct {
    val         E
    left, right *node
}

func New(cmp func(E, E) int) *Tree {
    return &Tree{compare: cmp}
}

func (t *Tree) find(v E) **node { ... }
func (t *Tree) Contains(v E) bool { ... }
func (t *Tree) Insert(v E) bool { ... }

Using:

package main

import "tree"

func init() {
    tree.E = append(tree.E, int, uint) // registration
}

func main(){
    t := tree.New[tree.E: int](func(a, b int) int { return a - b })

    var t2 tree.E // type of variable will be clarify later
    t2 = tree.New[tree.E: uint](func(a, b uint) uint { return a - b })
    // t2 = tree.New[tree.E: int] (...) Error: t2 have type tree[E: uint] already

    var (
        // For create a pointer of generic type
        // type added like in variable struct initialization
        v   = tree.Tree[E: float64]
        pt1  *tree.Tree[E: int]
        pt2 = new(tree.Tree[E: int])
    )

    // ...
}

Example 3

Example based on code from https://github.com/golang/proposal/blob/master/design/15292/2013-12-type-params.md#syntax

// This defines `T` as a type parameter for the parameterized type `List`.
var T = []type{int, float32}

type List struct {
    element T
    next *List[T]
}

type ListInt List[T:int]
var v1 List[T:float32]
var v2 List[T: ListInt]
var v3 List[T: List] // Error: List[T] is undefined

type S struct { f T }
func L(n int, e T) interface{} {
    if n == 0 {
        return e
    }
    // return L(n-1, S{f:e}) // Error: type T of struct S is undefined
    return L(n-1, S[T:T]{f:e})
}

// Example of using: 
// f := Counter[T:int]()
func Counter() func() T {
    var c T
    return func() T {
        c++
        return c
    }
}

Generic prototype with few types slice

Example 1

External package tools with empty types slice

package tools

var Num1 []type // empty types slice
var Num2 []type // empty types slice
var Num3 []type // empty types slice

// Summ is summary of two value with different types
func Summ(a Num1, b Num2) Num3 {
    return Num3(a) + Num3(b)
}
package main

import "fmt"
import "tools"

func init() {
    tools.Num1 = append(tools.Num1, int, float32, float64)
    tools.Num2 = tools.Num1
    tools.Num3 = tools.Num1
}

func main() {
    fmt.Println(tools.Summ[Num1: int, Num2: float32, Num3: float64](1,2.1))    // show: 3.1
    fmt.Println(tools.Summ[Num1: float64, Num2: float32, Num3: int](3.14,2.7)) // show: 5
}

Example 2

Swap types

type T, T2 []type

type S struct{t T, t2 T2}

// SwapTypes have argument and return type `struct S`, but that
// struct have different types
func SwapTypes(s S) S {
    return S[T:T2, T2:T]{t: T2(s.t), t2: T(s.t2)}
}

Example 3

Example based on code from https://github.com/golang/proposal/blob/master/design/15292/2013-12-type-params.md#syntax

var T []type
var T2 []type
type (
    MyMap  map[T]T2     // Error: type T, T2 is undefined
    MyMap2 map[T:int]T2 // Error: type T2 is undefined
)
package hashmap

var K, V []type

type bucket struct {
    next *bucket
    key K
    val V
}

type Hashfn func(K) uint
type Eqfn func(K, K) bool

type Hashmap struct {
    hashfn Hashfn[K]
    eqfn Eqfn[K]
    buckets []bucket[K, V]
    entries int
}

// Example of using:
// h := hashmap.New[K:int, V:string](hashfn, eqfn)
func New(hashfn Hashfn, eqfn Eqfn) *Hashmap {
    // Type clarifications
    return &Hashmap[K:K, V:V]{hashfn, eqfn, make([]bucket, 16), 0}
}

func (p *Hashmap) Lookup(key K) (val V, found bool) {
    h := p.hashfn(key) % len(p.buckets)
    for b := p.buckets[h]; b != nil; b = b.next {
        if p.eqfn(key, b.key) {
            return b.val, true
        }
    }
    return
}

Example 4

Example with 3 types slices in one struct. In struct structure used 2 types slices and 1 in struct method.

var T1,T2,T3 []type
type S struct{ t1 T1; t2 T2}
func (s S) Summ() T3 {
    return T3(s.t1) + T3(s.t2)
}
// example of using: 
// v := s[T1: int, T2: float32, T3: float64]{t1: 1, t2: 3.14}
// fmt.Println("%2f\n", v.Summ()) // return type is float64

Useful generics

package sliceoperation

var T []type // empty types slice

func Reverse(s []T) {
    first := 0
    last := len(s) - 1
    for first < last {
        s[first], s[last] = s[last], s[first]
        first++
        last--
    }
}

func Sum(x []T) T {
    var s T
    for _, v := range x {
        s += v
    }
    return s
}

Using in go package math

Code based on function math.Pow

package math

import powInt "https://github.com/Konstantin8105/pow"

var num = []type{float64, int}

// Pow returns x**y, the base-x exponential of y.
func Pow(x float64, y num) float64 {
    // Typical solution for switching by type:
    // switch v := y.(type) {
    //     case float64:
    //         return pow(x,v)
    //     case int:
    //         return powInt.En(x,v) // Just for example
    // }
    // 
    // But I think about switching by types slice `num`
    switch num {
         case float64:
             return pow(x,y)
         case int:
             return powInt.En(x,y)
    }
    panic("Unacceptable type")
}

Types for-range

I do not know - is it useful?

var nums = []type{float64, int}

func twice(v nums) nums{
    return v * 2
}

func main() {
    for _,num := range nums {
        fmt.Printf("%T\n", num)
        v := num(3.1415)
        fmt.Printf("%v. twice = %v",v, twice(v))
    }
}

or may be for tests

func Test(t *testing.T){
    for _,num := range nums {
        if num == []float64 {
            t.Fatalf("not acceptable test")
        }
    }
}

Pointers in types slice

var pnts = []type{*int, *float32}

func twice(v pnts) error {
    if v == nil {
        return fmt.Errorf("nil")
    }
    *v *= 2
    return nil
}

Embedded

var T []type

// All types T must be fmt.Stringer
var _ ftm.Stringer  = T

type S struct{
    T
    val int
}

func(s S) Name() string{
    return s.String()
}

// example of use:
// type sm struct{ name string }
// func(s sm) String() string { return s.name }
// v := S[T:sm]{val: 10}
// fmt.Printf("%s\n", v)

Generic from exist code

Replace on external package level

We have package with math operations sparse and we want to use that package but with changing type from float64 to float32.

package main

// package with typical slices of types
import (
    "go/generic/types"
    "go/math/big"
    "github.com/Konstantin8105/sparse"
)

var Calctype = []type{float32, float64, complex64, complex128, big.NewFloat(0.0).SetPrec(45)}
//                                      ----------------------------------------------------
//                                                it will be great

func init() {
    types.ReplaceAllPkg("Konstantin8105/sparse", float64, Calctype)
    // Now, package fully acceptable with float32 and float64
}

As we see - it is easy for adding new types, for example in future float128 and other.

Replace on function level for external package

For example, we found function:

package mymath

// Mult is naive matrix multiplication
func Mult(A,B,C [][] float64) {
    n := len(A)
    for i := 0; i < n; i++ {
        for j := 0; j < n; j++ {
            for k := 0; k < n; k++ {
                C[i][j] += A[i][k] * B[k][j]
            }
        }
    }
}

But we want use with another types in our code:

package

import "fmt"
import "Konstantin8105/mymath"
import "go/generic/types"

var Calctype = []type{float32, float64}

_ = Mult(A,B,C Calctype) // Acceptable for see a new function

func init() {
    types.ReplaceAllFunc("Konstantin8105/mymath.Mult", float64, Calctype, Mult)
    // Now, function acceptable with float32 and float64
    // where:
    //  "Konstantin8105/mymath/Mult" - location of function
    //  float64                      - replace from
    //  Calctype                     - replace to
    //  Mult                         - name of new function in that package
}

func main() {
    A64 := [][]float64{{2}}
    mymath.Mult(A64,A64,A64)
    fmt.Println(A64)
    Mult[Calctype: float64](A64,A64,A64)
    fmt.Println(A64)

    A32 := [][]float32{{2}}
    // mymath.Mult(A32,A32,A32) // Not acceptable, because function mymath.Mult work only with float64
    Mult[Calctype: float32](A32,A32,A32) // Acceptable. Function generated automatically. See function init.
    fmt.Println(A32)
}

TODO

I do not think about:

Feel free for close

ianlancetaylor commented 3 years ago

I just want to check: have you seen proposal #43651?

Konstantin8105 commented 3 years ago

Dear @ianlancetaylor, Yes, I seen that proposal and others. I hope that issue help to avoid strange too long type clarification like func New[Node NodeConstraint[Edge], Edge EdgeConstraint[Node]] (nodes []Node) *Graph[Node, Edge].

Also, for information, present implemented design go2go cannot create generic in function. code Error: prog.go2:34:13: function type cannot have type parameters

deanveloper commented 3 years ago

How does this fix the verbose function declaration syntax? Could you provide an example of how a graph implementation would look under your proposal?

ianlancetaylor commented 3 years ago

I don't understand how code like this

func init() {
    tools.Numeric = append(tools.Numeric, int, float32)
}

could work in Go. If the init function has a conditional when setting tools.Numeric that seems to require a fully dynamic language. Go is statically compiled: all types must be known at compile time.

Konstantin8105 commented 3 years ago

Dear @deanveloper ,

I remove comments

package graph

var Edge, Node []type

type NodeConstraint interface {
    Edges() []Edge
}

type EdgeConstraint interface {
    Nodes() (from, to Node)
}

// Graph is a graph composed of nodes and edges.
type Graph struct { 
        nodes []NodeConstraint
        edges []EdgeConstraint
 }

func New (nodes []Node) *Graph {
    ...
}

func (g *Graph) ShortestPath(from, to Node) []Edge { ... }

using:

package main

func init(){
    graph.Edge = append(graph.Edge, edgetype)
    graph.Node = append(graph.Node, nodetype)
}

type edgetype struct{...}
func (e *edgetype) Nodes() (from, to nodetype) { ... }

type nodetype struct{...}
func (e *nodetype) Edges() (es []edgetype) { ... }

func main() {
     var nodes []nodetype
     gr := graph.New[Node: nodetype , Edge: edgetype ](nodes)
     es := gr.ShortestPath(from,to)
    // ...
}
Konstantin8105 commented 3 years ago

Dear @ianlancetaylor , Yes, I see all types must be known at compile time in other issue comments and document.

Solution

For finding all acceptable types of types slice on go.ast level and avoid using functions func init(){ ... }, we can create a specific package from standard library with needed operations appending, remove, copy types slices and recording all types using only ast tree. Using functions from package "go/generic/types" only in global scope. Using in any functions, methods is not acceptable.

import  "go/generic/types"

// new types slice
var T = types.Append(types.Init(), float64, int)

// new types slice based on T with adding types and remove type `int`
var E = types.Append(T,
    float32,
    complex64,
).Remove(int)

// work like : type S = T
var S = types.Rename(T, T) // &S == &T

// new local types slice equal external types slice and add types
var myNumeric = types.Rename(Append(tools.Numeric, float32, float64), tools.Numeric)

Prototypes of types functions

In that case - need add in struct go.ast.File:

type File struct {
     ... // exist values
    // Types is map of types slices names and acceptable types name for each
    // Example:
    // Types = [][]string{
    //    "T": []string{ "float64", "int"},
    //    "E": []string{ "float64", "float32", "complex64"},
    //    "S": []string{ "T"},
    //    "tools.Numeric" : []string{ "float32", "float64"},
    //    "myNumeric": []string{ "tools.Numeric"},
    // }
    Types map[string]string
}
Konstantin8105 commented 3 years ago

Present Go package parser parse that types operations without ast.BadDecl or ast.BadExpr. See code.

package main

import (
    "bytes"
    "fmt"
    "go/ast"
    "go/parser"
    "go/token"
    "strings"
)

func main() {
    fset := token.NewFileSet() // positions are relative to fset

    src := `package main

import  types  "go/generic/types"

var (
    A = types.Init()
    B = types.Append(A)
    C = types.Init()
    D = types.Append(Init())
    E = types.Append(D, int)
    F = types.Append(types.Init(), int8, int16)
    H = types.Rename(types.Append(C, floats), C)
    G = types.Remove(types.Rename(types.Append(Init(), string, int8, int16), A), int8)
)

var T = types.Append(types.Init(), float64, int)

var E = types.Append(T,
    float32,
    complex64,
).Remove(int)

var S = types.Rename(T, T)
`

    // Parse src but stop after processing the imports.
    f, err := parser.ParseFile(fset, "", src, parser.ParseComments)
    if err != nil {
        fmt.Println(err)
        return
    }

    var buf bytes.Buffer
    err = ast.Fprint(&buf, fset, f, nil)
    if err != nil {
        fmt.Println(err)
        return
    }

    fmt.Println("AST tree have ast.BadDecl or ast.BadExpr :", strings.Contains(buf.String(), "Bad"))
    fmt.Println(buf.String())
}

result:

AST tree have ast.BadDecl or ast.BadExpr : false
     0  *ast.File {
     1  .  Doc: nil
     2  .  Package: 1:1
     3  .  Name: *ast.Ident {
     4  .  .  NamePos: 1:9
     5  .  .  Name: "main"
...
ianlancetaylor commented 3 years ago

If we can't use init functions, I don't understand the purpose of types.Append or the Remove method. The person writing the code should be able to write down all possible types. Why use a syntax like types.Append rather than just writing a list?

Konstantin8105 commented 3 years ago

At the first part of question.

About types manipulations Append, Remove and ...

In according to Type Parameters - Draft Design.

I can write:

package mymath

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

// Mult is naive matrix multiplication
func Mult[T Numeric] (A,B,C [][]T) {
    n := len(A)
    for i := 0; i < n; i++ {
        for j := 0; j < n; j++ {
            for k := 0; k < n; k++ {
                C[i][j] += A[i][k] * B[k][j]
            }
        }
    }
}
package main

import "fmt"

func main() {
    A64 := [][]float64{{2}}
    mymath.Mult(A64,A64,A64)
    fmt.Println(A64)
}

Now, that code is valid. code

But I do not understood - How I can add type complex64 in mymath.Numeric from package main? Because this acceptable from math point of view and go2go point of view.

At the second part of question

About types list any. We can add a function like:

import  types  "go/generic/types"

var T = types.Any()  // Any types
ianlancetaylor commented 3 years ago

But I do not understood - How I can add type complex64 in mymath.Numeric from package main?

You can't. Go is not a dynamic language. All types need to be known at compile time. You can't change types at run time.

About types list any.

We could add a function types.Any but what would we gain?

Konstantin8105 commented 3 years ago

Dear @ianlancetaylor ,

But I do not understood - How I can add type complex64 in mymath.Numeric from package main?

You can't. Go is not a dynamic language. All types need to be known at compile time. You can't change types at run time.

In go2go design type Numeric interface{ ... } in package mymath analyzed at compile time. That type uppercase so exported and we can use them in external packages (for example package main). But we cannot append new type in type mymath.Numeric from external packages at compile time. (it is like algorithms singly linked list or tree without knows parents). In my point of view, that option help if somebody forgot add needed types.

My main goal of that issue - trying to avoid long type clarification like func New[Node NodeConstraint[Edge], Edge EdgeConstraint[Node]] (nodes []Node) *Graph[Node, Edge] is impossible.

Feel free for close that issue. Thank you.

ianlancetaylor commented 3 years ago

Yes, the generics proposal has limitations. Those are because we want Go to remain a statically compiled language. It's true that there are advantages to languages with a more dynamic type system, but Go is not one of those languages.